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.
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) 
;
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 bajarish orqali CNF ga qisqartirish mumkin. keyingi operatsiyalar:
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. O'ziga xos xususiyat Mukammal CNF - bu mantiqiy funktsiyaning undagi 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, kompilyatsiya qilish qoidasini tuzamiz SKNF mantiqiy yozishmalar jadvaliga muvofiq vazifalarni bajaradi.
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.
Misol. CNF formulalarini toping 
~ 
~
SDNF ning mukammal disjunktiv normal shakli quyidagi algoritm yordamida tuzilishi mumkin:
1. = 1. DNF algoritmi
2. = 2. DNF algoritmi
3. = 3. DNF algoritmi
4. = 4. DNF algoritmi
5. Xuddi shunday noto'g'ri atamalarni, ya'ni shakl shartlarini tashlab qo'ying
6. Qolgan shartlarni etishmayotgan oʻzgaruvchilar bilan toʻldiring
7. 4-bandni takrorlang.
Misol. SDNF formulalarini toping.
~
SCNF ni qurish uchun siz quyidagi sxemadan foydalanishingiz mumkin:
Misol. SDNF formulalarini toping.
~
Ma'lumki (2.11, 2.12 teoremalar) SDNF va SCNF formula bilan yagona aniqlangan va shuning uchun ularni formulaning haqiqat jadvali yordamida qurish mumkin.
Haqiqat jadvali bo'yicha SDNF va SCNF ni qurish sxemasi formula uchun quyida keltirilgan. ~ :
 ~
| ||||
| 1 0 1 0 1 1 0 1 | SDNF; SKNF. |
2.2. Mashq qilish.
2.2.1 Quyida mantiqiy ifodalar keltirilgan. Bul mantiq qonunlaridan foydalanib variantingizning ifodalarini iloji boricha soddalashtiring. Keyin soddalashtirilgan ifodani asl ifoda bilan solishtirish uchun haqiqat jadvallaridan foydalaning.
2.2.2. f 1 va f 2 ning ekvivalentligi haqidagi savolni ularni SDNF ga kamaytirish orqali aniqlang (1-jadval).
2.2.3. Umumlashtirilgan va mantiqiy prinsipdan foydalanib f 3 uchun qo‘sh funksiyani toping (1-jadval). Natijalarni solishtiring.
| № | f 1 | f 2 | f 3 |
 | |||
 |
|||
 | |||
 | |||
 | |||
 |  |
||
 |  |
||
 |
|||
 | |||
 | |||
 |
|||
 | |||
 |  |
||
 | |||
 |
2.3. Nazorat savollari.
2.3.1. Bayonotni aniqlang.
2.3.2. Bayonotdagi asosiy operatsiyalarni sanab o'ting.
2.3.3. Haqiqat jadvali nima?
2.3.4. Quyidagi formulalar uchun haqiqat jadvallarini tuzing:
~ ~ 
~ ;
2.3.5. Amaliyotlarni bajarish tartibi to'g'risidagi konventsiyalarni hisobga olgan holda, formulalardagi "qo'shimcha" qavslar va "" belgisini tashlamang:
;
2.3.6. Ekvivalent o'zgarishlardan foydalanib, formulalarning bir xil haqiqatini isbotlang:
2.3.7. Ikkilamchi formulalarni toping:
)
2.3.8. Quyidagi formulalarni mukammal DNF (SDNF) shakliga qisqartiring:
~
2.3.9. Quyidagi formulalarni mukammal CNF (SCNF) shakliga qisqartiring:
~
Mavzu:“Mantiqiy funksiyalarni minimallashtirish. Mantiq"
Maqsad: Mantiqiy funktsiyalarni minimallashtirish usullari bilan ishlash bo'yicha amaliy ko'nikmalarga ega bo'lish.
3.1. Nazariy ma'lumotlar.
Minimal shakllar
Ko'rsatilgandek, har qanday mantiqiy funktsiya mukammal normal shaklda (dizyunktiv yoki kon'yunktiv) ifodalanishi mumkin. Bundan tashqari, bunday tasvir funksiyaning jadvalli spetsifikatsiyasidan uning analitik ifodasiga o‘tishdagi birinchi qadamdir. Kelgusida biz ayirma shakldan chiqamiz va qo'shma shakl uchun mos keladigan natijalar ikkilik printsipi asosida olinadi.
Mantiqiy sxemalarni mantiqiy asosda sintez qilishning kanonik muammosi Boolean funktsiyalarini minimallashtirishga to'g'ri keladi, ya'ni. ularni eng kichik harflar sonini (o'zgaruvchilar va ularning inkorlari) o'z ichiga olgan disjunktiv normal shaklda ifodalash. Bunday shakllar minimal deb ataladi. Kanonik sintezda ikkala signal va ularning inversiyalari kontaktlarning zanglashiga olib kirishlari bilan ta'minlanadi deb taxmin qilinadi.
Dis'yunktiv normal shaklda keltirilgan formula yopishtirish va singdirish operatsiyasini takroran qo'llash orqali soddalashtirilgan va (kon'yunktiv normal shakl uchun ikki xil identifikatsiyalar shaklga ega: va ). Bu erda va har qanday Boolean algebra formulasi sifatida tushunish mumkin. Natijada, biz analitik ifodaga kelamiz, unda keyingi o'zgarishlar endi mumkin emas, ya'ni. biz o'lik shaklni olamiz.
O'lik shakllar orasida minimal ajratuvchi shakl ham mavjud va u yagona bo'lmasligi mumkin. Berilgan o'lik shakl minimal ekanligiga ishonch hosil qilish uchun siz barcha o'lik shakllarni topib, ularni o'z ichiga olgan harflar soni bo'yicha taqqoslashingiz kerak.
Masalan, funktsiya mukammal normal dis'yunktiv shaklda berilsin:
Shartlarni guruhlash va yopishtirish operatsiyasini qo'llash bizda .
Boshqa guruhlash usuli bilan biz quyidagilarni olamiz:
Ikkala o'lik shakl ham minimal emas. Minimal shaklni olish uchun siz asl formulada bitta atamani takrorlashni taxmin qilishingiz kerak (bu har doim ham amalga oshirilishi mumkin, chunki ). Birinchi holda, bunday a'zo bo'lishi mumkin. Keyin. Atamani qo'shish orqali biz quyidagilarni olamiz: . Hamma narsani boshdan kechirgan mumkin bo'lgan variantlar, oxirgi ikki shakl minimal ekanligini tekshirishimiz mumkin.
Bu darajadagi formulalar bilan ishlash zulmatda kezishga o'xshaydi. Agar siz ushbu maqsad uchun maxsus ishlab chiqilgan ba'zi grafik va analitik tasvirlar va belgilardan foydalansangiz, minimal shakllarni qidirish jarayoni yanada vizual va maqsadli bo'ladi.
Ko'p o'lchovli kub
O'lchovli kubning har bir cho'qqisi birlikning tarkibiy qismi bilan bog'lanishi mumkin. Demak, belgilangan cho'qqilarning kichik to'plami o'zgaruvchilarning mantiqiy funksiyasining -o'lchovli kubi bo'yicha mukammal dis'yunktiv normal shakldagi xaritalashdir. Shaklda. 3.1-bandda 3.7-banddagi funksiya uchun bunday xaritalash ko'rsatilgan.
3.1-rasm SDNF da taqdim etilgan funksiyaning uch o lchamli kubda ko rinishi
Har qanday disjunktiv normal shaklda taqdim etilgan o'zgaruvchilar funktsiyasini ko'rsatish uchun uning minitermlari va -o'lchovli kub elementlari o'rtasida muvofiqlikni o'rnatish kerak.
(-1) darajali minitermni ikkita minitermni (birlikni tashkil etuvchi) bir-biriga yopishtirish natijasi deb hisoblash mumkin, ya'ni. 
, -o'lchovli kubda bu faqat bu uchlarni chekka bilan bog'laydigan koordinata qiymatlarida farq qiluvchi ikkita cho'qqini almashtirishga to'g'ri keladi (qirra unga tushadigan cho'qqilarni qoplashi aytiladi). Shunday qilib, (-1)-tartibli minitermlar -o'lchovli kubning qirralariga mos keladi. Xuddi shunday, (-2)-tartibdagi minitermlarning mosligi - o'lchovli kubning yuzlari bilan o'rnatiladi, ularning har biri to'rtta uchini (va to'rtta chetini) qoplaydi.
-o'lchovli kubning o'lchamlari bilan tavsiflangan elementlari -kublar deyiladi. Shunday qilib, uchlari 0 kub, qirralari 1 kub, yuzlar 2 kub va hokazo. Yuqoridagi mulohazalarni umumlashtirgan holda, biz o'zgaruvchilar funktsiyasi uchun dis'yunktiv normal shaklda ()-chi darajali minitermni -kub bilan ifodalanadi va har bir kub o'z bilan bog'liq bo'lgan pastki o'lchamdagi barcha kublarni qamrab oladi deb taxmin qilishimiz mumkin. uchlari. Misol sifatida rasmda. 3.2 uchta o'zgaruvchining funktsiyasini ko'rsatadi. Bu erda minitermlar 1 kub () ga to'g'ri keladi va miniterm 2 kub () bilan ifodalanadi.
Fig.3.2 Funktsiyani qamrab olish 
Demak, har qanday disjunktiv normal shakl birlik tarkibiy qismlariga (0-kublar) mos keladigan barcha uchlarini qamrab oluvchi -kublar to'plami orqali -o'lchovli kubga tasvirlangan. Qarama-qarshi gap ham to'g'ri: agar -kublarning ma'lum bir to'plami funktsiyaning birlik qiymatlariga mos keladigan barcha cho'qqilar to'plamini qamrab olsa, u holda bu kublarga mos keladigan minitermlarning dis'yunksiyasi bu funktsiyaning dis'yunktiv normaldagi ifodasidir. shakl. -kublarning bunday to'plami (yoki ularga mos keladigan minitermlar) funktsiyaning qoplamasini tashkil qiladi.
Minimal shaklga bo'lgan xohish intuitiv ravishda bunday qoplamani qidirish sifatida tushuniladi, ularning kublari soni kichikroq va ularning o'lchamlari kattaroq bo'ladi. Minimal shaklga mos keladigan qoplama minimal qamrov deb ataladi. Masalan, rasmdagi qoplama funktsiyasi uchun. 3.3 minimal shakllarga javob beradi 
Va 
.
Guruch. 3.3 Funktsiyalarni qamrab olish.
chap – ; o'ngda –
Funktsiyaning o'lchovli kubda ko'rinishi aniq va sodda bo'lganda. To'rt o'lchovli kubni rasmda ko'rsatilganidek tasvirlash mumkin. 3.4, bu to'rtta o'zgaruvchining funktsiyasini va uning ifodaga mos keladigan minimal qamrovini ko'rsatadi 
. Ushbu usuldan foydalanish juda murakkab konstruktsiyalarni talab qiladi, uning barcha afzalliklari yo'qoladi.
Guruch. 3.4 Funktsiyani ko'rsatish to'rt o'lchovli kubda
Carnot xaritalar
Mantiqiy funktsiyalarni grafik ko'rsatishning yana bir usuli qo'llaniladi Carnot xaritalar, bu maxsus tashkil etilgan yozishmalar jadvallari. Jadvalning ustunlari va satrlari ikkitadan ko'p bo'lmagan o'zgaruvchilarning barcha mumkin bo'lgan qiymatlari to'plamiga mos keladi va bu to'plamlar shunday tartibda joylashtirilganki, har bir keyingi o'zgaruvchilardan faqat bittasining qiymatida oldingisidan farq qiladi. . Buning yordamida jadvalning qo'shni kataklari gorizontal va vertikal ravishda faqat bitta o'zgaruvchining qiymatida farqlanadi. Jadvalning chetida joylashgan hujayralar ham qo'shni hisoblanadi va bu xususiyatga ega. Shaklda. 3.5-rasmda ikki, uch, to'rt o'zgaruvchilar uchun Karnaugh xaritalari ko'rsatilgan.
 |
|||||
 |
|||||
 |
|||||
Guruch. 3.5 Ikki, uch va to'rt o'zgaruvchilar uchun Carnaugh xaritalari
Oddiy haqiqat jadvallarida bo'lgani kabi, funktsiya 1 qiymatini oladigan to'plamlarning katakchalari birlar bilan to'ldiriladi (odatda nollar mos kelmaydi, ular bo'sh kataklarga mos keladi). Misol uchun, rasmda. 3.6, A Funktsiya uchun Karnaugh xaritasini ko'rsatadi, uning to'rt o'lchovli kubda ko'rinishi rasmda keltirilgan. 3.4. Narsalarni soddalashtirish uchun o'zgaruvchining 1 qiymatlariga mos keladigan qatorlar va ustunlar o'zgaruvchini ko'rsatadigan jingalak qavs bilan ajratib ko'rsatiladi.
 |
|||
 |
|||
Guruch. 3.6 Carnaugh xaritasida to'rtta o'zgaruvchining funksiyasini ko'rsatish
(a) va uning minimal qamrovi (b)
Funksiyalarni xaritalashlar orasida n-o'lchovli kub va Karno xaritasi u erda birma-bir yozishmalar mavjud. Carnot xaritasida s-kub qatorga, ustunga, kvadratga yoki to'rtburchakka (xaritaning qarama-qarshi qirralarining yaqinligini hisobga olgan holda) joylashtirilgan 2 ta qo'shni hujayralar to'plamiga mos keladi. Shuning uchun yuqorida ko'rsatilgan barcha qoidalar (xatboshiga qarang). ko'p o'lchovli kub), Karnaugh xaritalari uchun amal qiladi. Shunday qilib, rasmda. 3.6, b minimal disjunktiv shaklga mos keladigan xarita birliklarining qamrovini ko'rsatadi 
ko'rib chiqilayotgan funktsiya.
Karnaugh xaritasidan minitermlarni o'qish yordamida amalga oshiriladi oddiy qoida. Hujayralarning shakllanishi s-kub, vazir bering (n–s)-bularni o'z ichiga olgan o'rin (n–s) saqlaydigan o'zgaruvchilar bir xil qiymatlar Bu haqida s-kub, bunda 1 qiymati o'zgaruvchilarning o'ziga, 0 qiymati esa ularning inkorlariga mos keladi. O'z qiymatlarini saqlamaydigan o'zgaruvchilar s-kub, minitermda yo'q. Har xil usullar o'qishlar dis'yunktiv normal shaklda funktsiyaning turli xil ko'rinishlariga olib keladi (eng o'ngdagi minimal) (3.7-rasm).
 |  |
||||||||
 |
|||||||||
Karnaugh xaritalaridan foydalanish xaritalash bilan solishtirganda oddiyroq qurilishlarni talab qiladi n-o'lchovli kub, ayniqsa to'rtta o'zgaruvchida. Besh o'zgaruvchining funksiyalarini ko'rsatish uchun to'rtta o'zgaruvchi uchun ikkita Karnaugh xaritasi va oltita o'zgaruvchining funktsiyasi uchun to'rtta shunday xarita ishlatiladi. O'zgaruvchilar sonining ko'payishi bilan Karnaugh xaritalari amalda yaroqsiz holga keladi.
Adabiyotda mashhur Veitch kartalari Ular faqat o'zgaruvchan qiymatlar to'plamining turli tartibida farqlanadi va Karnaugh xaritalari bilan bir xil xususiyatlarga ega.
Kublar majmuasi
Ko'p sonli o'zgaruvchilar bilan grafik usullarning nomuvofiqligi turli xil usullar bilan qoplanadi analitik usullar mantiqiy funksiyalarning tasviri. Shunday vakilliklardan biri kublar majmuasi, maxsus ishlab chiqilgan simvolizm bilan birgalikda ko'p o'lchovli mantiqiy makonning terminologiyasidan foydalanish.
). Birlik tarkibiy qismlariga mos keladigan 0-kublar funksiya birlikka teng bo'lgan o'zgaruvchan qiymatlar to'plami bilan ifodalanadi. Yozuvda aniq
Guruch. 3.8 Uch o‘zgaruvchili funksiya kublar majmuasi ( A) va uning ramziy tasviri ( b)
Kublar majmuasi hosil bo'ladi maksimal funktsiyani qoplash. Undan hammasi bundan mustasno s-kattaroq o'lchamdagi kublar bilan qoplangan kublar, biz o'lik shakllarga mos keladigan qoplamalarni olamiz. Shunday qilib, ko'rib chiqilayotgan misol uchun (3.8-rasm) bizda o'lik qoplama mavjud
,
bu funksiyaga mos keladi 
. IN Ushbu holatda bu qamrov ham minimal.
Ikki mantiqiy funktsiya uchun diszyunksiya amali ularning kub komplekslarining birlashuviga, birikma amali esa kub komplekslarining kesishishiga mos keladi. Funksiyaning inkori kublar majmuasining to‘ldiruvchisiga to‘g‘ri keladi, ya’ni va funksiya 0 qiymatini oladigan barcha cho‘qqilar bilan aniqlanadi. Shunday qilib, algebra o‘rtasida birma-bir moslik (izomorfizm) mavjud. Mantiqiy funktsiyalar va kublar komplekslarini ifodalovchi mantiqiy to'plamlar.
Funktsiyani kublar komplekslari ko'rinishida ifodalash kamroq vizualdir, lekin uning eng muhim afzalliklari shundaki, o'zgaruvchilar soniga cheklovlar olib tashlanadi va kompyuterlardan foydalanishda axborotni kodlash osonlashadi.
Mantiqiy funktsiyalarni minimallashtirish
Muammoni shakllantirish. Mantiqiy asosda sxemani minimallashtirish minimal qamrovga mos keladigan minimal dis'yunktiv shaklni topishga to'g'ri keladi. Oddiy shaklga kiritilgan harflarning umumiy soni qoplash narxi bilan ifodalanadi 
, bu yerda n ta o‘zgaruvchining berilgan funksiyasining qoplamasini tashkil etuvchi kublar soni. Minimal qamrov tavsiflanadi eng past qiymat uning narxlari.
Odatda, minimallashtirish muammosi ikki bosqichda hal qilinadi. Birinchidan, biz maksimal o'lchamdagi barcha kublarni o'z ichiga olgan qisqartirilgan qopqoqni qidiramiz, lekin bu qopqoqning hech qanday kubi bilan qoplangan bitta kubni o'z ichiga olmaydi. Tegishli dis'yunktiv normal shakl reduksiyalangan, minitermlari esa oddiy implikantlar deb ataladi. Berilgan funksiya uchun qisqartirilgan qamrov noyobdir, lekin ba'zi kublar boshqa kublar to'plamlari bilan qoplanganligi sababli ortiqcha bo'lishi mumkin.
Ikkinchi bosqichda qisqartirilgan o'lik-end disjunktiv normal shakllarga o'tish amalga oshiriladi, ulardan minimal shakllar tanlanadi. O'lik shakllar qisqartirilgan qoplamadan barcha ortiqcha kublarni chiqarib tashlash yo'li bilan hosil bo'ladi, ularsiz qolgan kublar to'plami hali ham ma'lum bir funktsiyaning qoplamasini tashkil qiladi, lekin keyinchalik kublarning birortasini chiqarib tashlagan holda, u endi barcha kublarni qamrab olmaydi. funktsiyaning yagona qiymatlariga mos keladigan cho'qqilar, ya'ni u qoplama bo'lishni to'xtatadi.
Berilgan funksiyaning boshqa kublar bilan qamrab olinmagan uchlarini qamrab oluvchi qisqartirilgan qamrov kubi ortiqcha bo'lishi mumkin emas va har doim minimal qamrovga kiritiladi. Bunday kub, xuddi shunga mos implikant kabi, ekstremal (muhim implikant) deb ataladi va u qoplagan uchlari bekor qilingan cho'qqilar deb ataladi. Ekstremallar to'plami qoplamaning yadrosini tashkil qiladi, aniqki, qisqartirilgan qoplamadan minimal darajaga o'tishda, birinchi navbatda, barcha ekstremallarni izolyatsiya qilish kerak. Agar ekstremallar to'plami qoplamani hosil qilmasa, u holda u qisqartirilgan qoplamadan kublar bilan qoplash uchun to'ldiriladi.
Berilgan ta'riflar rasmda ko'rsatilgan. 3.9, bu erda qamrovni qisqartirish (3.9a-rasmga qarang, ) va minimal qoplamalar (3.9b-rasm) va (3.9-rasmga qarang, b) quyidagicha ifodalanadi.
Takliflar algebrasining disjunktiv va konyunktiv normal shakllari. Har bir taklif mantiqiy funktsiyasi uchun haqiqat jadvali tuzilishi mumkin. Teskari masala ham har doim yechilishi mumkin. Keling, bir nechta ta'riflarni keltiramiz.
Boshlang‘ich qo‘shma gaplar (bog'lovchilar) o'zgaruvchilarning birikmalari yoki har bir o'zgaruvchi eng ko'p uchraydigan ularning inkorlari deyiladi
bir marta.
Disjunktiv normal shakl(DNF) elementar birikmalarning diszyunksiyasi shakliga ega formuladir.
Elementar disjunksiyalar (ajralishlar) inkorli yoki inkorsiz o‘zgaruvchilarning diszyunksiyalari deyiladi.
Konyunktiv normal shakl(CNF) elementar disjunksiyalarning birikmasi shakliga ega bo'lgan formuladir.
Har bir taklif algebra funksiyasi uchun disjunktiv va kon'yunktiv normal shakllar to'plamini topish mumkin.
DNF yaratish algoritmi:
1. Ekvivalent transformatsiya formulalari yordamida mantiqiy operatsiyalarga o'ting.
2. Yaqin inkorlar bilan formulalarga, ya'ni inkorlar o'zgaruvchilardan yuqori bo'lmagan holda joylashgan formulaga o'ting - De Morgan qonunlarini qo'llang.
3. Qavslarni oching - taqsimot qonunlarini qo'llang.
4. Bir vaqtning o'zida takrorlanadigan atamalarni oling - idempotentlik qonuni.
5. Yutish va yarim yutilish qonunlarini qo'llang.
6-misol. DNF formulalarini toping: .
Boolean algebrasida bu to'g'ri ikkilik printsipi. Bu quyidagicha.
Funktsiya chaqiriladi ikkilik funksiyasiga agar . Bular. Berilganga dual funktsiyani topish uchun argumentlarning inkorlaridan funktsiyaning inkorini qurish kerak.
7-misol. ga dual funktsiyani toping.
Orasida elementar funktsiyalar mantiq algebrasi 1 ga dual 0 va aksincha, x dual ga, dual ga, dual va aksincha.
Agar funktsiyani ifodalovchi F 1 formulasida biz barcha birikmalarni almashtiramiz
dis'yunksiya bo'yicha, dis'yunksiya konyunksiya bo'yicha, 0 ga 1, 0 ga 1, keyin * ga dual funktsiyani ifodalovchi F * formulasini olamiz.
Konyunktiv normal shakl (CNF) DNF uchun ikki tomonlama tushunchadir, shuning uchun uni quyidagi sxema bo'yicha osongina qurish mumkin:
8-misol. CNF formulasini toping: .
6-misol natijasidan foydalanib, biz bor
Mukammal ayiruvchi va mukammal konyunktiv normal shakllar. Oddiy shakllarning har birida (dizyunktiv va kon'yunktiv) SDNF va SCNF mukammal shakllar sinfini ajratish mumkin.
Mukammal elementar birikma inkorli yoki inkorsiz barcha o‘zgaruvchilarning mantiqiy hosilasi bo‘lib, har bir o‘zgaruvchi ko‘paytmada faqat bir marta namoyon bo‘ladi.
Har qanday DNF barcha o'zgaruvchilarni o'z ichiga olmaydigan birikmalarni bo'lish orqali SDNF ga qisqartirilishi mumkin, ya'ni. etishmayotgan o'zgaruvchiga qo'shib x i distributiv qonun yordamida ko'paytiriladi
9-misol. 6-misoldagi DNF uchun SDNF ni toping
Mukammal elementar disjunksiya inkorli yoki inkorsiz barcha o‘zgaruvchilarning mantiqiy yig‘indisi bo‘lib, har bir o‘zgaruvchi yig‘indiga faqat bir marta kiritiladi.
X i o‘zgaruvchisi bo‘lmagan birikma atamasini birikma orqali qo‘shish va distributiv qonunni qo‘llash orqali har qanday CNF ni SCNF ga qisqartirish mumkin.
10-misol. KNFni SKNFga olib keling:
SCNF ni qurish uchun siz diagrammadan foydalanishingiz mumkin
11-misol. 6-misol formulasi uchun SCNF ni toping.
Har bir funktsiya SDNF va bundan tashqari, o'ziga xos xususiyatga ega. Har bir funktsiya SCNF va bundan tashqari, o'ziga xos xususiyatga ega.
Chunki SDNF va SKNF formulalar bilan yagona aniqlanadi, ular formulaning haqiqat jadvali yordamida tuzilishi mumkin.
SDNF ni 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, mukammal birikmada u inkorsiz, nolga teng bo‘lsa, inkor bilan qabul qilinadi. Keyin mukammal qo`shma gaplar (ularning soni jadvaldagi birliklar soniga teng) ayirma belgilari bilan bog`lanadi.
Haqiqat jadvali yordamida SCNF qurish uchun undagi F = 0 bo'lgan qatorlarni tanlash va mukammal elementar disjunksiyalarni yozish va keyin ularni birikma belgilari bilan bog'lash kerak. Agar haqiqat jadvalining talab qilingan qatorida (F=0) o‘zgaruvchining qiymati nolga to‘g‘ri kelsa, u holda mukammal bandda u inkorsiz, bitta bo‘lsa, inkor bilan qabul qilinadi.
12-misol. 6-misol formulasi uchun haqiqat jadvalidan foydalanib, SDNF va SCNF ni toping.
14-jadval faqat ko'rsatilgan yakuniy qiymat F=10101101. Batafsil haqiqat jadvalini tuzib, ushbu bayonotning to'g'riligini o'zingiz tekshirishingiz kerak.
14-jadval
| x | y | z | ||
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 tomonidan 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 qo‘shma gaplarning 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) argument qiymatlarining barcha to'plamlariga (t 1, ..., t n) tarqaladi. berilgan funksiya 1 qiymatini oladi. E'tibor bering, bunday to'plamlar to'plami bo'sh emas, shuning uchun yig'indi kamida bitta haddan iborat.
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 sizga boshqasini tanlash imkonini beradi to'liq tizimlar funktsiyalari. 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). Zhegalkin polinomining koeffitsientlari at kichik miqdor o'zgaruvchilarni noaniq koeffitsientlar usuli bilan 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.
