Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja

2- teorema. Mantiq algebrasining formulasi tavtologiya bo‘lishi uchun uning KNShidagi barcha elementar diz’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashishi zarur va yetarli.
Isboti. 1. Mantiq algebrasining P formulasi
P  A  A  ...  A
1 2 n
(5)
ko‘rinishda berilgan bo‘lib, uning KNShidagi barcha A (i  1, n) elementar diz’yunktiv hadlarida
i
kamida bittadan elementar mulohaza bilan birga bu mulohazaning inkori ham qatnashsin. Faraz
i i i
qilaylik, P formulaning A (i  1, n) hadida qandaydir x elementar mulohaza bilan birga uning x
i
inkori ham qatnashgan bo‘lsin. U holda x  x  J va J  A  J teng kuchliliklarga asosan barcha
i  1, n uchun A  J o‘rinlidir. Demak, agar barcha i  1, n uchun A hadlar tarkibida kamida bitta
elementar mulohaza bilan birga bu mulohazaning
i
inkori ham qatnashgan bo‘lsa, u holda
P  J  J  ...  J  J , ya’ni P tavtologiya bo‘ladi.
2. Mantiq algebrasining (5) ko‘rinishda ifodalangan P formulasi tavtologiya bo‘lsin. Teorema
tasdig‘iga teskari tasdiq o‘rinli deb faraz qilamiz. Ya’ni, P formula tarkibidagi A (i  1, n) elementar
i
diz’yunktiv hadlardan hech bo‘lmaganda bittasida hech qaysi bir elementar mulohaza o‘zining inkori bilan birga qatnashmagan bo‘lsin. Berilgan P formulaning KNShidagi hech qaysi bir elementar
mulohaza o‘zining inkori bilan birga qatnashmagan biror A (1 i' n) elementar diz’yunktiv hadini
i '
tahlil qilamiz. Bu formulada hech qaysi bir elementar mulohaza o‘zining inkori bilan birga
i '
qatnashmaganligi sababli A formula uchun tuzilgan chinlik jadvalining shunday satri topiladiki, unda
i '
barcha elementar mulohazalar yo qiymatga ega bo‘ladi va A formula tarkibidagi barcha diz’yunksiya
amallarini bajarish natijasi ham shu satr uchun yo bo‘ladi. Shuning uchun, kon’yunksiya amalining ta’rifiga ko‘ra, P formula uchun tuzilgan chinlik jadvalining o‘sha satridagi qiymat yo bo‘ladi. Bu esa teorema isbotining “ P formula tavtologiya bo‘lsin” degan shartiga ziddir. ■
2- teorema berilgan formula tavtologiya yoki tavtologiya emasligini, chinlik jadvaliga murojaat
qilmasdan, aniqlash imkonini beradi. Shuning uchun 2- teorema chinlik alomati deb yuritiladi. Chinlik alomatiga ko‘ra, berilgan formulaning tavtologiya bo‘lishi yoki bo‘lmasligini aniqlash uchun, uni KNShga keltirish kerak. Agar formulaning KNShdagi barcha elementar dizyunksiyalar ifodasida hech bo‘lmaganda bitta elementar mulohaza o‘zining inkori bilan birga qatnashgan bo‘lsa, u holda bu formula tavtologiya, aks holda esa tavtologiya emasligi aniqlanadi.
4- misol. 2- teoremadan foydalanib x  x  y  y va x  x  ( y  y  z) formulalarning tavtologiya bo‘lishi yoki bo‘lmasligini tekshiramiz. Berilgan formulalarni, mos ravishda, P va Q bilan belgilab, (1) va (2) formulalardan foydalansak, quyidagi KNShlarga ega bo‘lamiz:
P  x  x  y  y  x  x  y  y ,
Q  (x  x)  ( y  y  z)  (x  x)  ( y  y  z).
Bu formulalarning KNShlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashgani uchun berilgan formulalarning har biri tavtologiyadir. ■