Mukammal diz’yunktiv va kon’yuktiv normal formalar
Mukammal diz’yunktiv va kon’yuktiv normal formalar.
Reja
Yechilish muammosi.
Diz’yunktiv normal formalar (DNF).
Mukammal diz’yunktiv normal formalar (MDNF).
MDNF ga yoyish algoritmi.
Har qanday mantiqiy sistemalardagidek mulohazalar algebrasi uchun quyidagi 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 AR formulalar sinfidan kengroq bo`lgan bajariluvchi formulalar sinfi uchun ham qo`ysa bo`ladi. Albatta, keyingi muammoning yechimi oldingi muammoning ham yechimi bo`lishi ravshandir.
Har qanday mantiqiy sistemalardagidek mulohazalar algebrasi uchun quyidagi 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 AR formulalar sinfidan kengroq bo`lgan bajariluvchi formulalar sinfi uchun ham 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 ihtiyoriy 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 (algoritm) mavjud bo`lib, bu algoritm rostlik jadvalidan iboratdir.
Mulohazalar algebrasi uchun bu muammo ijobiy tarzda hal etiladi. Haqiqatan, -mulohazalar algebrasining ihtiyoriy 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 (algoritm) mavjud bo`lib, bu algoritm rostlik jadvalidan iboratdir.
Ammo bu algoritmning muhim kamchiligi bor ekanligini sezish mumkin. Haqiqatan, formula tarkibida ta propozitsional o`zgaruvchi qatnashgan bo`lsa, u holda uning qiymatlarini propozitsional o`zgaruvchilar qiymatlarining ta tizimida 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 bilan tanishamiz.
