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

Diz’yunktiv normal shaklni soddalashtirish va tupikli DNSh.
Mantiq algebrasining DNShdagi ixtiyoriy formulasi uchun
, , (1)
bo‘lsin, bu yerda – biror DNSh, – berilgan formulaning biror elementar kon’yunksiyasi, – shu elementar kon’yunksiyaning birorta ( indeksli) ko‘paytuvchisi, – ning qolgan ko‘paytuvchilari, ya’ni . DNShni soddalashtirishning ikki xil yo‘lini (tipini) ko‘rib o‘taylik.
I. Elementar kon’yunksiyani chetlashtirish operatsiyasi. DNShdan DNShga o‘tish uchun elementar kon’yunksiyani chetlashtirish kerak. Bunday o‘zgartirish bo‘lganda va faqat shundagina mumkin.
II. Ko‘paytuvchini chetlashtirish operatsiyasi. DNShdan DNShga o‘tish operatsiyasi. Buni bajarish uchun elementar kon’yunksiya ifodasidan ko‘paytuvchini chetlashtirish kerak. Bu almashtirish bo‘lganda aniqlangan.
1- ta’rif. I va II almashtirishlar yo‘llari bilan soddalashtirish mumkin bo‘lmagan DNSh (I va II almashtirishlarga nisbatan) tupikli DNSh (TDNSh) deb ataladi.
1- misol. DNSh I va II almashtirishlarga nisbatan tupikli DNShdir. ■
(1) va monotonlik aksiomasiga asosan va bo‘ladi. Shuning uchun TDNShlar orasida har doim minimal diz’yunktiv normal shakllar mavjud bo‘ladi.
Diz’yunktiv normal shaklni soddalashtirish. Endi yuqorida keltirilgan ikkita almashtirish asosida berilgan DNShni soddalashtirish algoritmini keltiramiz.
1. funksiyani ifodalovchi biror DNShni dastlabki DNSh sifatida olamiz. Masalan, shunday DNSh sifatida uning mukammal diz’yunktiv normal shaklini olamiz (chunki chinlik jadvali asosida uni formula orqali osongina yozish mumkin).
2. Dastlabki diz’yunktiv normal shaklda qo‘shiluvchi-larni va har bir qo‘shiluvchidagi ko‘paytuvchilarni tartibga solamiz. Bu tartiblash bilan DNSh ko‘rinishi beriladi.
3. Chapdan o‘ngga qarab DNSh ko‘rinishi ko‘rilib o‘tiladi. Navbatdagi ( ) elementar kon’yunksiyaga nisbatan elementar kon’yunksiyani chetlashtirish operatsiyasi qo‘llaniladi, agar bu mumkin bo‘lmasa, u vaqtda chapdan o‘ngga qarab elementar kon’yunksiyalarning ko‘paytuvchi hadlari ko‘rilib chiqiladi va ularga nisbatan mumkin bo‘lgunga qadar ko‘paytuvchini chetlashtirish operatsiyasi qo‘llaniladi. Shundan so‘ng keyingi elementar kon’yunksiyaga o‘tiladi.
Oxirgi elementar kon’yuknsiyani ishlab chiqqandan keyin, hosil bo‘lgan DNShni yana qaytadan chapdan o‘ngga qarab ko‘rib chiqiladi va elementar kon’yunksiyani chetlashtirish operatsiyasi sinab ko‘riladi. Natijada izlangan diz’yunktiv normal shaklga ega bo‘lamiz. ■