Mantiqiy funktsiyaning konyunktiv normal shakli. Mantiqiy funksiyalarning normal shakllari. To'liq dis'yunktiv va to'liq kon'yunktiv normal shakllar
Elementar diszyunksiya tushunchasini kiritamiz.
Elementar dis'yunksiya tashqi ko'rinishi deyiladi
Mantiqiy funktsiyaning kon'yunktiv normal shakli (CNF) juftlik bilan har xil elementar dis'yunksiyalarning har qanday terminal ko'pligining birikmasidir. Masalan, mantiqiy funktsiyalar
elementar ayirmalarning birikmasidir. Xo'sh, hid kon'yunktiv normal shaklda qayd etiladi.
Analitik ifoda bilan aniqlangan juda mantiqiy funktsiya CNFga vikonning hujumkor operatsiyalari orqali keltirilishi mumkin:
To'g'ri inversiya qoidalari qo'llaniladi, chunki sanab o'tish operatsiyasi mantiqiy ifodaga soddalashtirilgan;
Quyidagi taqsimot aksiomalari ko'paytiriladi:
Vykoristannya loydan yasalgan operatsiyalar:
Muhim disjunctionlarning ayblari takrorlanadi yoki ular sanab o'tiladi;
Yangi elementar disjunksiyalardan biridan tashqari hammasini olib tashlash;
Siz darhol ushbu ro'yxatga kiritilgan barcha ajratmalarni ko'rishingiz mumkin.
Qayta sug'urta operatsiyalarining adolatliligi mantiq algebrasining asosiy aksiomalari va shunga o'xshash munosabatlaridan kelib chiqadi.
Konyunktiv normal shakl yaxshilab chaqiriladi, chunki u funktsiya asosidagi barcha o'zgarishlarni to'g'ridan-to'g'ri yoki teskari ko'rinishda joylashtirish uchun undan oldin kiritilishi kerak bo'lgan teri elementar dis'yunksiyasidir.
KNFni to'liq KNFga qayta tashkil etish hujumkor operatsiyalarni yakunlash yo'nalishiga asoslanadi:
Teriga oʻzgarishlar qoʻshma gaplarining elementar disʼyunksiyasini qoʻshib, bu elementar disʼyunksiyaga badboʻy hid kirmasligi uchun ularni bloklash;
distributivlikning vikoristonlik aksiomalari;
Yangi elementar disjunksiyalardan biridan tashqari hammasini olib tashlash.
Puxta CNF har qanday mantiqiy funktsiyani, kremni taqdim etishi mumkin
ham teng birliklar (). Mukammal CNFning yagona vakolati undagi mantiqiy funktsiyani bitta sifatida ochib beradiganlardir.
To'liq CNF funktsiyasiga kiritilgan elementar dis'yunktsiyalar nolning tarkibiy qismlari deb ataladi. To'liq CNF tarkibiga kiradigan nol tarkibiy qismining terisi o'zgaruvchan qiymatlarning yagona to'plamida nolga aylanadi, bu nol funktsiyalar to'plamidir. Shuningdek, mantiqiy funktsiyaning nol to'plamlari soni uning to'liq CNF ga kiritilgan nolning tarkibiy qismlari soniga teng.
Puxta CNFda nol doimiysining mantiqiy funktsiyasi nolning 2n tashkil etuvchisining birikmasidir. Turlar jadvalining SCNF mantiqiy funktsiyasini shakllantirish qoidasini shakllantiramiz.
Funktsiya nolga teng bo'lgan turlar jadvalining teri qatori uchun barcha o'zgarishlarning elementar dis'yunktsiyasi hosil bo'ladi. Bunday holda, disjunktsiyaning o'zi o'zgaruvchan, chunki uning qiymatlari nolga teng yoki yopiq, chunki uning qiymatlari birlarga teng. Elementar ayirmalarni bartaraf qilish qo`shma gap belgisi bilan birikadi.
Butt 3.4. 2.2-jadvalda berilgan mantiqiy funktsiya z(x) uchun konyunktiv shakl muhim ahamiyatga ega.
000 funksiyaning nol to'plamiga mos keladigan jadvalning birinchi qatori uchun biz nol tarkibiy qismini topamiz. Boshqa, uchinchi va beshinchi qatorlar uchun shunga o'xshash operatsiyalarni bajargandan so'ng, CNF funktsiyalarini yaxshilab o'rganish kerak:
Shuni ta'kidlash kerakki, bitta to'plamlar soni nol to'plamlar sonidan kattaroq bo'lgan funktsiya uchun va ularning ixcham belgilanishi SKNF ga o'xshaydi.
Ajralishni kechiring(ingliz. inklyuziv disjunksiya) yoki ajratilgan(inglizcha disjunct) bir yoki bir nechta o'zgarishlarning dis'yunksiyasi yoki ularning o'zaro bog'lanishi deb ataladi va teri o'zgarishi bir martadan ko'p bo'lmagan keskinlashadi.
Oddiy ajratish
- povna chunki teri (yoki teri) aynan bir marta kiritilishi kerak;
- monoton o'zgarganlar ro'yxatida qasos olmaslik uchun.
Konyunktiv normal shakl, CNF(Inglizcha konjunktiv normal shakl, CNF) oddiy shakl bo'lib, unda mantiqiy funktsiya bir nechta oddiy bandlarning birikmasiga o'xshaydi.
KNF aktsiyalari:$f(x,y) = (x \lor y) \land (y \lor \neg ( z ))$
SKNF
To'liq kon'yunktiv normal shakl, SKNF(inglizcha mukammal kon'yunktiv normal shakl, PCNF) - bu ongni quvontiradigan CNF:
- unda oddiy ajralishlar mavjud emas
- terini oddiy ajratish povna
SKNF aktsiyalari:$f(x,y,z) = (x \lor \neg ( y ) \lor z) \land (x\lor y \lor \neg ( z ))$
Teorema: Har qanday mantiqiy funktsiya uchun $f(\vec ( x ))$, bir xil birlikka teng emas, uni belgilaydigan SCNF mavjud.
Sizga keltirgan:$\neg ( f ) (\vec x)$ funksiyasining inversiyasi $f(\vec x)$ nolga teng bo‘lgan shunday to‘plamlar bilan bir xil bo‘lgani uchun $\ uchun SDNF. neg ( f ) (\vec x)$ shunday yozilishi mumkin:
$\neg(f)(\vec x)=\bigvee\limits_(f(x^(\sigma_(1)), x^(\sigma_(2))), ..., x^(\sigma_( n))) = 0) (x_(1)^(\sigma_(1))\xanuz x_(2)^(\sigma_(2))\xana...\xanjar x_(n)^(\sigma_( n ) )) $, bu erda $ \sigma_ ( i ) $ $ x_ ( i ) $ uchun sanab bor yoki yo'qligini bildiradi.
Biz ifodaning chap va o'ng qismlarining inversiyasini bilamiz:
$ f(\vec x) = \neg (( \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) )) , x^ ( \sigma_ ( 2 ) )) , ... ,x^ ( \sigma_ ( n )) = 0 ) ( x_ ( 1 ) ^ ( \ sigma_ ( 1 ) ) \ xanjar x_ ( 2 ) ^ ( \ sigma_ ( 2 ) ) \ xanjar ... \ xanjar x_ ( n ) ^ ( \ sigma_ ( n ))) ))) $
De Morgan qoidasi o'ng tomondan olib tashlansa, biz quyidagilarni yo'q qilishimiz mumkin: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ) , \dots ,x^ ( \ sigma_n )) = 0 ) $ $(\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \dots \vee \neg ( x_n^ ( \sigma_n ) )) $
Qolgan viraz i ê SKNF. Shunday qilib, SCNF aniq nolga teng bo'lmagan har qanday funktsiya uchun yaratilishi mumkin bo'lgan SDNF dan ajratilganligi sababli, teorema tugallangan.
SKNF ni haqiqat jadvaliga olib borish algoritmi
- Haqiqat jadvali funktsiya qiymatlari $0 $ ga teng bo'lgan o'zgaruvchilar to'plamini aniqlaydi.
- To'plamga tayinlangan teri uchun biz barcha o'zgarishlarning diszyunksiyasini quyidagi qoida bo'yicha yozamiz: agar berilgan o'zgarishlarning qiymati $0$ bo'lsa, u holda dis'yunksiya o'zgarishlarni o'z ichiga oladi, aks holda u ro'yxatga olinadi.
- Barcha diszyunksiyalar birikma amallari bilan bog‘liq.
OAV uchun SKNF ko't
1). Haqiqat jadvali funktsiya qiymatlari $0 $ ga teng bo'lgan o'zgaruvchilar to'plamini aniqlaydi.
| x | y | z | $ \langle x,y,z \rangle $ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
2). To'plamga tayinlangan teri uchun biz barcha o'zgaruvchilarning konyunksiyasini quyidagi qoida bo'yicha yozamiz: agar berilgan o'zgaruvchining qiymati $0$ bo'lsa, u holda dis'yunksiya o'zgaruvchining o'zini o'z ichiga oladi yoki boshqacha.
| x | y | z | $ \langle x,y,z \rangle $ | |
| 0 | 0 | 0 | 0 | $(x \lor y \lor z)$ |
| 0 | 0 | 1 | 0 | $(x \lor y \lor \neg ( z ))$ |
| 0 | 1 | 0 | 0 | $(x \lor \neg (y) \lor z)$ |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | $(\neg (x)\lor y \lor z)$ |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
3). Barcha diszyunksiyalar birikma amallari bilan bog‘liq.
$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg (x) \lor y \lor z) \land (x \lor \neg (y) \lor z) \land (x \lor y \lor \neg ( z ))$
Faol funktsiyalar uchun SKNF dan foydalaning
Pirs o'qi: $ x \downarrow y = (\neg (x) \lor(y)) \land ((x) \lor \neg(y)) \land (\neg(x) \lor \neg(y) )$
Viklyuchne abo: $ x \oplus y \oplus z = (\neg ( x ) \lor \neg ( y ) \lor z) \land (\neg ( x ) \lor y \lor \neg ( z )) \land (x \lor \neg ( y ) \lor \neg ( z )) \land (x \lor y \lor z)$
Oddiy shakl Mantiqiy formulada elementar bo'lmagan formulalarning implikatsiya, ekvivalentlik va sanab belgilarini noto'g'ri joylashtirmang.
Oddiy shakl ikki xil bo'ladi:
kon'yunktiv normal shakl (CNF)-- dekal ayirmalarining birikmasi, masalan, $ \ left (A \ vee \ overline (B) \ vee C \ o'ng) \ xanjar \ chap (A \ vee C \ o'ng) $;
disjunktiv normal shakl (DNF)-- dekilkoh qo‘shma gaplarni ajratish, masalan, $ \ left (A wedge \ overline (B) \ wedge C \ right) \ vee \ left (B \ wedge C \ right) $.
SKNF
To'liq kon'yunktiv normal shakl (SCNF) - bu KNF, chunki u uchta fikrni qondiradi:
har qanday elementar disjunksiyadan o'ch olmang;
Ajralishdan kelib chiqib, yangilaridan o'ch olmaslik kerak;
Bu CNF narxidan oldin kiradiganlardan teri suyuqligini olib tashlash uchun elementar disjunction hisoblanadi.
Agar bu mantiqiy formula bo'lsa ham, agar u to'g'ri bo'lmasa, uni SKNFga topshirish mumkin.
SKNFni haqiqat jadvaliga rioya qilishga undash qoidalari
Funktsiyasi 0 ga teng bo'lgan har bir o'zgaruvchilar to'plami uchun yig'indi yoziladi va ro'yxatlardan qiymati 1 ga teng bo'lgan o'zgaruvchilar olinadi.
SDNF
To'liq disjunktiv normal shakl (SDNF) -- bu DNF, chunki u uchta fikrni qondiradi:
har qanday elementar ulanishlarni e'tiborsiz qoldirmang;
O'zgarganlardan o'ch olmaslik kerak;
Terining vazifasi teri suyuqligini DNF dan oldin kelganlardan bir xil tartibda olib tashlashdir.
Agar u mantiqiy formula bo'lsa ham, u bir xil formula emas, lekin uni SDNFda xuddi shu tarzda ifodalash mumkin.
SDNFni haqiqat jadvali orqasida haydash qoidalari
Funktsiyasi 1 ga teng bo'lgan har bir o'zgarishlar to'plami uchun qo'shimchalar yoziladi va 0 qiymatiga ega bo'lgan o'zgarishlar ro'yxatdan olinadi.
SKNF va SDNF bilimlarini qo'llang
Butun 1
Ushbu haqiqat jadvali orqasida mantiqiy funktsiyani yozing:
Malyunok 1.
Qaror:
Quyida SDNF ni so'rashning tezkor qoidasi keltirilgan:
Malyunok 2.
O'chirilgan SDNF:
Eng tezkor qoida SKNF bo'ladi.
Standart asos. Elementar formulalar - harflar. Elementar qo‘shma gap (dizyunksiya). Dizyunktiv (konyunktiv) - normal shakl va to'liq shakl. Teorema: kirish 0 (1-tur) bo'lgan har qanday mantiqiy funktsiya SDNF (SCNF) ko'rinishida ifodalanishi mumkin. Standart asosning to'liqligi. Tashqi asoslarning qo'llanilishi: Zhegalkin asosi, Schaefferning zarbasi, Pirs o'qi.
Standart asos - bu Boolean algebrasining uchta chiqish operatsiyalari to'plami: qo'shish (birlashtirish), ko'paytirish (kesish) va kesishish.
Mana bizni chaqirishadi tom ma'noda x ni o'zgartirish yoki kesishgan x va o'rtacha xˆ. Turli o'zgaruvchilar bilan belgilangan bir nechta literallarning mantiqiy o'tkazilishi, keyin. viraz ko'rinishi X = x 1 x 2. . . xˆ l deyiladi elementar birikma . Umid qilamizki, butun dunyoda qirg'inlar bo'ladi, shunda kelajakda o'zgarish bo'ladi. Agar bog‘lovchi bir qator yangi harflarni o‘z ichiga olsa, u holda qo‘shma gapning almashinishi, assotsiativligi va idempotentligi orqali ekvivalent formulaga o‘tish orqali kamida bitta harfni olib tashlash mumkin (masalan, x 1 x 1 = x 1). Agar birikma o'zgaruvchan va o'zaro bog'langan bo'lsa, u holda formula 0 doimiy ga ekvivalent bo'ladi, shuning uchun x x = 0 va har qanday Y formula uchun biz Y x x = 0 ga ega bo'lishimiz mumkin.
Ko'p 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.
Terining o'zgaruvchan elementar ulanishlari ombori DNF bilan bir xil bo'lganligi sababli, DNF deyiladi. yaxshilab . Ishorali dumbalar DNF emas, lekin ular puxta emas. Navpaki, 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
- shakl to'ldirilgan.
Boolean algebrasidagi fragmentlar qo'shish va ko'paytirish - nosimmetrik amallar va shuning uchun qo'shishni ko'paytirish va ko'paytirishni qo'shish sifatida talqin qilish mumkin va ikkita tushuncha mavjud - konyunktiv normal shakl (KNF ), elementar ayirmalarning bog‘lovchisi va yaxshilab konjunktiv shakl (SKNF ). Simmetrik bo'lganlar uchun ikkilik printsipiga asoslanib, DNF bayonoti nima bo'lishidan qat'i nazar, u ikki tomonlama CNF bayonotiga ekvivalent bo'lib, natijada ko'paytirish, ko'paytirish (birlashma) ii) qo'shilgan, doimiy 0 doimiy 1, doimiy 1 doimiy 0, tartibda. Shuning uchun biz DNFdan mahrum bo'lgan Vivchennoe haqida gapiramiz.
1.4 teorema. Doimiy 0 sifatida aniqlangan har qanday mantiqiy funktsiya SDNF ko'rinishida ifodalanadi.
◀X s ostida s = 1 boʻlgani uchun x formulasini va s = 0 boʻlgani uchun x formulasini tushunish maqsadga muvofiqdir. t 1 , t n ) (bunday vektor deyiladi tarkibiy birlik ). Shunday qilib, elementar birikma ham ushbu to'plamda 1 qiymatini oladi, lekin barcha n o'lchovli mantiqiy vektorlar yechimida nolga yo'qoladi. Keling, formulani ko'rib chiqaylik
unda summa (obedannaya) barcha to'plamlarga kengaytiriladi (t 1, . qo'shing.
Shuni ta'kidlash kerakki, P formulasi tinchlanish uchun 1 ga aylanadi va faqat ushbu qiymatlar uchun o'zgaradi, siz ko'rib turganingizdek, u 1 funktsiyaga aylanadi. Shuningdek, r formulasi f funksiyani ifodalaydi.
Naslidok 1.1. Standart asos oxirgi hisoblanadi.
◀ Funktsiya doimiy 0 bo'lmagani uchun u standart asosda formula bo'lgan SDNF ko'rinishida ham ko'rinadi. Doimiy 0 ni, masalan, f(x 1, x 2, .. , x n) = x 1 x 1 formulasi bilan ifodalash mumkin.
dumba 1.2. m(x 1, x 2, x 3) uchta o'zgarish funksiyasini ko'rib chiqamiz (1.4-jadval), deyiladi. majoritar funksiya ̆. Agar uning argumentlarining yarmidan ko'pi 1 qiymatiga ega bo'lsa, bu funktsiya 1 qiymatini oladi. Shuning uchun u ko'pincha ovoz berish funktsiyasi deb ataladi. Keling, u uchun SDNF qilaylik.
Standart asosning to'liqligi boshqa yangi funktsiyalar tizimlarini tanlash imkonini beradi. F ko'paytirgichning ko'pligi bunday qiymatlar yordamida o'rnatilishi mumkin. Tasavvur qilaylik, standart signalning uchta funktsiyasiga ega teri F ustidagi formula bilan ifodalanishi mumkin. 1.3 teorema va F bilan bir xil bo'ladi.
dumba 1.3. Shaxssiz operatsiya moduli 2, ko'paytirilgan va doimiy 1 deyiladi Jegalkin asosi . 2-moduldan keyin qo'shish va ko'paytirish - Z2 halqasining asosiy operatsiyalari, ifodalar, ularning yordami bilan qo'shimchalar - Z2 halqasi ustida juda ko'p atamalar mavjud. Bu holatda 1 doimiysi to'g'ri atama yozish uchun zarur. Agar xx = x bo'lsa, ko'phadga barcha qo'shimchalar 1-bosqichga ega. Shuning uchun ko'phadni yozishda siz qadam tushunchasisiz ham qilishingiz mumkin. Jegalkin asosida formulalarni qo'llang:
xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.
Agar bunday formula Zhegalkin ko'phad deb ataladi. Aslida, Zhegalkin polinomi Z2 halqasi ustidagi boy atamadir.
Standart asosni katlama va kodlash operatsiyalarini ifodalovchi Zhegalkin asosida formulalarni qurish muhim emas (ikki asosni alohida ko'paytirish):
x+y=x⊕y⊕xy, x =x⊕1.
Shuning uchun, Jegalkinning asosi shaxsiy emas.
Ko'rsatish mumkinki, har qanday mantiqiy funktsiya uchun Jegalkin polinomi yagona tayinlangan
(aniqrog'i, qo'shimchalar tartibiga qadar). Kam sonli o'zgaruvchilarga ega bo'lgan Zhegalkin polinomining koeffitsientlarini ahamiyatsiz koeffitsientlar usuli yordamida hisoblash mumkin.
dumba 1.4. Keling, bitta funktsiyani - Schaeffer zarbasini * batafsil ko'rib chiqaylik. Bu mutlaqo shaxsiy emas, bu osongina tekshirilishi mumkin bo'lgan bevosita o'xshashliklardan kelib chiqadi:
x = x | x, xy = x | y = (x | y) | (x | y), x + y = x | y = (x | x) | (y | y).
dumba 1,5. Bitta funktsiyadan hosil bo'lgan asos - Pirs o'qlari ham yangi. Buning teskarisi Schaeffer zarbasini qaytarishga o'xshaydi. Bundan tashqari, ushbu tartib nosimmetrik halqalar uchun ikkilik printsipi asosida ham ishlab chiqarilishi mumkin.
*Sxeffer zarbasi ikkilik va assotsiativ operatsiya emas. Shuning uchun, boshqa infix shakli bilan quyidagilar muhim: natija operatsiya tartibiga bog'liq. Va bu erda qo'shimcha tutqichlar yordamida operatsiyalar tartibini aniq ko'rsatish tavsiya etiladi, masalan, yozish (x | y) | z, va chi emas x | y | z, men formalarni teng ravishda ranjitmoqchiman.
Qiymat 1.Konyunktiv monomial (elementar birikma) O'zgarish turi bu o'zgaruvchanlarning birikmasi deb ataladi.
Masalan, - Boshlang‘ich bog‘lovchi.
Qiymat 2.Dizyunktiv monomial (elementar dis'yunksiya) O'zgarishlar orasida bu o'zgarishlarni ajratish va ularni blokirovka qilish deyiladi.
Masalan, - Elementar dis'yunktsiya.
Qiymat 3. Algebraning qadimgi formulasidan olingan va elementar kon'yunktiv monomiallarning dis'yunksiyasi bo'lgan formula deyiladi. disjunktiv normal shakl(DNF) bu formulalar.
Masalan,- DNF.
Qiymat 4. Algebraning qadimgi formulasidan kelib chiqqan va elementar ayiruvchi monomiallarning birikmasidan iborat formula deyiladi. konyunktiv normal shakl(CNF) bu formulalar.
Masalan, - KNF.
Teri algebrasi uchun formulalarni hech qanday ajratuvchi va kon'yunktiv normal shakllarsiz topish mumkin.
Oddiy shakllarni yaratish algoritmi
Mantiq algebrasining ekvivalentligidan foydalanib, formulada ko'rsatilgan barcha amallarni asosiylari bilan almashtiring: konyunksiya, dis'yunksiya, sanab o'tish:
Himoyalangan xavfsizlik tizimining belgilarini tan oling.
Agar kerak bo'lsa, taqsimlash kuchi va takomillashtirish formulasining birikmasi va dis'yunksiyasi operatsiyasidan oldin umumlashtirish.
2.6. To'liq dis'yunktiv va to'liq kon'yunktiv normal shakllar
Funktsiya mantiqiy bo'ladimi, u ko'p jihatdan DNF va CNF shaklida o'zini namoyon qilishi mumkin. Ayniqsa, bu hodisalarning o'rtasida DNF (SDNF) va skelet KNF (SKNF) muhim ahamiyatga ega.
Qiymat 1. Oddiy shakl butunlay disjunktivdir(SDNF) - bu DNF bo'lib, unda terining teri kon'yunktiv monomiali to'plamga aynan bir marta kiritilishi kerak va u o'zi yoki boshqasi tomonidan kiritilishi kerak.
Strukturaviy ravishda, DNF ga kiritilgan hosila algebrasining teri formulasining SDNF ni quyidagicha hisoblash mumkin:
Qiymat 2. Oddiy shakl butunlay disjunktivdir(SDNF) algebraik formulalar DNF deb ataladi, chunki ular kuchga kirishi mumkin:
Qiymat 3. To'liq kon'yuktiv normal shakl(SKNF) - bu KNF bo'lib, unda terining dis'yunktiv monomialini to'plamdan bir marta o'zgartirish mumkin va u o'zi yoki boshqasi tomonidan kiritilishi kerak.
Strukturaviy ravishda, CNFga induktsiya qilingan vizualizatsiya algebrasining teri formulasining SCNF ni quyidagicha hisoblash mumkin.
Qiymat 4. To'liq kon'yuktiv normal shakl(SKNF) bu algebra formulasi shunday vakolatlarni qanoatlantiradigan CNF deb ataladi.
Teorema 1. Teri Boolean funktsiyasi, albatta, halokatli bo'lmasa ham, SDNFda va bitta tartibda ifodalanishi mumkin.
SDNF ni topish usullari
1-usul
2-usul
Formula 1 qiymatini qo'shadigan qatorlarni ko'rishingiz mumkin;
Biz ong uchun birikma bilan disjunksiya hosil qilamiz, agar 1 qiymatlari bilan birikma kiritish mumkin bo'lsa, u holda bu o'zgarishni yozamiz, agar 0 qiymatlari bo'lsa, ular almashtiriladi. Biz SDNFni rad etamiz.
Teorema 2. Teri Boolean funktsiyasi, albatta, to'g'ri bo'lmasa ham, SCNFda va xuddi shu tarzda ifodalanishi mumkin.
SKNFni bilish usullari
1-usul- Teng kuchlardan yordam olish uchun qayta yarating:
2-usul- Mana yordam uchun haqiqat jadvali:
Formula 0 qiymatini yaratadigan qatorlarni ko'rishingiz mumkin;
Biz ong uchun dis'yunksiyaning birikmasini shakllantiramiz, shunda agar dis'yunksiya 0 qiymatlari bilan kiritilsa, biz bu o'zgarishni yozamiz, agar qiymatlar 1 bo'lsa, ular qo'shiladi. Biz SKNFni rad etamiz.
dumba 1. CNF funksiyalarini sinab ko'ring.
Qaror
O'zgarishlarni o'zgartirishning qo'shimcha qonunlari uchun "" havolasini kiritamiz:
= / De Morgan qonunlari va kichik bo'limi / =
/distributiv qonunlar/ =
dumba 2. Formulani DNF ga kamaytiring.
Qaror
Shubhasiz mantiqiy operatsiyalar va orqali:
= /o'zgarishlar kiritilgunga qadar va tezda ro'yxatga olinmaguncha ro'yxatga kiritiladi/ =
= / Taqsimlanish qonuni / .
dumba 3. Formulani DNF va SDNF da yozing.
Qaror
Vikoristik mantiq qonunlari, keling, ushbu formulani elementar birikmalarning disjunksiyalarini bartaraf etadigan shaklga keltiraylik. Formula o'chirildi va DNFga aylanadi:
SDNF dan foydalanish uchun biz ushbu formula uchun haqiqat jadvalini yaratamiz:
Bular jadvalning formulasi (qolgan ustun) 1 qiymatini qabul qiladigan qatorlardir. Har bir shunday satr uchun biz ushbu qatorning o'zgaruvchilar to'plamida ishlaydigan formula yozamiz:
1-qator: ;
3-qator: ;
5-qator:.
Ushbu uchta formulaning diszyunksiyasi faqat 1, 3, 5-qatorlardagi almashinishlar to'plamida 1 qiymatini oladi va shuningdek, chuqur izlangan disjunktiv normal shakl (SDNF) bo'ladi:
dumba 4. Formulani SKNF ga ikki usulda sozlang:
a) teng kuchlar yordami uchun;
b) qo'shimcha haqiqat jadvali bilan.
Qaror:
Elementar disjunksiyani teskari aylantiramiz:
Formula quyidagicha ko'rinadi:
b) ushbu formula uchun haqiqat jadvalini tuzing:
Formula (qolgan ustun) 0 qiymatini oladigan jadval qatorlarini ko'rsatadi. Har bir shunday qator uchun biz ushbu qatorning o'zgaruvchilar to'plamiga to'g'ri bo'lgan formulani yozamiz:
2-qator: ;
6-qator:.
Ushbu ikkita formulaning birikmasi 0 qiymatini faqat 2 va 6-qatorlardagi o'zgarishlar to'plamida qabul qiladi va shuningdek, batafsil izlangan kon'yunktiv normal shakl (SCNF) bo'ladi:
Mustaqil o'sish uchun ovqatlanish
1. Ekvivalent transformatsiyalar yordamida DNF ga formulalarni keltiring:
2. Ekvivalent transformatsiyalar yordamida formulalarni CNF ga keltiring:
3. Boshqa distributiv qonundan foydalanib, DNF ni CNF ga aylantiring:
A) 
;
4. DNF vazifalarini SDNF ga aylantiring:
5. KNF vazifalarini SKNF ga aylantiring:
6. Mantiqiy formulalarni o'rnatish uchun SDNF va SCNF dan ikki usulda foydalaning: teng o'zgartirishlardan foydalanish va qo'shimcha haqiqat jadvalidan foydalanish.
b) 
;