Loogikafunktsiooni konjunktiivset normaalvormi nimetatakse. Loogiliste funktsioonide konjunktiivsed esitusvormid

Näide. Leidke CNF-i valemid

~ ~

SDNF-i täiusliku disjunktiivse normaalvormi saab konstrueerida järgmise algoritmi abil:

1. = 1. DNF-algoritm

2. = 2. DNF-algoritm

3. = 3. DNF-algoritm

4. = 4. DNF-algoritm

5. Jäta välja identsed valed terminid, st vormi terminid

6. Täitke ülejäänud terminid puuduvate muutujatega

7. Korrake punkti 4.

Näide. Leidke sdnf valemid.

SKNF-i ehitamiseks saab kasutada järgmist skeemi:

Näide. Leidke sdnf valemid.

On teada (teoreemid 2.11, 2.12), et SDNF ja SKNF on üheselt defineeritud valemiga ja seetõttu saab neid ehitada valemi tõesuse tabeli järgi.

Skeem SDNF ja SKNF konstrueerimiseks vastavalt tõesuse tabelile on toodud allpool valemi jaoks ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. Harjutus.

2.2.1 Allpool on loogilised avaldised. Lihtsustage oma valiku väljendeid nii palju kui võimalik, kasutades Boole'i loogikaseadusi. Seejärel võrrelge tõetabeleid kasutades oma lihtsustatud avaldist algse väljendiga.

2.2.2. Leidke f 1 ja f 2 samaväärsuse küsimus, taandades need SDNF-iks (tabel 1).

2.2.3. Leia duaalfunktsioon f 3 jaoks vastavalt üldistatud ja Boole'i põhimõttele (tabel 1). Võrrelge tulemusi.

№	f1	f2	f 3

2.3. Kontrollküsimused.

2.3.1. Määratlege väide.

2.3.2. Loetlege avalduse põhitoimingud.

2.3.3. Mis on tõetabel?

2.3.4. Looge tõesuse tabelid järgmiste valemite jaoks:

~ ~ ~ ;

2.3.5. Võttes arvesse toimingute järjekorra kokkuleppeid, jätke valemitest välja "lisa" sulud ja märk "".

;

2.3.6. Kasutades samaväärseid teisendusi, tõestage valemite identset tõesust:

2.3.7. Leidke topeltvalemid:

)

2.3.8. Vähendage järgmised valemid täiuslikule DNF-i (SDNF) vormile:

2.3.9. Teisendage järgmised valemid täiuslikuks CNF (SKNF) vormiks:

Labor nr 3

Teema:"Boole'i funktsioonide minimeerimine. Loogika"

Sihtmärk: Praktiliste oskuste omandamine Boole'i funktsioonide minimeerimise meetoditega töötamiseks.

3.1. Teoreetiline teave.

Minimaalsed vormid

Nagu on näidatud , saab iga Boole'i funktsiooni esitada täiuslikul normaalkujul (disjunktiivsel või konjunktiivil). Veelgi enam, selline esitus on esimene samm funktsiooni tabelimääratluselt selle analüütilisele väljendusele üleminekul. Edaspidi alustame disjunktiivivormist ning konjunktiivivormile saadakse vastavad tulemused duaalsusprintsiibi alusel.

Loogikaahelate Boole'i baasil sünteesimise kanooniline probleem taandub Boole'i funktsioonide minimeerimisele, s.t. nende esitamiseks disjunktiivsel normaalkujul, mis sisaldab kõige vähem tähti (muutujaid ja nende eitusi). Selliseid vorme nimetatakse minimaalseks. Kanoonilises sünteesis eeldatakse, et nii signaalid kui ka nende inversioonid suunatakse ahela sisenditesse.

Disjunktiivsel normaalkujul esitatud valemit lihtsustab liimimisoperatsiooni ja neeldumisoperatsiooni korduv rakendamine ja (konjunktiivse normaalvormi topeltidentiteedid on: ja ). Siin saab mõista mis tahes Boole'i algebra valemit. Selle tulemusena jõuame sellise analüütilise avaldiseni siis, kui edasised teisendused pole enam võimalikud, s.t. saame tupikvormi.

Tupikvormide hulgas on ka minimaalne disjunktiivne vorm, mis ei pruugi olla ainulaadne. Veendumaks, et see ummikvorm on minimaalne, peate üles leidma kõik ummikvormid ja võrdlema neid neis sisalduvate tähtede arvu järgi.

Näiteks olgu funktsioon antud perfektsel normaaldisjunktiivsel kujul:

Liikmete rühmitamisel ja liimimisoperatsiooni rakendamisel on meil .

Teise rühmitusmeetodiga saame:

Mõlemad tupikvormid ei ole minimaalsed. Minimaalse vormi saamiseks peate arvama, et korrata ühte terminit algses valemis (seda saab alati teha, kuna). Esimesel juhul võib selline liige olla . Siis . Lisades termini, saame: . Pärast kõigi võimalike valikute läbimist saame veenduda, et kaks viimast vormi on minimaalsed.

Sellel tasemel valemitega töötamine on nagu pimedas ekslemine. Minimaalsete vormide otsimise protsess muutub visuaalsemaks ja sihipärasemaks, kui kasutada spetsiaalselt selleks loodud graafilisi ja analüütilisi esitusi ja sümboleid.

Mitmemõõtmeline kuup

-Dimensioonilise kuubi igale tipule saab määrata ühikulise koostisosa. Seetõttu on märgitud tippude alamhulk täiusliku disjunktiivse normaalkuju muutujate Boole'i funktsiooni -mõõtmelise kuubi vastendamine. Joonisel fig. 3.1 näitab funktsiooni sellist vastendust jaotisest 3.7.

Joonis 3.1 SDNF-is esitatud funktsiooni kuvamine kolmemõõtmelisel kuubil

Mis tahes disjunktiivsel normaalkujul esitatud muutujate funktsiooni kuvamiseks on vaja luua vastavus selle miniterminite ja -dimensionaalse kuubi elementide vahel.

(-1) järgu miniterminiks võib lugeda kahe -nda järgu minitermini (ühiku koostisosa) liimimise tulemuseks, s.o. , Dimensioonilisel kuubil vastab see kahe tipu, mis erinevad ainult neid tippe ühendava koordinaadi väärtuste poolest, asendamisele servaga (väidetavalt katab serv sellega langevad tipud). Seega vastavad järjestuse ( -1) miniterminid -dimensioonilise kuubi servadele. Samamoodi vastavad (-2) järgu miniterminid -dimensionaalse kuubi tahkudele, millest igaüks katab nelja tippu (ja nelja serva).

Mõõtmetega iseloomustatud -mõõtmelise kuubi elemente nimetatakse -kuubikuteks. Seega on tipud 0-kuubikud, servad 1-kuubikud, tahud 2-kuubikud jne. Üldistades ülaltoodud arutluskäiku, võime eeldada, et muutujate funktsiooni disjunktiivse normaalkuju ()-nda järgu minitermin on kaardistatud -kuubiga ja iga -kuubik hõlmab kõiki neid madalaima mõõtmega kuupe, mis on seotud selle tippudega. Näiteks joonisel fig. 3.2 näitab kolme muutuja funktsiooni kaardistamist. Siin vastavad miniterminid ja 1-kuubikud () ja miniterminid on esindatud 2-kuubikutega ().

Joon.3.2 Funktsioonide katvus

Seega kuvatakse mis tahes disjunktiivne normaalvorm -mõõtmelisel kuubil - kuubikute komplektina, mis katavad kõik ühiku koostisosadele vastavad tipud (0-kuubik). Tõene on ka vastupidine väide: kui teatud -kuubikute kogum katab kõigi funktsiooni ühikuväärtustele vastavate tippude hulga, siis nendele -kuubikutele vastavate miniterminite disjunktsioon on selle funktsiooni väljendus disjunktiivsel normaalkujul. . Öeldakse, et selline -kuubikute (või neile vastavate miniterminite) kogum moodustab funktsiooni katte.

Minimaalse vormi soovi all mõistetakse intuitiivselt sellise katte otsimist, mille -kuubikute arv oleks väiksem ja nende mõõtmed suuremad. Minimaalsele kujule vastavat katet nimetatakse miinimumkatteks. Näiteks katvuse funktsiooni jaoks joonisel fig. 3.3 vastab miinimumvormidele Ja .

Riis. 3.3 Funktsioonide katvus.

vasakule – ; paremal –

Funktsiooni kuvamine mõõtmelisel kuubil on selge ja lihtne, kui . Neljamõõtmelise kuubi saab joonistada, nagu on näidatud joonisel fig. 3.4, mis kuvab nelja muutuja funktsiooni ja selle avaldisele vastava minimaalse katvuse . Selle meetodi kasutamine nõuab nii keerulisi konstruktsioone, et kõik selle eelised kaovad.

Riis. 3.4 Funktsioonide ekraan neljamõõtmelisel kuubil

Karnoti kaardid

Teine meetod tõeväärtusfunktsioonide graafiku loomiseks Carnot kaardid, mis on spetsiaalselt organiseeritud otsingutabelid. Tabeli veerud ja read vastavad kõigile võimalikele mitte rohkem kui kahe muutuja väärtuste komplektidele ja need komplektid on paigutatud sellises järjekorras, et iga järgmine komplekt erineb eelmisest ainult ühe muutuja väärtuse poolest. . Tänu sellele erinevad tabeli külgnevad lahtrid nii horisontaalselt kui ka vertikaalselt vaid ühe muutuja väärtuse poolest. Tabeli servades asuvad lahtrid loetakse samuti külgnevateks ja neil on see omadus. Joonisel fig. 3.5 näitab Karnaughi kaarte kahe, kolme, nelja muutuja jaoks.

Riis. 3.5 Karnoti kaardid kahe, kolme ja nelja muutuja jaoks

Nagu tavalistes tõetabelites, täidetakse nende hulkade lahtrid, millel funktsioon võtab väärtuse 1, ühtedega (nullid tavaliselt ei mahu, need vastavad tühjadele lahtritele). Näiteks joonisel fig. 3,6, A näitab funktsiooni Karnaugh kaarti, mille kuvamine neljamõõtmelisel kuubil on toodud joonisel fig. 3.4. Lihtsustamise huvides on mõne muutuja väärtustele 1 vastavad read ja veerud esile tõstetud selle muutuja tähistusega lokkis sulgudes.

Riis. 3.6 Nelja muutuja funktsiooni Carnot' diagrammi kuvamine

(a) ja selle minimaalne katvus (b)

Funktsioonide kaardistamise vahel n-mõõtmeline kuubik ja Karnaugh' kaardil on üks-ühele vastavus. Carnot' kaardil s-kuubik vastab 2 kõrvuti asetseva lahtri komplektile, mis on paigutatud reas, veerus, ruudus või ristkülikus (võttes arvesse kaardi vastasservade lähedust). Seetõttu on kõik ülaltoodud sätted (vt lõik mitmemõõtmeline kuup) kehtivad Carnot kaartide jaoks. Niisiis, joonisel fig. 3,6, b kaardiühikute katvus näidatakse vastavalt minimaalsele disjunktiivivormile kõnealune funktsioon.

Miniterminite lugemine Karnoti kaardilt toimub lihtsa reegli järgi. Rakud, mis moodustuvad s-kuubik, anna miniter (n–s) auaste, mis hõlmab neid (n–s) muutujad, mis hoiavad sellel samu väärtusi s-kuubik, kus väärtus 1 vastab muutujatele endile ja väärtus 0 nende eitustele. Muutujad, mis ei säilita oma väärtusi s-kuubik, minitermis puuduvad. Erinevad lugemisviisid viivad funktsiooni erineva esituseni disjunktiivsel normaalkujul (parempoolseim on minimaalne) (joonis 3.7).

Karnaugh kaartide kasutamine nõuab lihtsamaid konstruktsioone võrreldes kuvamisega n-mõõtmeline kuup, eriti nelja muutuja puhul. Viie muutuja funktsioonide kuvamiseks kasutatakse nelja muutuja jaoks kahte Karnoti kaarti ja kuue muutuja funktsiooni jaoks nelja sellist kaarti. Muutujate arvu edasise kasvuga muutuvad Karnoti kaardid praktiliselt kasutuskõlbmatuks.

Kirjanduses tuntud Veitchi kaardid erinevad ainult muutujate väärtuste komplektide erinevas järjekorras ja neil on samad omadused kui Karnaugh' kaartidel.

Kuubikute kompleks

Graafiliste meetodite ebaõnnestumine suure hulga muutujate puhul kompenseeritakse erinevate Boole'i funktsioonide esitamise analüütiliste meetoditega. Üks neist esitustest on kuubikute kompleks, mis kasutab mitmemõõtmelise loogilise ruumi terminoloogiat kombineerituna spetsiaalselt kujundatud sümboolikaga.

). Ühtsuse koostisosadele vastavad 0-kuubikud on esindatud muutuvate väärtuste kogumitega, millel funktsioon võrdub ühtsusega. Ilmselgelt protokollis

Riis. 3.8 Kolme muutuja funktsioonide kuubikute kompleks ( A) ja selle sümboolne esitus ( b)

Moodustub kuubikute kompleks maksimaalne funktsioonide katvus. Kõik need välja arvatud s-kuubikud, mis on kaetud kõrgema mõõtmega kuubikutega, saame tupikvormidele vastavad katted. Seega on vaadeldava näite jaoks (joonis 3.8) meil tupikkate

mis vastab funktsioonile . Sel juhul on see katvus samuti minimaalne.

Kahe Boole'i funktsiooni puhul vastab disjunktsioonitehing nende kuubikomplekside ühendusele ja konjunktsioonitehe nende kuubikomplekside ristumiskohale. Funktsiooni eitus vastab kuubikute kompleksi liitmisele, st ja selle määravad kõik tipud, mille juures funktsioon saab väärtuse 0. Seega on algebra vahel üks-ühele vastavus (isomorfism). Boole'i funktsioonid ja Boole'i komplektid, mis esindavad kuubikute komplekse.

Funktsiooni esitamine kuubikute kompleksidena on vähem visuaalne, kuid selle olulisemad eelised on muutujate arvu piirangute kaotamine ja teabe kodeerimine arvutite kasutamisel.

Boole'i funktsioonide minimeerimine

Probleemi sõnastamine. Skeemi minimeerimine Boole'i baasil taandatakse minimaalsele disjunktiivsele vormile, mis vastab minimaalsele katvusele. Tavavormis sisalduvate tähtede koguarv väljendub kattekuluna , kus on - kuubikute arv, mis moodustavad antud funktsiooni katvuse n muutujas. Minimaalset katvust iseloomustab selle hinna madalaim väärtus.

Tavaliselt lahendatakse minimeerimisprobleem kahes etapis. Esiteks otsitakse vähendatud katet, mis sisaldab kõiki maksimaalse mõõtmega kuubikuid, kuid ei sisalda ühtegi selle kaane kuubikuga kaetud kuubikut. Vastavat disjunktiivset normaalvormi nimetatakse redutseeritud ja selle minitermineid lihtsateks implikantideks. Selle funktsiooni jaoks on vähendatud katvus ainus, kuid see võib olla üleliigne, kuna osa kuubikuid on kaetud teiste kuubikute kogumitega.

Teises etapis viiakse läbi üleminek taandatud disjunktiivsetelt normaalvormidelt tupikusse, mille hulgast valitakse minimaalsed vormid. Tupikvormid moodustatakse nii, et vähendatud kattest jäetakse välja kõik üleliigsed kuubikud, ilma milleta ülejäänud kuubikute kogum moodustab siiski antud funktsiooni katte, kuid ühegi kuubiku täiendava välistamisega ei kata see enam kõigi kuubikute hulka. funktsiooni ühikuväärtustele vastavad tipud, st lakkab olemast katvus .

Vähendatud kattekuubik, mis katab antud funktsiooni tippe, mida ükski teine kuup ei kata, ei saa olla üleliigne ja see sisaldub alati minimaalses kattes. Sellist kuupi, nagu ka sellele vastavat implikant, nimetatakse äärmuslikuks (essential implikant) ja sellega kaetud tippe nimetatakse tühistatud tippudeks. Katvuse tuumiku moodustab ekstreemsete kogum, selge on see, et vähendatud katvusest minimaalsele üle minnes tuleks ennekõike valida kõik ekstreemsed. Kui äärmuste komplekt ei moodusta katet, siis seda täiendatakse katteks kuubikutega vähendatud kaanest.

Antud definitsioonid on illustreeritud joonisel fig. 3.9, kus katvus on vähenenud (vt joonis 3.9a, ) ja minimaalsed katted (joonis 3.9b) ja (vt joonis 3.9b) on väljendatud järgmiselt.

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 eitusoperatsioon rakendatakse loogilisele avaldisele;

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 perfektseks, 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. Loogilise funktsiooni z(x) jaoks, mis on antud otsingutabelis 2.2, defineerime täiusliku konjunktiivivormi.

Tabeli esimese rea jaoks, mis vastab nullfunktsiooni komplektile 000, leiame nullkomponendi . Pärast sarnaseid toiminguid teise, kolmanda ja viienda rea jaoks määrame kindlaks 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.

normaalne vorm loogiline valem ei sisalda mitteelementaarvalemite implikatsiooni, ekvivalentsuse ja eituse märke.

Tavaline vorm on kahel kujul:

konjunktiivne normaalvorm (CNF)-- mitme disjunktsiooni konjunktsioon, näiteks $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

disjunktiivne normaalvorm (DNF)-- mitme sidesõna disjunktsioon, näiteks $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.

SKNF

Täiuslik konjunktiivne normaalvorm (SKNF) on CNF, mis vastab kolmele tingimusele:

ei sisalda identseid elementaardisjunkte;

ükski disjunktsioonidest ei sisalda samu muutujaid;

iga elementaarne disjunktsioon sisaldab antud CNF-is kõiki muutujaid.

SKNF-is saab esitada mis tahes Boole'i valemi, mis ei ole identselt tõene.

SKNF-i ehitamise reeglid tõetabeli järgi

Iga muutujate komplekti jaoks, mille funktsioon on 0, salvestatakse summa, kusjuures muutujad, mille väärtus on 1, võetakse koos eitusega.

SDNF

Perfect Disjunctive Normal Form (PDNF) on DNF, mis vastab kolmele tingimusele:

ei sisalda identseid elementaarsidendeid;

ükski sidesõna ei sisalda samu muutujaid;

iga elementaarkonjunktsioon sisaldab kõiki antud DNF-i muutujaid, pealegi samas järjekorras.

Mis tahes Boole'i valemit, mis ei ole identselt vale, saab SDNF-is esitada, pealegi ainulaadsel viisil.

SDNF-i ehitamise reeglid tõesuse tabeli järgi

Iga muutujate komplekti jaoks, milles funktsioon on võrdne 1-ga, kirjutatakse korrutis ja muutujad, mille väärtus on 0, võetakse eitusega.

Näited SKNF-i ja SDNF-i leidmiseks

Näide 1

Kirjutage loogiline funktsioon selle tõesuse tabeli järgi:

Pilt 1.

Lahendus:

Kasutame SDNF-i koostamiseks reeglit:

Joonis 2.

Saame SDNF-i:

Kasutame SKNF ehitusreeglit.

Boole'i funktsioonide normaalvormid 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 mintermitest, 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 mintermitest, 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 sisaldavad täpselt ükshaaval kõiki funktsiooni loogilisi muutujaid, 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 tahab ta intuitiivselt 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, mis ei ole vaadeldava funktsiooni SKNF-i avaldises.

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, 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 Teisenda 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, selle muutuja ja selle eitusega kaks korda:

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 tsyule. Minimaalne kuju l O loogiline funktsioonmõnel alusel võime pidada sellist baasi, mis sisaldab minimaalselt 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.

Vaatleme lihtsamat minimeerimisprobleemi 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 vähendada. 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 selgemal 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 muutujaga, maksimaalselt 5-6 muutujaga funktsioonidega.

Carnot' kaart see on kahemõõtmeline tabelivorm Boole'i funktsiooni tõesuse tabeli esitamiseks, mis teeb lihtsaks loogiliste funktsioonide minimaalse DNF-i leidmise graafilisel visuaalsel kujul. Tabeli iga lahter on seotud minimeeritud funktsiooni SDNF-i mintermiga, pealegi 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. 8. 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-t 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 number 1 ristkülikukujulises piirkonnas. 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 kui funktsiooni argumentide koguarv 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 suletud piirkondadega kaardirakkude 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 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 kaart silindriks kokku suruda nii horisontaalselt kui vertikaalselt. R vertikaaltelgedele vastaskülgede ühendusega ka R teie, st üksused, mis asuvad piki Carnot' kaardi servi, on 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. 13. 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 DISJUNKTIIVSED 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.21KB
	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 seatud 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õistel "funktsioon" on kodu- ja välismaises teaduskirjanduses erinev tähendus. Filosoofilises ja üldsotsioloogilises mõttes peetakse seda "objekti omaduste väliseks ilminguks antud suhete süsteemis"; kui üksikisikute või kehade tavaliste või konkreetsete tegevuste kogum
17873.		Loogilise UUD kujunemine 3. klassi õpilastel	846,71 KB
	Nooremate koolilaste loogiliste universaalsete toimingute kujunemise probleemi psühholoogilised ja pedagoogilised aspektid Loogilise UUD kujunemise hindamismeetodid. Üldharidussüsteemi universaalse õppetegevuse arendamise kontseptsiooni väljatöötamine vastab uutele sotsiaalsetele nõudmistele. Kaasaegse haridussüsteemi kõige olulisem ülesanne on universaalse õppetegevuse UUD kujundamine. 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.		RISKISUUNITSE LÄHENEMISE MÕISTE RAKENDAMINE HÄDAOLUKORRADE TEKKE JA ARENGU 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 arvukate riskidega, kuid enamik neist on endiselt potentsiaalsed.Riskiteooria annab kvantitatiivse hinnangu nii inimesele avalduva negatiivse mõju kui ka tema tervise- ja elukahju kohta.
11576.		Tehingute mõiste, liigid ja vormid. Nõutava tehinguvormi mittejärgimise tagajärjed	49,82KB
	Tehingu tunnistamine kehtetute tehingutüüpidena. Kursusetöö rakenduslik väärtus on tehingu mõiste lihtsustamine ehk 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 punktide komplektis antud funktsiooni väärtustest. Vastus sellisele küsimusele...
14058.		Riigi funktsioonide areng	29,99 KB
	Vene riik kui juriidiline nähtus peab eelkõige tagama riigi eesmärgi elluviimise, aga ka põhiseaduslikud tunnused vabariikliku valitsemisvormiga demokraatliku föderaalõigusliku sotsiaalse ilmaliku riigina. Riigi põhieesmärk on määratud Art.

Iga loogilise valemi jaoks on identsete teisenduste abil võimalik konstrueerida lõpmatu arv valemeid, mis on sellega ekvivalentsed. Loogika algebras on üheks peamiseks ülesandeks kanooniliste vormide (ehk ühe reegli, kaanoni järgi ehitatud valemite) otsimine.

Kui loogilist funktsiooni väljendatakse muutujate disjunktsiooni, konjunktsiooni ja eituse kaudu, siis seda esitusviisi nimetatakse normaalseks.

Normaalvormide hulgast paistavad silma täiuslikud normaalvormid (need vormid, milles funktsioonid on kirjutatud ainulaadsel viisil).

Perfect Disjunctive Normal Form (PDNF)

Definitsioon. Valemit nimetatakse elementaarkonjunktsiooniks, kui see on moodustatud teatud arvu muutujate või nende eituste konjunktsioonist.

Näited: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definitsioon. Valemit nimetatakse disjunktiivseks normaalvormiks (DNF), kui see on mittekorduvate elementaarsidendite disjunktsioon.

DNF kirjutatakse järgmisel kujul: F 1 ∨ F 2 ∨ ... ∨ F n , kus F i on elementaarkonjunktsioon

Näited: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definitsioon. K muutuja loogilist valemit nimetatakse täiuslikuks disjunktiivseks normaalvormiks (PDNF), kui:
1) valem on DNF, milles iga elementaarkonjunktsioon on k muutuja x 1 , x 2 , ..., x k konjunkt ja selle sidendi i-s koht on kas muutuja x i või selle eitus;
2) kõik elementaarkonjunktsioonid sellises DNF-is on paarikaupa erinevad.

Näide: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Täiuslik konjunktiivne normaalvorm (SKNF)

Definitsioon. Valemit nimetatakse elementaardisjunktsiooniks, kui see on moodustatud teatud arvu muutujate või nende eituste disjunktsioonist.

Näited: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definitsioon. Valemit nimetatakse konjunktiivseks normaalvormiks (CNF), kui see on mittekorduvate elementaardisjunktsioonide konjunktsioon.

CNF kirjutatakse järgmisel kujul: F 1 ∧ F 2 ∧ ... ∧ F n , kus F i on elementaardisjunktsioon

Näited: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definitsioon. K muutuja loogilist valemit nimetatakse täiuslikuks konjunktiivseks normaalvormiks (KDNF), kui:
1) valem on CNF, milles iga elementaardisjunktsioon on disjunktsioon k muutujast x 1 , x 2 , …, x k ja selle disjunktsiooni i-ndaks kohaks on kas muutuja x i või selle eitus;
2) kõik elementaardisjunktsioonid sellises CNF-is on paarikaupa erinevad.

Näide: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

Märka seda mis tahes loogilist funktsiooni, mis ei ole identselt võrdne 0 või 1-ga, võib esitada kui SDNF või SKNF.

Algoritm SDNF-i koostamiseks tõesuse tabeli järgi

Valige tabeli kõik read, milles funktsiooni väärtus on võrdne ühega.
Iga sellise rea jaoks kirjutage kõigi muutujate konjunktsioon järgmiselt: kui mõne muutuja väärtus selles hulgas on võrdne 1-ga, siis lisame konjunktsiooni muutuja enda, vastasel juhul selle eituse.
Kõik saadud konjunktsioonid ühendame disjunktsioonitehtetega.

Algoritm SKNF-i koostamiseks tõesuse tabeli järgi

Valige tabeli kõik read, milles funktsiooni väärtus on võrdne nulliga.
Iga sellise rea jaoks kirjutage kõigi muutujate disjunktsioon järgmiselt: kui mõne muutuja väärtus selles komplektis on 0, siis lisame konjunktsiooni muutuja enda, vastasel juhul selle eituse.
Ühendame kõik saadud disjunktsioonid konjunktsioonitehtetega.

Algoritmide analüüs näitab, et kui funktsiooni väärtus on enamikul tõesuse tabeli ridadel võrdne 0-ga, siis selle loogilise valemi saamiseks on parem konstrueerida SDNF, muidu - SKNF.

Näide: Antud on kolme muutuja loogilise funktsiooni tõesuse tabel. Looge loogiline valem, mis seda funktsiooni rakendab.

x	y	z	F(x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Sest enamikel tõesuse tabeli ridadel on funktsiooni väärtus võrdne 1-ga, siis konstrueerime SKNF-i. Selle tulemusena saame järgmise loogilise valemi:
F = (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Kontrollime saadud valemit. Selleks koostame funktsiooni tõesuse tabeli.

x	y	z	x	¬ x ∨ y ∨ z	¬z	¬ x ∨ y ∨ ¬ z	F(x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

Võrreldes algset tõetabelit ja loogilise valemi jaoks koostatud tabelit, märgime, et funktsiooni väärtuste veerud on samad. See tähendab, et loogiline funktsioon on õigesti üles ehitatud.

Kategooriad

Toimetaja valik