Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

1- teorema. Soddalashtirish algoritmini qo‘llash natijasida hosil qilingan diz’yunktiv normal shakl (I va II almashtirishlarga nisbatan) minimal DNSh bo‘ladi.
2- misol. Chinlik jadvali vositasida berilgan (1- jadval) 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. kon’yunksiyani chetlashtirish mumkin emas, ammo ko‘paytuvchini chetlashtirish mumkin, chunki . Natijada kon’yunksiyaga ega bo‘lamiz, undan birorta ham ko‘paytuvchini chetlashtirish mumkin emas.
2. kon’yunksiyani ham chetlashtirish mumkin emas. Bu kon’yunksiyadan ko‘paytuvchini chetlashtirish mumkin emasligini osongina ko‘rish mumkin, lekin ko‘paytuvchiga nisbatan ko‘paytuvchini chetlashtirish operatsiyasini qo‘llash mumkin. kon’yunksiyani hosil qilamiz. Ko‘paytuvchini chetlashtirish operatsiyasini ishlatib soddalashtirish mumkin emas.
3. kon’yunksiyani chetlashtirish mumkin, chunki .
4. kon’yunksiyani ham chetlashtirish mumkin, chunki .
5. kon’yunksiyani chetlashtirish mumkin emas, biroq ko‘paytuvchini tashlab yuborish mumkin. Natijada kon’yunksiyaga ega bo‘lamiz. Bu kon’yunksiyaga nisbatan ko‘paytuvchini chetlashtirish operatsiyasini ishlatib, uni soddalashtirish mumkin emas.
6. kon’yunksiyani ham chetlashtirish mumkin emas, ammo undan ko‘paytuvchini chetlashtirish mumkin. Natijada, kon’yunksiyani hosil qilamiz va uni boshqa soddalashtirish mumkin emas.
Shunday qilib, DNShni hosil qilamiz. Bu DNShga nisbatan kon’yunksiyani chetlashtirish operatsiyasini ishlatish natija bermaydi.
Demak, soddalashtirish algoritmini ishlatish natijasida
(2)
DNShni hosil qilamiz. Yuqorida keltirilgan hisoblashlar 2- jadvalda aks ettirilgan.
Agar soddalashtirish algoritmini ga nisbatan ishlatsak, u holda
(3)
diz’yunktiv normal shaklga ega bo‘lamiz.
3- jadvalda ga nisbatan ishlatilgan soddalashtirish algoritmi ishining asosiy bosqichlari keltirilgan. ■
2- misoldan ko‘rinib turibdiki, soddalashtirish algoritmi tatbiqining natijasi dastlabki DNShni qanday tartiblashga bog‘liq bo‘lar ekan.

2- jadval
Qadam tartib raqami	DNSh va ko‘rilayotgan tartib	Tekshiri- layotgan kon’yunksiya	Operatsiya turi
1			ni chetlashtirish
2			ni chetlashtirish
3			ni chetlashtirish
4			ni chetlashtirish
5			ni chetlashtirish
6			ni chetlashtirish
7
	Ikkinchi ko‘rish yangi natija bermaydi	Algoritmning ishi tugadi

Masalan, , , , , , va bu yerdan , , munosabatlar kelib chiqadi.

3- jadval
Qadam tartib raqami	DNSh va ko‘rilayotgan tartib	Tekshiri- layotgan kon’yunksiya	Operatsiya turi
1			ni chetlashtirish
2			ni chetlashtirish
3			ni chetlashtirish
4			ni chetlashtirish
5			ni chetlashtirish
6			ni chetlashtirish
7			qo‘llanilmaydi
8			ni chetlashtirish
9			qo‘llanilmaydi
10			ni chetlashtirish
11			qo‘llanilmaydi
12		Algoritmning ishi tugadi

“Istalgan 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- teorema. – matematik mantiq algebrasining ixtiyoriy funksiyasi va uning ixtiyoriy (I va II almashtirishlarga nisbatan) tupikli DNSh bo‘lsin. U holda MDNShning shunday tartiblashi mavjud bo‘ladiki, undan soddalashtirish algoritmi yordami bilan tupikli DNShni hosil qilish mumkin.
Natija. Tupikli DNShlar orasida albatta L indeksga nisbatan minimal DNShlar (hammasi bo‘lishi shart emas) mavjud bo‘lgani uchun, soddalashtirish algoritmi, MDNShni ma’lum ravishda tartiblash natijasida, minimal DNShni ham topishga imkon yaratadi.
Shunday qilib, minimal DNShni topish uchun MDNShni tartiblash kerak va unga nisbatan soddalashtirish algoritmini ishlatish kerak.
Teoremaning isbotidan¹ soddalashtirish algoritmi yordami bilan tupikli DNShlarni mukammal DNShdan yasash uchun faqat kon’yunksiyalar ifodasida ko‘paytuvchilar joylashishini variatsiyalash yetarligi kelib chiqadi.
Hozirgi vaqtda kon’yunksiyalarni DNSh ifodasidan chetlashtirish va ko‘paytuvchilarni kon’yunksiyalar ifodasidan chetlashtirish mumkinligini tekshirishlar soni (MDNSh tartiblashning hamma turi bo‘yicha)

sondan ortiq emasligi isbotlangan. Bu son sondan ancha kamdir, ya’ni soddalashtirish algoritmi birma-bir ko‘zdan kechirish algoritmidan yaxshiroq ekanligi ma’lum bo‘ladi.


Minimallashtirish masalasining geometrik tarzda qo‘yilishi
Birlik kub va uning elementlariga mos keladigan funksiya. Hamma majmua to‘plamini bilan belgilaymiz. to‘plamni birlik kubning hamma uchlari to‘plami sifatida qarash mumkin. Shu sababli to‘plam o‘lchovli kub, esa kub uchlari deb ataladi.
o‘lchovli kub 1- shakldagidek tasvirlanishi mumkin.
1- ta’rif. shunday 0 va 1 sonlardan iborat tayinlangan sonlar sistemasi bo‘lib, , uchun bajarilganda kubning uchlaridan tuzilgan to‘plam o‘lchovli yoq deb ataladi.
Mantiq algebrasining funksiyasi berilgan bo‘lsin. kubning shartni qanoatlantiradigan barcha uchlaridan tashkil topgan to‘plamni bilan belgilaymiz, ya’ni bajarilganda va faqat shunda , bo‘ladi. Masalan, ushbu bobning 2- paragrafidagi 1- jadvalda berilgan funksiyaga

to‘plam mos keladi.
Ravshanki, . Agar to‘plam berilgan bo‘lsa, u holda unga mos funksiyaning analitik ko‘rinishini yozish mumkin.
1- misol. Quyidagi to‘plamlarga mos keladigan funksiyalarning analitik ko‘rinishi topamiz:
;
.
Berilgan to‘plamlarga mos keladigan funksiyalarning analitik ko‘rinishi
quyidagicha bo‘ladi:
;
. ■
Shunday qilib, to‘plam berilgan bo‘lsa, u holda unga mos funksiyani, funksiya berilganda esa, to‘plamni topish mumkin.
Dastlabki funksiya sifatida rangli elementar kon’yunksiyani olaylik.