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

x	y	z
f (x, y, z)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Aşağıdakı əməliyyatları yerinə yetirək.

1) Mülahizə dəyişənlərinin qiymətləri yığımının (0; 1; 1), (1; 0; 1), (1; 1; 0), (1; 1;

1. 
   olduğu hallarda
   

f (x, y, z)  1 _olur.

2. 
   Bunların hər birinə uyğun
   

x, y, z

dəyişənlərinin konyunksiyasını qururuq, belə

ki, nizamlı üçlükdə 0 ədədinə uyğun dəyişənin inkarını, 1 ədədinə isə uyğun dəyişənin özünü yazmaqla konyuksiya qururuq:

(0; 1; 1) yığımına –


x  y  z

konyunksiyasını,

(1; 0; 1) yığımına –

(1; 1; 0) yığımına –

x  y  z


x  y  z

konyunksiyasını, konyunksiyasını,

(1; 1; 1) yığımına –

x  y  z

konyunksiyasını.

3. 
   Bu konyunksiyaların dizyunksiyaları yalnız və yalnız o zaman vahidə bərabər olur ki, verilmiş funksiya 1 qiyməti alsın.
   

Deməli bu dizyunksiya

f (x, y, z)

funksiyasının mümkün olan ifadələrindən biri

olur, yəni

f (x, y, z)  xyz  xyz  xy z  xyz _.

Aydındir ki, bu ifadə verilən funksiyanın MDNF-sıdır.

Məntiq cəbrinin bütün düsturları “eyniliklə yalan”, “eyniliklə doğru” və “yerinə yetirilə bilən” kimi üç qrupa bölünür. Eynilklə doğru və eyniliklə yalan düsturların tərifləri yuxarıda verilmişdir.

Eyniliklə doğru olmayan F düsturu, ona daxil olan dəyişənlərin heç olmasa bir yığımında “doğru”, yəni 1 qiyməti alarsa, onda o, yerinə yetirilə bilən düstur adlanır.

Bununla əlaqədar olaraq verilmiş ixtiyari F düsturunun hansı sinfə aid olmasını müəyyənləşdirmək problemi qarşıya çıxır. Bu məsələ həll oluna bilmə problemi adlanır. Aşkardır ki, məntiq cəbrinin həll oluna bilmə probleminin özü həll oluna biləndir.

Doğrudan da, məntiq cəbrinin hər bir düsturu üçün doğruluq cədvəli tərtib etmək olar və

bu cədvəl qoyulan suala cavab verə bilər. Lakin

^x_i ,


i  1, n

dəyşənlərinin sayının kifayət

qədər böyük olduğu hallarda (bu say 2ⁿ -dir) praktiki olaraq doğruluq cədvəlini qurmaq çox çətin olur. Dogruluq cədvəlindən istifadə etmədən F düsturunun hansı sinfə aid olmasını müəyyənləşdirməyə imkan verən digər üsul mövcuddur. Bu üsul F düsturunun normal (DNF yaxud KNF) formaya gətirilməsinə və düsturun eyniliklə doğru olub- olladığına araşdıran alqoritmə əsaslanır.

Tutaq ki, bizə məntiq cəbrinin düsturu üçün eyniliklə doğruluq kriterisi məlumdur. Onun tətbiq mexanizmi belədir: A düsturunun eyniliklə doğru olduğunu yoxlayırıq. Əgər o eyniliklə doğru olarsa, onda məsələ həll olunmuş olur. Əks halda eyniliklə doğruluq

kriterisini ^A üçün yoxlayırıq. Əgər ^A eyniliklə doğru olarsa, onda A eyniliklə yalan

olur və məsələ həll olunmuş olur. Əgər ^A eyniliklə doğru olmasa, onda yalnız bir hal qalır: A yerinə yetirilə biləndir.

Deməli baxılan problemin həlli üçün eyniliklə doğruluq kriterisini tapmaq kifayətdir. İndi məntiq cəbrinin eyniliklə doğruluq kriterisini quraq. Bu məqsədlə əvvəlcə elementar dizyunksiyaların eyniliklə doğruluq kriterisini söyləyək və isbat edək.