8 §. Formulalarning normal shakllari (dnf va knf)

8 - §. Formulalarning normal shakllari (DNF va KNF)
Ta'rif: Oddiy disjunksiya (inklyuziv disjunksiya) yoki disjunkt (inglizcha disjunct) bu bir yoki bir nechta o'zgaruvchilarning disjunksiyasi yoki ularning inkorlari bo'lib, har bir o'zgaruvchi bir martadan ko'p bo'lmagan holda sodir bo'ladi.
Oddiy disyunktsiya

• 
  har bir o'zgaruvchi (yoki uning inkor etilishi) unda bir marta paydo bo'lsa to'liq;
  
• 
  monoton, agar u o'zgaruvchini inkor qilmasa.
  

Ta'rif: Konjunktiv normal shakl, KNF (inglizcha conjunctive normal form, CNF) - mantiqiy funktsiya bir nechta sodda gaplarning birikmasi shakliga ega bo'lgan normal shakl.
KNF misoli:
Ta'rif: Perfect conjunctive normal form, PCNF (mukammal kon'yunktiv normal shakl, PCNF) bu quyidagi shartlarga javob beradigan CNF:

• 
  unda bir xil sodda ajratmalar mavjud emas
  
• 
  h ar bir oddiy disjunktsiya tugallangan
  

SKNF misoli:

Teorema: Identifikatsiya birligiga teng bo'lmagan har qanday mantiqiy f (x⃗) funktsiyasi uchun uni belgilaydigan SKNF mavjud.

Dalillar: Funktsiya inversiyasidan beri ¬f (x⃗) f (x⃗) nolga teng bo lgan yo nalmalardagi biriga teng, keyin ¬f (x⃗) uchun SDNF quyidagicha yozilishi mumkin:

bu erda σi xi da inkorning mavjudligini yoki yo'qligini bildiradi
Ifodaning chap va o'ng tomonlariga teskari toping:

O'ng tomonda olingan ifodaga de Morgan qoidasini ikki marta qo'llasak, quyidagilarga erishamiz:

Oxirgi ifoda SKNF. SKNF bir xil nolga teng bo'lmagan har qanday funktsiya uchun tuzilishi mumkin bo'lgan SDNF-dan olinganligi sababli, teorema isbotlangan.
Haqiqat jadvali bo'yicha SKNFni qurish algoritmi

1. 
   Haqiqat jadvalida biz funktsiyaning qiymati 0 ga teng bo'lgan o'zgaruvchilar to'plamlarini belgilaymiz.
   

2. Belgilangan har bir to'plam uchun biz barcha o'zgaruvchilarning disjunktsiyasini quyidagi qoidaga muvofiq yozamiz: agar ba'zi bir o'zgaruvchilarning qiymati 0 ga teng bo'lsa, u holda o'zgaruvchining o'zi disjunktsiyaga kiritilgan, aks holda uning inkor qilinishi.
3. Natijada paydo bo'ladigan barcha ajratishlarni birikma operatsiyalari bilan bog'laymiz.
Media uchun SKNF qurishga misol. SCNF-ni uchta argument medianasi uchun belgilash

1. 
   Haqiqat jadvalida funktsiya qiymati 0 ga teng bo'lgan o'sha o'zgaruvchilar to'plamini belgilaymiz.
   

2. Belgilangan har bir to'plam uchun biz barcha o'zgaruvchilarning birikmasini quyidagi qoidaga muvofiq yozamiz: agar ba'zi bir o'zgaruvchilarning qiymati 0 ga teng bo'lsa, u holda biz o'zgaruvchining o'zini disjunksiyaga kiritamiz, aks holda uning inkor qilinishi.

3. Olingan barcha ajratmalar konyunksiya operatsiyalari bilan bog'langan.

SCNF-ni beshta dalilning medianasi uchun belgilash


Ba'zi funktsiyalar uchun SKNF misollari
Pirsning o'qi:

Eksklyuziv yoki:

KNFni qurish algoritmi

1. 
   formulada mavjud bo'lgan barcha mantiqiy operatsiyalardan xalos bo'ling, ularni asosiylari bilan almashtiring: birikma, disjunksiya, inkor. Buni teng keladigan formulalar yordamida amalga oshirish mumkin:
   

2) formulalar asosida individual o'zgaruvchan bayonotlarga murojaat qilib, inkor belgisini butun iborani nazarda tutib, inkor belgilariga almashtiring:

3) Ikkita inkor belgilaridan xalos bo'ling.
4) agar kerak bo'lsa, tarqatish xususiyatlarini va assimilyatsiya formulasini birlashtirish va ajratish operatsiyalariga qo'llang.
KNFni qurishga misol. KNF ga formulani keltiramiz:

Keling, formulani o'zgartiramiz F o'z ichiga olmaydi formulaga

Olingan formulada biz inkorni o'zgaruvchiga o'tkazamiz va ikki barobar salbiyni kamaytiramiz:

Tarqatish qonuniga ko'ra biz CNFni olamiz:

k-konjunktiv normal shakli
K-kon'yunktiv normal shakl - bu har bir disjunktsiya tarkibida to'liq k literallarni o'z ichiga olgan konjunktiv normal shakl.
Masalan, 2-CNF da quyidagi formula yozilgan:

K NF dan SKNF ga o'tish. Agar oddiy disjunktsiyada ba'zi bir o'zgaruvchilar etishmayotgan bo'lsa (masalan, z), unda unga ifodani qo'shing: (bu disjunktsiyani o'zi o'zgartirmaydi) , keyin tarqatish qonuni yordamida qavslarni ochamiz:

Shunday qilib, CNFdan biz SKNFni otkazdik.
Ta'rif: Oddiy birikma (inglizcha qo'shma birikma) yoki qo'shma (inglizcha kon'yunktuk) bir yoki bir nechta o'zgaruvchilarning birikmasi yoki ularning inkorlari bo'lib, har bir o'zgaruvchi bir martadan ortiq bo'lmaydi.
Oddiy birikma

• 
  har bir o'zgaruvchi (yoki uning inkor etilishi) unda to'liq 1 marta paydo bo'lsa to'liq;
  
• 
  monoton, agar u o'zgaruvchini inkor qilmasa.
  

Ta'rif: Disjunctive normal form, DNF (inglizcha disjunctive normal form, DNF) - bu mantiqiy funktsiya bir nechta sodda qo'shimchalarning disjunksiyasi shakliga ega bo'lgan normal shakl.
DNF misoli:
Ta'rif: Perfect disjunctive normal form, SDNF (English perfect disjunctive normal form, PDNF) - DNF, shartlarni qondiradigan:

• 
  unda bir xil sodda bog‘lovchilar mavjud emas,
  
• 
  har bir oddiy birikma tugallangan.
  

S DNF misoli:
Teorema: Bir xil nolga teng bo'lmagan har qanday mantiqiy funktsiya uchun f (x⃗) uchun uni belgilaydigan SDNF mavjud.
Dalillar: Mantiqiy funktsiyalar uchun Shannon kengayishi deb nomlangan quyidagi munosabat quyidagicha bo'ladi:

Ushbu munosabatni xi (0 va 1) ning mumkin bo'lgan qiymatlarini almashtirish orqali osongina tekshirish mumkin. Ushbu formula xi funktsiyasini belgisidan tashqariga qo'yishga imkon beradi. X (x) belgisi tashqarisiga x1, x2,.., f(x⃗ ),ni ketma-ket joylashtirib, quyidagi formulani olamiz:


Ushbu munosabatni har bir o'zgaruvchiga qo'llash birlashtiruvchi sonini ikki baravar ko'paytirganligi sababli, n o'zgaruvchining vazifasi uchun bizda bog`lovchilar. Ularning har biri funksiyaning bittasidagi qiymatiga mos keladi
n o'zgaruvchi uchun mumkin bo'lgan qiymatlar to'plami. Agar biron bir to'plamda bo'lsa f(x⃗ )=0 u holda butun mos keladigan kon'yunkt ham nolga teng bo'ladi va uni ushbu funktsiya vakilligidan chiqarib tashlash mumkin. Agar
f(x⃗ )=1 u holda mos keladigan kon'yunkturada funktsiyaning o'zi qiymati tushirib qo'yilishi mumkin. Natijada, ixtiyoriy funktsiya uchun SDNF qurildi.
Median uchun SDNF qurishga misol. Uch dalil medianasi uchun SDNF qurilishi
1. Haqiqat jadvalida biz funktsiyaning qiymati 1 ga teng bo'lgan o'zgaruvchilar to'plamlarini belgilaymiz.


2. Belgilangan har bir to'plam uchun biz barcha o'zgaruvchilarning bog'lanishini quyidagi qoidaga binoan yozamiz: agar ba'zi bir o'zgaruvchilarning qiymati 1 ga teng bo'lsa, u holda o'zgaruvchini o'zi qo'shilishga, aks holda uning inkorini kiritamiz.

3. Hosil bo'lgan barcha bog'lovchilar ajratish operatsiyalari bilan bog'lanadi:

Beshta dalilning medianasi uchun SDNF qurilishi



B a'zi funktsiyalar uchun SDNF misollari
Perfect disjunctive normal shakli. Funktsiyasi biriga teng bo'lgan o'zgaruvchilar to'plamini olaylik, agar bu to'plamdagi o'zgaruvchining qiymati 0 ga teng bo'lsa, u holda bu o'zgaruvchi inkor bilan qabul qilinadi, agar ushbu to'plamdagi o'zgaruvchining qiymati 1 ga teng bo'lsa keyin bu o'zgaruvchi inkor qilinmasdan olinadi.
Ushbu to'plamga mos keladigan barcha o'zgaruvchilarni & (va qisqartirish uchun & belgisini qo'yib yuborish) belgisi bilan birlashtirsak, biz elementar birikmani olamiz.Shunda o'zgaruvchilar qiymatlari to'plamiga mos keladigan barcha elementar birikmalarning ajralishi, bu erda funktsiya biriga teng, asl funktsiyasini tiklaydi. Bu bizning funktsiyamizning mukammal disjunktiv normal shakli (SDNF).
Mukammal kon'yunktiv normal shakl. Funktsiyasi nolga teng bo'lgan o'zgaruvchilar to'plamlarini oling. Agar bu to plamdagi o zgaruvchining qiymati 0 ga teng bo lsa, u holda bu o zgaruvchi inkor etilmaydi, agar ushbu to plamdagi o zgaruvchining qiymati 1 ga teng bo lsa, u holda bu o zgaruvchi inkor bilan olinadi.
Ushbu to'plamga mos keladigan barcha o'zgaruvchilarni belgi bilan bog'lab, biz elementar disjunktsiyani qo'lga kiritamiz.Shunda funktsiya nolga teng bo'lgan o'zgaruvchilar qiymatlari to'plamlariga mos keladigan barcha elementar ajratmalarning birikmasi asl funktsiyani tiklaydi Bu bizning funktsiyamizning mukammal kon'yunktiv normal shakli (SCNF) bo'lib, qisqartirish uchun & belgisi qoldiriladi.
Disjunktiv normal shakllarni minimallashtirish
1. Implikant. Mantiqiy funktsiya g mantiqning implikanti deyiladi
funktsiya f, agar ushbu funktsiyalar argumentlarining har qanday qiymatlar to'plami uchun g = 1 tenglik f = 1 tenglikni bildiradi.
Birlashtiruvchi normal shakllarni minimallashtirish
Funktsiyasining minimal kon'yunktiv normal shaklini (MCNF) qurish uchun f funktsiyasining minimal DNFini (f funktsiyasini inkor qilish) qurish kerak va natijada minimal DNF da & ishorasini belgi bilan almashtiring, o'rnini almashtiring bilan belgilang va har bir o'zgaruvchiga manfiy belgini qo'ying.Bu f funktsiyasining minimal CNF bo'ladi, shunda x (ikkita inkor) = x ekanligini hisobga olamiz.
misoldan f funktsiyasining minimal CNF ni tuzamiz. F funktsiyasi uchun haqiqat jadvalini tuzamiz.Bu qiymat uchun 0 ni 1 ga almashtiring va 1 ni 0 ga almashtiring.