Ta'rif 1.Konyunktiv monomial (elementar birikma) o'zgaruvchilardan bu o'zgaruvchilarning birikmasi yoki ularning inkorlari deyiladi.
misol uchun, elementar bog‘lovchidir.
Ta'rif 2.Dizyunktiv monomial (elementar dis'yunksiya) o'zgaruvchilardan bu o'zgaruvchilarning diszyunksiyasi yoki ularning inkorlari deyiladi.
misol uchun, 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.
Misol uchun,- DNF.
Ta'rif 4. Berilgan taklif algebra formulasiga ekvivalent va elementar ayiruvchi monomiyalarning birikmasidan iborat formula deyiladi. konyunktiv normal shakl Ushbu formulaning (CNF).
misol uchun, – KNF.
Har bir taklif algebra formulasi uchun disjunktiv va kon'yunktiv normal shakllar to'plamini topish mumkin.
Oddiy shakllarni qurish algoritmi
Mantiq algebrasining ekvivalentlaridan foydalanib, formuladagi barcha amallarni asosiylari bilan almashtiring: konyunksiya, disjunksiya, inkor:
Ikki tomonlama salbiylardan xalos bo'ling.
Agar kerak bo'lsa, kon'yunksiya va dis'yunktsiya operatsiyalariga distributivlik va yutilish formulalarini qo'llang.
Har qanday mantiqiy funktsiya juda ko'p DNF va CNF ko'rinishlariga ega bo'lishi mumkin. Bu vakillar orasida alohida o'rinni mukammal DNF (SDNF) va mukammal CNF (SKNF) 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 va o'zi yoki uning inkori kiradi.
Strukturaviy ravishda, DNFga qisqartirilgan taklif algebrasining har bir 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(SKNF) 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 kiradi.
Strukturaviy ravishda, CNF ga qisqartirilgan taklif algebrasining har bir formulasi uchun SKNFni quyidagicha aniqlash mumkin.
Ta'rif 4. Mukammal kon'yunktiv normal shakl Berilgan taklif algebra formulasining (SKNF) quyidagi xossalarni qanoatlantiradigan CNF hisoblanadi.
Teorema 1. Bir xil noto'g'ri bo'lmagan o'zgaruvchilarning har bir mantiqiy funktsiyasi SDNFda va bundan tashqari, o'ziga xos tarzda ifodalanishi mumkin.
SDNF ni topish usullari
1-yo'l
2-yo'l
formula 1 qiymatini oladigan qatorlarni tanlang;
bog‘lovchilar diszyunksiyasini amalga oshiramiz, agar o‘zgaruvchi 1 qiymati bilan birikmaga kiritilgan bo‘lsa, u holda bu o‘zgaruvchini yozamiz, agar qiymat 0 bo‘lsa, uning inkori. Biz SDNFni olamiz.
Teorema 2. Bir xil to'g'ri bo'lmagan o'zgaruvchilarning har bir mantiqiy funksiyasi SKNFda va bundan tashqari o'ziga xos tarzda ifodalanishi mumkin.
SKNFni topish usullari
1-yo'l- ekvivalent transformatsiyalar yordamida:
2-yo'l- haqiqat jadvallaridan foydalanish:
formula 0 qiymatini oladigan qatorlarni tanlang;
biz dis'yunktsiyalar birikmasini tuzamiz, agar o'zgaruvchi 0 qiymati bilan dis'yunktsiyaga kiritilgan bo'lsa, u holda biz bu o'zgaruvchini yozamiz, agar qiymat 1 bo'lsa, u holda uning inkori. Biz SKNFni olamiz.
1-misol CNF funksiyalarini chizing.
Qaror
O'zgaruvchilarni o'zgartirish qonunlaridan foydalangan holda "" havolasini olib tashlang:
= /de Morgan qonunlari va ikkilamchi inkor/ =
/distributiv qonunlar/ =
2-misol Formulani DNF ga aylantiring.
Qaror
Biz mantiqiy amallarni quyidagi shartlarda ifodalaymiz va:
= /Inkorni o'zgaruvchilarga bog'lang va ikkilamchi inkorlarni kamaytiring/ =
= /tarqatilish qonuni/ .
3-misol Formulani DNF va SDNF da yozing.
Qaror
Mantiq qonunlaridan foydalanib, biz ushbu formulani faqat elementar birikmalarning disjunksiyalarini o'z ichiga olgan shaklga keltiramiz. Olingan formula kerakli DNF bo'ladi:
SDNF ni yaratish uchun biz ushbu formula uchun haqiqat jadvalini tuzamiz:
Biz jadvalning formulasi (oxirgi ustun) 1 qiymatini oladigan qatorlarni belgilaymiz. Har bir bunday qator uchun ushbu qatorning ,, o'zgaruvchilar to'plamida to'g'ri bo'lgan formulani yozamiz:
1-qator: ;
3-qator: ;
5-qator: .
Ushbu uchta formulaning diszyunksiyasi faqat 1, 3, 5-qatorlardagi o'zgaruvchilar to'plamida 1 qiymatini oladi va shuning uchun zarur bo'lgan mukammal dis'yunktiv normal shakl (PDNF) bo'ladi:
4-misol Formulani SKNFga ikki usulda keltiring:
a) ekvivalent transformatsiyalar yordamida;
b) haqiqat jadvalidan foydalanish.
Qaror:
Ikkinchi elementar disjunksiyani aylantiramiz:
Formula quyidagicha ko'rinadi:
b) ushbu formula uchun haqiqat jadvalini tuzing:
Jadvalning formulasi (oxirgi ustun) 0 qiymatini oladigan qatorlarni belgilaymiz. Har bir bunday qator uchun ushbu qatorning o'zgaruvchilari 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 zarur bo'lgan mukammal kon'yunktiv normal shakl (CKNF) bo'ladi:
Mustaqil hal qilish uchun savollar va vazifalar
1. Ekvivalent transformatsiyalardan foydalanib, formulalarni DNF ga keltiring:
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 SKNF ga aylantiring:
6. Berilgan mantiqiy formulalar uchun SDNF va SKNF ni ikki usulda tuzing: ekvivalent transformatsiyalar yordamida va haqiqat jadvalidan foydalanish.
b) 
;
Elementar diszyunksiya tushunchasini kiritamiz.
Elementar diszyunksiya 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 gaplaridir. Shuning uchun ular konyunktiv normal shaklda yoziladi.
Analitik ifoda bilan berilgan 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:
Takrorlanuvchi 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 ajratishlarni o'chirish.
Sanab o'tilgan amallarning haqiqiyligi mantiq algebrasining asosiy aksiomalari va o'ziga xoslik 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.
Har qanday mantiqiy funktsiya mukammal CNFda ifodalanishi mumkin, bundan mustasno
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 CNFdagi har bir nol komponent funksiyaning nol to'plami bo'lgan yagona o'zgaruvchan qiymatlar to'plamida yo'qoladi. Binobarin, mantiqiy funktsiyaning nol to'plamlari soni uning mukammal CNF tarkibiga kiritilgan nol tarkibiy qismlar soniga to'g'ri keladi.
Mukammal CNFdagi mantiqiy funktsiya nol doimiysi nolning 2nkonjunksiyasi bilan ifodalanadi. Keling, muvofiqlik jadvaliga muvofiq mantiqiy funktsiyaning SKNF ni tuzish qoidasini tuzamiz.
Funktsiya nolga teng bo'lgan yozishmalar jadvalining har bir satri uchun barcha o'zgaruvchilarning elementar dis'yunktsiyasi tuziladi. Dizyunksiya o'zgaruvchining o'zini, agar uning qiymati nolga teng bo'lsa, yoki uning 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-jadvalda berilgan mantiqiy z(x) funksiyasi uchun mukammal konyunktiv shaklni aniqlaymiz.
000 nol funksiya to'plamiga mos keladigan jadvalning birinchi qatori uchun biz null komponentni 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 SKNF 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.
~
SKNFni qurish uchun quyidagi sxemadan foydalanish mumkin:
Misol. Sdnf formulalarini toping.
~
Ma'lumki (2.11, 2.12 teoremalar) SDNF va SKNF formula bilan yagona aniqlangan va shuning uchun ularni formulaning haqiqat jadvaliga muvofiq qurish mumkin.
Haqiqat jadvali bo'yicha SDNF va SKNF 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. Boole mantiq qonunlaridan foydalangan holda variantingizning ifodalarini iloji boricha soddalashtiring. Keyin, haqiqat jadvallaridan foydalanib, soddalashtirilgan ifodani asl ifoda bilan solishtiring.
2.2.2. f 1 va f 2 ning ekvivalentligi haqidagi savolni ularni SDNF ga qisqartirish orqali toping (1-jadval).
2.2.3. Umumlashtirilgan va mantiqiy prinsipga asosan f 3 uchun qo‘sh funksiyani toping (1-jadval). Natijalarni solishtiring.
| № | f1 | f2 | f 3 |
 | |||
 |
|||
 | |||
 | |||
 | |||
 |  |
||
 |  |
||
 |
|||
 | |||
 | |||
 |
|||
 | |||
 |  |
||
 | |||
 |
2.3. Test savollari.
2.3.1. Bayonotni aniqlang.
2.3.2. Bayonotdagi asosiy amallarni sanab bering.
2.3.3. Haqiqat jadvali nima?
2.3.4. Quyidagi formulalar uchun haqiqat jadvallarini tuzing:
~ ~ 
~ ;
2.3.5. Amaliyotlar tartibi to'g'risidagi konventsiyalarni hisobga olgan holda, formulalardagi "qo'shimcha" qavslar va "" belgisini tashlab qo'ying:
;
2.3.6. Ekvivalent o'zgarishlarni qo'llash orqali 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 (SKNF) shakliga aylantiring:
~
№3 laboratoriya
Mavzu:“Mantiqiy funksiyalarni minimallashtirish. Mantiq"
Maqsad: Mantiqiy funktsiyalarni minimallashtirish usullari bilan ishlash bo'yicha amaliy ko'nikmalarni egallash.
3.1. Nazariy ma'lumotlar.
Minimal shakllar
-da ko'rsatilganidek, har qanday mantiqiy funktsiya mukammal normal shaklda (dis'yunktiv yoki kon'yunktiv) ifodalanishi mumkin. Bundan tashqari, bunday tasvirlash funksiyaning jadvalli ta’rifidan uning analitik ifodasiga o‘tishning birinchi bosqichidir. Kelajakda biz ayirma shakldan boshlaymiz va qo'shma shakl uchun mos keladigan natijalar ikkilik printsipi asosida olinadi.
Mantiqiy sxemalarni mantiqiy asosda sintez qilishning kanonik muammosi Boolean funktsiyalarini minimallashtirishga qisqartiriladi, ya'ni. ularni eng kichik harflar sonini o'z ichiga olgan disjunktiv normal shaklda ifodalash (o'zgaruvchilar va ularning inkorlari). 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 yutilish operatsiyasini takroran qo'llash orqali soddalashtirilgan va (kon'yunktiv normal shakl uchun ikki xil identifikatsiyalar: va ). Bu erda mantiqiy algebraning istalgan formulasini tushunish mumkin. Natijada, keyingi transformatsiyalar endi mumkin bo'lmaganda, biz analitik ifodaga kelamiz, ya'ni. biz o'lik shaklini olamiz.
O'lik shakllar orasida minimal ajratuvchi shakl ham mavjud va u yagona bo'lmasligi mumkin. Ushbu 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:
A'zolarni 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 mumkin, chunki). Birinchi holda, bunday a'zo bo'lishi mumkin. Keyin. Atamani qo'shish orqali biz quyidagilarni olamiz: . Barcha mumkin bo'lgan variantlarni ko'rib chiqqandan so'ng, oxirgi ikki shakl minimal ekanligiga ishonch hosil qilishimiz mumkin.
Bu darajadagi formulalar bilan ishlash qorong'ulikda sarson bo'lishga o'xshaydi. Minimal shakllarni qidirish jarayoni, agar bu maqsad uchun maxsus ishlab chiqilgan ba'zi bir grafik va analitik tasvirlar va belgilar ishlatilsa, yanada vizual va maqsadli bo'ladi.
Ko'p o'lchovli kub
O'lchovli kubning har bir cho'qqisiga birlik tarkibiy qismi tayinlanishi 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-da 3.7-bo'limdagi funksiya uchun bunday xaritalash ko'rsatilgan.
3.1-rasm SDNF da berilgan funksiyaning uch o'lchovli kubida ko'rsatish
Har qanday disjunktiv normal shaklda taqdim etilgan o'zgaruvchilar funktsiyasini ko'rsatish uchun uning minitermlari va o'lchovli kub elementlari o'rtasida moslikni o'rnatish kerak.
(-1)-darajali minitermni --darajali ikkita minitermni (birlik tashkil etuvchi) yopishtirish natijasi deb hisoblash mumkin, ya'ni. 
, -o'lchovli kubda bu faqat shu cho'qqilarni bog'laydigan koordinata qiymatlarida farq qiluvchi ikkita cho'qqini chekka bilan almashtirishga to'g'ri keladi (qirra unga tushgan cho'qqilarni qoplashi aytiladi). Shunday qilib, (-1) tartibning minitermlari -o'lchovli kubning qirralariga mos keladi. Xuddi shunday, (-2)-tartibdagi minitermlar - o'lchovli kubning yuzlariga mos keladi, ularning har biri to'rtta uchni (va to'rtta chetini) qamrab oladi.
-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 umumlashtirib, biz o'zgaruvchilar funktsiyasi uchun dis'yunktiv normal shakldagi ()-chi darajali minitermni -kub bilan tasvirlangan deb taxmin qilishimiz mumkin va har bir kub eng kichik o'lchamdagi barcha kublarni qamrab oladi. uning uchlari bilan. Misol tariqasida, rasmda. 3.2 uchta o'zgaruvchili funktsiyaning xaritasini ko'rsatadi. Bu erda minitermlar va 1-kub () ga mos keladi va minitermlar 2-kub () bilan ifodalanadi.
Fig.3.2 Funktsiyani qamrab olish 
Demak, har qanday disjunktiv normal shakl -o'lchovli kubda birlik tarkibiy qismlariga (0-kub) mos keladigan barcha uchlarini qamrab oluvchi -kublar to'plami orqali ko'rsatiladi. Qarama-qarshi gap ham to'g'ri: agar -kublarning ma'lum bir to'plami funktsiyaning birlik qiymatlariga mos keladigan barcha uchlar to'plamini qamrab olsa, u holda bu kublarga mos keladigan minitermlarning dis'yunksiyasi bu funktsiyaning dis'yunktiv normal shakldagi ifodasidir. . Aytishlaricha, -kublarning bunday to'plami (yoki ularga mos keladigan minitermlar) funktsiyaning qoplamasini hosil qiladi.
Minimal shaklga bo'lgan istak intuitiv ravishda bunday qopqoqni izlash sifatida tushuniladi, ularning soni -kublari kichikroq va ularning o'lchamlari kattaroq bo'ladi. Minimal shaklga mos keladigan qopqoq minimal qopqoq deb ataladi. Masalan, rasmdagi qamrov funksiyasi uchun. 3.3 minimal shakllarga mos keladi 
va 
.
Guruch. 3.3 Funktsiyalarni qamrab olish.
chap – ; o'ngda –
Funktsiyani o'lchovli kubda ko'rsatish aniq va sodda bo'lganda. To'rt o'lchovli kubni rasmda ko'rsatilganidek chizish mumkin. 3.4, bu to'rtta o'zgaruvchining funktsiyasini va ifodaga mos keladigan uning 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
Karnot xaritalar
Mantiqiy funktsiyalarni grafik qilishning yana bir usuli qo'llaniladi Carnot kartalari, bu maxsus tashkil etilgan qidirish jadvallari. Jadvalning ustunlari va satrlari ko'pi bilan ikkita o'zgaruvchi uchun barcha mumkin bo'lgan qiymatlar to'plamiga mos keladi va bu to'plamlar shunday tartibda joylashtirilganki, har bir keyingi to'plam avvalgisidan faqat bitta o'zgaruvchining qiymati bilan farq qiladi. Shu sababli, 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 ikki, uch, to'rt o'zgaruvchilar uchun Karnaugh xaritalarini ko'rsatadi.
 |
|||||
 |
|||||
 |
|||||
Guruch. 3.5 Ikki, uch va to'rtta o'zgaruvchilar uchun Karnot 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 berilgan. 3.4. Soddalashtirish uchun ba'zi o'zgaruvchilar uchun 1 qiymatlariga mos keladigan qatorlar va ustunlar ushbu o'zgaruvchining belgisi bilan jingalak qavs bilan ta'kidlangan.
 |
|||
 |
|||
Guruch. 3.6 To'rt o'zgaruvchili funksiyaning Karno diagrammasi ko'rinishi
(a) va uning minimal qamrovi (b)
Funktsiyalarni xaritalashlar o'rtasida n-o'lchovli kub va Karnaugh xaritasida birma-bir yozishma mavjud. Carnot xaritasida s-kub qator, ustun, kvadrat yoki to'rtburchakda (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) Carnot xaritalari uchun amal qiladi. Shunday qilib, rasmda. 3.6, b xarita birliklarining qamrovi minimal disjunktiv shaklga mos keladigan tarzda ko'rsatiladi 
ko'rib chiqilayotgan funktsiya.
Karnot xaritasidan minitermlarni o'qish oddiy qoida bo'yicha amalga oshiriladi. Shakllanadigan hujayralar s-kub, vazir bering (n–s) shularni o'z ichiga olgan daraja (n–s) bunda bir xil qiymatlarni saqlaydigan o'zgaruvchilar 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. O'qishning turli usullari disjunktiv normal shaklda funktsiyaning turli xil ko'rinishlariga olib keladi (eng o'ngdagisi minimal) (3.7-rasm).
 |  |
||||||||
 |
|||||||||
Karnaugh xaritalaridan foydalanish ekranda ko'rsatishga qaraganda oddiyroq konstruktsiyalarni talab qiladi n-o'lchovli kub, ayniqsa to'rtta o'zgaruvchida. Besh o'zgaruvchining funksiyalarini ko'rsatish uchun to'rtta o'zgaruvchi uchun ikkita Karnot xaritasi va oltita o'zgaruvchining funktsiyasi uchun to'rtta shunday xarita ishlatiladi. O'zgaruvchilar sonining yanada ortishi bilan Karnot xaritalari amalda yaroqsiz holga keladi.
Adabiyotda tanilgan Veitch kartalari faqat o'zgaruvchan qiymatlar to'plamining boshqa tartibida farqlanadi va Karnaugh xaritalari bilan bir xil xususiyatlarga ega.
Kublar majmuasi
Ko'p sonli o'zgaruvchilar uchun grafik usullarning muvaffaqiyatsizligi mantiqiy funktsiyalarni ifodalash uchun turli xil analitik usullar bilan qoplanadi. Ushbu vakilliklardan biri kublar majmuasi, bu ko'p o'lchovli mantiqiy makonning terminologiyasini maxsus ishlab chiqilgan simvolizm bilan birgalikda ishlatadi.
). Birlik tarkibiy qismlariga mos keladigan 0-kublar funksiya birlikka teng bo'lgan o'zgaruvchan qiymatlar to'plami bilan ifodalanadi. Rekordda aniq
Guruch. 3.8 Uch o‘zgaruvchili funksiyalar kublari majmuasi ( a) va uning ramziy tasviri ( b)
Kublar majmuasi hosil bo'ladi maksimal funktsiyani qoplash. Bularning barchasi 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 qopqoq bor
,
bu funksiyaga mos keladi 
. Bunday holda, bu qamrov ham minimaldir.
Ikki mantiqiy funktsiya uchun ajratish amali ularning kub komplekslarining birlashuviga, konyunksiya amali esa kub komplekslarining kesishishiga mos keladi. Funksiyaning inkori kublar majmuasini qo‘shishga 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 tasvirlash 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. Sxemani mantiqiy asosda minimallashtirish minimal qamrovga mos keladigan minimal dis'yunktiv shaklni topishga qisqartiriladi. Oddiy shaklga kiritilgan harflarning umumiy soni qoplash narxi bilan ifodalanadi 
, bu yerda - n ta o'zgaruvchida berilgan funksiyaning qamrovini tashkil etuvchi kublar soni. Minimal qoplama uning narxining eng past qiymati bilan tavsiflanadi.
Odatda, minimallashtirish muammosi ikki bosqichda hal qilinadi. Birinchidan, maksimal o'lchamdagi barcha kublarni o'z ichiga olgan qisqartirilgan qopqoq qidiriladi, lekin bu qopqoqning birorta kubi bilan qoplangan kublarni o'z ichiga olmaydi. Tegishli dis'yunktiv normal shakl reduksiyalangan, minitermlari esa oddiy implikantlar deyiladi. Bu funksiya uchun qisqartirilgan qamrov yagonadir, lekin ba'zi kublar boshqa kublar to'plamlari bilan qoplanganligi sababli ortiqcha bo'lishi mumkin.
Ikkinchi bosqichda qisqartirilgandan o'lik-end disjunktiv normal shakllarga o'tish amalga oshiriladi, ulardan minimal shakllar tanlanadi. O'lik shakllar qisqartirilgan qopqoqdan barcha ortiqcha kublarni chiqarib tashlash orqali hosil bo'ladi, ularsiz qolgan kublar to'plami hali ham ma'lum bir funktsiyaning qopqog'ini tashkil qiladi, lekin keyinchalik kublarning birortasini chiqarib tashlagan holda, u endi barcha kublarni qamrab olmaydi. funktsiyaning birlik qiymatlariga mos keladigan tepaliklar, ya'ni u qopqoq bo'lishni to'xtatadi.
Muayyan funktsiyaning boshqa kublar bilan qoplanmagan uchlarini qoplaydigan qisqartirilgan qopqoq kubi ortiqcha bo'lishi mumkin emas va har doim minimal qopqoqqa kiritiladi. Bunday kub, shuningdek, unga mos keladigan implikant ekstremal (muhim implikant) deb ataladi va u bilan qoplangan cho'qqilar bekor qilingan cho'qqilar deb ataladi. Ekstremallar to'plami qamrovning o'zagini tashkil qiladi, aniqki, qisqartirilgan qamrovdan minimal darajaga o'tishda, birinchi navbatda, barcha ekstremallarni tanlash kerak. Agar ekstremallar to'plami qopqoqni hosil qilmasa, u holda u qisqartirilgan qopqoqdan kublar bilan qopqoq bilan 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.9b-rasmga qarang) quyidagicha ifodalanadi.
Takliflar algebrasining dis'yunktiv va kon'yunktiv normal shakllari. Taklif mantiqining har bir funksiyasi uchun haqiqat jadvalini tuzish 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 ularning inkorlari deyiladi, bunda har bir o'zgaruvchi eng ko'p uchraydi
bir marta.
Disjunktiv normal shakl(DNF) elementar birikmalarning diszyunksiyasi shakliga ega formuladir.
Elementar disjunksiyalar (bandlar bo'yicha) inkorli yoki inkorsiz o'zgaruvchilarning dis'yunktsiyalari deyiladi.
Konyunktiv normal shakl(CNF) elementar ayirmalarning birikmasi shakliga ega bo'lgan formuladir.
Takliflar algebrasining har bir funksiyasi uchun disjunktiv va kon'yunktiv normal shakllar to'plamini topish mumkin.
DNF qurish algoritmi:
1. Ekvivalent transformatsiya formulalari yordamida mantiqiy operatsiyalarga o'ting.
2. Negativlari yaqin bo'lgan formulalarga, ya'ni negativlar o'zgaruvchilardan yuqori bo'lmagan holda joylashgan formulaga o'ting - de Morgan qonunlarini qo'llang.
3. Qavslarni oching - taqsimot qonunlarini qo'llang.
4. Bir marta olish uchun atamalarni takrorlash - idempotentlik qonuni.
5. Yutish va yarim yutilish qonunlarini qo'llang.
6-misol DNF formulalarini toping: .
Boole algebrasida, 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.
Mantiq algebrasining elementar funksiyalari orasida 1 ga dual 0 va aksincha, x ga dual, ga ikkilik, ga ikkilik va aksincha.
Agar funktsiyani ifodalovchi F 1 formulada barcha birikmalar almashtiriladi
dis'yunksiya bo'yicha, kon'yunksiya bo'yicha dis'yunksiya, 0 ga 1, 0 ga 1, keyin biz formulani olamiz F * , funktsiyani ifodalovchi * , dual .
Konyunktiv normal shakl (CNF) DNF uchun ikki tomonlama tushunchadir, shuning uchun uni sxema bo'yicha osongina qurish mumkin:
8-misol CNF formulalarini toping: .
6-misol natijasidan foydalanib, biz bor
Mukammal ayiruvchi va mukammal konyunktiv normal shakllar. Oddiy shakllarning har birida (dizyunktiv va kon'yunktiv) SDNF va SKNF ning mukammal shakllari sinfini ajratib ko'rsatish mumkin.
Mukammal elementar birikma inkorli yoki inkorsiz barcha o‘zgaruvchilarning mantiqiy hosilasi bo‘lib, har bir o‘zgaruvchi ko‘paytmaga bir martagina kiritiladi.
Har qanday DNF barcha o'zgaruvchilarni o'z ichiga olmaydigan birikmalarni bo'lish orqali SDNF ga qisqartirilishi mumkin, ya'ni. etishmayotgan x i o'zgaruvchisi uchun qo'shilish taqsimot qonuni yordamida ko'paytiriladi
9-misol 6-misol uchun DNF uchun SDNF toping
Mukammal elementar disjunksiya inkorli yoki inkorsiz barcha o'zgaruvchilarning mantiqiy yig'indisi deyiladi, bundan tashqari har bir o'zgaruvchi yig'indiga faqat bir marta kiritiladi.
X i o‘zgaruvchisi bo‘lmagan qo‘shma atamani qo‘shish va distributiv qonunni qo‘llash orqali har qanday CNF SKNF ga qisqartirilishi mumkin.
10-misol. CNF ni SKNF ga aylantiring:
SKNFni qurish uchun siz sxemadan foydalanishingiz mumkin
11-misol. 6-misol formulasi uchun SKNF ni toping.
Har bir funktsiyada SDNF mavjud va bundan tashqari, yagona . Har bir funktsiyada SKNF va bundan tashqari, bitta .
Chunki SDNF va SKNF formulalar bilan yagona aniqlanadi, ular formulaning haqiqat jadvaliga muvofiq 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 konyunksiyada u inkorsiz, nolga teng bo‘lsa, inkor bilan qabul qilinadi. So`ngra mukammal qo`shma gaplar (ularning soni jadvaldagi birliklar soniga teng) ayirma belgilari bilan bog`lanadi.
SKNF ni haqiqat jadvali bo’yicha qurish uchun undagi F=0 bo’lgan qatorlarni tanlab, mukammal elementar disjunksiyalarni yozib, so’ngra ularni birikma belgilari bilan bog’lash kerak. Agar haqiqat jadvalining kerakli qatorida (F=0) o‘zgaruvchining qiymati nolga to‘g‘ri kelsa, mukammal dis’yunktda inkorsiz, birga teng bo‘lsa, inkor bilan qabul qilinadi.
12-misol. 6-misol formulasi uchun haqiqat jadvaliga muvofiq SDNF va SKNF ni toping.
14-jadvalda faqat yakuniy qiymat F=10101101 ko'rsatilgan. Ushbu bayonotning to'g'riligi kengaytirilgan haqiqat jadvalini tuzish orqali mustaqil ravishda tekshirilishi 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) boshqa har qanday mantiqiy funktsiya SDNF (SKNF) sifatida ifodalanishi mumkin. Standart asosning to'liqligi. To'liq asoslarga misollar: Jegalkin asosi, Sheffer zarbasi, Pirs o'qi.
Standart asos Bu uchta boshlang'ich mantiqiy algebra 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'rinishdagi ifoda. . . xˆ l, deyiladi elementar birikma . Barcha o'zgaruvchilarning har xil bo'lishi talabi quyidagilardan kelib chiqadi. Agar qo‘shma gapda bir nechta bir xil harflar bo‘lsa, u holda qo‘shma gapning almashinuvchanligi, assotsiativligi va idempotentligi tufayli ekvivalent formulaga o‘tsak, faqat bitta harf qoldirishimiz mumkin (masalan, x 1 x 1 = x 1). Agar birikma o'zgaruvchini va uning inkorini o'z ichiga olsa, u holda formula doimiy 0 ga 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 . Misol uchun,
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 shakldir.
Mantiqiy algebrada qo‘shish va ko‘paytirish nosimmetrik amallar bo‘lib, har doim qo‘shishni ko‘paytirish, ko‘paytirishni esa qo‘shish deb talqin qilish mumkin bo‘lganligi sababli, ikki tomonlama tushuncha ham 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 haqidagi har qanday bayonot CNF haqidagi qo'shilish (ajralish) ni ko'paytirish, ko'paytirish (konjunksiya) ni qo'shish, doimiy 0 ni doimiy 1, doimiy 1 bilan almashtirish orqali olinadi. doimiy 0 bo'yicha, tartib munosabatlari ikkilik (teskari) bo'yicha. 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 bilan rozi boʻlaylik, agar s = 1 boʻlsa, x formulasi, s = 0 boʻlsa, x formulasi tushuniladi. f(y 1 , . . . , y n) funksiya vektor (t 1) boʻyicha 1 qiymatini qabul qilsin. , .., t n ) (bunday vektor deyiladi tarkibiy birlik ). Keyin elementar birikma ham ushbu to'plamda 1 qiymatini oladi, lekin boshqa barcha n o'lchovli mantiqiy vektorlarda yo'qoladi. Formulani ko'rib chiqing
bunda yig'indisi (birlashmasi) berilgan funktsiya 1 qiymatini oladigan argument qiymatlarining barcha to'plamlari (t 1, . . . ., t n) bo'ylab tarqaladi. E'tibor bering, bunday to'plamlar to'plami bo'sh emas, shuning uchun sum kamida bitta atamani o'z ichiga oladi.
Ko'rinib turibdiki, P formulasi ular uchun 1 ga aylanadi va faqat ko'rib chiqilayotgan funktsiya 1 ga aylanadigan o'zgaruvchilar qiymatlari uchun. Demak, r formula f funksiyani ifodalaydi.
Xulosa 1.1. Standart asos tugallandi.
◀ Haqiqatan ham, agar funktsiya doimiy 0 bo'lmasa, u standart asosda formula bo'lgan SDNF sifatida ham ko'rsatilishi 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. ko'pchilik funktsiyasi ̆. 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 buzzi funksiyalarining har biri F ustidagi formula bilan ifodalanishi mumkin. Keyin, 1.3-teoremaga ko'ra, F ning boshqaligi to'liq bo'ladi.
1.3-misol. 2 qo'shish, ko'paytirish va doimiy 1 moduli operatsiyalari to'plami deyiladi Jegalkin asosi . Modulo 2 qo'shish va ko'paytirish Z2 halqasining asosiy amallari, ularning yordami bilan tuzilgan ifodalar Z2 halqasi ustidagi ko'phadlardir. Bu holda 1 doimiysi bepul a'zoni yozish uchun kerak bo'ladi. Xx \u003d x bo'lgani uchun, polinomdagi 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 formula Jegalkin ko'phadli deb ataladi. Aslida, Jegalkin ko'phad Z2 halqasi ustidagi ko'phaddir.
Standart bazisni qo'shish va inkor qilish operatsiyalarini ifodalovchi Jegalkin asosi bo'yicha formulalarni qurish oson (ikkita 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, atamalar tartibiga qadar). O'zgaruvchilar soni kam bo'lgan Jegalkin ko'phadining koeffitsientlarini noaniq koeffitsientlar usuli bilan topish mumkin.
1.4-misol. Bitta funktsiya to'plamini ko'rib chiqing - Schaeffer zarbasi*. Bu toʻplam toʻliq boʻlib, u quyidagi oson tekshiriladigan identifikatorlardan kelib chiqadi:
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 Pirs o'qi ham to'liq. Buni tekshirish Schaeffer zarbasi holatiga o'xshaydi. Biroq, bu xulosani simmetrik yarim halqalar uchun ikkilik printsipi asosida ham qilish mumkin.
*Schaffer zarbasi ikkilik operatsiya, lekin assotsiativ emas. Shuning uchun, infix formasidan foydalanganda ehtiyot bo'lishingiz kerak: natija operatsiyalarni bajarish tartibiga bog'liq. Bunday holda, qavslar yordamida amallar tartibini aniq ko'rsatish tavsiya etiladi, masalan, (x | y) | z, x | emas y | z, garchi ikkala shakl ham ekvivalent.
