Mukammal diz’yunktiv va kon’yuktiv normal formalar

5-misol. formula o`zgaruvchilarga nisbatan MDNF dir.

DNF va MDNF larning ta`rifidan ko`rinadiki, bunday formulalar keltirilgan formulalardir.

•  

TEOREMA. Mulohazalar algebrasining aynan yolg’on bo`lmagan ixtiyoriy formulasi yagona MDNF ga teng kuchlidir.

•  

MISOL. (A ˥B)C) C formulaning MDNF ini yozing

yoki

•  

Jadvaldan ko`rinadiki: berilgan formula proposirsional o`zgaruvchilar qiymatlarining (1,1,1), (1,1,0), (1,0,0), (0,1,1), (0,1,0), (0,0,1) va (0,0,0) tizimlarida 1 (rost) qiymatni qabul qiladi.

•  

A	B	C
1 1 1 1 0 0 0 0	11 00 11 00	1 0 1 0 1 0 1 0	0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	1 1 1 1 0 0 1 1	1 1 0 0 1 1 1 1	1 0 1 0 0 0 1 0	1 0 0 0 1 0 1 0	1 1 0 1 1 1 1 1

A	B	C
1 1 1 1 0 0 0 0	11 00 11 00	1 0 1 0 1 0 1 0	0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	1 1 1 1 0 0 1 1	1 1 0 0 1 1 1 1	1 0 1 0 0 0 1 0	1 0 0 0 1 0 1 0	1 1 0 1 1 1 1 1

Berilgan formula 7 ta tizimda 1 qiymatga, bitta tizimda esa 0 qiymatga egadir, demak, u formula emas. (4) dan k o`rinadiki, berilgan formulaning MDNF iga ettita to`liq elementar kon`yunksiya kiradi. Demak, tekshirilayotgan formula bo`lsa, uning MDNF iga ta to`liq elementar kon`yunksiya kiradi.

• Berilgan formula 7 ta tizimda 1 qiymatga, bitta tizimda esa 0 qiymatga egadir, demak, u formula emas. (4) dan k o`rinadiki, berilgan formulaning MDNF iga ettita to`liq elementar kon`yunksiya kiradi. Demak, tekshirilayotgan formula bo`lsa, uning MDNF iga ta to`liq elementar kon`yunksiya kiradi.
• Shunday qilib, mulohazalar algebrasining formulasini formulami yoki yo`qmi ekanligini aniqlash uchun uni MDNF ga yoyib, bu MDNF dagi to`liq elementar kon`yunksiyalar sonini sanash kerak: to`liq elementar kon`yunksiyalar soni ta bo`lsa, berilgan formula formula, bo`lganda-bajariluvchi formula bo`ladi. Agar bo`lsa, u holda berilgan formula bo`lishi ravshandir.

•  

Yuqoridagi ta`riflarda “kon`yunksiya” so`zini “diz`yunksiya” so`zi bilan, “diz`yunksiya” so`zini “kon`yunksiya” so`zi bilan almashtirsak, u holda “elementar diz`yunksiya”, “to`liq elementar diz`yunksiya”, “mukammal kon`yunktiv normal forma (MKNF)” tushunchalari hosil bo`ladi.

• Yuqoridagi ta`riflarda “kon`yunksiya” so`zini “diz`yunksiya” so`zi bilan, “diz`yunksiya” so`zini “kon`yunksiya” so`zi bilan almashtirsak, u holda “elementar diz`yunksiya”, “to`liq elementar diz`yunksiya”, “mukammal kon`yunktiv normal forma (MKNF)” tushunchalari hosil bo`ladi.
• MKNF lar uchun quyidagi teorema o`rinli.
• TEOREMA. Mulohazalar algebrasining bo`lmagan ixtiyoriy formulasi yagona MKNF ga teng kuchlidir.

•