Mühazirələr Orta İxtisas Təhsil müəssisələrində fənnin tədrisi üçün nəzərdə tutulub

Məntiq cəbrinin funksiyaları

Tərif. n sayda dəyişəninin hər biri yalnız iki qiymət: 0 və 1, və bu zaman özü də yalnız iki qiymət: 0 və 1 qiyməti alan funksiya məntiq cəbrinin n dəyişənli funksiyası, yaxud Bul funksiyası adlanır.

Məntiq cəbrinin n dəyişənli hər bir funksiyasının qiymətlərini məntiq cəbrinin düsturlarında olduğu kimi 2ⁿ sətirdən ibarət olan cədvəl şəklində vermək olar.

Deməli məntiq cəbrinin hər bir n dəyişənli funksiyası, bu funksiyanın qiymətlər cəd- vəlində sıfır və birlərdən ibarət 2ⁿ sayda qiymət alır.

Deməli n dəyişənli funksiya sıfır və vahidlərdən ibarət 2ⁿ sayda elementlər toplusu

vasitəsi ilə tam müəyyən olunur.

Sıfır və vahidlərdən ibarət 2ⁿ uzunluqlu sonlu ardıcıllıqlar toplusunda mümkün olan variantların cəmi sayı isə 𝟐^𝟐𝒏-dir. Deməli məntiq cəbrinin n dəyişənli funksiyalarının cəmi sayı 𝟐^𝟐𝒏 -ə bərabərdir.

Xüsusi halda n=1 olduqda məntiq cəbrinin cəmi 4, n=2 olduqda isə cəmi 16 müxtəlif

funksiyası vardır.

Birdəyişənli müxtəlif funksiyaların doğruluq cədvəlinə baxaq:

x	f1(x)	f2(x)	f3(x)	f4(x)
1	1	1	0	0
0	1	0	1	0

Bu cədvəldən görünür ki, birdəyisənli funlsiyalardan ikisi sabit olur: f₁(x)=1, f₄(x)=0,

digər ikisi isə


f₂(x)  x, f₃(x)  x

olur. Bütün mümkün olan ikidəyişənli funksiyaların

doğruluq cədvəli aşağıdakı kimi olur:

f_i 

f_i (x, y), i  1, 16 _.

x	y	𝑓1	𝑓2	𝑓3	𝑓4	𝑓5	𝑓6	𝑓7	𝑓8	𝑓9	^𝑓10	^𝑓11	^𝑓12	^𝑓13	^𝑓14	^𝑓15	^𝑓16
1	1	1	1	1	1	0	1	1	0	0	0	1	0	0	0	1	0
1	0	1	1	1	0	1	1	0	0	1	1	0	0	0	1	0	0
0	1	1	1	0	1	1	0	0	1	1	0	1	0	1	0	0	0
0	0	1	0	1	1	1	0	1	1	0	1	0	1	0	0	0	0

Bu funksiyaların qiymətləri cədvəlinə nəzər saldıqda aydın olur ki, onların analitik ifadələrini aşağıdakı kimi yazmaq olar:

f₁  1_,

f₂  x  y _,

f₃  y  x _,

f₄  x  y _,


f₅  x  y

_, f₆

 x _,

f₇  x  y _,


f₈  x _,


f₉  x  y _,

^f10


 y _,

^{f11  y} ,

^f12

 x  y _,

^{f13  y  x} ,

f₁₄  x  y _,

f₁₅  x  y _,

f₁₆  0 _.

^{Tutaq ki, (x}1^,x2^,…,xn^{) (1) mülahizə dəyişənləri sistemi verilmişdir. (1) mülahizələr} sistemindən olan dəyişənlərin özləri və yaxud onların inkarlarının ən çoxu bir dəfə iştirak etməklə yalnız dizyunksiya əməli vasitəsi ilə yazilan düsturlar elementar dizyunksiyalar adlanırlar.

(1) mülahizələr sistemindən olan dəyişənlərin özləri və yaxud onların inkarlarının ən çoxu bir dəfə iştirak etməklə yalnız konyunksiya əməli vasitəsi ilə yazilan düsturlar isə elementar konyunksiyalar adlanırlar.

Əgər F düsturu (1) mülahizələr sistemindən düzəldilmiş elementar konyunksiyaların dizyunksiyaları olarsa, onda bu düstur (1) mülahizələr sisteminin dizyunktiv normal forması (DNF) adlanır.

Əgər F düsturu (1) mülahizələr sistemindən düzəldilmiş elementar dizyunksiyaların konyunksiyaları olarsa, onda bu düstur (1) mülahizələr sisteminin konyunktiv normal for- ması (KNF) adlanır. Əgər F düsturu (1) mülahizələr sistemindən düzəldilmiş müxtəlif tam elemendar dizyunksiyaların konyunksiyaları olarsa, onda bu düstur (1) mülahizələr sistemindən asılı mükəmməl konyunktiv normal forma (MKNF) adlanır.

Əgər F düsturu (1) mülahizələr sistemindən düzəldilmiş müxtəlif tam elemendar konyunksiyaların dizyunksiyaları olarsa, onda bu düstur (1) mülahizələr sistemindən asılı mükəmməl dizyunktiv normal forma (MDNF) adlanır.

Rezolyusiya prinsipi. Konyunktiv normal formaların yerinə yetirilən olmasının yoxlanılması üçün ümumi səmərəli kriteriya mövcud deyil. Buna baxmayaraq, dizyunktlar çoxluğunun yerinə yetirilə bilən olmadığını aşkara çıxaran rahat metod var. Doğurdan da, dizyunktlar çoxluğu yerinə yetirilə bilən deyil o vaxt ki, boş dizyunkt (“yalan”-Y) ondan məntiqi nəticə kimi alınsın. Beləliklə, S-dən boş dizyunktu çıxarana qədər məntiqi nəticə almaqla yoxlamaq olar.

Məntiqi nəticə çıxarmaq üçün çox sadə mühakimə sxemindən istifadə etmək olar:

Tutaq ki, A, B və X düsturlardır. Fərz edək ki, ^{A  X } və ^{B  X }düsturları doğrudur.

Əgər X-da doğrudursa, onda buradan almaq olar ki, B-də doğrudur. Əksinə, əgər X yalandırsa, onda A doğrudur. Hər 2 halda ^{A  X } doğrudur.

Yəni,

A  X , B  X  A  B

(1)

Xüsusi halda X-mülahizə, A və B dizyunktlar olduqda, (1) “rezolyusiya qaydası” adlanır. Rezolyusiya metodu deduksiya prinsipinin yerinə yetirilməsi zamanı isbat mexanizmi kimi istifadə edilir.

Məntiqi deduksiya adlanan fundamental problem aşağıdakından ibarətdir:

• 
  C düsturunun E düsturlar çoxluğunun məntiqi nəticəsi olub-olmadığını təyin etməli.
  

• 
  C düsturu ancaq o vaxt sonlu E çoxluğunun məntiqi nəticəsi olur ki, yetirilə bilməyən olsun.
  

Deyilənlər aşağıdakı teoremlə ümumiləşdirilir:

^{E C} yerinə

Teorem: S düsturlar çoxluğu ancaq o vaxt yerinə yetirilə biləndir ki, onun bütün sonlu altçoxluqları yerinə yetirilə bilən olsun.

Məntiq cəbrinin ixtiyari düsturunun mükəmməl normal formaya gətirilməsi qaydası:

a) MDNF-ya gətirilməsi qaydası.

Tərifdən alınır ki, əgər F düsturu üçün “mükəmməllik xassələri” adlanan aşağıdakı xassələr doğru olarsa, onda F düsturu MDNF olur:

1. 
   onun iki eyni toplananı (dizyunktiv həddi) yoxdur;
   
2. 
   heç bir toplanan iki eyni vuruğa malik deyildir, yəni mülahizə dəyişəni hər dizyunktiv həddə bir dəfə iştirak edir.
   
3. 
   Heç bir toplananda hər hansı dəyişənin özü və onun inkarı eyni zamanda iştirak etmir.
   

edir.

4. 
   hər toplananda vuruq olaraq ya
   

10. 
    dəyişəni, ya da onun inkarı
    

^xi _, i  1, n

iştirak

DNF-nin MDNF olması üçün zəruri və kafi şərt a)-d) şərtlərinin ödənilməsidir. Bu şərtlər eyniliklə sıfır olmayan istənilən düsturu, eynigüclü çevirmələr vasitəsi ilə onun üçün yeganə olan MDNF-yə gətirmək qaydasını ifadə etməyə imkan verir. Bu qaydanı ifadə edək.

Tutaq ki, ixtiyari F ^{(x1,..., xn )} düsturu verilmişdir. Aşağıdakı beş əməliyyat vasitəsi

ilə bu düstur MDNF şəklinə gətirilir.

1. 
   Eynigüclü çevirmələr vasitəsi ilə onu hansısa DNF formasına gətiririk.
   
2. 
   Əgər hər hansı bir toplanan məsələn B toplananı ^xi dəyişənini özündə
   

saxlamırsa, onda o toplananı çevirmədir, belə ki,

^{xi B  x}i ^B

cəmi ilə əvəz edirik. Bu əvəzetmə eynigüclü

3.5

1.8

1.3

^{xi  B  x}i ^{ B (xi  x}i ^{)  B 1 B  B .}

Bu əməliyyatı yerinə yetirməklə mükəmməllik xassələrindən d) bəndinin tələbini ödəmiş oluruq.

3. 
   Əgər alınmış ifadədə eyni toplananlar olarsa, onda onlardan birindən başqa digərlərini atmaqla (1.2) idempotentlik qanuna əsasən yenə də eynigüclü ifadə alırıq. Burada biz mükəmməllik xassəsinin a) bəndinin tələbini ödəmiş olduq.
   
4. 
   Əgər bundan sonra hansısa toplananda eyni vuruq bir neçə dəfə iştirak edərsə, onda (1.1) idempotentlik qanununa əsasən artıq olanlarını atırıq. Bununla biz mükəmməllik xassəsinin b) bəndinin tələbinin ödənməsini təmin etmiş oluruq.
   

5. 
   Nəhayət hər hansı
   

^xi dəyişəni ilə ^x_i

inkarını inkarını eyni zamanda özündə

saxlayan toplananları atırıq, belə ki, (15) ziddiyyət qanununa əsasən onlar eyniliklə yalan ifadədir.

Bununla mukəmməllik xassəsinin c) bəndinin tələbini ödəmiş oluruq. Burada əgər bütün toplananlar bu cür olarsa, onda bütünlükdə DNF eyniliklə yalan olur və MDNF-yə malik olmur. Buna görə də hökm edə bilirik ki, əgər F eyniliklə yalan düstur olmasa, onda

onun istənilən DNF-sındə mükəmməllik xassəsinin c) bəndinin şərtini ödəyən toplananı vardır.

Hansısa dəyişəni öz inkarı ilə bərabər özündə saxlayan bütün toplananları atmaqla mükəmməllik xassəsinin bütün tələblərini ödəyən DNF, yəni MDNF alırıq.

Qeyd edək ki, verilmiş F düsturunun eyniliklə yalan olub-olmamasını əvvəlcədən biEynigüclü çevirmələr vasitəsi ilə onu hansısa DNF formasına gətiririk.

Əgər hər hansı bir toplanan məsələn B toplananı

^xi dəyişənini özündə saxlamırsa,

onda o toplananı


^{xi B  x}i ^B

cəmi ilə əvəz edirik. Bu əvəzetmə eynigüclü çevirmədir, belə

3.5

1.8

1.3

ki,

^{xi  B  x}i ^{ B (xi  x}i ^{)  B 1 B  B} _.

Bu əməliyyatı yerinə yetirməklə mükəmməllik xassələrindən d) bəndinin tələbini

ödəmiş oluruq.

Əgər alınmış ifadədə eyni toplananlar olarsa, onda onlardan birindən başqa digərlərini atmaqla (1.2) idempotentlik qanuna əsasən yenə də eynigüclü ifadə alırıq. Burada biz mükəmməllik xassəsinin a) bəndinin tələbini ödəmiş olduq.

Əgər bundan sonra hansısa toplananda eyni vuruq bir neçə dəfə iştirak edərsə, onda (1.1) idempotentlik qanununa əsasən artıq olanlarını atırıq. Bununla biz mükəmməllik xassəsinin b) bəndinin tələbinin ödənməsini təmin etmiş oluruq.

Nəhayət hər hansı

^xi dəyişəni ilə ^xi

inkarını inkarını eyni zamanda özündə saxlayan

toplananları atırıq, belə ki, (15) ziddiyyət qanununa əsasən onlar eyniliklə yalan ifadədir. Bununla mukəmməllik xassəsinin c) bəndinin tələbini ödəmiş oluruq. Burada əgər bütün toplananlar bu cür olarsa, onda bütünlükdə DNF eyniliklə yalan olur və MDNF-yə malik olmur. Buna görə də hökm edə bilirik ki, əgər F eyniliklə yalan düstur olmasa, onda onun istənilən DNF-sındə mükəmməllik xassəsinin c) bəndinin şərtini ödəyən toplanalməyə ehtiyac yoxdur. Belə ki, yuxarıda qeyd olunan əməlləri yerinə yetirməklə bütün toplananlar atılarsa, onda F eyniliklə yalan düstur olur və onun üçün MDNF

alınmır.