Mantiqiy funktsiyaning kon'yunktiv normal shakli. Mantiqiy funktsiyalarni ifodalashning kon'yunktiv shakllari
Oddiy kon'yunktiv shakl avtomatik teoremani isbotlash uchun qulay. Har qanday mantiqiy formulani CNF ga aylantirish mumkin. Buning uchun siz quyidagilarni ishlatishingiz mumkin: ikki tomonlama inkor qonuni, de Morgan qonuni, taqsimlanish.
YouTube kolleji
-
1 / 5
Formula KNFda:
¬ A ∧ (B ∨ C), (\ Displaystyle \ neg A \ xanjar (B \ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\ Displaystyle (A \ vee B) \ xanjar (\ neg B \ vee C \ vee \ neg D) \ xanjar ( D \ vee \ neg E),) A ∧ B. (\ Displaystyle A \ xanjar B.)Formula KNFda emas:
¬ (B ∨ C), (\ Displaystyle \ neg (B \ vee C),) (A ∧ B) ∨ C, (\ Displaystyle (A \ takoz B) \ vee C,) A ∧ (B ∨ (D ∧ E)). (\ Displaystyle A \ xanjar (B \ vee (D \ takoz E)).)Ammo CNFda bo'lmagan bu 3 ta formulalar CNFdagi quyidagi formulalarga teng:
¬ B ∧ ¬ C, (\ Displaystyle \ neg B \ wedge \ neg C,) (A ∨ C) ∧ (B ∨ C), (\ Displaystyle (A \ vee C) \ takoz (B \ vee C),) A ∧ (B ∨ D) ∧ (B ∨ E). (\ Displaystyle A \ wedge (B \ vee D) \ wedge (B \ vee E).)CNFni qurish
CNF yaratish algoritmi
1) Formulada mavjud bo'lgan barcha mantiqiy operatsiyalardan qutuling, ularni asosiylari bilan almashtiring: konjunksiya, disjunksiya, inkor. Buni ekvivalent formulalar yordamida amalga oshirish mumkin:
A → B = ¬ A ∨ B, (\ Displaystyle A \ o'ng o'q B = \ neg A \ vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ Displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ xanjar (A \ vee \ neg B).)2) Formulalarga asoslangan individual o'zgaruvchan bayonotlarga asoslanib, inkor etish belgisini, butun ifodaga murojaat qilib, inkor qilish belgilari bilan almashtiring:
¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ Displaystyle \ neg (A \ vee B) = \ neg A \ takoz \ neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B. (\ Displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)3) Ikkita inkor qilish belgilaridan xalos bo'ling.
4) Agar kerak bo'lsa, konjunksiya va disjunksiya operatsiyalariga taqsimlanish xossalari va yutilish formulasini qo'llang.
CNF qurishga misol
Keling, CNF formulasini keltiraylik
F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ Displaystyle F = (X \ o'ng o'q Y) \ takoz ((\ neg Y \ o'ng o'q Z) \ o'ng o'q \ neg X).)Keling, formulani o'zgartiramiz F (\ Displaystyle F) o'z ichiga olmaydigan formulaga → (\ Displaystyle \ o'ng o'q):
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ Displaystyle F = (\ neg X \ vee Y) \ wedge (\ neg (\ neg Y \ rightarrow Z) \ vee \ neg X) = (\ neg X \ vee Y) \ wedge (\ neg (\ neg \ neg Y \ vee Z) \ vee \ neg X).)Olingan formulada biz inkorni o'zgaruvchilarga o'tkazamiz va ikkita negativni kamaytiramiz:
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\ Displaystyle F = (\ neg X \ vee Y) \ wedge ((\ neg Y \ wedge \ neg Z) \ vee \ neg X).)Masalan, 2-CNFda quyidagi formula yozilgan:
(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C). (\ Displaystyle (A \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)Oddiy birikma chaqirdi birikma bitta yoki bir nechta o'zgaruvchilar, da bu har biri o'zgaruvchan uchrashadi emas Ko'proq bitta marta (yoki o'zi, yoki u rad etish).
Masalan, oddiy birikma,
Aniq bo'lmagan normal shakl(DNF) chaqirdi ajralish oddiy birikmalar.
Masalan, ifoda DNF.
Zo'r tartibsiz normal shakl(SDNF) chaqirdi shunday tartibsiz normal shakl, da qaysi v har bir birikma kiritilgan hamma o'zgaruvchilar berilgan ro'yxat (yoki o'zlari, yoki ularning rad etishlar), bundan tashqari v bitta va tovush xuddi shuxop.
Masalan, ifoda DNF, lekin SDNF emas. Ifoda
SDNF hisoblanadi.Shunga o'xshash ta'riflar (konjunksiyani disjunksiya bilan almashtirish bilan va aksincha) CNF va SKNF uchun amal qiladi. Bu erda aniq formulalar.
Oddiy ajralish chaqirdi ajralish bitta yoki bir nechta o'zgaruvchilar, da bu har biri o'zgaruvchan kiradi emas Ko'proq bitta marta (yoki o'zi, yoki u rad etish) Masalan, ifoda oddiy disjunksiya,
Birlashtiruvchi normal shakl(CNF) chaqirdi birikma oddiy ajratish(masalan, ifoda CNF).
Zo'r kon'yunktiv normal shakl (SCNF) - bu har bir oddiy disjunksiya berilgan ro'yxatning barcha o'zgaruvchilarini (o'zlarini ham, inkorlarini ham) bir xil tartibda o'z ichiga olgan CNF.
Masalan, ifoda
bu SKNF.Bu erda bir shakldan boshqasiga o'tish algoritmlari keltirilgan. Tabiiyki, muayyan holatlarda (ma'lum bir ijodiy yondashuv bilan), algoritmlardan foydalanish, ma'lum bir shaklning o'ziga xos turidan foydalangan holda, oddiy o'zgarishlarga qaraganda, ko'proq mehnat talab qiladi:
a) DNFdan CNFga o'tish
Bu o'tish algoritmi quyidagicha: biz DNFdan ikkita inkorni qo'yamiz va de Morgan qoidalaridan foydalangan holda (yuqori inkorga tegmasdan) DNF inkorini DNFga qaytaramiz. Bunday holda, siz singdirish qoidasi (yoki Bleyk qoidasi) yordamida qavslarni ochishingiz kerak. Olingan DNFni inkor qilish (yuqori) (yana de Morgan qoidasiga ko'ra) bizga darhol CNF beradi:
E'tibor bering, agar biz chiqaradigan bo'lsak, CNFni dastlabki ifodadan ham olish mumkin da qavs tashqarisida;
b) CNFdan DNFga o'tish
Bu o'tish qavslarni oddiy ochish orqali amalga oshiriladi (bu holda, yana singdirish qoidasi ishlatiladi)
Shunday qilib, biz DNFga ega bo'ldik.
Teskari o'tish (SDNFdan DNFga) DNFni minimallashtirish muammosi bilan bog'liq. Bu Seksiyada batafsilroq muhokama qilinadi. 5, bu erda biz DNF (yoki SDNF) ni Bleyk qoidasiga muvofiq qanday soddalashtirishni ko'rsatamiz. Bu DNF deyiladi qisqartirilgan DNF;
v) DNF (yoki SDNF) ning qisqartmasi qoida Bleyk
Ushbu qoidani qo'llash ikki qismdan iborat:
Agar DNFda ajratilgan atamalar orasida atamalar bo'lsa
, keyin butun disjunksiyaga biz atamani qo'shamiz TO 1 TO 2018-05-01 xoxlasa buladi 121 2. Biz ushbu operatsiyani barcha mumkin bo'lgan juftliklar uchun bir necha marta (ketma -ket bo'lishi mumkin, bir vaqtning o'zida bo'lishi mumkin) bajaramiz, so'ngra biz odatdagi singdirishni qo'llaymiz;Agar qo'shilgan atama DNFda allaqachon mavjud bo'lsa, uni umuman bekor qilish mumkin, masalan.
yoki
Albatta, qisqartirilgan DNF o'ziga xos ta'rifga ega emas, lekin ularning hammasi bir xil harflarni o'z ichiga oladi (masalan, DNF bor)
, Bleyk qoidasini qo'llaganingizdan so'ng, siz unga teng keladigan DNFga kelishingiz mumkin):v) DNFdan SDNFga o'tish
Agar ba'zi oddiy birikmalarda o'zgaruvchi bo'lmasa, masalan: z, unga ifodani kiriting, so'ngra qavsni kengaytiring (bu holda biz takroriy ajratilgan atamalarni yozmaymiz). Masalan:
d) CNFdan SKNFga o'tish
Bu o'tish avvalgisiga o'xshash tarzda amalga oshiriladi: agar oddiy disjunksiyada biror o'zgaruvchi bo'lmasa (masalan, z, keyin biz unga ifoda qo'shamiz (bu disjunksiyaning o'zini o'zgartirmaydi), shundan so'ng tarqatish qonunidan foydalanib qavslarni kengaytiramiz):
Shunday qilib, SKNF CNFdan olinadi.
E'tibor bering, minimal yoki qisqartirilgan CNF odatda tegishli DNFdan olinadi.
Oddiy ajralish(inklyuziv disjunksiya) yoki ajratish(Inglizcha disjunct) - bu bir yoki bir nechta o'zgaruvchilarning disjunksiyasi yoki ularning inkorlari va har bir o'zgaruvchi bir martadan ko'p bo'lmaydi.
Oddiy ajralish
- to'liq agar har bir o'zgaruvchi (yoki uni inkor etish) unda aynan bir marta paydo bo'lsa;
- monoton agar u o'zgaruvchan negativlarni o'z ichiga olmasa.
Oddiy kon'yunktiv shakl, CNF(ing. kon'yunktiv normal shakl, CNF) normal shakl, bu erda boolean funktsiyasi bir nechta oddiy gaplarning birikmasi shakliga ega.
CNF misoli: $ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $
SKNF
Zo'r kon'yunktiv normal shakl, SKNF(mukammal kon'yunktiv normal shakl, PCNF) - bu quyidagi shartlarga javob beradigan CNF:
- u bir xil oddiy ajratishlarga ega emas
- har bir oddiy ajratish tugallangan
SKNF misoli:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $
Teorema: Har qanday uchun boolean funktsiyasi$ f (\ vec (x)) $, identifikatorga teng emas, uni belgilaydigan SKNF mavjud.
Isbot:$ \ Neg (f) (\ vec x) $ funktsiyasining teskarisi $ f (\ vec x) $ nolga teng bo'lgan birlashmalarga teng bo'lgani uchun $ \ neg (f) uchun SDNF. (\ vec x) $ ni quyidagicha yozish mumkin:
$ \ neg (f) (\ vec x) = \ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n) ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ x x (2) ^ (\ sigma_ (2)) \ takoz ... \ x_ x (n) ^ (\ sigma_ (n) ))) $, bu erda $ \ sigma_ (i) $, $ x_ (i) $ uchun rad etishning mavjudligini yoki yo'qligini bildiradi.
Keling, ifodaning chap va o'ng tomonlarining teskarisini topaylik:
$ f (\ vec x) = \ neg ({\ bigvee \ limits_ (f (x ^ (\ sigma_ (1))), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n) ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ x x (2) ^ (\ sigma_ (2)) \ takoz ... \ x_ x (n) ^ (\ sigma_ (n) $))))) $
O'ng tomonda olingan ifodaga de Morgan qoidasini ikki marta qo'llagan holda, biz quyidagilarni olamiz: $ f (\ vec x) = \ bigwedge \ limits_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ nuqta) , x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ nuqta \ vee \ neg (x_n ^ (\ sigma_n $))
Oxirgi ifoda - SKNF. SKNF bir xil nol bo'lmagan har qanday funktsiya uchun tuzilishi mumkin bo'lgan SDNF -dan olinganligi sababli, teorema isbotlangan.
Haqiqat jadvali bo'yicha SKNFni tuzish algoritmi
- Haqiqat jadvalida biz funktsiya qiymati $ 0 $ ga teng bo'lgan o'zgaruvchilar to'plamini belgilaymiz.
- Belgilangan har bir to'plam uchun biz barcha o'zgaruvchilarning disjunksiyasini quyidagi qoida bo'yicha yozamiz: agar ba'zi o'zgaruvchilar qiymati $ 0 $ bo'lsa, biz o'zgarmaydiganni disjunksiyaga kiritamiz, aks holda uni inkor qilamiz.
- Biz hosil bo'lgan barcha ajratishlarni birlashma operatsiyalari bilan bog'laymiz.
Median uchun SKNF tuzishga misol
1). Haqiqat jadvalida biz funktsiya qiymati $ 0 $ ga teng bo'lgan o'zgaruvchilar to'plamini belgilaymiz.
x y z $ \ langle x, y, z \ rangle $ 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 2). Har bir belgilangan to'plam uchun biz barcha o'zgaruvchilarning konjunksiyasini quyidagi qoidaga binoan yozamiz: agar ba'zi o'zgaruvchilar qiymati $ 0 $ bo'lsa, biz o'zgarmaydiganni disjunksiyaga kiritamiz, aks holda uni inkor qilamiz.
x y z $ \ langle x, y, z \ rangle $ 0 0 0 0 $ (x \ lor y \ lor z) $ 0 0 1 0 $ (x \ lor y \ lor \ neg (z)) $ 0 1 0 0 $ (x \ lor \ neg (y) \ lor z) $ 0 1 1 1 1 0 0 0 $ (\ neg (x) \ lor y \ lor z) $ 1 0 1 1 1 1 0 1 1 1 1 1 3). Biz hosil bo'lgan barcha ajratishlarni birlashma operatsiyalari bilan bog'laymiz.
$ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $
Ba'zi funktsiyalar uchun SKNF misollari
Pirs o'qi: $ x \ pastga y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) $
Eksklyuziv yoki: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $
Ta'rif 1.Birlashtiruvchi monomial (elementar birikma) o'zgaruvchilardan bu o'zgaruvchilarning birikmasi yoki ularning inkorlari deyiladi.
Masalan, Elementar birikma.
Ta'rif 2.Disjunktiv monomial (elementar disjunksiya) o'zgaruvchilardan bu o'zgaruvchilarning disjunksiyasi yoki ularni inkor qilish deyiladi.
Masalan, - elementar disjunksiya.
Ta'rif 3. Algebra elementar kon'yunktiv monomiyalarining ajratilishi bo'lgan, taklif qilingan algebra formulasiga teng bo'lgan formula deyiladi. disjunktiv normal shakl(DNF) ushbu formuladan.
Masalan,- DNF.
Ta'rif 4. Algebraning taklifli formulasiga teng va elementar ajratuvchi monomiallarning birikmasi bo'lgan formulaga deyiladi. Oddiy kon'yunktiv shakl Ushbu formulaning (CNF).
Masalan, - CNF.
Propozitsion algebraning har bir formulasi uchun birlashtiruvchi va kon'yunktiv normal shakllar to'plamini topish mumkin.
Oddiy shakllarni yaratish algoritmi
Mantiq algebrasining ekvivalentlarini ishlatib, formuladagi barcha amallarni asosiylari bilan almashtiring: konjunksiya, disjunksiya, inkor:
Ikki tomonlama rad etish belgilaridan xalos bo'ling.
Agar kerak bo'lsa, taqsimlanish xususiyatlarini va yutilish formulasini birlashtirish va ajratish operatsiyalariga qo'llang.
2.6. 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 fikrlar 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, DNF ga 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 etilishi 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, lekin agar o'zgaruvchi 1 qiymati bilan birikmaga kiritilgan bo'lsa, biz bu o'zgaruvchini yozamiz, agar qiymati 0 bo'lsa, uni inkor etish. Biz SDNF -ni olamiz.
Teorema 2. O'zgaruvchilarning bir xil bo'lmagan haqiqiy mantiqiy funktsiyasi SKNF -da va o'zgacha tarzda ifodalanishi mumkin.
SKNFni topish usullari
1 -yo'l- ekvivalent transformatsiyalar yordamida:
2 -chi yo'l- haqiqat jadvallari yordamida:
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 / =
Misol 2. Formulani DNF ga keltiring.
Yechim
Mantiqiy operatsiyalarni quyidagicha ifodalaymiz va:
= / biz inkorni o'zgaruvchilarga havola qilamiz va ikki tomonlama negativlarni 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 formulalar (oxirgi ustun) 1 qiymatini oladi. Har bir shunday 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 qatorlaridagi o'zgaruvchilar to'plamida oladi va shuning uchun istalgan mukammal disjunktiv normal shakl (SDNF) bo'ladi:
Misol 4. Formulani SKNFga ikki usulda 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, shuning uchun kerakli mukammal kon'yunktiv normal shakl (SCNF) bo'ladi:
Mustaqil hal qilish uchun savollar va topshiriqlar
1. Ekvivalent konvertatsiyadan foydalanib, formulalarni DNF ga keltiring:
2. Ekvivalent o'zgarishlardan foydalanib, formulalarni CNFga keltiring:
3. DNFni CNFga aylantirish uchun ikkinchi tarqatish qonunidan foydalaning:
a)
;4. Berilgan DNFlarni SDNFlarga aylantiring:
5. Berilgan CNFni SKNF ga aylantiring:
6. Berilgan mantiqiy formulalar uchun SDNF va SKNFni ikki usulda tuzing: ekvivalent transformatsiyalar yordamida va haqiqat jadvalidan foydalaning.
b)
;Propozitsion algebraning kon'yunktiv va kon'yunktiv normal shakllari. Fikrlar mantig'ining har bir funktsiyasi uchun siz haqiqat jadvalini tuzishingiz mumkin. Teskari muammo ham har doim hal qilinadi. Keling, bir nechta ta'riflarni keltiraylik.
Elementar birikmalar (birikmalar) o'zgaruvchilar konjunksiyalari yoki ularning inkorlari deyiladi, bunda har bir o'zgaruvchi eng ko'p uchraydi
bir marta.
Oddiy disjunktiv shakl(DNF) - bu elementar birikmalarning ajralishi shakliga ega bo'lgan formula.
Boshlang'ich jumlalar (bandlar) inkor qilingan yoki bo'lmagan holda o'zgaruvchilarning disjunksiyalari deyiladi.
Oddiy kon'yunktiv shakl(CNF) - bu elementar disjunksiyalar birikmasi shakliga ega bo'lgan formula.
Takliflar algebrasining har bir funktsiyasi uchun birlashtiruvchi va kon'yunktiv normal shakllar to'plamini topish mumkin.
DNF tuzish algoritmi:
1. Ekvivalent transformatsiyali formulalar yordamida mantiqiy operatsiyalarga o'ting.
2. Yaqin rad etiladigan formulalarga, ya'ni inkorlar o'zgaruvchilardan yuqori bo'lmagan formulaga o'ting - de Morgan qonunlarini qo'llang.
3. Qavslarni kengaytirish - taqsimot qonunlarini qo'llang.
4. Takroriy atamalarni bir marta oling - idempotentsiya qonuni.
5. Absorbsiya va yarim yutilish qonunlarini qo'llang.
Misol 6. DNF formulalarini toping:
Mantiqiy algebra ikkilik printsipi... Bu quyidagicha.
Funktsiya deyiladi ikki tomonlama agar funktsiyaga. Bular. berilgan funktsiyaga ikkilangan funktsiyani topish uchun argumentlarni inkor qilishdan funktsiyani inkor etishni qurish kerak.
Misol 7. To ikkilangan funktsiyani toping.
Mantiqiy algebraning elementar funktsiyalari orasida 1 - dual 0 ga va aksincha, x - x ga dual, dual, dual va aksincha.
Agar funktsiyani ifodalovchi F 1 formulasida barcha birikmalar almashtiriladi
disjunksiya, konjunksiya bo'yicha disjunksiya, 1 dan 0 gacha, 0 dan 1 gacha, keyin biz * dual funktsiyasini ifodalovchi F * formulasini olamiz.
Oddiy kon'yunktiv shakl (CNF) DNF uchun ikki tomonlama tushunchadir, shuning uchun uni sxema bo'yicha qurish oson:
Misol 8. CNF formulasini toping:
6 -misol natijasidan foydalanib, bizda
Mukammal kon'yunktiv va mukammal kon'yunktiv normal shakllar. Oddiy shakllarning har bir turida (kon'yunktiv va kon'yunktiv) SDNF va SKNF mukammal shakllar sinfini ajratish mumkin.
Barkamol elementar birikma - bu barcha o'zgaruvchilarning inkor qilingan yoki rad etilmagan mantiqiy mahsuloti va har bir o'zgaruvchi mahsulotda faqat bir marta paydo bo'ladi.
Har qanday DNFni barcha o'zgaruvchilar o'z ichiga olmaydigan birikmalarni ajratish orqali SDNF ga kamaytirish mumkin, ya'ni. etishmayotgan x i o'zgaruvchiga qo'shimcha taqsimot qonuni yordamida ko'paytiriladi
Misol 9. Misol DNF 6 uchun SDNF ni toping
Zo'r elementar disjunksiya inkor qilingan yoki rad etilmagan barcha o'zgaruvchilarning mantiqiy yig'indisidir va har bir o'zgaruvchi yig'indiga faqat bir marta kiritiladi.
Har qanday o'zgaruvchan X i kon'yunkturasini o'z ichiga olmaydigan birikma atamasini qo'shish va tarqatish qonunini qo'llash orqali har qanday CNFni SKNF ga kamaytirish mumkin.
Misol 10. CNFni SKNFga keltiring:
SKNFni yaratish uchun siz sxemadan foydalanishingiz mumkin
Misol 11. 6 -misoldagi formula uchun SKNF ni toping.
Har bir funktsiyada SDNF mavjud va bundan tashqari, u o'ziga xosdir. Har bir funktsiyada SKNF mavjud va bundan tashqari, yagona.
Chunki SDNF va SKNF formulalar bilan aniqlanadi, ular formulaning haqiqat jadvaliga muvofiq tuzilishi mumkin.
SDNFni qurish uchun F 1 qiymatini oladigan qatorlarni tanlash va ular uchun mukammal elementar birikmalarni yozish kerak. Agar haqiqat jadvalining kerakli qatoridagi o'zgaruvchining qiymati birga teng bo'lsa, unda mukammal kon'yunktda u inkor qilinmasdan, nol bo'lsa, inkor bilan olinadi. Keyin mukammal kon'yunktlar (ularning soni jadvaldagi sonlar soniga teng) disjunksiya belgilari bilan bog'lanadi.
SKNFni haqiqat jadvaliga muvofiq qurish uchun undagi chiziqlarni tanlash kerak, bu erda F = 0, va mukammal elementar disjunksiyalarni yozib, keyin ularni birikma belgilari bilan bog'lash kerak. Agar haqiqat jadvalining kerakli qatorida (F = 0) o'zgaruvchining qiymati nolga to'g'ri keladigan bo'lsa, u holda mukammal bandda u inkor qilinmasdan, agar bo'lsa - inkor bilan qabul qilinadi.
Misol 12. 6 -misoldagi formulaning haqiqat jadvalidan foydalanib, SDNF va SKNF ni toping.
14 -jadvalda faqat F = 10101101 ning yakuniy qiymati ko'rsatilgan. Kengaytirilgan haqiqat jadvalini tuzish orqali siz ushbu bayonotning to'g'riligiga o'zingiz ishonch hosil qilishingiz kerak.
14 -jadval
x y z
