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

1-teorema. Soddalashtirish algoritmini qo‘llash natijasida hosil etilgan dizyunktiv normal shakl (I va II almashtirishlarga nisbatan) minimal DNSH bo‘ladi.

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 tupikli DNSH (I va II almashtirishlarga nisbatan) bo‘lsin. U vaqtda mukammal dizyunktiv normal shaklni shunday tartiblashi mavjud bo‘ladiki, undan soddalashtirish algoritmi yordami bilan tupikli DNSH ni hosil qilish mumkin.

Natija. Tupikli DNSHlar orasida albatta L indeksga nisbatan minimal DNSHlar (hammasi bo‘lishi shart emas) mavjud bo‘lganligi uchun, soddalashtirish algoritmi, MDNSH ni ma’lum ravishda tartiblash natijasida, minimal DNSH ni ham topishga imkon yaratadi.

Shunday qilib, minimal DNSH ni topish uchun MDNSH ni tartiblash kerak va unga nisbatan soddalashtirish algoritmini ishlatish kerak.

Teoremaning isbotidan (С.В.Яблонский, Введение в дискретную математику, М., 1979 г., 213 - sahifaga qarang) shu narsa kelib chiqadiki, soddalashtirish algoritmi yordami bilan tupikli DNSH larni mukammal DNSH dan yasash uchun faqat konyunktsiyalar ifodasida ko‘paytuvchilar joylashishini variatsiyalamoq yetarli.

Hozirgi vaqtda konyunktsiyalarni DNSH ifodasidan chetlashtirish va ko‘paytuvchilarni konyunktsiyalar ifodasidan chetlashtirish mumkinligini tekshirish soni (MDNSH tartiblashning hamma turi bo‘yicha)

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