Diz’yunktiv normal shaklni soddalashtirish va tupikli dnsh

- t e o r e m a . Soddalashtirish algoritmini qo‘llash natijasida hosil qilingan diz’yunktiv normal shakl (I va II almashtirishlarga nisbatan) minimal DNSh bo‘ladi.

2. 
   - m i s o l . Chinlik jadvali vositasida berilgan (2.1-jadval) funksiyani ko‘rib o‘taylik.
   

f (x₁ , x₂ , x₃ )

2.1-jadval
x1	x2	x3	f (x1 , x2 , x3 )	x1	x2	x3	f (x1 , x2 , x3 )
0	0	0	1	1	0	0	1
0	0	1	1	1	0	1	0
0	1	0	0	1	1	0	1
0	1	1	1	1	1	1	1

f (x₁, x₂ , x₃ ) funksiya uchun dastlabki DNSh sifatida MDNShni olamiz va ikki
tartiblashni o‘tkazamiz:
D'  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃  x₁x₂ x₃ ,
D''  x₁ x₂ x₃  x₃ x₁ x₂  x₂ x₁ x₃  x₁x₂ x₃  x₃ x₁ x₂  x₁ x₂ x₃ .
Tartibga solingan D' DNSh uchun algoritmning ishlashini ko‘ramiz.

1. 
   ^x₁ ^x₂ ^x₃ kon’yunksiyani chetlashtirish mumkin emas, ammo x₁
   

ko‘paytuvchini chetlashtirish mumkin, chunki
x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃ . Natijada



x₂ x₃

kon’yunksiyaga ega bo‘lamiz, undan birorta ham ko‘paytuvchini chetlashtirish mumkin emas.

2. 
   x₁ x₂ x₃ kon’yunksiyani ham chetlashtirish mumkin emas. Bu
   

^{kon’yunksiyadan} x₁
ko‘paytuvchini chetlashtirish mumkin emasligini osongina

ko‘rish mumkin, lekin
x₂ ^{ko‘paytuvchiga nisbatan}
x₂ ^{ko‘paytuvchini}

chetlashtirish operatsiyasini qo‘llash mumkin.

x₁ x₃
kon’yunksiyani hosil qilamiz.

Ko‘paytuvchini chetlashtirish operatsiyasini ishlatib soddalashtirish mumkin emas.

3. 
   x₁ x₂ x₃
   

.
kon’yunksiyani chetlashtirish mumkin, chunki



x₁ x₃  x₁ x₂ x₃  x₁ x₂ x₃

4. 
   x₁ x₂ x₃ kon’yunksiyani ham chetlashtirish mumkin, chunki
   

x₂ x₃  x₁ x₂ x₃  x₁ x₂ x₃ .

5. 
   x₁ x₂ x₃ kon’yunksiyani chetlashtirish mumkin emas, biroq x₂
   

ko‘paytuvchini tashlab yuborish mumkin. Natijada


x₁ x₃
kon’yunksiyaga ega

bo‘lamiz. Bu kon’yunksiyaga nisbatan ko‘paytuvchini chetlashtirish operatsiyasini ishlatib, uni soddalashtirish mumkin emas.

6. 
   x₁ x₂ x₃ kon’yunksiyani ham chetlashtirish mumkin emas, ammo undan x₁
   

ko‘paytuvchini chetlashtirish mumkin. Natijada, va uni boshqa soddalashtirish mumkin emas.
x₂ x₃
kon’yunksiyani hosil qilamiz

Shunday qilib,
x₂ x₃  x₁ x₃  x₁ x₃  x₂ x₃
DNShni hosil qilamiz. Bu DNShga

nisbatan kon’yunksiyani chetlashtirish operatsiyasini ishlatish natija bermaydi.
Demak, soddalashtirish algoritmini ishlatish natijasida



D₁  x₂ x₃  x₁ x₃  x₁ x₃  x₂ x₃
(2)

DNShni hosil qilamiz. Yuqorida keltirilgan hisoblashlar 2.2-jadvalda aks ettirilgan.

Agar soddalashtirish algoritmini
D'' ga nisbatan ishlatsak, u holda



D₂  x₂ x₃  x₁ x₃  x₁ x₂

(3)

diz’yunktiv normal shaklga ega bo‘lamiz.
2.3-jadvalda D'' ga nisbatan ishlatilgan soddalashtirish algoritmi ishining
asosiy bosqichlari keltirilgan. ■
2.2-misoldan ko‘rinib turibdiki, soddalashtirish algoritmi tatbiqining natijasi dastlabki DNShni qanday tartiblashga bog‘liq bo‘lar ekan.

2.2-jadval
Qadam tartib raqami	DNSh va ko‘rilayotgan tartib	Tekshiri- layotgan kon’yunksiya	Operatsiya turi
1	x1 x2 x3  x1 x2 x3   x1 x2 x3  x1 x2 x3   x1 x2 x3  x1 x2 x3	x1 x2 x3	x1 ni chetlashtirish

2	x2 x3  x1 x2 x3   x1 x2 x3  x1 x2 x3   x1 x2 x3  x1 x2 x3	x1 x2 x3	x2 ^nichetlashtirish
3	x2 x3  x1 x3   x1 x2 x3  x1 x2 x3   x1 x2 x3  x1 x2 x3	x1 x2 x3	x1 x2 x3 ni chetlashtirish
4	x2 x3  x1 x3  x1 x2 x3   x1 x2 x3  x1 x2 x3	x1 x2 x3	x1 x2 x3 ni chetlashtirish
5	x2 x3  x1 x3   x1 x2 x3  x1 x2 x3	x1 x2 x3	x2 ni chetlashtirish
6	x2 x3  x1 x3   x1 x3  x1 x2 x3	x1 x2 x3	x1 ni chetlashtirish
7	x2 x3  x1 x3   x1 x3  x2 x3
	Ikkinchi ko‘rish yangi natija bermaydi	Algoritmning ishi tugadi

Masalan,
L_h (D₁ )  8 ,
L_h (D₂ )  6 ,
L_k (D₁ )  4 ,
L_k (D₂ )  3 ,
L_i (D₁ )  4 ,
L_i (D₂ )  3 va

2.3-jadval
Qadam tartib raqami	DNSh va ko‘rilayotgan tartib	Tekshiri- layotgan kon’yunksiya	Operatsiya turi
1	x1 x2 x3  x3 x1 x2   x2 x1 x3  x1 x2 x3   x3 x1 x2  x1 x2 x3	x1 x2 x3	x1 ni chetlashtirish
2	x2 x3  x3 x1 x2   x2 x1 x3  x1 x2 x3   x3 x1 x2  x1 x2 x3	x3 x1 x2	x3 ni chetlashtirish
3	x2 x3  x1 x2   x2 x1 x3  x1 x2 x3   x3 x1 x2  x1 x2 x3	x2 x1 x3	x2 ni chetlashtirish
4	x2 x3  x1 x2 

bu yerdan chiqadi.
L_h (D₁ )  L_h (D₂ ) ,
L_k (D₁ )  L_k (D₂ ) ,
L_i (D₁ )  L_i (D₂ )
munosabatlar kelib

	x1 x3  x1 x2 x3   x3 x1 x2  x1 x2 x3	x1 x2 x3	x1 ni chetlashtirish
5	x2 x3  x1 x2   x1 x3  x2 x3   x3 x1 x2  x1 x2 x3	x3 x1 x2	x3 ni chetlashtirish
6	x2 x3  x1 x2   x1 x3  x2 x3   x1 x2  x1 x2 x3	x1 x2 x3	x1 x2 x3 ni chetlashtirish
7	x2 x3  x1 x2   x1 x3  x2 x3  x1 x2	x2 x3	qo‘llanilmaydi
8	x2 x3  x1 x2   x1 x3  x2 x3  x1 x2	x1 x2	x1 x2 ni chetlashtirish
9	x2 x3  x1 x3   x2 x3  x1 x2	x1 x3	qo‘llanilmaydi
10	x2 x3  x1 x3   x2 x3  x1 x2	x2 x3	x2 x3 ni chetlashtirish
11	x2 x3  x1 x3  x1x2	x1 x2	qo‘llanilmaydi
12	x2 x3  x1 x3  x1 x2	Algoritmning ishi tugadi

“Istalgan
f (x₁, x₂ ,..., x_n )
funksiya uchun biror tartiblash oqibatida

soddalashtirish algoritmini tatbiq etib minimal DNShni hosil etish mumkinmi yoki yo‘qmi?” degan savol tug‘iladi. Bu savolga quyidagi teorema javob beradi.

2.