Loogikafunktsiooni konjunktiivset normaalvormi nimetatakse. Boole'i ​​funktsioonide eriesitlused

Propositsioonialgebra disjunktiivsed ja konjunktiivsed normaalvormid. Propositsiooniloogika iga funktsiooni jaoks saab koostada tõesuse tabeli. Ka pöördülesanne on alati lahendatav. Tutvustame mitut määratlust.

Elementaarsed sidesõnad (konjunktid) nimetatakse muutujate konjunktsioonideks või nende eitusteks, milles iga muutuja esineb maksimaalselt

üks kord.

Disjunktiivne normaalvorm(DNF) on valem, millel on elementaarsidendite disjunktsiooni vorm.

Elementaarsed disjunktsioonid (klauslite järgi) nimetatakse muutujate disjunktsioonideks eitustega või ilma.

Konjunktiivne normaalvorm(CNF) on valem, millel on elementaardisjunktsioonide konjunktsiooni vorm.

Propositsioonialgebra iga funktsiooni jaoks võib leida disjunktiivsete ja konjunktiivsete normaalvormide komplekti.

DNF-i ehitamise algoritm:

1. Minge samaväärsete teisendusvalemite abil Boole'i ​​operatsioonide juurde.

2. Minge valemite juurde, millel on lähedased negatiivsed, see tähendab, et valemiga, milles negatiivsed ei asu muutujate kohal - rakendage de Morgani seadusi.

3. Avage sulgud – rakendage jaotusseadusi.

4. Terminite kordamine ühe korra võtmiseks – idempotentsuse seadus.

5. Rakenda neeldumise ja poolabsorptsiooni seaduspärasusi.

Näide 6 Otsige DNF-i valemeid: .

Boole algebras duaalsuse põhimõte. See on järgmine.

Funktsiooni kutsutakse kahekordne funktsioonile if . Need. antud funktsiooniga duaalse funktsiooni leidmiseks on vaja argumentide eitustest konstrueerida funktsiooni eitus.

Näide 7 Leidke funktsioon dual to .

hulgas elementaarsed funktsioonid loogika algebra 1 on duaalne 0-ga ja vastupidi, x on duaalne x-ga, on duaalne , on duaalne ja vastupidi.

Kui funktsiooni esindavas valemis F 1 asendatakse kõik sidesõnad

disjunktsioonil, disjunktsioonil konjunktsioonil, 1 0-l, 0 1-l, siis saame valemi F * , mis esindab funktsiooni * , dual .

Konjunktiivne normaalvorm (CNF) on DNF-i jaoks kahekordne mõiste, nii et seda saab hõlpsasti konstrueerida vastavalt skeemile:

Näide 8 Leidke CNF-i valemid: .

Kasutades näite 6 tulemust, saame

Täiuslikud disjunktiivsed ja täiuslikud konjunktiivsed normaalvormid. Igas normaalvormi tüübis (disjunktiivne ja konjunktiivne) võib välja tuua SDNF-i ja SKNF-i täiuslike vormide klassi.

Täiuslik elementaarkonjunktsioon on kõigi muutujate loogiline korrutis koos eitusega või ilma ja iga muutuja sisaldub korrutises ainult üks kord.

Mis tahes DNF-i saab taandada SDNF-ks, tükeldades sidesõnu, mis ei sisalda kõiki muutujaid, st. puuduva muutuja x i liitmine korrutatakse distributiivsuse seaduse abil

Näide 9 Otsige DNF-i näite 6 jaoks üles SDNF

Täiuslik elementaarne disjunktsioon kutsutakse kõigi muutujate loogilist summat koos eitustega või ilma, pealegi on iga muutuja summas ainult üks kord.

Mis tahes CNF-i saab taandada SKNF-iks, lisades sidesõna, mis ei sisalda muutujat X i, ja rakendades distributsiooniseadust

Näide 10. Teisendage CNF SKNF-iks:

SKNF-i koostamiseks võite kasutada skeemi

Näide 11. Leidke näite 6 valemi jaoks SKNF.

Igal funktsioonil on SDNF ja pealegi ainus . Igal funktsioonil on SKNF ja lisaks üks .

Sest SDNF ja SKNF on üheselt määratletud valemitega, neid saab ehitada valemi tõesuse tabeli järgi.

SDNF-i koostamiseks tuleb valida read, milles F võtab väärtuse 1, ja kirjutada nende jaoks üles täiuslikud elementaarkonjunktsioonid. Kui tõesuse tabeli soovitud real on muutuja väärtus võrdne ühega, siis perfektses konjunktis võetakse see ilma eituseta, kui null, siis eitusega. Seejärel ühendatakse perfektsed konjunktid (nende arv võrdub ühikute arvuga tabelis) disjunktsioonimärkidega.

SKNF-i ülesehitamiseks tõesuse tabeli järgi on vaja valida selles read, kus F=0, ja kirjutada üles perfektsed elementaardisjunktsioonid ning seejärel ühendada need sidemärkidega. Kui tõesuse tabeli nõutud real (F=0) vastab muutuja väärtus nullile, siis perfektses disjunktis võetakse see ilma eituseta, kui on võrdne ühega, siis eitusega.

Näide 12. Leidke näite 6 valemi tõesuse tabeli järgi SDNF ja SKNF.

Tabel 14 näitab ainult lõppväärtust F=10101101. Selle väite paikapidavust tuleks sõltumatult kontrollida, koostades laiendatud tõetabeli.

Tabel 14

x	y	z

standardne alus. Elementaarvalemid on literaalid. Elementaarne konjunktsioon (disjunktsioon). Disjunktiivne (konjunktiivne) normaalvorm ja perfektne vorm. Teoreem: mis tahes Boole'i ​​funktsiooni peale 0 (alates 1) saab esitada kui SDNF (SKNF). Standardbaasi täielikkus. Täielike aluste näited: Zhegalkini alus, Shefferi löök, Pierce'i nool.

Standardne alus on kolme algse Boole'i ​​algebra operatsiooni kogum: liitmine (liit), korrutamine (lõikepunkt) ja eitus.

Siin me helistame sõnasõnaline muutuja x või selle eitus x ja tähistada xˆ. Erinevate muutujatega määratletud mitme literaali Boole'i ​​ristmik, st. vormi X = xˆ 1 xˆ 2 avaldis. . . xˆ l, nimetatakse elementaarne side . Nõue, et kõik muutujad peavad olema erinevad, tuleneb järgmisest. Kui sidesõnas on mitu identset literaali, siis sidesõna kommutatiivsuse, assotsiatiivsuse ja idempotentsuse tõttu saame ekvivalentsele valemile üle minnes jätta ainult ühe literaali (näiteks x 1 x 1 = x 1). Kui konjunktsioon sisaldab muutujat ja selle eitust, siis on valem samaväärne konstandiga 0, kuna x x = 0 ja iga valemi Y jaoks on meil Y x x = 0.

Mitme elementaarkonjunktsiooni disjunktsiooni nimetatakse disjunktiivne normaalvorm , või DNF . Näiteks,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

Kui muutujate koostis antud DNF igas elementaarkonjunktsioonis on sama, siis DNF nimetatakse täiuslik . Toodud näide on DNF, mis pole täiuslik. Vastupidi, valem

x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4

on ideaalne vorm.

Kuna Boole'i ​​algebras on liitmine ja korrutamine sümmeetrilised tehted ja liitmist saab alati tõlgendada korrutamisena ja korrutamist liitmisena, on ka kahekordne mõiste - konjunktiivne normaalvorm (KNF ), mis on elementaardisjunktsioonide konjunktsioon ja täiuslik konjunktiivivorm (SKNF ). Sümmeetriliste poolringide duaalsuse põhimõttest tuleneb, et iga väide DNF-i kohta vastab duaalsele väitele CNF-i kohta, mis saadakse liitmise (disjunktsiooni) asendamisel korrutamisega, korrutamise (konjunktsiooni) liitmisega, konstanti 0 konstandiga 1, konstanti 1 asendamisega. konstandiga 0, järjesta seoseid duaali (pöördvõrdeline) järjekorras. Seetõttu keskendume edaspidi ainult DNF-i uurimisele.

Teoreem 1.4. Mis tahes Boole'i ​​funktsiooni peale konstantse 0 saab esitada SDNF-ina.

◀ Leppige kokku, et x σ tähendab valemit x, kui σ = 1 ja valemit x, kui σ = 0. Olgu funktsiooni f(y 1 , . . . , yn) väärtus 1 vektoril (t 1 , ..., tn ) (sellist vektorit nimetatakse koostisüksus ). Siis saab elementaarkonjunktsioon ka sellel hulgal väärtuse 1, kuid kaob kõikidel teistel n-mõõtmelistel Boole'i ​​vektoritel. Mõelge valemile

milles summa (liit) laieneb kõigile neile argumentide väärtuste hulkadele (t 1 , . . . , tn), millel antud funktsioon võtab väärtuse 1. liige.

On lihtne näha, et valem Φ muutub 1-ks nende ja ainult nende muutujate väärtuste puhul, mille puhul vaadeldav funktsioon muutub 1-ks. Seega tähistab valem Ψ funktsiooni f.

Järeldus 1.1. Standardne alus on valmis.

◀ Tõepoolest, kui funktsioon ei ole konstantne 0, saab seda esitada kas SDNF-ina, mis on standardaluse valem. Konstanti 0 saab esitada näiteks valemiga f(x 1 , x 2 , . . . , x n) = x 1 x 1 .

Näide 1.2. Vaatleme kolme muutuja funktsiooni m(x 1 , x 2 , x 3) (tabel 1.4), nn. enamusfunktsioon ̆. Selle funktsiooni väärtus on 1, kui enam kui pooltel selle argumentidest on väärtus 1. Seetõttu nimetatakse seda sageli hääletamisfunktsiooniks. Ehitame selle jaoks SDNF-i.

Standardbaasi täielikkus võimaldab valida ka teisi terviklikke funktsioonisüsteeme. Hulga F täielikkuse saab kindlaks teha järgmiste kaalutluste põhjal. Oletame, et kõik kolm standardset buzzis-funktsiooni on esitatavad valemiga F . Siis on teoreemi 1.3 kohaselt F teistsus täielik.

Näide 1.3. Kutsutakse välja tehtekogum moodul 2 liitmine, korrutamine ja konstant 1 Zhegalkini alusel . Modulo 2 liitmine ja korrutamine on rõnga Z2 põhitehted, nende abil koostatud avaldised on rõnga Z2 kohal olevad polünoomid. Konstant 1 on sel juhul vajalik vabaliikme kirjutamiseks. Kuna xx \u003d x, siis on polünoomi kõikidel teguritel aste 1. Seetõttu saab polünoomi kirjutamisel hakkama ilma astme mõisteta. Näited valemitest Zhegalkini alusel:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Iga sellist valemit nimetatakse Zhegalkini polünoomiks. Tegelikult on Zhegalkini polünoom rõnga Z2 kohal.

Zhegalkini baasil on lihtne koostada valemeid, mis esindavad standardaluse liitmise ja eitamise toiminguid (kahe aluse korrutamine on tavaline):

x+y=x⊕y⊕xy, x=x⊕1.

Seetõttu on Zhegalkini alus täielik komplekt.
Võib näidata, et mis tahes Boole'i ​​funktsiooni jaoks on Zhegalkini polünoom üheselt defineeritud

(täpsemalt terminite järjekorrani). Väikese arvu muutujatega Zhegalkini polünoomi koefitsiendid saab leida määramatute koefitsientide meetodil.

Näide 1.4. Mõelge ühe funktsiooni komplektile – Schaefferi käigule*. See komplekt on täielik, mis tuleneb järgmistest hõlpsasti kontrollitavatest identiteetidest:

x=x|x, xy=x|y=(x|y)|(x|y), x+y=x |y=(x|x)|(y|y).

Näide 1.5. Täielik on ka ühest funktsioonist, Pierce noolest, koosnev alus. Selle kontrollimine on sarnane Schaefferi algarvu juhtumiga. Selle järelduse saab aga teha ka sümmeetriliste poolrõngaste duaalsusprintsiibi alusel.

*Schafferi löök on kahendtehte, kuid mitte assotsiatiivne. Seetõttu tuleks infix-vormi kasutamisel olla ettevaatlik: tulemus sõltub toimingute sooritamise järjekorrast. Sel juhul on soovitatav sulgude abil selgelt määrata toimingute järjekord, näiteks kirjuta (x | y) | z, mitte x | y | z, kuigi mõlemad vormid on samaväärsed.

Definitsioon 1.Konjunktiivmonoom (elementaarne konjunktsioon) muutujatest nimetatakse nende muutujate konjunktsiooniks või nende eitusteks.

näiteks, on elementaarne side.

Definitsioon 2.Disjunktiivne monoom (elementaarne disjunktsioon) muutujatest nimetatakse nende muutujate disjunktsiooniks või nende eitusteks.

näiteks, on elementaarne disjunktsioon.

3. määratlus. Valemit, mis on ekvivalentne antud lausealgebra valemiga ja on elementaarkonjunktiivsete monomialide disjunktsioon, nimetatakse disjunktiivne normaalvorm(DNF) selle valemi.

Näiteks,- DNF.

4. definitsioon. Valemit, mis on ekvivalentne antud lausealgebra valemiga ja on elementaardisjunktiivsete monomialide konjunkt, nimetatakse konjunktiivne normaalvorm(CNF) selle valemi.

näiteks, – KNF.

Iga lausealgebra valemi jaoks võib leida disjunktiivsete ja konjunktiivsete normaalvormide komplekti.

Algoritm normaalvormide konstrueerimiseks

Kasutades loogika algebra ekvivalente, asendage kõik valemis olevad toimingud peamistega: konjunktsioon, disjunktsioon, eitus:

Vabanege topeltnegatiividest.

Vajadusel rakendage konjunktsiooni ja disjunktsiooni tehtetele jaotus- ja neeldumisvalemite omadusi.

2.6. Täiuslikud disjunktiivsed ja täiuslikud konjunktiivsed normaalvormid

Igal Boole'i ​​funktsioonil võib olla palju DNF- ja CNF-esitusi. Erilise koha nende esituste hulgas on täiuslik DNF (SDNF) ja täiuslik CNF (SKNF).

Definitsioon 1. Täiuslik disjunktiivne normaalvorm(SDNF) on DNF, milles iga konjunktiivne monoom sisaldab iga muutujat komplektist täpselt ühe korra ja siseneb kas ise või selle eitus.

Struktuuriliselt saab lausealgebra iga valemi SDNF-i, mis on taandatud DNF-iks, määratleda järgmiselt:

Definitsioon 2. Täiuslik disjunktiivne normaalvorm Propositsioonialgebra valemi (SDNF) nimetatakse selle DNF-iks, millel on järgmised omadused:

3. määratlus. Täiuslik konjunktiivne normaalvorm(SKNF) on CNF, milles iga disjunktiivne monoom sisaldab iga muutujat komplektist täpselt ühe korra ja siseneb kas ise või selle eitus.

Struktuuriliselt saab lausealgebra iga valemi SKNF-i, mis on taandatud CNF-iks, määratleda järgmiselt.

4. definitsioon. Täiuslik konjunktiivne normaalvorm(SKNF) antud propositsioonialgebra valemis on selle CNF, mis vastab järgmistele omadustele.

1. teoreem. Iga muutujate Boole'i ​​funktsiooni, mis ei ole identselt vale, saab esitada SDNF-is ja pealegi ainulaadsel viisil.

SDNF-i leidmise viisid

1. viis

2. viis

vali read, kus valem võtab väärtuse 1;

teeme sidesõnade disjunktsiooni eeldusel, et kui muutuja sisaldub konjunktsioonis väärtusega 1, siis kirjutame selle muutuja, kui väärtusega 0, siis selle eituse. Saame SDNF-i.

2. teoreem. Iga muutujate Boole'i ​​funktsiooni, mis ei ole identselt tõene, saab esitada SKNF-is ja pealegi ainulaadsel viisil.

SKNF-i leidmise viisid

1. viis– samaväärsete teisenduste abil:

2. viis- kasutades tõetabeleid:

vali read, kus valem võtab väärtuse 0;

koostame disjunktsioonide konjunktsiooni, eeldusel, et kui muutuja sisaldub disjunktsioonis väärtusega 0, siis kirjutame selle muutuja, kui väärtusega 1, siis selle eituse. Saame SKNF-i.

Näide 1 Joonistage CNF-i funktsioonid.

Lahendus

Likvideerige link "", kasutades muutujate teisendamise seadusi:

= /de Morgani seadused ja topelteitus/ =

/jaotusseadused/ =

Näide 2 Teisendage valem DNF-iks.

Lahendus

Me väljendame loogilisi tehteid järgmiselt:

= /Seotage eitus muutujatega ja vähendage topelt eitusi/ =

= /jaotusseadus/ .

Näide 3 Kirjutage valem DNF-i ja SDNF-i.

Lahendus

Loogikaseadusi kasutades taandame selle valemi vormiks, mis sisaldab ainult elementaarsidendite disjunkte. Saadud valem on soovitud DNF:

SDNF-i loomiseks koostame selle valemi tõesuse tabeli:

Märgistame need tabeli read, milles valem (viimase veeru) väärtus on 1. Iga sellise rea kohta kirjutame välja valemi, mis on tõene selle rea muutujate hulgal ,,:

rida 1: ;

rida 3: ;

rida 5: .

Nende kolme valemi disjunktsioon võtab väärtuse 1 ainult ridade 1, 3, 5 muutujate kogumitel ja on seetõttu nõutav täiuslik disjunktiivne normaalvorm (PDNF):

Näide 4 Viige valem SKNF-i kahel viisil:

a) samaväärsete teisenduste abil;

b) tõetabeli kasutamine.

Lahendus:

Teisendame teise elementaardisjunktsiooni:

Valem näeb välja selline:

b) koostage selle valemi jaoks tõepära tabel:

Märgistame need tabeli read, milles valem (viimase veeru) väärtus on 0. Iga sellise rea kohta kirjutame välja valemi, mis on tõene selle rea muutujate hulgal ,,:

rida 2: ;

rida 6: .

Nende kahe valemi konjunktsioon omandab väärtuse 0 ainult ridade 2 ja 6 muutujate kogumitel ja on seetõttu soovitud täiuslik konjunktiivne normaalvorm (CKNF):

Küsimused ja ülesanded iseseisvaks lahendamiseks

1. Kasutades samaväärseid teisendusi, viige valemid DNF-i:

2. Kasutades samaväärseid teisendusi, viige valemid CNF-i:

3. Kasutades teist jaotusseadust, teisendage DNF CNF-iks:

a) ;

4. Teisendage antud DNF-id SDNF-ideks:

5. Teisendage antud CNF SKNF-iks:

6. Konstrueerige antud loogiliste valemite jaoks SDNF ja SKNF kahel viisil: kasutades ekvivalentseid teisendusi ja kasutades tõesuse tabelit.

b) ;

Tutvustame elementaarse disjunktsiooni mõistet.

Elementaarne disjunktsioon on vormi väljendus

Konjunktiivne normaalvorm (CNF) loogiline funktsioon nimetatakse mis tahes paarikaupa eristuvate elementaardisjunktsioonide lõpliku hulga konjunktsiooniks. Näiteks loogilised funktsioonid

on elementaardisjunktsioonide konjunktsioonid. Seetõttu on need kirjutatud konjunktiivses normaalvormis.

Analüütilise avaldise poolt antud suvalise loogilise funktsiooni saab taandada CNF-iks, tehes järgmisi toiminguid:

Inversioonireegli kasutamine, kui eitustoimingut rakendatakse tõeväärtuslik väljend;

Jaotuse aksioomi kasutamine korrutamisel:

Absorbeerimisoperatsiooni kasutamine:

Erandid korduvate muutujate või nende eituste disjunktsioonides;

Kõigi identsete elementaardisjunktsioonide eemaldamine, välja arvatud üks;

Kustutatakse kõik disjunktsioonid, mis sisaldavad samaaegselt muutujat ja selle eitust.

Loetletud tehete kehtivus tuleneb loogika algebra põhiaksioomidest ja identiteedisuhetest.

Konjunktiivset normaalvormi nimetatakse täiuslikuks, kui iga selles sisalduv elementaardisjunktsioon sisaldab otsesel või pöördkujul kõiki muutujaid, millest funktsioon sõltub.

CNF-i muutmine täiuslikuks CNF-iks viiakse läbi järgmiste toimingute abil:

Muutujate sidesõnade ja nende eituste iga elementaardisjunktsiooni lisandid, kui need ei sisaldu selles elementaardisjunktsioonis;

Distributiivsuse aksioomi kasutamine;

Kõigi identsete elementaardisjunktsioonide eemaldamine, välja arvatud üks.

Iga loogilist funktsiooni saab esitada täiuslikus CNF-is, välja arvatud

identselt võrdne ühega (). Täiusliku CNF-i eripäraks on see, et loogilise funktsiooni esitus selles on ainulaadne.

Täiuslikus CNF-funktsioonis sisalduvaid elementaardisjunkte nimetatakse nullkomponentideks. Täiusliku CNF-i iga nullkomponent kaob ainsal muutujaväärtuste komplektil, mis on funktsiooni nullkomplekt. Järelikult langeb loogilise funktsiooni nullkomplektide arv kokku selle täiuslikus CNF-is sisalduvate nullkomponentide arvuga.

Loogilise funktsiooni nullkonstant täiuslikus CNF-is on esindatud nulli konjunktsiooniga 2nconstituent. Sõnastame loogilise funktsiooni SKNF-i koostamise reegli vastavustabeli järgi.

Iga vastavustabeli rea jaoks, kus funktsioon on võrdne nulliga, koostatakse kõigi muutujate elementaarne disjunktsioon. Disjunktsioon hõlmab muutujat ennast, kui selle väärtus on võrdne nulliga, või eitust, kui selle väärtus on võrdne ühega. Saadud elementaardisjunktsioonid ühendatakse sidemärgiga.

Näide 3.4. Otsingutabelis 2.2 antud loogilise funktsiooni z(x) jaoks defineerime täiusliku konjunktiivivormi.

Tabeli esimese rea jaoks, mis vastab nullfunktsiooni komplektile 000, leiame nullkomponendi . Tehes sarnaseid toiminguid teise, kolmanda ja viienda rea ​​jaoks, määrame soovitud täiusliku CNF-funktsiooni:

Tuleb märkida, et funktsioonide puhul, mille ühikuhulkade arv ületab nullkomplektide arvu, on kompaktsem kirjutada need SKNF-i kujul ja vastupidi.