Diskirit tuzilmalari fanidan

 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).