Mulohazalar algebrasi. Mulohazalar ustida amallar

5.4-teorema. sistemalar to’liq sistemalardir.
Isbot. ekanligini rostlik jadvali yordamida bevosita tekshirib ko’rish mumkin. to’liq sistema bo’lgani uchun ham amallarning to’liq sistemasini tashkil etadi; ning to’liqligi ham xuddi shu tarzda isbotlanadi.


6§. YECHILISH MUAMMOSI. NORMAL FORMALAR
Har qanday mantiqiy sistemalaridagidek mulohazalar algebrasi uchun masalani qo’yish mumkin: mulohazalar algebrasining har qanday formulasi formula yoki formula emasligini chekli qadamdan so’ng aniqlab beradigan yagona usul (algoritm) mavjudmi yoki mavjud emasmi? Bu masala yechilish muammosi deb ataladi. Yechilish muammosini faqat formulalar uchun emas, balki formulalar sinfidan kengroq bo’lgan bajariluvchi formulalar sinfi uchun qo’ysa bo’ladi. Albatta, keyingi muammoning yechimi oldingi muammoning ham yechimi bo’lishi ravshandir.
Mulohazalar algebrasi uchun bu muammo ijobiy tarzda hal etiladi. Haqiqatan, mulohazalar algebrasining ixtiyoriy formulasi bo’lsa, uning rostlik jadvalini tuzish bilan formulaning bajariluvchi formula yoki formula ekanligini bir qiymatli aniqlash mumkin. Demak, yuqoridagi muammoni ijobiy hal etuvchi yagona usul (algortm) mavjud bo’lib, bu algortm rostlik jadvalidan iboratdir.
Ammo bu algortmning muhim kamchligi bor ekanligini sezish mumkin. Haqiqatan, formula tarkibida ta propozitsional o’zgaruvchi qatnashgan bo’lsa, u holda uning qiymatlarini propozitsional o’zgaruvchilar qiymatlarining ta tanlanmaida hisoblashga to’g’ri keladi. Ravshanki, bu usul hatto uncha murakkab bo’lmagan formulalar qiymatlarini hisoblashda ham juda katta qiyinchiliklar tug’diradi. Shuning uchun ham bu usul amaliy foydalanish nuqtai nazaridan qulaysizdir. Biz quyida amaliy jihatdan katta qulaylik beradigan boshqa usul tanishamiz.
Eslatma. Biz bu paragrafda formulani qiqacha ko’rinishida yozamiz.
Quyidagi belgilashni kiritamiz:

6.1-ta’rif. propozitsional o’zgaruvchilar 1 va 0 lardan tuzilgan tanlanma bo’lsa, u holda formula elementar konyuksiya deyiladi (bunda propozitsional o’zgaruvchilar takrorlangan bo’lishi ham mumkin).
6.1-misol. formulalar elementar konyuksiyalardir.
6.2-ta’rif. Elementar konyuksiyalarning har qanday dizyunksiyasi dizyunktiv normal forma (DNF) deyiladi.
6.2-misol. formula 6.1-misolda keltirilgan elementar konyuksiyalardan tuzilgan DNF dir.