Mantiqiy funktsiyaning konyunktiv normal shakli. Mantiqiy funksiyalarni ifodalashning konyunktiv shakllari
Har qanday mantiqiy formula uchun identifikatsiya o'zgarishlaridan foydalangan holda, unga teng keladigan cheksiz ko'p formulalarni qurish mumkin. Mantiq algebrasida asosiy vazifalardan biri kanonik shakllarni izlashdir (ya'ni, bitta qoida bo'yicha tuzilgan formulalar, kanon).
Agar mantiqiy funktsiya o'zgaruvchilarning diszyunksiyasi, konyunksiyasi va inkori orqali ifodalansa, u holda tasvirlashning bu shakli normal deyiladi.
Oddiy shakllar orasida mukammal normal shakllar ajralib turadi (funktsiyalar o'ziga xos tarzda yozilgan shakllar).
Mukammal disjunktiv normal shakl (PDNF)
Ta'rif. Agar formula ma’lum sonli o‘zgaruvchilar yoki ularning inkorlari qo‘shilishidan hosil bo‘lsa, elementar birikma deyiladi.
Misollar: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4
Ta'rif. Formula, agar u takrorlanmaydigan elementar birikmalarning dis'yunksiyasi bo'lsa, dis'yunktiv normal shakl (DNF) deb ataladi.
DNF quyidagi ko'rinishda yoziladi: F 1 ∨ F 2 ∨ ... ∨ F n , bu erda F i elementar birikma.
Misollar: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2
Ta'rif. K o'zgaruvchidagi mantiqiy formula mukammal dis'yunktiv normal shakl (PDNF) deb ataladi, agar:
1) formula DNF bo'lib, unda har bir elementar birikma k o'zgaruvchilarning x 1, x 2, ..., x k va bo'yicha birikmasidir. i-o'rin bu birikma yoki x i o'zgaruvchisi yoki uning inkori;
2) bunday DNFdagi barcha elementar qo‘shma gaplar juft-juft bo‘lib farqlanadi.
Misol: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)
Mukammal kon'yunktiv normal shakl (PCNF)
Ta'rif. Formula, agar u ma'lum miqdordagi o'zgaruvchilarning dis'yunksiyasi yoki ularning inkori natijasida hosil bo'lsa, elementar dis'yunksiya deyiladi.
Misollar: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3
Ta'rif. Formula, agar u takrorlanmaydigan elementar disjunksiyalarning birikmasi bo'lsa, kon'yunktiv normal shakl (CNF) deb ataladi.
CNF quyidagi ko'rinishda yoziladi: F 1 ∧ F 2 ∧ ... ∧ F n, bu erda F i elementar dis'yunksiya.
Misollar: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)
Ta'rif. K o'zgaruvchidagi mantiqiy formula mukammal kon'yunktiv normal shakl (CPNF) deb ataladi, agar:
1) formula CNF bo'lib, unda har bir elementar dis'yunksiya k o'zgaruvchilarning x 1, x 2, ..., x k dis'yunksiyasi bo'lib, bu dis'yunksiyaning i-o'rinida yo o'zgaruvchi x i yoki uning inkori joylashgan;
2) bunday CNFdagi barcha elementar disjunksiyalar juft-juft farqlanadi.
Misol: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)
e'tibor bering, bu 0 yoki 1 ga teng bo'lmagan har qanday mantiqiy funktsiya SDNF yoki SKNF sifatida ifodalanishi mumkin.
Haqiqat jadvali yordamida SDNF ni qurish algoritmi
- Funktsiya qiymati birga teng bo'lgan barcha jadval qatorlarini tanlang.
- Har bir shunday satr uchun barcha o'zgaruvchilarning birikmasini quyidagicha yozing: agar bu to'plamdagi ba'zi bir o'zgaruvchining qiymati 1 ga teng bo'lsa, u holda biz o'zgaruvchining o'zini birikmaga kiritamiz, aks holda uning inkori.
- Biz barcha hosil bo'lgan birikmalarni ajratish operatsiyalari bilan bog'laymiz.
Haqiqat jadvali yordamida SCNF ni qurish algoritmi
- Funktsiya qiymati nolga teng bo'lgan barcha jadval qatorlarini tanlang.
- Har bir shunday satr uchun barcha o'zgaruvchilarning diszyunksiyasini quyidagicha yozing: agar bu to'plamdagi ba'zi o'zgaruvchining qiymati 0 ga teng bo'lsa, u holda o'zgaruvchining o'zini konjunksiyaga kiritamiz, aks holda uning inkori.
- Biz barcha hosil bo'lgan ayirmalarni birikma amallari bilan bog'laymiz.
Algoritmlar tahlili shuni ko'rsatadiki, agar haqiqat jadvalining ko'pgina qatorlarida funksiya qiymati 0 ga teng bo'lsa, uning mantiqiy formulasini olish uchun SDNF ni, aks holda - SCNF ni qurish yaxshidir.
Misol: uchta o'zgaruvchining mantiqiy funksiyasining haqiqat jadvali berilgan. Ushbu funktsiyani amalga oshiradigan mantiqiy formulani tuzing.
| x | y | z | F(x, y, z) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Chunki Haqiqat jadvalining ko'p satrlarida funksiya qiymati 1 ga teng, keyin biz SCNF ni tuzamiz. Natijada biz quyidagi mantiqiy formulani olamiz:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)
Olingan formulani tekshiramiz. Buning uchun funksiyaning haqiqat jadvalini tuzamiz.
| x | y | z | ¬x | ¬ x ∨ y ∨ z | ¬z | ¬ x ∨ y ∨ ¬ z | F(x, y, z) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
Asl haqiqat jadvali va mantiqiy formula uchun tuzilgan jadvalni taqqoslab, biz funktsiya qiymatlari ustunlari mos kelishini ta'kidlaymiz. Bu mantiqiy funktsiya to'g'ri tuzilganligini bildiradi.
Elementar diszyunksiya tushunchasini kiritamiz.
Elementar dis'yunksiya shaklning ifodasidir
Mantiqiy funktsiyaning kon'yunktiv normal shakli (KNF) har qanday chekli juftlik bilan ajralib turadigan elementar disjunksiyalarning birikmasidir. Masalan, mantiqiy funktsiyalar
elementar ayirmalarning qo‘shma gaplarini ifodalaydi. Shuning uchun ular konyunktiv normal shaklda yoziladi.
Analitik ifoda bilan aniqlangan ixtiyoriy mantiqiy funktsiyani quyidagi amallarni bajarish orqali CNF ga qisqartirish mumkin:
Agar mantiqiy ifodaga inkor amali qo'llanilsa, inversiya qoidasidan foydalanish;
Ko'paytirishga nisbatan distributivlik aksiomasidan foydalanish:
Absorbsiya operatsiyasidan foydalanish:
Takroriy o'zgaruvchilarning dis'yunktsiyalari yoki ularning inkorlaridagi istisnolar;
Bittasidan tashqari barcha bir xil elementar disjunksiyalarni olib tashlash;
Bir vaqtning o'zida o'zgaruvchini va uning inkorini o'z ichiga olgan barcha disjunctionlarni olib tashlash.
Sanab o'tilgan amallarning haqiqiyligi mantiq algebrasining asosiy aksiomalari va bir xil munosabatlaridan kelib chiqadi.
Konyunktiv normal shakl, agar unga kiritilgan har bir elementar dis'yunksiya to'g'ridan-to'g'ri yoki teskari shaklda funktsiya bog'liq bo'lgan barcha o'zgaruvchilarni o'z ichiga olsa, mukammal deyiladi.
CNF ni mukammal CNF ga aylantirish quyidagi operatsiyalarni bajarish orqali amalga oshiriladi:
O‘zgaruvchilar qo‘shma gaplarining har bir elementar diszyunksiyasiga qo‘shimchalar va ularning inkorlari, agar ular ushbu elementar diszyunksiyaga kiritilmagan bo‘lsa;
Tarqatish aksiomasidan foydalanish;
Bittasidan tashqari barcha bir xil elementar disjunksiyalarni olib tashlash.
Mukammal CNFda har qanday mantiqiy funktsiyadan tashqari ifodalanishi mumkin
bir xil () ga teng. Mukammal CNFning o'ziga xos xususiyati shundaki, undagi mantiqiy funktsiyaning tasviri noyobdir.
Mukammal CNF funktsiyasiga kiritilgan elementar disjunksiyalar nol tarkibiy qismlar deb ataladi. Mukammal CNF tarkibiga kiritilgan har bir nol tarkibiy qism funktsiyaning nol to'plami bo'lgan yagona o'zgaruvchan qiymatlar to'plamida yo'qoladi. Shunday qilib, mantiqiy funktsiyaning nol to'plamlari soni uning mukammal CNF tarkibiga kiritilgan nol tarkibiy qismlar soniga to'g'ri keladi.
Mukammal CNFda nolning mantiqiy funktsiya konstantasi nolning 2n tashkil etuvchi birikmasi bilan ifodalanadi. Keling, muvofiqlik jadvali yordamida mantiqiy funktsiyaning SCNF ni kompilyatsiya qilish qoidasini tuzamiz.
Funktsiya nolga teng bo'lgan yozishmalar jadvalining har bir qatori uchun barcha o'zgaruvchilarning elementar dis'yunktsiyasi tuziladi. Bunday holda, agar uning qiymati nolga teng bo'lsa, dis'yunksiya o'zgaruvchining o'zini yoki qiymati birga teng bo'lsa, inkorni o'z ichiga oladi. Hosil boʻlgan elementar ayirma gaplar bogʻlovchi belgisi bilan birikadi.
3.4-misol. 2.2 muvofiqlik jadvalida berilgan z(x) mantiqiy funksiyasi uchun mukammal konyunktiv shaklni aniqlaymiz.
000 funktsiyaning nol to'plamiga mos keladigan jadvalning birinchi qatori uchun biz nolning tarkibiy qismini topamiz. Ikkinchi, uchinchi va beshinchi qatorlar uchun shunga o'xshash operatsiyalarni bajarib, biz kerakli mukammal CNF funktsiyasini aniqlaymiz:
Shuni ta'kidlash kerakki, birlik to'plamlari soni nol to'plamlar sonidan ortiq bo'lgan funktsiyalar uchun ularni SCNF ko'rinishida va aksincha yozish ancha ixchamdir.
Ta'rif 1.Konyunktiv monomial (elementar birikma) o'zgaruvchilarning o'zgaruvchilari - bu o'zgaruvchilarning birikmasi yoki ularning inkorlari.
Masalan, elementar bog‘lovchidir.
Ta'rif 2.Dizyunktiv monomial (elementar dis'yunksiya) o'zgaruvchilardan - bu o'zgaruvchilarning diszyunksiyasi yoki ularning inkorlari.
Masalan, elementar disjunksiyadir.
Ta'rif 3. Berilgan taklif algebra formulasiga ekvivalent va elementar kon'yunktiv monomiyalarning dis'yunksiyasi bo'lgan formula deyiladi. disjunktiv normal shakl(DNF) ushbu formuladan.
Masalan,- DNF.
Ta'rif 4. Berilgan taklif algebra formulasiga ekvivalent va elementar ayiruvchi monomiyalarning birikmasi bo'lgan formula deyiladi. konyunktiv normal shakl(CNF) ushbu formuladan.
Masalan, – KNF.
Har bir taklif algebra formulasi uchun disjunktiv va kon'yunktiv normal shakllar to'plamini topish mumkin.
Oddiy shakllarni qurish algoritmi
Mantiqiy algebra ekvivalentlaridan foydalanib, formuladagi barcha asosiy amallarni almashtiring: konyunksiya, disjunksiya, inkor:
Ikki tomonlama salbiylardan xalos bo'ling.
Agar kerak bo'lsa, kon'yunksiya va dis'yunksiya amallariga distributivlik va yutilish formulalarining xossalarini qo'llang.
2.6. Mukammal ayiruvchi va mukammal konyunktiv normal shakllar
Har qanday mantiqiy funktsiya DNF va CNF ko'rinishida ko'plab tasvirlarga ega bo'lishi mumkin. Bu tasvirlar orasida alohida o'rinni mukammal DNF (SDNF) va mukammal CNF (SCNF) egallaydi.
Ta'rif 1. Mukammal disjunktiv normal shakl(SDNF) DNF bo'lib, unda har bir kon'yunktiv monomial to'plamdagi har bir o'zgaruvchini aynan bir marta o'z ichiga oladi, yoki uning o'zi yoki inkori.
Strukturaviy ravishda, DNF ga qisqartirilgan har bir taklif algebra formulasi uchun SDNF quyidagicha aniqlanishi mumkin:
Ta'rif 2. Mukammal disjunktiv normal shakl Taklifli algebra formulasining (SDNF) quyidagi xususiyatlarga ega bo'lgan DNF deb ataladi:
Ta'rif 3. Mukammal kon'yunktiv normal shakl(SCNF) CNF bo'lib, unda har bir ajratuvchi monomial to'plamdagi har bir o'zgaruvchini aynan bir marta o'z ichiga oladi va o'zi yoki uning inkori paydo bo'ladi.
Strukturaviy ravishda, CNF ga qisqartirilgan har bir taklif algebra formulasi uchun SCNF quyidagicha aniqlanishi mumkin.
Ta'rif 4. Mukammal kon'yunktiv normal shakl Berilgan taklif algebra formulasining (SCNF) quyidagi xossalarni qanoatlantiradigan CNF deyiladi.
Teorema 1. Bir xil noto'g'ri bo'lmagan o'zgaruvchilarning har bir mantiqiy funktsiyasi SDNFda va o'ziga xos tarzda taqdim etilishi mumkin.
SDNF ni topish usullari
1-usul
2-usul
formula 1 qiymatini oladigan qatorlarni tanlang;
Agar o‘zgaruvchi 1 qiymati bilan birikmaga kiritilgan bo‘lsa, u holda bu o‘zgaruvchini yozamiz, agar qiymat 0 bo‘lsa, uni inkor qilish sharti bilan bog‘lovchilar diszyunksiyasini tuzamiz. Biz SDNFni olamiz.
Teorema 2. Bir xil to'g'ri bo'lmagan o'zgaruvchilarning har bir mantiqiy funktsiyasi SCNFda va o'ziga xos tarzda ifodalanishi mumkin.
SCNFni topish usullari
1-usul- ekvivalent transformatsiyalardan foydalanish:
2-usul- haqiqat jadvallaridan foydalanish:
formula 0 qiymatini oladigan qatorlarni tanlang;
Agar o'zgaruvchi 0 qiymati bilan dis'yunksiyaga kiritilgan bo'lsa, u holda bu o'zgaruvchini yozamiz, agar qiymat 1 bo'lsa, u holda uni inkor qilish sharti bilan dis'yunktsiyalar birikmasini tuzamiz. Biz SKNFni olamiz.
1-misol. CNF funksiyalarini tuzing.
Yechim
O'zgaruvchilarni o'zgartirish qonunlaridan foydalangan holda "" bog'lovchisini yo'q qilaylik:
= /de Morgan qonunlari va ikkilamchi inkor/ =
/distributiv qonunlar/ =
2-misol. Formulani DNFga bering.
Yechim
Mantiqiy amallarni va yordamida ifodalaymiz:
= /inkorni o'zgaruvchilar sifatida tasniflaymiz va qo'sh salbiyni kamaytiramiz/ =
= /tarqatilish qonuni/ .
3-misol. Formulani DNF va SDNF da yozing.
Yechim
Mantiq qonunlaridan foydalanib, biz ushbu formulani faqat elementar birikmalarning disjunksiyalarini o'z ichiga olgan shaklga keltiramiz. Olingan formula kerakli DNF bo'ladi:
SDNF ni qurish uchun ushbu formula uchun haqiqat jadvalini tuzamiz:
Biz jadvalning formulasi (oxirgi ustun) 1 qiymatini oladigan qatorlarni belgilaymiz. Har bir bunday qator uchun biz ushbu qatorning o'zgaruvchilar to'plamida to'g'ri bo'lgan formulani yozamiz:
1-qator: ;
3-qator: ;
5-qator: .
Ushbu uchta formulani ajratish faqat 1, 3, 5-qatorlardagi o'zgaruvchilar to'plamida 1 qiymatini oladi va shuning uchun kerakli mukammal dis'yunktiv normal shakl (PDNF) bo'ladi:
4-misol. Formulani SKNFga ikki usulda keltiring:
a) ekvivalent transformatsiyalar yordamida;
b) haqiqat jadvalidan foydalanish.
Yechim:
Ikkinchi elementar disjunksiyani o'zgartiramiz:
Formula quyidagicha ko'rinadi:
b) ushbu formula uchun haqiqat jadvalini tuzing:
Biz jadvalning formulasi (oxirgi ustun) 0 qiymatini oladigan qatorlarni belgilaymiz. Har bir bunday satr uchun biz ushbu qatorning o'zgaruvchilar to'plamida to'g'ri bo'lgan formulani yozamiz:
2-qator: ;
6-qator: .
Ushbu ikkita formulaning birikmasi faqat 2 va 6-qatorlardagi o'zgaruvchilar to'plamida 0 qiymatini oladi va shuning uchun kerakli mukammal kon'yunktiv normal shakl (PCNF) bo'ladi:
Mustaqil hal qilish uchun savollar va vazifalar
1. Ekvivalent transformatsiyalardan foydalanib, formulalarni DNF ga kamaytiring:
2. Ekvivalent transformatsiyalardan foydalanib, formulalarni CNF ga keltiring:
3. Ikkinchi taqsimot qonunidan foydalanib, DNF ni CNF ga aylantiring:
A) 
;
4. Berilgan DNF larni SDNF ga aylantiring:
5. Berilgan CNF ni SCNF ga aylantiring:
6. Berilgan mantiqiy formulalar uchun SDNF va SCNF ni ikki usulda tuzing: ekvivalent transformatsiyalar yordamida va haqiqat jadvalidan foydalanish.
b) 
;
Oddiy shakl mantiqiy formulada elementar bo'lmagan formulalarning implikatsiya, ekvivalentlik va inkor belgilari mavjud emas.
Oddiy shakl ikki shaklda bo'ladi:
kon'yunktiv normal shakl (CNF)-- bir nechta ayirmalarning birikmasi, masalan, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;
disjunktiv normal shakl (DNF)-- bir nechta birikmalarning diszyunksiyasi, masalan, $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.
SKNF
Mukammal kon'yunktiv normal shakl (PCNF) uchta shartni qondiradigan CNF hisoblanadi:
bir xil elementar disjunksiyalarni o'z ichiga olmaydi;
disjunksiyalarning hech birida bir xil o'zgaruvchilar mavjud emas;
Har bir elementar disjunksiya ma'lum bir CNFga kiritilgan har bir o'zgaruvchini o'z ichiga oladi.
Bir xil to'g'ri bo'lmagan har qanday mantiqiy formulani SKNFda ko'rsatish mumkin.
Haqiqat jadvali yordamida SKNFni qurish qoidalari
Funktsiya 0 ga teng bo'lgan har bir o'zgaruvchilar to'plami uchun yig'indi yoziladi va 1 qiymatiga ega bo'lgan o'zgaruvchilar inkor bilan olinadi.
SDNF
Mukammal disjunktiv normal shakl (PDNF) Bu uchta shartni qondiradigan DNF:
bir xil elementar qo‘shma gaplarni o‘z ichiga olmaydi;
qo‘shma gaplarning hech birida bir xil o‘zgaruvchilar mavjud emas;
Har bir elementar birikma ma'lum bir DNF tarkibiga kiritilgan har bir o'zgaruvchini va bir xil tartibda o'z ichiga oladi.
Bir xil noto'g'ri bo'lmagan har qanday mantiqiy formula SDNFda va o'ziga xos tarzda taqdim etilishi mumkin.
Haqiqat jadvali yordamida SDNF qurish qoidalari
Funktsiya 1 ga teng bo'lgan har bir o'zgaruvchilar to'plami uchun mahsulot yoziladi va 0 qiymatiga ega bo'lgan o'zgaruvchilar inkor bilan olinadi.
SCNF va SDNF ni topishga misollar
1-misol
Haqiqat jadvalidan foydalanib mantiqiy funktsiyani yozing:
1-rasm.
Yechim:
SDNF ni yaratish qoidasidan foydalanamiz:
2-rasm.
Biz SDNFni olamiz:
SCNF ni qurish qoidasidan foydalanamiz.
Standart asos. Elementar formulalar harflardir. Elementar qo‘shma gap (dizyunksiya). Dizyunktiv (konyunktiv) normal shakl va mukammal shakl. Teorema: 0 dan (1 dan) farq qiladigan har qanday mantiqiy funktsiya SDNF (SCNF) ko'rinishida ifodalanishi mumkin. Standart asosning to'liqligi. To'liq asoslarga misollar: Zhegalkin asosi, Schaeffer zarbasi, Peirce o'qi.
Standart asos mantiqiy algebraning uchta asosiy amallari to'plamidir: qo'shish (birlashma), ko'paytirish (kesish) va inkor qilish.
Mana biz qo'ng'iroq qilamiz tom ma'noda x o'zgaruvchisi yoki uning inkori x va xˆni belgilang. Turli o'zgaruvchilar bilan aniqlangan bir nechta literallarning mantiqiy kesishishi, ya'ni. X = xˆ 1 xˆ 2 ko'rinishining ifodasi. . . xˆ l, deyiladi elementar birikma . Barcha o'zgaruvchilarning har xil bo'lishi talabi quyidagilar bilan belgilanadi. Agar bog‘lovchi bir nechta bir xil harflarni o‘z ichiga olsa, u holda qo‘shma gapning almashinuvchanligi, assotsiativligi va idempotentligi tufayli ekvivalent formulaga o‘tib, faqat bitta harf qoldirish mumkin (masalan, x 1 x 1 = x 1). Agar birikma o'zgaruvchini va uning inkorini o'z ichiga olsa, u holda formula 0 doimiyga ekvivalent bo'ladi, chunki x x = 0 va har qanday Y formula uchun bizda Y x x = 0 bo'ladi.
Bir nechta elementar birikmalarning diszyunksiyasi deyiladi disjunktiv normal shakl , yoki DNF . Masalan,
x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5.
Agar berilgan DNF ning har bir elementar birikmasidagi o‘zgaruvchilar tarkibi bir xil bo‘lsa, DNF deyiladi. mukammal . Berilgan misol mukammal bo'lmagan DNF. Aksincha, formula
x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4
mukammal shakl mavjud.
Mantiqiy algebrada qoʻshish va koʻpaytirish nosimmetrik amallar boʻlib, siz har doim qoʻshishni koʻpaytirish, koʻpaytirishni esa qoʻshish sifatida talqin qilishingiz mumkin boʻlganligi sababli, ikki tomonlama tushuncha mavjud - konyunktiv normal shakl (KNF ), elementar ayirmalarning bog‘lovchisi va mukammal qo‘shma gap shakli (SKNF ). Simmetrik yarim halqalar uchun ikkilik printsipidan kelib chiqadiki, DNF bilan bog'liq har qanday bayonotga CNF bo'yicha qo'shilish (ajralish) ni ko'paytirish, ko'paytirish (konjunksiya) ni qo'shish, doimiy 0 ni doimiy 1, doimiy bilan almashtirish orqali olinadi. 1 doimiy 0 bilan, tartib munosabati ikkilik (teskari) bilan. Shuning uchun, bundan keyin biz faqat DNFni o'rganishga e'tibor qaratamiz.
1.4 teorema. Doimiy 0 dan boshqa har qanday mantiqiy funksiya SDNF sifatida ifodalanishi mumkin.
◀X s deganda s = 1 boʻlsa x formulasini, s = 0 boʻlsa x formulasini tushunamiz. 1, .., t n) (bunday vektor deyiladi tarkibiy birlik ). Keyin elementar birikma ham ushbu to'plamda 1 qiymatini oladi, lekin boshqa barcha n o'lchovli Boolean vektorlarida yo'qoladi. Formulani ko'rib chiqing
bunda yig'indisi (birlashmasi) berilgan funksiya 1 qiymatini oladigan argument qiymatlarining barcha to'plamlariga (t 1, . . . ., t n) tarqaladi. E'tibor bering, bunday to'plamlar to'plami bo'sh emas, shuning uchun sum kamida bitta atamani o'z ichiga oladi.
Ko'rib chiqilayotgan funktsiya 1 ga aylanadigan o'zgaruvchilarning qiymatlari uchun PH formulasi 1 ga aylanishini ko'rish oson. Demak, r formula f funksiyani ifodalaydi.
Xulosa 1.1. Standart asos to'liq.
◀ Haqiqatan ham, agar funktsiya doimiy 0 bo'lmasa, u standart asosda formula bo'lgan SDNF ko'rinishida ifodalanishi mumkin. Doimiy 0 ni, masalan, f(x 1, x 2, . . , x n) = x 1 x 1 formulasi bilan ifodalash mumkin.
1.2-misol. m(x 1, x 2, x 3) uchta o‘zgaruvchili funksiyani ko‘rib chiqaylik (1.4-jadval), deyiladi. majoritar funktsiya ̆. Agar uning argumentlarining yarmidan ko'pi 1 qiymatiga ega bo'lsa, bu funktsiya 1 ga baholanadi. Shuning uchun u ko'pincha ovoz berish funktsiyasi deb ataladi. Buning uchun SDNF quramiz.
Standart asosning to'liqligi boshqa to'liq funktsiyalar tizimlarini tanlash imkonini beradi. F to'plamining to'liqligini quyidagi fikrlardan aniqlash mumkin. Faraz qilaylik, uchta standart avtobus funksiyalarining har biri F dan yuqori formula bilan ifodalanishi mumkin. Keyin, 1.3-teorema bo'yicha, F o'ziga xosligi to'liq bo'ladi.
1.3-misol. 2 qo'shish, ko'paytirish va doimiy 1 moduli operatsiyalari to'plami deyiladi Jegalkin asosi . 2-modul qoʻshish va koʻpaytirish Z2 halqasining asosiy amallari boʻlib, ular yordamida tuzilgan ifodalar Z2 halqasi ustidagi koʻphadlardir. Bu holda 1 doimiysi erkin terminni yozish uchun zarur. Xx = x bo'lgani uchun, ko'phaddagi barcha omillar 1 darajaga ega. Shuning uchun ko'phadni yozishda siz daraja tushunchasisiz ham qilishingiz mumkin. Jegalkin asosidagi formulalarga misollar:
xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.
Har qanday bunday formulalar Jegalkin ko'phadli deb ataladi. Aslida, Jegalkin ko'phad Z2 halqasi ustidagi ko'phaddir.
Standart asosni qo'shish va inkor qilish operatsiyalarini ifodalovchi Jegalkin asosi bo'yicha formulalarni qurish qiyin emas (ikki asosni ko'paytirish keng tarqalgan):
x+y=x⊕y⊕xy, x =x⊕1.
Shuning uchun, Zhegalkin asosi to'liq to'plamdir.
Ko'rsatish mumkinki, har qanday mantiqiy funktsiya uchun Jegalkin polinomi yagona aniqlangan
(aniqrog'i, shartlar tartibiga qadar). Kam sonli o'zgaruvchilarga ega bo'lgan Jegalkin ko'phadining koeffitsientlarini noaniq koeffitsientlar usuli yordamida topish mumkin.
1.4-misol. Keling, bitta funktsiya to'plamini ko'rib chiqaylik - Schaeffer zarbasi*. Bu toʻplam quyidagi oson tekshiriladigan identifikatorlardan kelib chiqqan holda toʻliqdir:
x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).
1.5-misol. Bitta funktsiyadan tashkil topgan asos, Peirce o'qi ham to'liq. Buning uchun test Schaeffer zarbasi holatiga o'xshaydi. Biroq, bu xulosa nosimmetrik yarim halqalar uchun ikkilik printsipi asosida ham amalga oshirilishi mumkin.
*Sxeffer zarbasi ikkilik, lekin assotsiativ emas. Shuning uchun, infix shaklidan foydalanganda ehtiyot bo'lishingiz kerak: natija operatsiyalar tartibiga bog'liq. Bunday holda, qavslar yordamida operatsiyalar tartibini aniq ko'rsatish tavsiya etiladi, masalan, (x | y) | z, x | emas y | z, garchi ikkala shakl ham ekvivalent.
