Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja

3- teorema. Mantiq algebrasining ixtiyoriy formulasini DNShga keltirish mumkin.
Isboti. 1- teoremaga ko‘ra mantiq algebrasining ixtiyoriy formulasini qandaydir
A  A  ...  A KNShga keltirish mumkin, bu yerda A (i  1, m) – elementar dizyunksiyalar.
1 2 m i
Ravshanki, elementar dizyunksiyning inkori elementar konyunksiya bo‘ladi. Shuning uchun berilgan formulaning inkori
A  A  ......  A  A  A  ......  A
1 2 m 1 2 m
DNShda bo‘ladi, bunda A (i  1, m) – elementar konyunksiyalar. ■
i
4- teorema. Mantiq algebrasining formulasi aynan yolg‘on bo‘lishi uchun uning DNShdagi barcha elementar kon’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashishi zarur va yetarli.
1 2 n
Isboti. 1. Mantiq algebrasining P formulasi P  A  A  ...  A ko‘rinishda berilgan
i
bo‘lib, uning DNShidagi barcha A (i  1, n) elementar kon’yunktiv hadlarida kamida bittadan
i
elementar mulohaza bilan birga bu mulohazaning inkori ham qatnashsin. Berilgan P formulaning A
i i
(i  1, n) hadida qandaydir x elementar mulohaza bilan birga uning x inkori ham qatnashgan bo‘lsin
i i
deb faraz qilaylik. 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 inkori
ham qatnashgan bo‘lsa, u holda
P  J  J  ...J   J , ya’ni P aynan yolg‘on bo‘ladi.

P  P fopmulaning DNShdagi barcha kon’yunktiv hadlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashadi. ■

2. Mantiq algebrasining P formulasi aynan yolg‘on bo‘lsin. U holda P formulaning inkori doimo chin bo‘ladi. Shuning uchun, 2- teoremaga asosan, P formulaning KNShdagi barcha elementar diz’yunksiyalarida kamida bittadan elementar mulohaza bilan birga uning inkori ham topiladi. Demak,

• teorema berilgan formulaning doimo yolg‘on bo‘lishi yoki bo‘lmasligini, chinlik jadvaliga murojaat qilmasdan, aniqlash imkonini bergani uchun, uni yolg‘onlik alomati deb atash mumkin.
• misol. Berilgan

P  (x  x  y)  ( y  y  z)  (x  y  x  z  z )
formulaning doimo yolg‘on formula bo‘lishini ko‘rsatamiz.

Haqiqatdan
ham, P formula
DNShda yozilgan bo‘lib, uning tarkibidagi 1- elementar
kon’yunksiya ifodasida x , 2- ifodasida y , 3-sida esa x va z elementar mulohazalar o‘zlarining inkorlari bilan birgalikda qatnashganlari uchun, yolg‘onlik alomatiga asosan, P  J . ■