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

4- misol. Formulani MKNShga keltirish algoritmidan foydalanib , , va elementar mulohazalarning formulasini MKNShga keltiramiz. Dastlab, algoritmning 1- bandiga ko‘ra, berilgan formulani KNShga keltiramiz. Buning uchun, avvalo, va teng kuchliliklardan foydalanib formulani faqat kon’yunksiya, diz’yunksiya va inkor mantiqiy amallari orqali ifodalaymiz:
.
Hosil bo‘lgan formulaga teng kuchlilikni qo‘llasak, formula KNShga keladi.
KNSh ifodasida barcha elementar diz’yunksiyalar turlicha bo‘lganligi sababli algoritmning 2- bandini bajarishga hojat yo‘q.
KNSh ifodasidagi 1- va 2- elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalar bo‘lmaganligi uchun algoritmning 3- banda ifodalangan jarayonlarni bajarishga o‘tamiz. KNSh ifodasidagi hech qaysi elementar diz’yunksiya ifodasida birorta ham o‘zgaruvchi o‘zining inkori bilan birgalikda qatnashmaganligi sababli 3- banddagi a) hol bu yerda ro‘y bermaydi. KNSh ifodasidagi 1- elementar diz’yunksiyada , 2- elementar diz’yunksiyada esa ikki marta qatnashgani uchun b) holda bayon qilingandek ish yuritib, formula uchun barcha elementar diz’yunksiyalari to‘g‘ri elementar diz’yunksiyalardan iborat KNShni hosil qilamiz. Ushbu bobning 5- paragrafidagi 2- teoremaga asosan, formula tavtologiya emas.
Algoritmning 4- bandini bajaramiz. Ko‘rinib turibdiki, KNShdagi 1- elementar diz’yunksiyada , va , 2- elementar diz’yunksiyada , va , 3- va 4- elementar diz’yunksiyalarda esa va o‘zgaruvchilar yoki ularning inkorlari yo‘q. Shularni e’tiborga olib, KNSh ifodasidagi to‘rtala elementar diz’yunksiyalarni to‘liq elementar diz’yunksiyalar shakliga keltirish maqsadida 4- bandda ifodalangan jarayonni qo‘llaymiz. Natijada 1- elementar diz’yunksiya ( ) uchun







,
2- elementar diz’yunksiya ( ) uchun²


,
3- elementar diz’yunksiya ( ) uchun


va 4- elementar diz’yunksiya ( ) uchun


teng kuchliliklarga ega bo‘lamiz.
Topilgan barcha KNShlar , , va elementar mulohazalarga nisbatan to‘liq KNShlardir. Bu KNShlarni o‘zaro solishtirib, ularning tarkibida bir xil elementar diz’yunksiyalar bor (masalan, 1- va 2- KNShlardagi elementar diz’yunksiya) bo‘lgan vaziyat ro‘y berganligini aniqlaymiz. Shuning uchun, algoritmning 5- bandi boshqarishni uning 2- bandiga o‘tkazadi.
Algoritmning 2- bandini bajarib, formula uchun





KNSh ifodasiga ega bo‘lamiz.
Algoritmning 3- bandi boshqarishni uning 4- bandiga, 4- bandi esa 6- bandiga o‘tkazadi, chunki oxirgi KNSh ifodasidagi barcha elementar diz’yunksiyalar to‘g‘ri va to‘liq elementar diz’yunksiyalardir. Sunday qilib, berilgan formula uchun oxirgi formula MKNShdir. ■
Ravshanki, agar formulaning MKNShi tarkibida qatnashuvchi barcha ifodalardagi belgi o‘rniga belgi va, aksincha, o‘rniga qo‘yilsa, u holda MDNSh hosil bo‘ladi. Xuddi shuningdek, agar formulaning MDNShi tarkibida qatnashuvchi barcha ifodalarda shunday o‘zgartirishlar bajarilsa, u holda MKNSh hosil bo‘ladi.