Mukammal kon'yuktiv normal shakl (mdnsh), uni tuzish usuli

Normal shakllar.
Har bir fikr algebrasi formulasi uchun unga teng kuchli boʻlgan va faqatgina inkor, kon'yunksiya &,
diz'yunksiya V amallarini o'z ichiga olgan formulani keltirish mumkin. Buning uchun implikasiya va ekvivalensiyadan qutulish qoidalaridan foydalanish kifoya.
Ta'rif 1. A, A,, ..., A fikr oʻzgaruvchilarining kon'yunktiv bir hadi deb, ushbu o'zgaruvchilar yoki ularning teskarilarining kon'yunksiyasiga aytiladi.


Masalan: ⌐A&A,&A, ⌐A&A,&A,&A,
Ta'rif 2. A, A, ..., A, fikr oʻzgaruvchilarining
diz'yunktiv bir hadi deb, ushbu oʻzgaruvchilarning yoki ularning teskarilarining diz'yunksiyasiga aytiladi.
Masalan: ⌐A1VA2VA3



Mukammal normal shakllar
⚫ Ta'rif 5. Agar bir hadga Ai yoki-Ai formulalar juftligidan faqat bittasi kirgan boʻlsa, A, A,, ..., A, fikr oʻzgaruvchilarining kon'yunktiv yoki diz'yunktiv bir hadlari mukammal deyiladi.


Ta'rif 6. Agar KNSh yoki DNSh larda A,, A,, ..., A oʻzgaruvchilarning takrorlanmaydigan mukammal bir hadlari kirgan bo'lsa, A, A, ..., A, fikr
oʻzgaruvchilarining KNSh yoki DNSh lari mukammal deyiladi.
Masalan: A&BV-A&BVA&-B - A va B fikr oʻzgaruvchilarining Mukammal diz'yunktiv normal shakli (MDNSh) boʻladi. AVB - esa MKNSh boʻladi. Teorema 1. Har bir ayniy yolg'on boʻlmagan formula yagona MDNF ega boʻladi.
Teorema 2. Har bir tavtologiya boʻlmagan fikrlar algebrasi formulasi, yagona MKNSh ga ega boʻladi.
 Mukammal kon'yunktiv va mukammal kon'yunktiv normal shakllar
Har qanday mantiqiy funktsiya DNF va CNF ko'rinishida ko'plab tasvirlarga ega bo'lishi mumkin. Bu namoyishlar orasida alohida o'rinni mukammal DNF (SDNF) va mukammal CNF (SKNF) egallaydi.
Ta'rif 1. A'lo disjunktiv normal shakl(SDNF) - bu DNF bo'lib, unda har bir kon'yunktiv monomialda to'plamdagi har bir o'zgaruvchi aynan bir marta sodir bo'ladi va o'zi yoki uning inkor qilinishi paydo bo'ladi.
Konstruktiv ravishda, DNFga tushirilgan taklif algebrasining har bir formulasi uchun SDNF quyidagicha ta'riflanishi mumkin:
Ta'rif 2. A'lo disjunktiv normal shakl(SDNF) taklifli algebra formulasi quyidagi xususiyatlarga ega bo'lgan DNF deb nomlanadi:
Ta'rif 3. Barkamol kon'yunktiv normal shakl(SKNF) - bu har bir ajratuvchi


monomialda to'plamdagi har bir o'zgaruvchi aynan bir marta sodir bo'ladigan va o'zi yoki uning inkor qilinishi paydo bo'ladigan CNF.
Strukturaviy ravishda, CNF ga tushirilgan taklif algebrasining har bir formulasi uchun SKNF quyidagicha ta'riflanishi mumkin.
Ta'rif 4. Barkamol kon'yunktiv normal shakl(SKNF) berilgan taklifli algebra formulasi quyidagi xususiyatlarga javob beradigan CNF deb ataladi.
Teorema 1. Bir xil noto'g'ri bo'lmagan o'zgaruvchilarning har bir mantiqiy funktsiyasi SDNFda, shuningdek, o'ziga xos tarzda ifodalanishi mumkin.
SDNFni topish usullari
1 -yo'l
2 -chi yo'l
formula 1 qiymatini oladigan qatorlarni tanlang;
biz konjunktivlarning disjunksiyasini tuzamiz, agar shartli o'zgaruvchiga 1 qiymati qo'shilsa, biz bu o'zgaruvchini yozamiz, agar qiymati 0 bo'lsa, uni inkor etish. Biz SDNF -ni olamiz.
Teorema 2. O'zgaruvchilarning har bir mantiqiy funktsiyasi bir xil emas, SKNF -da va o'zgacha tarzda ifodalanishi mumkin.
SKNFni topish usullari
1 -yo'l- ekvivalent transformatsiyalar yordamida:
2 -chi yo'l- haqiqat jadvallaridan foydalanish:
formula 0 qiymatini oladigan qatorlarni tanlang;
agar biz o'zgarmaydigan 0 qiymatli disjunksiyaga kiritilgan bo'lsa, biz bu o'zgaruvchini yozamiz, agar qiymati 1 bo'lsa, uni inkor etish. Biz SKNFni olamiz.
Misol 1. CNF chizish funktsiyalari.
Yechim
Keling, o'zgaruvchilarni o'zgartirish qonunlaridan foydalangan holda "" to'plamini chiqarib tashlaylik:
= / de Morgan va er -xotin inkor qonunlari / =
/ tarqatish qonunlari / =
2 -misol. Formulani DNF ga keltiring.
Yechim
Mantiqiy operatsiyalarni quyidagicha ifodalaylik va:
= / biz inkorni o'zgaruvchilarga havola qilamiz va ikkita negativni kamaytiramiz / =
= / tarqatish qonuni /.
Misol 3. Formulani DNF va SDNF ga yozing.
Yechim
Mantiq qonunlaridan foydalanib, biz bu formulani faqat elementar birikmalarning disjunksiyalarini o'z ichiga oladigan shaklga keltiramiz. Olingan formula kerakli DNF bo'ladi:
SDNFni yaratish uchun biz ushbu formula uchun haqiqat jadvalini tuzamiz:
Biz jadvalning satrlarini belgilaymiz, unda formula (oxirgi ustun) 1 qiymatini oladi. Har bir bunday satr uchun biz berilgan satrning o'zgaruvchilar to'plamiga to'g'ri keladigan formulani yozamiz:
1 -qator:;
3 -qator:;
5 -qator:.
Bu uchta formulaning disjunksiyasi 1 qiymatini faqat 1, 3, 5 qatorlar o'zgaruvchilar to'plamida oladi va shuning uchun istalgan mukammal disjunktiv normal shakl (SDNF) bo'ladi:
Misol 4. Formulani SKNFga ikki yo'l bilan keltiring:
a) ekvivalent transformatsiyalar yordamida;
b) haqiqat jadvalidan foydalanish.
Yechim:
Biz ikkinchi elementar disjunksiyani o'zgartiramiz:
Formulasi:
b) ushbu formula uchun haqiqat jadvalini tuzing:

Biz jadvalning satrlarini belgilaymiz, unda formula (oxirgi ustun) 0 qiymatini oladi. Har bir bunday satr uchun biz berilgan satrning o'zgaruvchilar to'plamiga to'g'ri keladigan formulani yozamiz:
2 -qator:;
6 -qator:.
Bu ikkita formulaning birikmasi 0 qiymatini faqat 2 va 6 -satrlardagi o'zgaruvchilar to'plamida oladi va shuning uchun kerakli mukammal kon'yunktiv normal shakl (SCNF) bo'ladi:
Har qanday mantiqiy formulalar uchun bir xil aylantirishlar yordamida unga teng keladigan cheksiz ko'p formulalar tuzish mumkin. Mantiq algebrasida asosiy vazifalardan biri kanonik shakllarni qidirishdir (ya'ni bitta qoida, kanon bo'yicha tuzilgan formulalar).
Agar mantiqiy funktsiya o'zgaruvchilarning ajralishi, konjunksiyasi va inkor qilinishi orqali ifodalansa, bu tasvirning shakli normal deyiladi.
Oddiy shakllar orasida mukammal normal shakllar ajratiladi (funktsiyalari o'ziga xos tarzda yozilgan shakllar).