Formulalarning normal shakllari Elementar kon’yunksiya va elementar diz’yunksiya tushunchalari

5- misol. Berilgan

formulaning doimo yolg‘on formula bo‘lishini ko‘rsatamiz.

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

5- teorema. Mulohazalar algebrasining ixtiyoriy formulasi uchun yechilish muammosi doimo ijobiy hal bo‘ladi.

Isboti. Agar mulohazalar algebrasining berilgan formulasi KNShda

bo‘lmasa, uni KNShga keltirgandan so‘ng, 2- teoremaga asosan, bu formulaning tavtologiya bo‘lishi yoki bo‘lmasligi aniqlanadi. Agar berilgan formula tavtologiya bo‘lmasa, uni DNShga keltirib, 4- teorema asosida, formulaning aynan yolg‘on bo‘lishi yoki bo‘lmasligi aniqlanadi. Agar tekshirilayotgan formula doimo chin va doimo yolg‘on bo‘lish shartlarini qanoatlantirmasa, u holda u bajariluvchi formula bo‘ladi. Demak, mulohazalar algebrasining berilgan formulasi tavtologiya, aynan yolg‘on yoki bajariluvchi formula bo‘lishini chekli sondagi qadamlar jarayonida aniqlash mumkin. Shuning uchun mulohazalar algebrasining ixtiyoriy formulasi uchun yechilish muammosi doimo ijobiy hal bo‘ladi. ■