Mumkin. Isboti. Mantiq algebrasining ixtiyoriy formulasini tahlil qilib, agar berilgan formula knshda bo‘lmasa, u vaqtda quyidagi ikkita hollardan biri ro‘y berishini ta’kidlaymiz

Teoremaning yuqorida keltirilgan isboti konstruktiv xususiyatga ega, ya’ni

bu isbotdan mantiq algebrasining berilgan formulasi uchun KNShni hosil qilishda algoritm sifatida foydalanish mumkin.
Ixtiyoriy f (x x,x 2,...,x n) funksiyaning qisqartirilgan diz’yunktiv normal shaklini yasash uchun quyidagi operasiyalami bajaramiz:

1) / ( x p x 2, . . . , x j funksiyaning istalgan kon’yunktiv normal shaklini olamiz, masalan, mukammal KNSh;
2) qavslarni ochib chiqamiz, ya’ni av->va turdagi almashtirishni o ‘tkazamiz;
3) hosil qilingan ifodadan 0 ga teng hadlarni chetlashtiramiz va K XK 2 v K 2 = K l , K x v K x = K x
formulalardan foydalanib uni soddalashtiramiz. Natijada, qisqartirilgan DNShga kelamiz. ■

9.6.2. MisoIIar.

1-misol. Na ={(0,0,0),(0,0,1),(1,0,1),(1,1,1),(1,1,0),(0,1,0)} to‘plamga
mos / 2(x ,,x 2,x 3) funksiyaning MKNShni
f ( x x,x 2, . л (jif VV...V.V,"') (1)
formuladan foydalanib yozamiz:
f 2(x ,, x2, x3) = (x, v x 2 v x3)(x, v x 2 v x 3).
Algoritmning 2- va 3- qadamlarini bajaramiz:
(X , V X2 V X3 ) ( x , V X2 V X3) = X,X, V X,X2 V X,X3 V XjX2 v x 2x 2 v
v x 2x 3 v x , x 3 v x 2x 3 v x 3x 3 =

= x , x 2 V x , x 3 V x , x 2 V x 2x 3 v x , x 3 V x 2x 3 .
Geometrik ma’nodagi tupikli diz’yunktiv normal shakl tushunchasini o‘rganish uchun misolga murojaat qilamiz.
1 - m i s о 1. Ushbu bobning 4- paragrafidagi misolda (5) formula bilan berilgan / 2(x ,,x 2,x 3) funksiyaning N ki,Nk^,...,Nki>maksimal intervallardan iborat Nf qoplama
N k = N ki I W ,, илг,, IW „, IW „, I W 4> (1)
ekanligini ko‘rsatgan edik. Bu yerda

Nfi = {(0,0,0), (0,0,1), (1,0,1), (1,1,1), (1,1,0), (0,1,0)},

N ki = {(1,1,0), (1,1,1)},

N ki = {(1,0,1), (1,1,1)},