asosida biz quyidagilarni olamiz

Mantiqiy funksiyalarning normal shakllari Mantiqiy funktsiyaning kon'yunktiv a'zolarning (birlik tashkil etuvchi) Ki , , (2.7) dis'yunksiyasi ko'rinishida ifodalanishi bu funksiyaning dis'yunktiv normal shakli (DNF) deyiladi. Agar DNF dagi barcha kon’yunktiv atamalar mintermlar bo‘lsa, ya’ni ular bir vaqtning o‘zida barcha mantiqiy o‘zgaruvchilarni bir vaqtning o‘zida, ya’ni inkorlar bilan yoki inkorlarsiz olingan holda o‘z ichiga olsa, u holda funksiyani ifodalashning bu shakli bu funksiyaning mukammal dis’yunktiv normal shakli (SDNF) deyiladi. . SDNF mukammal deyiladi, chunki disjunksiyadagi har bir atama barcha o'zgaruvchilarni o'z ichiga oladi; dis'yunktiv, chunki formuladagi asosiy operatsiya dis'yunksiyadir. "Oddiy shakl" tushunchasi berilgan funktsiyani amalga oshiradigan formulani yozishning aniq usulini anglatadi. Yuqoridagilardan kelib chiqib, 2.1 teorema quyidagi teoremani nazarda tutadi. Teorema 2. Har qanday mantiqiy funktsiya (0 ga bir xil bo'lmagan) SDNFda ifodalanishi mumkin va bunday tasvir noyobdir. Misol 3. Jadval funksiyasi f (x1 (10-jadval).
Formula (2.6) asosida biz quyidagilarni olamiz:
Formula (2.6) asosida biz quyidagilarni olamiz: . Ko'rib turganingizdek, SDNF funksiyasini kompilyatsiya qilishda funktsiya qiymatini oladigan barcha mintermlarni diszyunksiya qilish kerak 1. Mantiqiy funktsiyani dis'yunktiv atamalar birikmasi (ta'sis nol) shaklida ifodalash Di. Bu funktsiyaning kon'yunktiv normal shakli (CNF) deb ataladi.
Agar CNF ning barcha dis'yunktiv hadlari makstermlar bo'lsa, ya'ni ular inkorlar bilan yoki inkorlarsiz olingan funktsiyaning barcha mantiqiy o'zgaruvchilarini birin-ketin o'z ichiga olgan bo'lsa, unda bunday CNF bu funktsiyaning mukammal kon'yunktiv normal shakli (PCNF) deb ataladi. Teorema 3. Har qanday mantiqiy funktsiya (1 ga bir xil bo'lmagan) SKNFda ifodalanishi mumkin va bunday tasvir yagonadir. Teoremaning isboti 2.1-teoremaning isbotiga o'xshab, konyunktiv parchalanish bo'yicha quyidagi Shennon lemmasi asosida amalga oshirilishi mumkin. Lemma Shennon. m o‘zgaruvchining istalgan mantiqiy funksiyasi f (x1 , x2 , …, xm) quyidagicha ifodalanishi mumkin:
Shuni ta'kidlash kerakki, mantiqiy funktsiyani ifodalashning ikkala shakli (DNF va CNF) nazariy jihatdan o'z imkoniyatlarida tengdir: har qanday mantiqiy formulalar DNF da (bir xil noldan tashqari) va CNF da (bir xil birlikdan tashqari) ifodalanishi mumkin. . Vaziyatga qarab, funktsiyaning u yoki bu shaklda ifodalanishi qisqaroq bo'lishi mumkin. Amalda, DNF ko'pincha qo'llaniladi, chunki bu shakl odamga ko'proq tanish: bolaligidan u summalarni ko'paytirishdan ko'ra mahsulot qo'shishga ko'proq odatlangan (ikkinchi holda, u intuitiv ravishda qavslarni ochish va shu bilan borishni xohlaydi. DNF ga).
Misol 4. Jadvalda berilgan f (x1, x2, x3) funksiya uchun. 10, uni SKNFga yozing. SDNF dan farqli o'laroq, SKNF ni kompilyatsiya qilishda mantiqiy funktsiyaning haqiqat jadvalida siz funktsiya 0 qiymatini oladigan o'zgaruvchilar kombinatsiyasini ko'rib chiqishingiz va mos keladigan maxtermslarning birikmasini yaratishingiz kerak, lekin o'zgaruvchilar teskari bilan olinishi kerak. inversiya:
Shuni ta'kidlash kerakki, funktsiyaning SDNF dan to'g'ridan-to'g'ri SKNF ga yoki aksincha o'tish mumkin emas. Bunday o'zgarishlarni amalga oshirishda kerakli funktsiyalarga teskari bo'lgan funktsiyalar olinadi. SDNF va SKNF funktsiyalari uchun ifodalarni faqat uning haqiqat jadvalidan to'g'ridan-to'g'ri olish mumkin.

Misol 5. Jadvalda berilgan f (x1, x2, x3) funksiya uchun. 10, SDNF dan SKNF ga o'tishga harakat qiling.

2.3-misol natijasidan foydalanib, biz quyidagilarni olamiz: Ko'rib turganingizdek, umumiy inversiya ostida biz 2.4-misolda olingan funktsiyaga nisbatan teskari bo'lgan mantiqiy funktsiyaning SKNF ni olamiz: , chunki u barcha maksimal terminlarni o'z ichiga oladi. ko'rib chiqilayotgan funksiyaning SKNF ifodasida emas.
Keyinchalik, mantiqiy funksiyalarning xossalaridan foydalangan holda funktsiyaning analitik ko'rinishini normal shaklga o'tkazishning sistematik protsedurasini (algoritmini) taqdim etamiz.
1. Amallarning xossalaridan (9-jadvalga qarang) identifikatsiya (), yig'indisi moduli
2 (), implikatsiya () yordamida VA, OR, EMAS (Boole asosiga) amallarga o'tamiz. 2. Inkor qilish xossalaridan va de Morgan qonunlaridan (9-jadvalga qarang) foydalanib, inkor amallari butun ifodalarga emas, balki faqat alohida o‘zgaruvchilarga tegishli bo‘lishiga erishamiz.
3. VA va YOKI mantiqiy amallarning xossalaridan foydalanib (9-jadvalga qarang) biz normal shaklni (DNF yoki CNF) olamiz.
4. Agar kerak bo'lsa, biz mukammal shakllarga o'tamiz (SDNF yoki SKNF). Misol uchun, SKNFni olish uchun siz ko'pincha mulkdan foydalanishingiz kerak: . Misol
6. Mantiqiy funktsiyani SKNF ga aylantiring
Shunday qilib, f (x1 , x2 , x3) funksiyaning CNF ni oldik. Uning SKNF ni olish uchun siz har qanday o'zgaruvchisi yo'q bo'lgan har bir dis'yunktsiyani ikki marta takrorlashingiz kerak - bu o'zgaruvchi bilan va uning inkori bilan: