Mavzu: Normal formalar. Mdnf, mknf. Mulohazalar algebrasi formulalarini mdnf va mknf larda ifodalash

2- teorema.Elementar mulohazalarning aynan yolg‘on bo‘lmagan ixtiyoriyformulasini MDNShga keltirish mumkin.
Isboti. Elementar mulohazalarning aynan yolg‘on formulasidan farqli berilgan formulasini bilan belgilab, avvalo, formulani MKNShga keltiramiz. teng kuchlilikdan foydalanib, formulaning MKNShi tarkibida qatnashuvchi barcha ifodalardagi belgi o‘rniga belgi va, aksincha, o‘rniga hamda elementar mulohazalar o‘rinlariga mos ravishda ularning inkorlari, va, aksincha, elementar mulohazalarning inkorlari o‘rinlariga mos ravishda ularning o‘zlari qo‘yilsa, u holda formulaning MDNShi hosil bo‘ladi. ■
5- misol. 2- teoremadan foydalanib, 4- misolda MKNShi topilgan formulani MDNShga keltiramiz. Ushbu bobning 5- paragrafidagi 4- teoremaga asoslanib, berilgan formulaning doimo yolg‘on emasligiga ishonch hosil qilish qiyin emas. Avvalo mantiqiy formulani MKNShga keltirish algoritmidan foydalanib formulani MKNShga keltiramiz:



.
formulaning topilgan MKNShi tarkibida qatnashgan barcha belgilar o‘rniga belgi va, aksincha, o‘rniga hamda , va elementar mulohazalar o‘rinlariga mos ravishda , va , shunga o‘xshash, , va inkorlar o‘rinlariga mos ravishda , , va qo‘yilsa, u holda formulaning MDNShi hosil bo‘ladi. ■
5- ta’rif. Agar formulaning MKNShi (MDNShi) ifodasida qatnashuvchi barcha elementar mulohazalardan tuzish mumkin bo‘lgan barcha elementar diz’yunksiyalar (kon’yunksiyalar) shu ifodada ishtirok etsa, u holda bunday MKNSh (MDNSh) to‘liq MKNSh (MDNSh) deb ataladi.
6- misol. Ushbu formula va elementar mulohazalarga nisbatan MKNShda bo‘lsada, u to‘liq MKNShda emas. va elementar mulohazalarga nisbatan to‘liq MKNShi ifodasi ko‘rinishga ega.
MDNShdagi formula , va elementar mulohazalarga nisbatan to‘liq MDNShda emas, lekin formula bu elementar mulohazalarga nisbatan to‘liq MDNShdagi formuladir. ■

1^“Mukammalkon’yunktiv normal shakl”iborasini, qisqacha, MKNSh, “mukammaldiz’yunktiv normal shakl” iborasini esa, MDNSh deb yozamiz.

2^Bu yerda va keyingi elementar diz’yunksiyalar uchun oralik teng kuchliliklarni tushirib qoldirdik.