Ikkilik printsipi. o'zgaruvchilarda mantiqiy funktsiyalarni kengaytirish. mukammal ayiruvchi va konyunktiv normal shakllar. Laboratoriya ishi Mantiqiy funksiyalar algebrasi (Mantiqiy funksiyalar) Mantiqiy funksiya kengayishi teoremasi

Shunda f(x 1, x 2, x 3) funksiyani ikkita o‘zgaruvchining ikkita funksiyasining diszyunksiyasi sifatida ko‘rsatish mumkin va bu formula quyidagicha ko‘rinishga ega bo‘ladi:

Quyidagi formulalarni ko'rib chiqing:

Birinchi formulaning chap tomoni o'ngga ekvivalent bo'ladi, chunki x 1 =0 uchun va birikma amaliga muvofiq. Ikkinchi formulaning haqiqiyligini xuddi shunday ko'rsatish mumkin. Shunday qilib, ushbu formulalarni oldingi disjunctionga qo'yib, biz quyidagilarni olamiz:

Bu ifoda f(x 1 ,x 2 ,x 3) funksiyaning x 1 oʻzgaruvchiga nisbatan kengayishi deyiladi.

Endi xuddi shunday x 2 da f(0,x 2 ,x 3) va f(1,x 2 ,x 3) funksiyalarini kengaytirishimiz mumkin. Oling

Ushbu formulalarni oldingilariga almashtirib, biz olamiz

Operatsiyaning taqsimlanishiga muvofiq &, biz x 1 o'zgaruvchisini va uning qavs ichiga inversiyasini kiritamiz, biz olamiz

Umuman olganda, f(x 1 ,x 2 ,..,x n) funksiyasi uchun n oʻzgaruvchining m oʻzgaruvchidagi kengayishi (m £ n) koʻrinishga ega boʻladi.

bunda dis'yunksiya x 1 ,x 2 ,..,x m o'zgaruvchilarning barcha 2 m to'plamidan olinadi.

m=n bo'lganda ekstremal holatda parchalanishni (*4) ko'rib chiqaylik. (misolga qarang (*3)).

Keyin barcha birikmalarda har bir sobit to'plamdagi f funktsiyasining qiymatlari nolga yoki birga teng qiymatlarga ega bo'ladi. Barcha nol birikmalarni olib tashlab, biz yangi parchalanishni olamiz va bu yangi parchalanishda biz birikmalardagi funktsiyalar omillarini olib tashlaymiz, chunki ular 1 ga teng. Qolgan ifoda CDNF (mukammal disjunktiv normal shakl) deb ataladi.

Bularning barchasini, masalan, (*3) qilaylik.

Berilgan to‘plamlarda f funksiyaning nol qiymatiga ega bo‘lgan (*3) birikmalarni olib tashlaganimizdan so‘ng biz quyidagilarni olamiz:

Chunki haqiqat jadvaliga ko'ra

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

keyin bog‘lovchilardan funksiya omillarini olib tashlaymiz, shundan so‘ng biz quyidagilarni olamiz:

Bu mantiqiy f funktsiyaning mukammal dis'yunktiv normal shaklidir.

Lemma. Har qanday mantiqiy funktsiya (doimiy "0" dan tashqari) PDNFga ega va faqat bitta.

Xuddi shunday, siz konyunktiv shaklni kiritishingiz mumkin,

Jadval orqali berilgan funksiya uchun SDNF ni qurish

Bu xulosa konstruktivdir, chunki funktsiya jadvaliga ko'ra, u SDNF (agar ) bo'lgan formulani yaratishga imkon beradi.
sdnf funktsiyalari f Jadvalda qancha bo‘lsa, shuncha bog‘lovchi mavjud f; har bir "bitta" to'plamga (d 1 ,…,d n), bular. funktsiya qiymati 1 ga teng bo'lgan to'plam barcha o'zgaruvchilar konjunksiyasiga mos keladi. x i salbiy bilan qabul qilingan if d i=0, va agar inkor qilmasdan d i =1.

Vakillik masalasini ko'rib chiqing n-lokal mantiqiy funksiya f(x 1 ,x 2 ,…,x n) ba'zi bir taklif algebra formulasi bilan.

Belgilanishni kiritamiz, bu erda parametr 0 yoki 1 ga teng.

Bu aniq

1.1 teorema. Mantiq algebrasining har bir funksiyasif(x 1 , x 2 ,…, x n ) har qanday uchunm (1£ m £ n) quyidagi shaklda ifodalanishi mumkin:

bu erda disjunksiya o'zgaruvchilarning barcha mumkin bo'lgan qiymatlari to'plamidan olinadi.

Isbot. Berilgan funktsiyaning barcha o'zgaruvchilari qiymatlarining ixtiyoriy to'plamini ko'rib chiqing. Keling, ushbu to'plamda (1) formulaning chap va o'ng qismlari bir xil qiymatga ega ekanligini ko'rsatamiz. Chap tomoni , to'g'ri

chunki , agar faqat , agar , agar , u holda tegishli mantiqiy atama o'chirilishi mumkin.

Izoh. Teoremada ko'rsatilgan funktsiyaning ifodalanishi funktsiyaning ni bo'yicha kengayishi deyiladi m o'zgaruvchilar.

Xulosa 1(bir o'zgaruvchida kengaytirish).

Bunday holda, funktsiyalar va chaqirdi parchalanish komponentlari.

Natija 2(barcha o'zgaruvchilarda kengayish).

Shubhasiz, agar , keyin

Shunday qilib, agar funktsiya f(x 1 ,x 2 ,…,x n) bir xil noto'g'ri funksiya bo'lmasa, u holda uni ekvivalent formula bilan ifodalash mumkin, bu shaklning turli ko'paytmalarining mantiqiy yig'indisi , va bunday tasvir yagonadir.

Formula (2) shaklini juda soddalashtirish mumkin. Ma'lumki, mantiq algebrasining har qanday formulasini faqat konyunksiya va inkor yoki dis'yunksiya va inkorni o'z ichiga olgan formulaga ekvivalent o'zgartirishlar yordamida kamaytirish mumkin. Ekvivalent o'zgarishlarni amalga oshirish natijasida bir nechta formulalarni olish mumkin, ammo ulardan faqat bittasi quyidagi xususiyatlarga ega bo'ladi:

1. Har bir mantiqiy atama formulaga kiritilgan barcha o'zgaruvchilarni o'z ichiga oladi f(x 1 ,x 2 ,…,x n).

2. Hech bir mantiqiy atama o‘zgaruvchini ham, uning inkorini ham o‘z ichiga olmaydi.

3. Formuladagi barcha mantiqiy atamalar har xil.

4. Hech bir mantiqiy atama bir xil o‘zgaruvchini ikki marta o‘z ichiga olmaydi.

Ushbu to'rtta xususiyat deyiladi mukammallik xususiyatlari(yoki C ning xususiyatlari).

Agar f(x 1 ,x 2 ,…,x n) haqiqat jadvali bilan berilgan bo'lsa, unda tegishli mantiqiy algebra formulasini juda oddiy tarzda tiklash mumkin. Barcha argument qiymatlari uchun x 1 ,x 2 ,…,x n, qaysi vaqtda f 1 qiymatini oladi, siz birikma muddatini hisobga olgan holda takliflarning elementar o'zgaruvchilari birikmasini yozishingiz kerak. x i, agar x i=1, va agar x i=0. Barcha qayd etilgan qo‘shma gaplarning diszyunksiyasi zarur formula bo‘ladi. Qadriyatlar haqida f 0 tashvishlanishingizga hojat yo'q, chunki formuladagi tegishli atama 0 ga teng bo'ladi va ekvivalentlik tufayli bekor qilinishi mumkin fÚ 0 ≡ f.

Masalan, funksiyaga ruxsat bering f(x, y, z) quyidagi haqiqat jadvaliga ega:

O'zgaruvchilarda mantiqiy funktsiyalarning parchalanishi.

G 0 yoki 1 ga teng parametr bo'lsin. Belgilashni kiritamiz:

Buni tekshirish orqali tekshirish oson x G = 1 agar va faqat agar x= G. Bundan kelib chiqadiki, birikma 1 ga teng (bu erda G 0 yoki 1 ga teng), agar va faqat . Masalan, birikma (bunda G 2 \u003d G 1 \u003d 0, G 3 \u003d G 4 \u003d 1) faqat agar bo'lsa, 1 bo'ladi. x 1 = x 2 = 0, x 3 = x 4 = 1.

Teorema 1Har qanday mantiqiy funktsiya f(x 1 ,x 2 ,…,x n) quyidagi shaklda ifodalanishi kerak:

bu yerda 1 ≤ k ≤ n, dis'yunksiyada o'zgaruvchan qiymatlarning barcha to'plamlari ustidan olinadi.

Bu tasvir funksiyaning o‘zgaruvchilar bo‘yicha kengayishi deyiladi. Masalan, n = 4, k = 2 uchun kengayish (3.1) quyidagi ko'rinishga ega:

.

Kengayishni isbotlaymiz (3.1). Buning uchun ixtiyoriy o'zgaruvchan qiymatlar to'plamini oling . (3.1) munosabatning chap va o'ng tomonlari bir xil qiymat olishini ko'rsatamiz. Haqiqatan ham, beri x G = 1 agar va faqat agar x= G, u holda 2 ta orasida (3.1) ning o'ng tomonining faqat bitta birikmasi birlikka aylanadi, bunda . Boshqa barcha birikmalar nolga teng.

Shu sababdan . Kengayishning natijasi (3.1) sifatida biz quyidagi ikkita maxsus kengaytmani olamiz.

O'zgaruvchan kengayish x n:

Agar mantiqiy funktsiya doimiy 0 bo'lmasa, u holda kengayish haqiqiydir

Barcha o'zgaruvchilarda kengayish:

, (3.3)

bu erda dis'yunksiya barcha to'plamlar ustidan olinadi , buning uchun funksiya qiymati 1 ga teng.

Dekompozitsiya (3.3) odatda funksiyaning mukammal disjunktiv normal shakli (qisqartirilgan SDNF belgisi) deb ataladi.

Parchalanish (3.3) SDNFni qurish yo'lini beradi. Buning uchun haqiqat jadvalida barcha qatorlarni belgilang , unda . Har bir bunday qator uchun biz bog'lovchi hosil qilamiz va keyin barcha hosil bo'lgan bog'lanishlarni ajratish belgisi bilan bog'laymiz.

Dᴀᴋᴎᴍ ᴏsᴩᴀᴈᴏᴍ, funktsiyaning haqiqat jadvali o'rtasida yakkama-yakka muvofiqlik mavjud va uning SDNF. Va bu mantiqiy funksiya uchun SDNF noyob ekanligini anglatadi.

Sdnf ga ega bo'lmagan bitta mantiqiy funktsiya doimiy 0 dir.

1-misol Funksiyaning mukammal ayiruvchi shaklini toping .

Bu funksiya uchun haqiqat jadvalini tuzamiz:

Bu erdan biz olamiz: = = .

Mantiq algebrasida mantiqiy funktsiyalarning quyidagi parchalanishi muhim rol o'ynaydi.

Teorema 2Har qanday mantiqiy funktsiya quyidagi shaklda taqdim etilishi kerak:

bu yerda 1≤k≤n va birikma olinadi barcha 2 k o'zgaruvchan qiymatlar to'plamida.

Haqiqatan ham, ruxsat bering o'zgaruvchan qiymatlarning ixtiyoriy to'plamidir. (3.4) munosabatning chap va o'ng qismlari bir xil qiymat olishini ko'rsatamiz. Faqat qachondan beri , keyin 2 k disjunksiyalar orasida (3.4) ning o'ng tomonida faqat bittasi yo'qoladi, unda . Boshqa barcha disjunctionlar 1 ga teng.

Shu sababdan = = .

Mantiqiy funktsiyalarning kengayishi to'g'ridan-to'g'ri kengaytirishdan kelib chiqadi (3.4):

Oxirgi parchalanish mukammal kon'yunktiv normal shakl (CKNF) deb ataladi. Parchalanish (3.6) SKNFni qurish yo'lini beradi. Buning uchun haqiqat jadvalida biz barcha qatorlarni belgilaymiz. Har bir bunday qator uchun biz disjunction hosil qilamiz keyin esa barcha hosil bo‘lgan qo‘shma gaplarni bog‘lovchi belgisi bilan bog‘laymiz. Dᴀᴋᴎᴍ ᴏsᴩᴀᴈᴏᴍ, funktsiyaning haqiqat jadvali o'rtasida yakkama-yakka muvofiqlik mavjud va uning SKNF. Va bu mantiqiy funktsiya uchun SKNF noyob ekanligini anglatadi.

SKNF ga ega bo'lmagan yagona mantiqiy funktsiya doimiy 1 hisoblanadi.

2-misol Funksiyaning mukammal konyunktiv normal shaklini toping .

Bu funksiya uchun haqiqat jadvalini tuzamiz.

Bu erdan biz SKNFni olamiz

Shakl formulasi (qisqa belgi), bu erda - bog‘lovchilar chaqirdi disjunktiv normal shakl (DNF).

DNF ning yuqoridagi ta'rifi tufayli, masalan, iboralar bo'ladi: , .

2.2-bandda ta'kidlanganidek, barcha mantiqiy operatsiyalarni uchtaga qisqartirish mumkin: birikmalar, disjunctionlar va inkorlar. Bundan tashqari, de Morgan qonunini hisobga olgan holda, inkor belgisi faqat o'zgaruvchilarga tegishli deb taxmin qilish mumkin.

Endi distributiv qonundan foydalanib, qavslarni ochamiz va ayiruvchi normal shaklni olamiz. Demak, quyidagi teorema haqiqatdir.

Teorema 3 Mantiq algebrasining har qanday formulasi uchun unga ekvivalent bo'lgan dis'yunktiv normal shakl mavjud.

Bu teoremaning isboti mantiq algebrasidagi har qanday formula uchun disjunktiv normal shaklni qurish usulini beradi.

3-misol Quyidagi formula uchun disjunktiv normal shaklni toping: .

Qonun bo'yicha belgi bundan mustasno va de Morgan qonunlarini va ikkilamchi inkorni qo'llash orqali biz quyidagilarni olamiz:

Keyin taqsimot qonunini qo'llagan holda, biz qavslarni kengaytiramiz

Oxirgi ifoda disjunktiv normal shakldir.

Shaklni ko'rish (qisqa belgi), bu yerda disjunksiyalar chaqirdi kon'yunktiv normal shakl (CNF).

Bu, masalan, iboralar:

, .

Yuqorida ko'rsatilganidek, mantiq algebrasining har qanday formulasi uchun unga ekvivalent bo'lgan dis'yunktiv shakl mavjud. Distribyutor qonunidan foydalanib, berilgan DNF dan CNF ni olish oson.

Demak, quyidagi teorema haqiqatdir.

Teorema 4 Mantiq algebrasining har qanday formulasi uchun unga ekvivalent konyunktiv normal shakl mavjud.

Bu teoremaning isboti mantiq algebrasidagi har qanday formula uchun kon’yunktiv normal shaklni qurish yo‘lini beradi.

4-misol Quyidagi formula uchun ayiruvchi va konyunktiv normal shakllarni toping: .

Qonundan foydalanish , biz belgini istisno qilamiz. Biz formulani olamiz.

De Morgan qonunidan foydalanib, formulani olamiz . Qavslarni kengaytirib, biz disjunktiv normal shaklni olamiz

.

Konyunktiv normal shaklni olish uchun formulaga murojaat qiling taqsimlash qonuni, biz olamiz:

Oxirgi ifoda konyunktiv normal shakldir. Chunki va , natijada olingan CNF quyidagi CNF ga ekvivalentdir:

Ushbu formulaning barcha normal formulalari orasida biz ayirma va kon'yunktiv mukammal normal shaklni ajratamiz. Dekompozitsiyani (3) ko'rib chiqsak, aniq n ta xil o'zgaruvchini o'z ichiga olgan mantiq algebrasi formulasining mukammal dis'yunktiv normal shakli uning dis'yunktiv normal shakli ekanligini ko'rish oson, bunda:

1) barcha qo‘shma gaplar juftlik bilan ajralib turadi;

2) har bir bog‘lovchi aniq n ta o‘zgaruvchidan iborat;

3) har bir birikmada n ta o‘zgaruvchi bor.

1-misolda biz haqiqat jadvalini tuzish asosida SDNF qurish usullaridan birini ko'rib chiqdik. SDNFni qurishning keyingi usuli mantiq algebrasi qonunlarini qo'llashga asoslangan.

5-misol Formulaning mukammal ayiruvchi shaklini toping.

Bundan foydalanish , olamiz. De Morgan qonunlari va ikkilamchi inkorni hisobga olgan holda, biz disjunktiv normal shaklga ega bo'ldik. Bu DNF formulaga tengdir.

Qavslarni kengaytirib, biz quyidagilarni olamiz: .

Idepotentlik qonunidan foydalanib, biz kerakli SDNFni olamiz:

Dekompozitsiyani (3.6) hisobga olsak, mantiq algebrasi formulasining mukammal kon'yunktiv normal shakli aniq o'z ichiga olganligini ko'rish oson. n turli o'zgaruvchilar, uning kon'yunktiv normal shakli mavjud, unda:

1) barcha disjunksiyalar juft-juft farqlanadi;

2) har bir diszyunksiya n ta a'zodan iborat; agar u qiymat qabul qilsa, xuddi shunday to'g'ri rost.

Xuddi shunday haqiqiy formulalarga quyidagi formulalar misol bo'la oladi:

xuddi shunday yolg'on, agar u o'zgaruvchilarning barcha qiymatlari bilan birga qiymatni qabul qilsa Yolg'on.

Xuddi shunday noto'g'ri formulalarga misollar formulalardir:

Mantiq algebrasining formulasi odatda deyiladi qilish mumkin, agar unga kiritilgan o'zgaruvchilarning ba'zi qiymatlari uchun qiymatni oladi rost.

Mumkin bo'lgan formulalarga quyidagi formulalar misol bo'ladi:

Mantiq algebrasida quyidagi muammoni qo'yish mumkin: mantiq algebrasining har bir formulasi uchun uning bir xil to'g'ri yoki noto'g'ri ekanligini aniqlashga imkon beradigan usulni (algoritmni) ko'rsatish. Vazifa chaqiriladi hal qilish muammolari.

Ushbu muammoni hal qilishning quyidagi ikkita usulini ko'rib chiqing.

1-usul (jadval) Berilgan formulaning bir xil to'g'ri yoki noto'g'ri ekanligini aniqlash uchun uning haqiqat jadvalini tuzish kifoya.

Shu bilan birga, bu usul, garchi u hal qilish imkoniyati muammosini tubdan hal qilishni ta'minlasa ham, juda og'ir.

2-usul formulalarni oddiy shaklga keltirishga asoslangan.

Teorema 4Mantiq algebrasining formulasi bir xil to'g'ri bo'ladi, agar har bir dis'yunksiya o'zining kon'yunktiv normal shaklidagi inkor bilan birga qandaydir o'zgaruvchini o'z ichiga olsagina.

Haqiqatan ham, agar konyunktiv normal shakldagi har bir dis'yunksiya o'z inkori bilan birga o'zgaruvchini o'z ichiga olsa, u holda barcha dis'yunksiyalar 1 ga teng, chunki , . Bundan kelib chiqadiki, CNF xuddi shunday haqiqatdir.

Keling, berilgan formula bir xil to'g'ri bo'lsin va ruxsat bering bu formulaning CNF da ba'zi dis'yunktsiya mavjud. Faraz qilaylik, berilgan diszyunksiya inkori bilan birga o‘zgaruvchini o‘z ichiga olmaydi. Bunda inkor belgisi ostida bo'lmagan har bir o'zgaruvchiga 0 qiymatini, inkor belgisi ostida bo'lgan har bir o'zgaruvchiga esa 1 qiymatini berishimiz mumkin.Ushbu almashtirishdan so'ng barcha disjunksiyalar 0 ga teng bo'ladi, shuning uchun formula bir xil to'g'ri emas. Bizda qarama-qarshilik bor.

7-misol Formula bir xil to'g'ri yoki yo'qligini aniqlang

.

Bundan foydalanish , olamiz.

Tarqatish qonunini qo'llash orqali biz CNFni olamiz:

Har bir disjunksiya o'z inkori bilan birga ba'zi o'zgaruvchilarni o'z ichiga olganligi sababli, formula xuddi shunday to'g'ri.

Oldingi teorema kabi quyidagi teorema isbotlangan:

Teorema 5Mantiq algebrasining formulasi, agar har bir birikma oʻzining ayiruvchi koʻrinishidagi inkor bilan birga qandaydir oʻzgaruvchini ham oʻz ichiga olsagina yolgʻon hisoblanadi..

O'zgaruvchilarda mantiqiy funktsiyalarning parchalanishi. - tushuncha va turlari. “O‘zgaruvchilarda mantiqiy funksiyalarning dekompozitsiyasi” kategoriyasining tasnifi va xususiyatlari. 2017, 2018 yil.