Mavzu formulalarning normal shakllari. Mukammal kon’yunktiv va diz’yunktiv normal shakllar

2- teorema. va formulalar teng kuchli bo‘lishi uchun

formula tavtologiya bo‘lishi zarur va yetarli.

Isboti. va formulalarning chinlik to‘plamlari, mos ravishda, va bo‘lsin.

a) va formulalar teng kuchli, ya’ni bo‘lsin. U holda va, shu sababli ekvivalensiyaning chinlik to‘plami

bo‘ladi. Bundan formulalarning tavtologiya ekanligi kelib chiqadi.

b) formula tavtologiya bo‘lsin. U holda teng kuchlilik o‘rinli bo‘lgani uchun, kon’yunksiya ta’rifiga asosan, va teng kuchliliklar o‘rinlidir. 1- teoremaga ko‘ra, va , ya’ni bo‘lishi kelib chiqadi. Bu, o‘z navbatida, va formulalarning mantiqiy ekvivalentligini tasdiqlaydi. ■

1^ “Mukammal kon’yunktiv normal shakl” iborasini, qisqacha, MKNSh, “mukammal diz’yunktiv normal shakl” iborasini esa, MDNSh deb yozamiz.

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

3