Mavzu: Formulalarning normal shakllari. Formulalarning mukammal normal shakllari Reja

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. ■
1. To‘g‘ri va to‘liq elementar kon’yunksiya va diz’yunksiyalar.
Yuqorida teng kuchli almashtirishlar bajarib, mantiq algebrasining berilgan formulasi uchun turli KNShlar va DNShlar topish mumkinligi haqida ma’lumot berilgan edi. Formulalar uchun turli KNShlar va DNShlar orasida muayyan shartlarni qanoatlantiradiganlari muhim hisoblanadi. Quyida shunday shakllar o‘rganiladi.
1- ta’ r i f . Agar elementar kon’yunksiya (diz’yunksiya) ifodasida ishtirok etuvchi har bir
elementar mulohaza shu ifodada faqat bir marta uchrasa, u holda bu ifoda to‘g‘ri elementar kon’yunksiya (diz’yunksiya) deb ataladi.

• - misol. Berilgan a  b  c va a  d  f elementar diz’yunksiyalar to‘g‘ri elementar

diz’yunksiyalar, abdc va aecb elementar kon’yunksiyalar esa to‘g‘ri elementar kon’yunksiyalardir. Lekin, a  u  u  c va u  u  e  n elementar diz’yunksiyalar ifodasida u elementar mulohaza bir martadan ortiq qatnashganligi sababli, ularning hech biri to‘g‘ri elementar diz’yunksiya bo‘la
olmaydi. x2 elementar mulohaza x x x x va x x x x x elementar kon’yunksiyalar tarkibida bir
1 2 3 2 2 2 2 2 6
martadan ortiq qatnashganligi sababli, bu ifodalarning hech qaysisi to‘g‘ri elementar kon’yunksiya bo‘la olmaydi. ■

• ta’ rif. Agar berilgan elementar mulohazalarning har biri elementar kon’yunksiya (diz’yunksiya) ifodasida faqat bir matra qatnashsa, bu ifoda shu elementar mulohazalarga nisbatan