I kirish II. Asosiy qism matematik mantiq funksiyalarining minimallashtirish muammosi masalasining qo‘yilishi

1-misol. Quyida chinlik jadvalida berilgan funksiyani ko‘rib o‘taylik.

1-jadval

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

funksiya uchun dastlabki DNSH sifatida MDNSHni olamiz va ikki tartiblashni o‘tkazamiz:

,

.

tartibga solingan DNSH uchun algoritmning ishlashini ko‘ramiz.

1. konyunktsiyani chetlashtirish mumkin emas, ammo ko‘paytuvchini chetlashtirish mumkin, chunki

Natijada konyunktsiyaga ega bo‘lamiz, undan birorta ham ko‘paytuvchini chetlashtirish mumkin emas.

2. konyunktsiyani ham chetlashtirish mumkin emas. Bu konyunktsiyadan ko‘paytuvchini chetlashtirish mumkin emasligini osongina ko‘rish mumkin, lekin ko‘paytuvchiga nisbatan ko‘paytuvchini chetlashtirish operatsiyasini qo‘llash mumkin. konyunktsiyani hosil qilamiz. Ko‘paytuvchini chetlashtirish operatsiyasini ishlatib soddalashtirish mumkin emas.
3. konyunktsiyani chetlashtirish mumkin, chunki

.

4. konyunktsiyani ham chetlashtirish mumkin, chunki

.

5. konyunktsiyani chetlashtirish mumkin emas, biroq ko‘paytuvchini tashlab yuborish mumkin. Natijada konyunktsiyaga ega bo‘lamiz. Bu konyunktsiyaga nisbatan ko‘paytuvchini chetlashtirish operatsiyasini ishlatib, uni soddalashtirish mumkin emas.

6. konyunktsiyani ham chetlashtirish mumkin emas, ammo undan ko‘paytuvchini chetlashtirish mumkin. Natijada, konyunktsiyani hosil qilamiz va uni boshqa soddalashtirish mumkin emas.

SHunday qilib, DNSH ni hosil qilamiz. Bu DNSH ga nisbatan konyunktsiyani chetlashtirish operatsiyasini ishlatish natija bermaydi.

Demak, soddalashtirish algoritmini ishlatish natijasida

(2)

dizyunktiv normal shaklni hosil qilamiz. Keltirilgan hisoblar 2-jadvalda aks ettirilgan.

2-jadval

Qa-dam №	DNSH va ko‘rilayotgan tartib	Tekshirilayotgan konyunktsiya	Operatsiya turi
1	2	3	4
1			chetlashtirish
2			Chetlashtirish
3			Chetlashtirish
4			chetlashtirish
5			chetlashtirish
6			chetlashtirish
7
	Ikkinchi ko‘rish hech narsa bermaydi	Algoritm tamom bo‘ldi

Agarda soddalashtirish algoritmini ^II ga nisbatan ishlatsak, u holda

(3)

dizyunktiv normal shaklga ega bo‘lamiz.