Loogikafunktsiooni konjunktiivset normaalvormi nimetatakse. Boole'i funktsioonide normaalvormid
normaalsed vormid loogilised funktsioonid Boole'i funktsiooni esitust ühikukomponentide Ki 2.7 konjunktiivsete liikmete disjunktsiooni kujul nimetatakse selle funktsiooni DNF-i disjunktiivseks normaalvormiks. sisaldavad täpselt ükshaaval kõiki loogilisi muutujaid, mis on võetud eitustega või ilma, siis nimetatakse seda funktsiooni esitusvormi selle funktsiooni SDNF täiuslikuks disjunktiivseks normaalvormiks. Nagu näete, peate SDNF-funktsiooni kompileerimisel tegema disjunktsiooni kõigist mintterminitest, mille jaoks funktsioon võtab väärtuse 1.
Jagage tööd sotsiaalvõrgustikes
Kui see töö teile ei sobi, on lehe allosas nimekiri sarnastest töödest. Võite kasutada ka otsingunuppu
Loeng 1.xx
Boole'i funktsioonide normaalvormid
Boole'i funktsiooni esitus konjunktiivsete terminite disjunktsiooni kujul (ühiku koostisosa) K i
, (2.7)
helistas disjunktiivne normaalvorm(DNF) selle funktsiooni.
Kui kõik DNF-i konjunktiiviterminid on rahapaja , st sisaldavad täpselt ükshaaval kõiki loogilisi muutujaid, eitustega või ilma, siis seda funktsiooni esitusviisi nimetataksetäiuslik disjunktiivne normaalvorm(SDNF ) selle funktsiooni. SDNF nimetatakse täiuslik , sest disjunktsiooni iga liige sisaldab kõiki muutujaid; disjunktiivne , sest valemis on põhitehte disjunktsioon. Kontseptsioon "normaalne vorm” tähendab üheselt mõistetavat valemi kirjutamise viisi, mis rakendab antud funktsiooni.
Eeltoodut silmas pidades eeldab teoreem 2.1 järgmist teoreemi.
2. teoreem. Mis tahes tõeväärtusfunktsioon(ei ole identselt võrdne 0-ga) saab esitada SDNF-is, .
Näide 3 Olgu meil tabelifunktsioon f (x 1, x 2, x 3) (tabel 10).
Tabel 10
|
f (x 1 , x 2 , x 3 ) |
|||
Valemi (2.6) põhjal saame:
Nagu näete, peate SDNF-funktsiooni kompileerimisel tegema disjunktsiooni kõigist mintterminitest, mille jaoks funktsioon võtab väärtuse 1.
Boole'i funktsiooni esitus disjunktiivsete terminite konjunktsiooni kujul (koostisosa null) D i
, (2.8)
helistas konjunktiivne normaalvorm(CNF ) selle funktsiooni.
Kui kõik CNF-i disjunktiivsed terminid on maxterms , st sisaldama täpselt ükshaaval kõiki loogilisi funktsiooni muutujad eitustega või ilma, siis sellist CNF-i nimetataksetäiuslik konjunktiivne normaalvorm(SKNF) selle funktsiooni.
3. teoreem. Mis tahes tõeväärtusfunktsioon(ei ole identselt võrdne 1-ga) saab esitada SKNF-ile, ja see esitus on ainulaadne.
Teoreemi tõestust saab läbi viia sarnaselt teoreemi 2.1 tõestusega järgmise konjunktiivse lagunemise Shannoni lemma alusel.
Shannoni Lemma . Mis tahes tõeväärtusfunktsioon f (x 1 , x 2 , …, x m ) alates m muutujaid saab esitada kui:
. (2.9)
Tuleb märkida, et mõlemad loogilise funktsiooni esitusvormid (DNF ja CNF) on oma võimalustelt teoreetiliselt võrdsed: mis tahes loogilist valemit saab esitada nii DNF-is (välja arvatud identne null) kui ka CNF-is (välja arvatud identne ühik). . Olenevalt olukorrast võib funktsiooni esitus ühel või teisel kujul olla lühem.
Praktikas kasutatakse kõige sagedamini DNF-i., sest see vorm on inimesele tuttavam: lapsepõlvest peale on ta rohkem harjunud korrutiste liitmisega kui summade korrutamisega (viimasel juhul on tal intuitiivselt soov sulgud avada ja seeläbi DNF-i minna).
Näide 4. Funktsiooni f (x 1, x 2, x 3 ), toodud tabelis. 10, kirjutage see SKNF-ile.
Erinevalt SDNF-ist tuleb SKNF-i kompileerimisel loogilise funktsiooni tõesuse tabelis vaadata muutujate kombinatsioone, mille puhul funktsioon võtab väärtuse 0, ja teha vastavate maxterminite konjunktsioon,kuid muutujaid tuleb võtta pöördpöördega:
Tuleb märkida, et funktsiooni SDNF-ist otse selle SKNF-i või vastupidi pole võimalik minna. Selliseid teisendusi proovides saadakse funktsioonid, mis on pöördvõrdelised soovitud funktsioonidega. Funktsioonide SDNF ja SKNF avaldisi saab otse saada ainult selle tõesuse tabelist.
Näide 5. Funktsiooni f (x 1, x 2, x 3 ), toodud tabelis. 10, proovige lülituda SDNF-ilt SKNF-ile.
Kasutades näite 2.3 tulemust, saame:
Nagu näete, saame üldise inversiooni all loogilise funktsiooni SKNF-i, mis on pöördvõrdeline näites 2.4 saadud funktsiooni suhtes:
kuna see sisaldab kõiki maksitermineid, mida vaadeldava funktsiooni SKNF-i avaldises pole.
1. Kasutades tehte omadusi (vt tabel 9) identiteet (), sum modulo 2 (), implikatsioon (), läheme üle tehtetele AND, OR, NOT (Boole'i alusele).
2. Kasutades eituse omadusi ja de Morgani seadusi (vt tabel 9), saavutame selle, et eitustehted kehtivad ainult üksikute muutujate, mitte tervete avaldiste kohta.
3. Kasutades loogikatehete JA ja VÕI omadusi (vt tabel 9), saame normaalkuju (DNF või CNF).
4. Vajadusel läheme üle täiuslikele vormidele (SDNF või SKNF). Näiteks SKNF-i saamiseks peate sageli kasutama atribuuti: .
Näide 6 Teisendage SKNF Boole'i funktsiooniks
Tehes ülaltoodud algoritmi samme järjekorras, saame:
Kasutades neeldumisomadust, saame:
Seega oleme saanud CNF-funktsioonid f (x 1, x 2, x 3 ). Selle SKNF-i saamiseks peate kordama iga disjunktsiooni, milles mõni muutuja puudub, kaks korda - selle muutuja ja selle eitusega:
2.2.6. Boole'i funktsioonide minimeerimine
Kuna sama loogilist funktsiooni saab esindada h isiklikud valemid, siis lihtsaima pho leidmine R muul mis defineerib Boole'i funktsiooni lihtsustab loogikalülitust mis rakendab Boole'i funktsiooni tsyu juurde. Minimaalne kuju l O loogiline funktsioonmõnel alusel võime pidada sellist baasi, mis sisaldab minimaalse arvu func superpositsioonide arvu To alus, lubamine ja sulud. Siiski on raske ehitada tõhusat l sellise minimeerimise algoritm minimaalse sulgudes oleva fo saamisega r meie.
Kaaluge rohkem lihtne ülesanne minimeerimine kombineeritud ahelate sünteesil, mille puhul ei otsita funktsiooni minimaalset sulgudes vormi, vaid selle minimaalset DNF-i. Selle ülesande jaoks on olemas lihtsad tõhusad algoritmid.
Quine meetod
Minimeeritav funktsioon on esindatud SDNF-is ja sellele rakendatakse kõik võimalikud mittetäieliku liimimise toimingud
, (2.10)
ja seejärel imendumine
, (2.11)
ja seda sammu rakendatakse korduvalt. Seega on võimalik terminite järjestust alandada. Seda protseduuri korratakse seni, kuni ei jää ühtegi terminit, mida saaks mõne muu terminiga liimida.
Pange tähele, et võrrandi (2.10) vasakut poolt saab kohe minimeerida lihtsamal ja ilmsemal viisil:
See meetod on halb, sest sellise otsese minimeerimise korral konjunktiiviterminid kas kaovad, kuigi on veel juhtumeid, kus neid kasutatakse liimimiseks ja ülejäänud terminitega absorbeerimiseks.
Tuleb märkida, et Quine'i meetod on üsna aeganõudev, mistõttu on tõenäosus, et teisenduste käigus vigu tehakse, üsna suur. Kuid selle eeliseks on see, et teoreetiliselt saab seda kasutada mis tahes arvu argumentide jaoks ja muutujate arvu suurenedes muutuvad teisendused vähem keerukaks.
Carnot' kaardi meetod
Kaartide (tabelite) Carnot' meetod on visuaalsem, vähem aeganõudvam ja töökindlam viis loogiliste funktsioonide minimeerimiseks, kuid selle kasutamine piirdub praktiliselt 3-4 muutuja funktsioonidega, maksimaalselt 5-6 muutujaga.
Carnot' kaart - see on kahemõõtmeline tabelivorm Boole'i funktsiooni tõesuse tabeli esitamiseks, mis muudab loogiliste funktsioonide minimaalse DNF-i leidmise lihtsaks graafilisel visuaalsel kujul. Iga tabeli lahter on seotud minimeeritud funktsiooni SDNF-i mintermiga ja nii, et tabeli mis tahes sümmeetriateljed vastavad tsoonidele, mis on mõnes muutujas vastastikku pöördvõrdelised. Selline lahtrite paigutus tabelis võimaldab hõlpsalt määrata kleepuvaid SDNF-i termineid (mis erinevad ainult ühe muutuja inversioonimärgi poolest): need on tabelis paigutatud sümmeetriliselt.
Tõe tabelid ja Karnaugh kaardid kahe sõiduraja funktsioonide JA ja VÕI jaoks e Muutujad on esitatud joonisel fig. 8. Igasse kaardi lahtrisse kirjutatakse väärtus. a funktsiooni väärtus sellele lahtrile vastava argumendi väärtuste komplektis n tov.
A ) JA b ) VÕI
Riis. kaheksa. Näide kahe muutuja funktsioonide Karnaugh kaartidest
Funktsiooni And jaoks on Karnaughi kaardil ainult üks 1, seega ei saa seda millegagi liimida. Minimaalse funktsiooni avaldises on ainult sellele 1-le vastav termin:
f = x y .
Karnaughi kaardil on funktsiooni VÕI jaoks juba kolm 1-st ja saab teha kaks liimimispaari, kusjuures 1 vastab terminile xy , kasutatakse kaks korda. Minimaalse funktsiooni avaldisesse peate kirjutama liimitavate paaride tingimused, jättes neisse kõik muutujad, mis selle paari puhul ei muutu, ja eemaldades muutujad, mis muudavad nende väärtust. Horisontaalseks liimimiseks saame x , ja vertikaalseks y , selle tulemusena saame väljendi
f = x + y .
Joonisel fig. 9 näitab kahe kolme muutuja funktsiooni tõesuse tabeleid ( a ) ja nende Karnoti kaardid ( b ja c). Funktsioon f 2 erineb esimesest selle poolest, et seda ei defineerita kolmel muutujakomplektil (seda tähistab tabelis kriips).
Funktsiooni minimaalse DNF-i määramisel kasutatakse järgmisi reegleid. Kõik 1-t sisaldavad lahtrid ühendatakse suletud ristkülikukujulisteks aladeks, mida nimetatakse k -kuubikud , kus k = log 2 K , K – kogus 1 ristkülikukujulisel alal. Sel juhul peaks iga ala olema ristkülik lahtrite arvuga 2 k , kus k = 0, 1, 2, 3, … . Kui k = 1 ristkülik nimetatakseüks on kuubik ja sisaldab 2 1 = 2 ühikut; jaoks k = 2 ristkülik sisaldab 2 2 = 4 ühikut ja seda nimetatakse kahe kuubikuga; kui k = 3 pindala 2 3 = kutsutud 8 ühikut kolme kuubikuga ; jne. Võib kutsuda ühikuid, mida ei saa ristkülikuteks kombineerida null kuubikut , mis sisaldavad ainult ühte ühikut (2 0 = 1). Nagu näha, isegi k piirkonnad võivad olla ruudukujulised (kuid mitte tingimata) ja paaritu korral k - ainult ristkülikud.
|
b c |
||||||
Riis. 9. Näide Karnaugh kaartidest kolme muutuja funktsioonide jaoks
Need alad võivad kattuda, st samad lahtrid võivad kuuluda erinevatesse piirkondadesse. Seejärel kirjutatakse funktsiooni minimaalne DNF kõigi vastavate konjunktiivsete terminite disjunktsioonina k - kuubikud.
Kõik need alad Karnaughi kaardil on minimaalses DNF-is esindatud sidesõnaga, mille argumentide arv on k vähem koguarv funktsiooni argumendid m st see number on m-k . Iga minimaalse DNF-i konjunktsioon koosneb ainult nendest argumentidest, millel on kaardi vastava ala jaoks väärtused kas ilma inversioonideta või ainult inversioonidega, st ei muuda nende väärtust.
Seega tuleks kaardirakkude kinniste piirkondadega katmisel püüda tagada, et piirkondade arv oleks minimaalne ja iga piirkond sisaldaks võimalikult palju rakke, kuna sel juhul on minimaalses DNF-is terminite arv minimaalne ja argumentide arv vastavas konjunktsioonis on minimaalne.
Funktsiooni jaoks vastavalt Karnoti kaardile joonisel fig. 9, b leiame
kuna ülemise suletud piirkonna jaoks muutujad x 1 ja x 2 on väärtused ilma inversioonideta, madalamate jaoks x 1 küsimused inversiooniga ja x 3 - ilma inversioonita.
Määratlemata väärtused kaardil joonisel fig. 9, v saab uuesti määratleda, asendades selle nulli või ühega. Selle funktsiooni puhul on selge, et kasulikum on asendada mõlemad ebakindlad väärtused 1-ga. Sel juhul moodustub kaks piirkonda, mis on erinevat tüüpi 2-kuubikud. Siis on minimaalse DNF-funktsiooni avaldis järgmine:
Suletud alade rajamisel on lubatud Karnoti kaarti nii horisontaalselt kui ka vertikaalselt silindriks kokku suruda. R vertikaaltelgedele vastaskülgede ühendusega ka R teie, st ühikud, mis asuvad piki Carnot' kaardi servi, sümmeetriliselt h aga saab ka kombineerida.
Karnoti kaarte saab joonistada mitmel viisil (joonis 10).
|
x 2 x 3 |
||||||||||
a b
Riis. 10. Carnot' kaartide kujutamise erinevad viisid
3 muutuja funktsiooni jaoks
Kuid kõige mugavamad Karnaughi kaartide versioonid 2–4 muutuja funktsioonide jaoks on need, mis on näidatud joonisel fig. 11 tabelit, sest need näitavad iga lahtri kohta a kõik muutujad on otsesel või pöördkujul.
a b
Riis. üksteist. Carnot kaartide kõige mugavam pilt
funktsioonide 3 jaoks ( a) ja 4 (b) muutujad
5 ja 6 muutuja funktsioonide puhul kasutatakse joonisel fig. 10, v.
Riis. 12. Pilt Karnaugh' kaardist 5 muutuja funktsiooni jaoks
Riis. kolmteist. Pilt Karnaugh' kaardist 6 muutuja funktsiooni jaoks
Muud seotud tööd, mis võivad teile huvi pakkuda.vshm> |
|||
| 9020. | DUAALSUSE PÕHIMÕTE. MUUTUJATES TAHTUMISE FUNKTSIOONIDE LAIENDAMINE. TÄIUSLIKUD DISJUNKTIIV- JA KOONJANDAVAD NORMAALVORMID | 96,34 KB | |
| See teoreem on konstruktiivne, kuna see võimaldab meil konstrueerida iga funktsiooni jaoks valemi, mis realiseerib selle täiusliku d.s kujul. f. Selleks märgime iga funktsiooni tõesuse tabelisse kõik read, milles | |||
| 6490. | Loogikafunktsioonide kirjeldus ja minimeerimine | 187,21 KB | |
| Verbaalses vormis väljendatakse seost funktsiooni argumentide ja selle väärtuste vahel. Näide: kolme argumendiga funktsioon hindab, kui funktsiooni kaks või enam argumenti on võrdsed. See seisneb tõetabeli koostamises, mis sisaldab funktsiooni väärtusi kõigi argumentide väärtuste komplektide jaoks. Selles näites saame tõetabeli järgi sellise kirje kujul DNF ... | |||
| 6707. | Relatsiooniandmebaaside kujundamine. Disainiprobleemid klassikalises lähenemises. Normaliseerimispõhimõtted, normaalvormid | 70,48 KB | |
| Mis on relatsiooniandmebaasi kujundus?See on omavahel seotud seoste kogum, milles on määratletud kõik atribuudid, seatud on seose esmased võtmed ja seatakse mõned täiendavad seose omadused, mis on seotud terviklikkuse säilitamise põhimõtetega. Seetõttu peab andmebaasi ülesehitus olema väga täpne ja kontrollitud. Tegelikult on andmebaasiprojekt tulevase tarkvarapaketi vundament, mida kasutatakse pikka aega ja paljud kasutajad. | |||
| 4849. | Riigi ülesannete täitmise vormid ja meetodid | 197,3 KB | |
| Mõistet "funktsioon" kasutatakse nii kodu- kui ka välismaises keeles teaduskirjandus kaugel samast väärtusest. Filosoofilises ja üldsotsioloogilises mõttes peetakse seda "objekti omaduste väliseks ilminguks antud suhetesüsteemis"; kui üksikisikute või kehade tavaliste või konkreetsete tegevuste kogum | |||
| 17873. | Loogilise UUD kujunemine 3. klassi õpilastel | 846,71 KB | |
| Loogiliste universaalsete toimingute kujunemise probleemi psühholoogilised ja pedagoogilised aspektid nooremad koolilapsed Loogilise UUD moodustumise hindamise meetodid. Süsteemi universaalse õppetegevuse arendamise kontseptsiooni väljatöötamine Üldharidus vastab uutele sotsiaalsetele nõudmistele. Kõige tähtsam ülesanne kaasaegne süsteem haridus on universaalse kasvatustegevuse kujunemine UUD. Universaalse õppetegevuse kujundamine on kooliraskuste ennetamise võti. | |||
| 2638. | Loogiliste ühenduste tehniline teostus automaatsetes blokeerimissüsteemides | 1,04 MB | |
| Loogiliste ühenduste tehniline teostus automaatsetes blokeerimissüsteemides Kolmekohaliste ja neljakohaliste AB juhtimisalgoritmide tehniline teostus on saavutatav releekontakti ja mittekontaktsete diskreetsete ja integraalsete loogikaelementide... | |||
| 10203. | RISKISUUNATUD LÄHENEMISE MÕISTE RAKENDAMINE HÄDAOLUKORRADE TEKKE JA ARENG STRUKTUURILISTE JA LOOGILISTE MUDELITE KONSTRUKTSIOONIL | 70,8 KB | |
| Üldine riskianalüüs Tootmiskeskkond on küllastunud võimsate tehnoloogiliste süsteemide ja tehnoloogiatega, mis muudavad inimtöö tootlikuks ja füüsiliselt vähem raskeks, kuid ohtlikumaks. Riski iseloomustab ohtliku olukorra ootamatus ja äkilisus. Iga päev seisame silmitsi paljude riskidega, kuid enamik neist jääb potentsiaalseks m. Riskiteooria näeb ette kvantitatiivse hinnangu negatiivne mõju inimese kohta, samuti kahju tema tervisele ja elule. | |||
| 11576. | Tehingute mõiste, liigid ja vormid. Nõutava tehinguvormi mittejärgimise tagajärjed | 49,82KB | |
| Tehingu tunnistamine kehtetute tehingutüüpidena. Rakendatud väärtus referaat on tehingu mõiste lihtsustamine, st selle avalik esitlemine kättesaadavamal kujul. | |||
| 6213. | Funktsioonide lähendamine | 3,08 MB | |
| Esimene seisneb mõne analüütiliselt või tabelina antud funktsiooni asendamises mõne teise, algsele lähedase, kuid lihtsama ja arvutusteks mugavama funktsiooniga. Näiteks funktsiooni asendamine polünoomiga võimaldab saada lihtsaid valemeid arvuliseks integreerimiseks ja diferentseerimiseks; tabeli asendamine ligikaudse funktsiooniga võimaldab saada väärtusi selle vahepunktides. Samuti tekib teine probleem teatud segmendi funktsiooni taastamiseks sellel segmendil diskreetses punktides antud funktsiooni väärtustest. Vastus sellisele küsimusele... | |||
| 14058. | Riigi funktsioonide areng | 29,99 KB | |
| Vene riikÕigusnähtusena peaks see eelkõige tagama riigi eesmärgi elluviimise, aga ka põhiseaduslikud tunnused vabariikliku valitsemisvormiga demokraatliku föderaalse õigusliku sotsiaalse ilmaliku riigina. Riigi põhieesmärk on määratud Art. | |||
Tutvustame elementaarse disjunktsiooni mõistet.
Elementaarne disjunktsioon on vormi väljendus
Loogilise funktsiooni konjunktiivne normaalvorm (CNF) on paarikaupa eristuvate elementaardisjunktsioonide mis tahes lõpliku hulga konjunktsioon. 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. Iga täiusliku CNF-i 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.
Lihtne sidesõna helistas sidesõna üks või mitu muutujad, juures see iga muutuv kohtub mitte rohkem üks korda (või ise, või teda eitus).
Näiteks on lihtne sidesõna,
disjunktiivne normaalne vormi(DNF) helistas disjunktsioon lihtne sidesõnad.
Näiteks väljend on DNF.
Täiuslik disjunktiivne normaalne vormi(SDNF) helistas selline disjunktiivne normaalne vormi, juures mis v iga sidesõna on kaasatud kõik muutujad antud nimekirja (või ise, või nende eitamine), ja v üks ja maht samaokei.
Näiteks väljend on DNF, kuid mitte SDNF. Väljendus 
on SDNF.
Sarnased määratlused (konjunktsiooni asendamisega disjunktsiooniga ja vastupidi) kehtivad ka CNF-i ja SKNF-i puhul. Esitame täpsed koostised.
Lihtne disjunktsioon helistas disjunktsioon üks või mitu muutujad, juures see iga muutuv kaasatud mitte rohkem üks korda (või ise, või teda eitus). Näiteks avaldis on lihtne disjunktsioon,
Konjunktiiv normaalne vormi(KNF) helistas sidesõna lihtne disjunktsioonid(näiteks väljend - CNF).
Täiuslik konjunktiivne normaalvorm (PCNF) on CNF, milles iga lihtne disjunktsioon sisaldab kõiki muutujaid see nimekiri(kas ise või nende eitused) ja samas järjekorras.
Näiteks väljend 
on SKNF.
Tutvustame algoritme ühelt vormilt teisele üleminekuks. Loomulikult võib konkreetsetel juhtudel (teatud loomingulise lähenemisega) algoritmide rakendamine olla töömahukam kui lihtsad teisendused, mis kasutavad antud kuju konkreetset vormi:
a) üleminek DNF-ilt CNF-ile
Selle ülemineku algoritm on järgmine: paneme DNF-i kohale kaks eitust ja toome de Morgani reeglite abil (ülemist eitust puudutamata) DNF-i eituse tagasi DNF-i. Sel juhul tuleb sulgud avada absorptsioonireegli (või Blake’i reegli) abil. Saadud DNF-i (ülemine) eitus (jällegi de Morgani reegli järgi) annab meile kohe CNF-i:
Pange tähele, et CNF-i saab ka algsest avaldisest, kui võtame välja juures sulgude jaoks;
b) üleminek CNF-ilt DNF-ile
See üleminek viiakse läbi lihtsalt sulgude avamisega (sel juhul kasutatakse jällegi neeldumisreeglit)
Seega saime DNF-i.
Pöördüleminek (SDNF-ilt DNF-ile) on seotud DNF-i minimeerimise probleemiga. Sellest tuleb täpsemalt juttu rubriigis. 5, siin näitame, kuidas lihtsustada DNF-i (või SDNF-i) vastavalt Blake'i reeglile. Sellist DNF-i nimetatakse lühendatud DNF;
c) lühend DNF (või SDNF) poolt reegel Blake
Selle reegli rakendamisel on kaks osa:
Kui DNF-i mitteühendatud terminite hulgas on termineid 
, siis lisame termini kogu disjunktsioonile TO 1 TO 2. Teeme seda toimingut mitu korda (võimalik järjest, on võimalik üheaegselt) kõikide võimalike terminipaaride puhul ja seejärel rakendame tavalist neeldumist;
Kui lisatud termin oli juba DNF-is sisaldunud, võib selle üldse ära jätta, näiteks
või
Loomulikult ei ole lühendatud DNF üheselt määratletud, kuid need kõik sisaldavad sama arvu tähti (näiteks on olemas DNF 
, pärast Blake'i reegli rakendamist võib jõuda antud reegliga samaväärsele DNF-ile):
c) üleminek DNF-ilt SDNF-ile
Kui muutuja puudub mõnes lihtsas ühenduses, näiteks z, sisestage sellesse avaldis, mille järel avame sulud (korduvaid disjunkttermineid me ei kirjuta). Näiteks:
d) üleminek CNF-ilt SKNF-ile
See üleminek viiakse läbi sarnaselt eelmisele: kui mõni muutuja puudub lihtsas disjunktsioonis (näiteks z, siis lisame sellele avaldise (see ei muuda disjunktsiooni ennast), mille järel avame jaotusseaduse abil sulud:
Seega saadakse SKNF CNF-ist.
Pange tähele, et minimaalne või lühendatud CNF tuletatakse tavaliselt vastavast DNF-ist.
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 konjunktsioonis on muutuja ja selle eitus, 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 σ on valem x, kui σ = 1 ja valem x, kui σ = 0. Olgu funktsioon f(y 1 , . . . , yn) väärtuseks 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 insuldi 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.
