Carnot kartta

Carnot-kartta ( Carnot- kuutio , Carnot- kaavio , Veitch-kartta ) on graafinen tapa esittää Boolen funktioita niiden kätevän ja visuaalisen manuaalisen minimoinnin tarkoituksena [1] .

Se on yksi vastaavista tavoista kuvata tai määrittää loogisia funktioita yhdessä totuustaulukon tai Boolen algebralausekkeiden kanssa . Karnaugh-kartan muunnos totuustaulukoksi tai Boolen kaavaksi ja päinvastoin suoritetaan alkeisalgoritmilla.

Tällaisen loogisen funktion esityksen mukavuus ja selkeys johtuu siitä, että loogiset termit, joihin voidaan soveltaa pareittain epätäydellisen liimauksen ja alkeisabsorption operaatioita, on ryhmitelty Carnot-kartassa visuaalisesti ilmeisiksi suorakaiteen muotoisiksi taulukoiksi, jotka sisältävät samat arvot (nollat ja ykköset) soluissaan.

Karnaugh-karttoja voidaan pitää kehityksenä n - ulotteisen Boolen kuution tasolle , ja tämän hyperkuution ulottuvuus on sama kuin esitettävän funktion muuttujien lukumäärä, ja jokainen hyperkuution kärki vastaa yksi yhteen yksi Karnaugh-kartan solu. Graafisesti Karnaughin kartta on kuvattu suorakulmiona tai neliöinä soluista, joiden lukumäärä on yhtä suuri kuin , ja mitkä tahansa kaksi vierekkäistä solua pysty- tai vaakasuunnassa tai toisin sanoen von Neumannin naapurustossa kuvaavat termejä, jotka eroavat vain yhden muuttujan osalta. - loogisella negaatiolla ja ilman loogista kieltämistä. Vierekkäin ovat myös ensimmäinen ja viimeinen rivi, taulukon vasen ja oikea sarake, joten Carnot-taulukko on itse asiassa loogisen hyperkuution kehitys toroidin pinnalle . Samalle funktiolle on mahdollista rakentaa erilaisia karttoja, jotka täyttävät ehdon: solujen geometrinen naapuruus von Neumannin merkityksessä on termien looginen lähialue - eli naapurisolujen termien Hamming-etäisyyden ollessa yhtä suuri 1. Mikä tahansa näistä taulukoista on yhtä kätevä funktion minimoimiseen, mutta yleensä muuttujat Karnaugh-kartan riveissä ja sarakkeissa on järjestetty refleksiivisen Gray-koodin mukaan muistin ja selkeyden vuoksi. $2^{n}$

Historia

Karnaugh-kartat esitteli vuonna 1952 Edward V. Veitch [2] ja Bell Labsin fyysikko Maurice Karnaugh paransi niitä vuonna 1953 yksinkertaistaakseen digitaalisten järjestelmien suunnittelua [ 3] .

Perusperiaatteet

Karnaugh-kartta on erityisellä tavalla muotoiltu totuustaulukko, joka sopii visuaaliseen manuaaliseen minimointiin. Minimoimisen tulos on joko disjunktiivinen normaalimuoto (DNF) tai konjunktiivinen normaalimuoto (CNF). Ensimmäisessä tapauksessa työ tehdään kartan soluilla, joissa on ykkösiä, toisessa - soluilla, joissa on nollia. Alkuperäisessä kartassa, kuten myös totuustaulukossa, jokainen yksikkö vastaa yhtä täydellisen disjunktiivisen normaalimuodon (PDNF) termiä ja jokainen nolla vastaa yhtä täydellisen konjunktiivisen normaalimuodon (CKNF) termiä .

Läheiset ykkösten tai nollien ryhmät Karnaugh-kartalla yhdistetään suorakaiteen muotoisiksi alueiksi tai "liimauksiksi" solujen koon mukaan. Kukin tällainen ryhmä lopullisessa loogisessa kaavassa vastaa yhtä termiä (jos oletetaan, että looginen " TAI " -operaatio on "summaus" ja looginen " AND " -operaatio on "kerto", niin yksi termi vastaa yhtä termiä DNF:n tapauksessa tai yhteen tekijään CNF:n tapauksessa) sisältävät muuttujat, tätä ryhmittelyä kutsutaan yleensä "liimaukseksi" [4] . Näin ollen kartan kanssa työskentely tarkoittaa useiden ykkösten (nollien) optimaalisen joukon valitsemista ja niiden muuntamista loogiseksi lausekkeeksi. ${\displaystyle 2^{a}\times 2^{b))$ $nab$

Minimoimisen periaatteet

Päämenetelmä SDNF: nä tai SKNF :nä esitettyjen loogisten funktioiden minimoimiseksi on pareittainen epätäydellinen liimaus ja alkeisabsorptio. Pariliimaus suoritetaan kahden saman muuttujan sisältävän termin välillä, joiden esiintymiset (suora ja käänteinen) ovat samat kaikille muuttujille yhtä lukuun ottamatta. Tässä tapauksessa kaikki muuttujat yhtä lukuun ottamatta voidaan ottaa pois suluista ja yhden suluissa olevan muuttujan suorat ja käänteiset esiintymät voidaan absorboida. Esimerkiksi:

${\overline {X}}_{1}X_{2}X_{3}X_{4}\vee {\overline {X}}_{1}X_{2}{\overline {X}}_{3 }X_{4}={\overline {X}}_{1}X_{2}X_{4}(X_{3}\vee {\overline {X}}_{3})={\overline {X }}_{1}X_{2}X_{4}\cdot 1={\overline {X}}_{1}X_{2}X_{4}.$

Samoin CNF:lle:

$({\overline {X}}_{1}\vee X_{2}\vee X_{3}\vee X_{4})({\overline {X}}_{1}\vee X_{2}\ vee {\overline {X}}_{3}\vee X_{4})={\overline {X}}_{1}\vee X_{2}\vee X_{4}\vee X_{3}{ \overline {X}}_{3}={\overline {X}}_{1}\vee X_{2}\vee X_{4}\vee 0={\overline {X}}_{1}\ vee X_{2}\vee X_{4}.$

Absorption mahdollisuus seuraa ilmeisistä yhtäläisyyksistä:

$A\vee {\overline {A}}=1;A{\overline {A}}=0.$

Näin ollen päätehtävä SDNF:n ja SKNF:n minimoinnissa on liimaukseen sopivien termien etsiminen myöhemmän absorption kanssa, mikä voi olla monien loogisten muuttujien funktioille melko vaikea tehtävä. Karnaugh-kartat tarjoavat visuaalisen tavan löytää tällaisia termejä.

N muuttujan loogiset funktiot , jotka esitetään muodossa SDNF tai SKNF, voivat sisältää vain erilaisia termejä. Kaikki nämä alkeistermit voidaan esittää joksikin rakenteeksi, joka topologisesti vastaa -ulotteista kuutiota, ja mitkä tahansa kaksi reunalla yhdistettyä termiä sopivat liimaukseen ja absorptioon. $2^{n}$ $n$

Kuvassa on yksinkertainen totuustaulukko kahden muuttujan funktiolle, tätä taulukkoa vastaava 2-ulotteinen kuutio (neliö) sekä 2-ulotteinen kuutio SDNF-jäsenten merkinnöillä ja vastaava taulukko termien ryhmittelyä varten:

Kolmen muuttujan funktion tapauksessa on käsiteltävä kolmiulotteista kuutiota. Tämä on monimutkaisempaa ja vähemmän visuaalista, mutta teknisesti mahdollista. Esimerkkinä kuvassa on totuustaulukko kolmen muuttujan Boolen funktiolle ja sitä vastaavalle kuutiolle.

Kuten kuvasta voidaan nähdä, kolmiulotteisessa tapauksessa monimutkaisemmat termien konfiguraatiot ovat mahdollisia. Esimerkiksi neljä kuution samalle pinnalle kuuluvaa termiä yhdistetään yhdeksi termiksi kahden muuttujan absorptiolla:

${\overline {X}}_{1}{\overline {X}}_{2}{\overline {X}}_{3}\vee X_{1}{\overline {X}}_{2} {\overline {X}}_{3}\vee {\overline {X}}_{1}{\overline {X}}_{2}X_{3}\vee X_{1}{\overline {X }}_{2}X_{3}=$

$={\overline {X}}_{2}({\overline {X}}_{1}{\overline {X}}_{3}\vee {\overline {X}}_{1}X_{ 3}\vee X_{1}{\overline {X}}_{3}\vee X_{1}X_{3})={\overline {X}}_{2}({\overline {X}} _{1}\vee X_{1})({\overline {X}}_{3}\vee X_{3})={\overline {X}}_{2}$

Yleisessä tapauksessa voidaan sanoa, että hyperkuution tuohon -ulotteiseen pintaan kuuluvat termit liimataan yhdeksi termiksi, kun taas muuttujat absorboituvat. $2^k$ $k$ $k$

Työn yksinkertaistamiseksi useiden muuttujien Boolen funktioiden kanssa ehdotettiin seuraavaa kätevää temppua. Kuutio, joka on termirakenne, avataan tasolle kuvan osoittamalla tavalla. Siten on mahdollista esittää Boolen funktioita useammalla kuin kahdella muuttujalla tasaisen taulukon muodossa. On syytä muistaa, että taulukon termikoodien järjestys (00 01 11 10) ei vastaa leksikografisessa järjestyksessä (00 01 10 11) kirjoitettujen binäärilukujen järjestystä ja äärimmäisissä sarakkeissa sijaitsevien solujen järjestystä. pöydät ovat vierekkäin.

Vastaavasti voit työskennellä useiden muuttujien loogisten funktioiden kanssa.

Carnot-karttojen esitystyylit

Perinteisesti Karnot-karttojen esittämiseen on useita tyylejä. Usein otsikko ja vasen sarake sisältävät muuttujien numeeriset arvot, aivan kuten ne näkyvät totuustaulukossa (a). Tässä tyylissä on ilmeisintä, että Karnaugh-kartta on erikoinen totuustaulukon esityksen muoto. Karnaugh-kartan solut seuraavat kuitenkin hieman eri järjestyksessä kuin totuustaulukon rivit, koska totuustaulukossa on tapana järjestää rivit binäärilukujen leksikografisessa kasvussa. Esimerkiksi neljän muuttujan Karnaugh-kartassa totuustaulukon karttasolujen ja rivien järjestys on sama, jos kartan kolmas-neljäs sarake ja kolmas-neljäs rivit vaihdetaan.

Jokainen totuustaulukon rivi ja jokainen Karnaugh-kartan solu vastaa yhtä DNF:n termiä, joten muuttujien (suorat ja käänteiset) esiintymiset voidaan ilmoittaa kartan otsikossa ja vasemmassa sarakkeessa, kuten ne näyttävät SDNF:ssä ( b). Tästä esitystyylistä on olemassa lyhennetty versio, jossa apurivit ja -sarakkeet osoittavat, missä muodossa, suoraan tai käänteisesti, kukin muuttuja esitetään vastaavalla kartan rivillä tai sarakkeessa (c).

Lopuksi joissakin tapauksissa viivat osoittavat sarakkeita ja rivejä kartan reunoilla, joissa vastaava muuttuja on esitetty suorassa muodossa (d).

a) b) c) d)

Kuinka työskennellä Karnot-kartan kanssa

Alkutieto Karnaugh-kartan kanssa työskentelemistä varten on minimoidun funktion totuustaulukko . Totuustaulukko sisältää täydelliset tiedot loogisesta funktiosta, joka antaa sen arvot kaikille mahdollisille 2 n syöttömuuttujien sarjalle X 1 … X n . Karnaughin kartta sisältää myös 2 n solua, joista jokainen liittyy ainutlaatuiseen syöttömuuttujien joukkoon X 1 … X n . Siten totuustaulukon ja Karnaugh-kartan välillä on yksi yhteen vastaavuus, ja Karnaughin karttaa voidaan pitää sopivasti muotoiltuna totuustaulukkona.

Tässä osiossa käytetään esimerkkinä kuvan 2 totuustaulukon antamaa neljän muuttujan funktiota. 2a. Carnot-kartta samalle funktiolle on esitetty kuvassa. 2b.

Liimausperiaatteet

Karnaugh-kartan suorakaiteen muotoista aluetta, joka koostuu 2 k :sta identtisestä arvosta (ykkösiä tai nollia, riippuen siitä, minkä muodon haluat saada), kutsutaan liimaukseksi , ryhmäksi tai alueeksi . Kaikkien nollien (ykkösten) jakautumista Carnot-kartassa liimauksille kutsutaan peitoksi . Boolen funktion minimoimiseksi on tarpeen rakentaa Carnot-kartan peitto niin, että liimausten määrä on minimaalinen ja jokaisen liimauksen koko on mahdollisimman suuri. Tätä varten sinun on noudatettava seuraavia sääntöjä.

Saman Carnot-kartan solut voidaan liimata sekä ykkösillä (a) että nollilla (b). Ensimmäinen on tarpeen DNF :n saamiseksi, toinen on välttämätön CNF :n saamiseksi .

a) b)

Voit liimata vain suorakaiteen muotoisia alueita, joissa on ykkösten (nollien) määrä, joka on kahden kokonaislukupotenssi (1, 2, 4, 8, 16, 32… solua).

On suositeltavaa valita mahdollisimman suuret liimausalueet. Jos liimausala ei ole suurin mahdollinen, tämä ei ole virhe, mutta DNF (CNF) ei ole pienin.

Joissakin tilanteissa asetteluun muodostuu eristetty ykkönen tai nolla, jota ei voi sisällyttää mihinkään alueeseen. Tässä tapauksessa yksikkö (nolla) tarttuu yhteen "itsensä kanssa". Et voi jättää "riippuvia" ykkösiä (nollia), koska tämä johtaa funktion virheelliseen lausekkeeseen.
Kaikkien ykkösten (nollien) täytyy osua jollekin alueelle.

Liimattavan alueen tulee sisältää samat arvot - vain ykkösiä tai vain nollia.

Karnaugh-kartoissa, joissa on muuttujien lukumäärä 3 ja 4, pätee seuraava sääntö: kunkin vaaka- ja pystysuoran äärisolut rajaavat toisiaan ja ne voidaan yhdistää suorakulmioiksi (topologisesti Karnaugh-kartta on torus). Tämän säännön seuraus on Karnaugh-kartan kaikkien neljän kulmasolun vierekkäisyys neljälle muuttujalle. Carnot-kartoissa, joissa on alle 3 muuttujaa, tämä sääntö ei ole järkevä, koska äärimmäiset solut ovat jo toistensa reunassa; Karnaugh-kartoissa, joissa on enemmän kuin neljä muuttujaa, viereisyyssäännöt ovat monimutkaisempia.

Karnot-kartan yksi solu voidaan sisällyttää usealle alueelle kerralla. Tämä seuraa Boolen funktioiden ilmeisestä ominaisuudesta: jo olemassa olevan termin (tekijän) toisto ei vaikuta funktioon: $A\vee A=A;A\cdot A=A.$

Älä turhaan sisällytä solua kaikkiin mahdollisiin liimauksiin, tämä ei ole virhe, mutta se monimutkaistaa kaavaa. DNF ( CNF ) -minimaalisuuden kannalta liimausmäärän tulee olla mahdollisimman pieni (jokainen lisäliimaus synnyttää lisätermin), ja liimauksen solujen lukumäärän tulee olla mahdollisimman suuri (mitä enemmän soluja liimauksessa sitä vähemmän muuttujia termi sisältää. A 2 k solua generoi termin, jossa on n - k muuttujia) [4] .

Toisin kuin SDNF ja SKNF, DNF ja CNF eivät aina ole ainutlaatuisia. Joillekin funktioille on olemassa useita toisiaan vastaavia DNF:itä (CNF), jotka vastaavat erilaisia tapoja peittää Karnaughin kartta suorakaiteen muotoisilla alueilla. Hyvin usein kahdella eri DNF:llä (CNF) on sama monimutkaisuus, mikä ei salli yksiselitteistä vähimmäiskaavan valintaa.

Kortit, joilla on epävarma merkitys

Käytännössä on tapauksia, joissa Boolen funktiota ei ole määritelty joillekin argumenttien arvoille. Esimerkiksi Boolen funktio kuvaa digitaalista laitetta, jolle jotkin tulosignaalien yhdistelmät ovat fyysisesti mahdottomia, tai joillekin tulosignaalien arvoille laitteen reaktiolla ei ole väliä. Tällaisissa tapauksissa puhutaan "epävarmista ehdoista", ja tällaista funktiota kutsutaan "osittain määritellyksi" tai yksinkertaisesti "osittaiseksi" [5] .

Kuvassa on digitaalinen laite F , jossa on neljä binaarituloa . Tulosignaalit voivat olla piirissä toimivien antureiden lukemia ja siksi niillä on vain kaksi arvoa - "on" (1) ja "off" (0). Oletetaan, että laitteen suunnitteluominaisuuksista johtuen 2. ja 4. anturi eivät voi toimia samanaikaisesti, eli signaalien yhdistäminen on fyysisesti mahdotonta. Tässä tapauksessa Karnot-kartan neljän solun funktion arvolla ei ole merkitystä, mikä näkyy ehdollisesti symbolilla "×". ${\displaystyle x_{1}...x_{4))$ $x_{2}x_{4}=11$

Tällaisia soluja voidaan mielivaltaisesti sisällyttää mihin tahansa liimaukseen, eikä niitä myöskään saa sisällyttää mihinkään liimaukseen, toisin sanoen ne voidaan valinnaisesti määritellä 1:ksi tai 0:ksi [5] .

Kartan muuntaminen kaavaksi

Kun kaikki Karnaugh-kartan liimaukset on määritetty, tuloksena oleva Karnaugh-kartta on muutettava kaavaksi. Näin tehdessään he noudattavat seuraavia periaatteita:

Jokainen liimaus Karnaugh-kartalla on DNF-termi liimattaessa ykkösillä ja CNF-tekijä liimattaessa nollia.
Jos liimaus kattaa 2k solua, se vastaa n–k tekijän termiä DNF:ssä ja tekijää, jossa on nk termiä CNF:ssä. Esimerkiksi kun minimoidaan 4 muuttujan funktio, 4 yksikön liimaus vastaa kahden tekijän termiä.
Karnaughin kartassa jokaiselle muuttujalle on kaksi vyöhykettä, joista kukin vie tasan puolet kartan soluista. Yhdessä vyöhykkeessä muuttuja on läsnä suorassa muodossa, toisessa - käänteisessä muodossa. Jos liimaus on kokonaan jollakin näistä vyöhykkeistä, vastaava muuttuja on termissä (tekijä). Jos liimaus tapahtuu samanaikaisesti kahdella vyöhykkeellä, tämä muuttuja kokee absorption, eikä sitä ole termissä (tekijä).

Kuvaus

Karnaugh-kartta voidaan rakentaa mille tahansa määrälle muuttujia, mutta on kätevää työskennellä enintään viiden muuttujan kanssa. Pohjimmiltaan Karnaugh-kartta on totuustaulukko, joka esitetään matriisina 2-ulotteisessa muodossa.

Jokainen tämän kartan solu vastaa yhtä riviä klassisessa totuustaulukossa ja on merkitty rivillä muuttujia inversioiden kanssa ja ilman. Anna esimerkiksi totuustaulukkoon 4 muuttujan funktiolle yksi riveistä näyttää tältä: 0 1 1 0 | 1, niin tätä riviä vastaavalla Karnaugh-kartan solulla on nimi ja tähän soluun laitetaan 1. Karnaugh-kartan solujen nimien ilmaisu suoritetaan yleensä ylimääräisellä rivillä ylhäällä ja lisäsarakkeella vasemmalla . ${\näyttötyyli x_{1},x_{2},x_{3},x_{4},}$ ${\overline {x}}_{1},x_{2},x_{3},{\overline {x}}_{4}$

On oleellista, että Carnot-kartassa naapurisoluilla on välttämättä naapurikoodit Hamming -etäisyyden merkityksessä, eli Hamming-etäisyys naapurisolujen välillä on yhtä suuri kuin 1, ja eroavat vain yhden tilassa - inversiolla tai ilman. ja vain yksi muuttujista. Naapurisolut ovat vierekkäin vierekkäisiä soluja, myös vasemman ja oikeanpuoleisen sarakkeen soluja sekä ensimmäisen ja viimeisen rivin soluja pidetään naapurisoluina. Näin ollen Carnot-kartta tasossa vastaa topologisesti kolmiulotteisen toruksen pintaa tai hypertoruksen pintaa avaruudessa, jonka ulottuvuus 1 on suurempi kuin vastaavan moniulotteisen Karnot-kartan ulottuvuus.

Koska loogisen funktion muuttujien permutaatio ei muuta itse funktiota, eli esimerkiksi tai mikä on sama, totuustaulukon muuttujien sarakkeiden permutaatio ei muuta funktiota, vaihtoehtoja on useita totuustaulukon näyttämiseen Karnaugh-kartalla samalla kun säilytetään solujen "naapuruus". Mutta käytännössä Karnaugh-kartta täytetään useimmiten käyttämällä inkrementaalista Grey-koodia rivien ja sarakkeiden osoittamiseksi. Tämä lähestymistapa takaa Karnot-kartan luomisen välttäen subjektiivisia virheitä. $F(x_{1},x_{2},x_{3},x_{4})=F(x_{4},x_{2},x_{3},x_{1})$

Kun kartta on täytetty, syötetään rivin ja sarakkeen leikkauskohtaan vastaava arvo totuustaulukosta - 0 tai 1. Kartan täytön jälkeen aloitetaan minimointi.

Jos on tarpeen saada minimi DNF , niin Kartassa otetaan huomioon vain ne solut, jotka sisältävät ykkösiä, jos tarvitaan CNF , otetaan huomioon ne solut, jotka sisältävät nollia. Itse minimointi suoritetaan seuraavien sääntöjen mukaisesti (esimerkiksi DNF).

Yhdistämme vierekkäiset ykköset sisältävät solut alueeksi siten, että yksi alue sisältää ( kokonaisluku = 0 ... ) soluja (muista, että äärimmäiset rivit ja sarakkeet ovat vierekkäin), alueella ei saa olla nollia sisältäviä soluja; $2^{n}$ $n$ $\infty$
Alueen on oltava symmetrinen akselin (akselien) kanssa (akselit sijaitsevat joka neljäs solu);
Muut kuin vierekkäiset alueet, jotka sijaitsevat symmetrisesti akselin (akselien) suhteen, voidaan yhdistää yhdeksi;
Alueen tulee olla mahdollisimman suuri ja alueiden lukumäärän mahdollisimman pieni;
Alueet voivat olla päällekkäisiä;
Saatavilla on useita peittovaihtoehtoja.

Seuraavaksi otetaan ensimmäinen alue ja katsotaan mitkä muuttujat eivät muutu tällä alueella, kirjoitetaan näiden muuttujien konjunktio ; jos muuttumaton muuttuja on nolla, aseta inversio sen päälle . Otamme seuraavan alueen, teemme samoin kuin ensimmäiselle ja niin edelleen kaikille alueille. Alueiden konjunktiot yhdistetään disjunktiolla .
Esimerkiksi (Mapsissa 2 muuttujalle):

{\overline {X_{1}}}\ {\overline {X_{2}}}

{\overline {X_{1}}}\ X_{2}

X_{1}\ X_{2}\

X_{1}\ {\overline {X_{2))}

{\overline {X_{2))}

{\overline {X_{1))}

{X_{2}}\

{X_{1}}\

S_{1}\vee S_{2}=

S_{1}\vee S_{2}=

S_{1}\vee S_{2}=

S_{1}\vee S_{2}=

S_{1}\vee S_{2}=

S_{1}\vee S_{2}=

=X_{1}X_{2}\vee

=X_{1}{\overline {X_{2}}}\vee

=X_{2}\vee X_{1}

=X_{1}\vee {\overline {X_{2))}

={\overline {X_{1}}}\vee {\overline {X_{2}}}

=X_{2}\vee {\overline {X_{1))}

\vee {\overline {X_{1}}}\ {\overline {X_{2}}}

\vee {\overline {X_{1}}}X_{2}

CNF:ssä kaikki on sama, vain tarkastelemme soluja, joissa on nollia, yhdistämme muuttumattomat muuttujat saman alueen sisällä disjunktioiksi (inversiot lasketaan yksikkömuuttujien päälle) ja alueiden disjunktiot yhdistetään konjunktioksi. Tämä täydentää minimoinnin. Joten kuvan Karnot-kartalle. 1, lauseke DNF-muodossa näyttää tältä:

$f(X_{1},X_{2},X_{3},X_{4})=S_{1}\vee S_{2}\vee S_{3}={\overline {X_{1 }}}\ {\overline {X_{4}}}\vee X_{1}\ X_{2}\ X_{4}\vee {\overline {X_{4}}}{\overline {X_{2} }}.$

CNF-muodossa:

$f(X_{1},X_{2},X_{3},X_{4})=S_{1}S_{2}S_{3}=(X_{1}\vee {\overline { X_{4}}})(X_{2}\vee {\overline {X_{4}}})({\overline {X_{1}}}\vee {\overline {X_{2}}}\vee X_{4}).$

Voit myös vaihtaa DNF:stä CNF:ään ja takaisin De Morganin lakien avulla .

Esimerkkejä

Esimerkki 1

Poika Kolyalla on äiti, isä, isoisä ja isoäiti. Kolya menee kävelylle kadulle, jos ja vain, jos vähintään kaksi sukulaista sen sallii.

Lyhytyyden vuoksi merkitään Koljan sukulaisia kirjaimin:
äiti - X1
isä - X2
isoisä - X3
isoäiti - X4

Sovitaan, että sukulaisten suostumus on yksi, erimielisyys nolla. Mahdollisuus lähteä kävelylle merkitään kirjaimella f, Kolja lähtee kävelylle - f = 1, Kolya ei mene kävelylle - f = 0.
Tehdään totuustaulukko:

Piirretään totuustaulukko uudelleen 2-ulotteisessa muodossa:

Järjestetään sen rivit ja sarakkeet uudelleen Gray-koodin mukaisesti (viimeinen ja toiseksi viimeinen sarake vaihdetaan). Vastaanotettu Karnot-kortti:

Täytetään se totuustaulukon arvoilla (ensimmäinen rivi ei vastaa totuustaulukkoa, koska f=0 ja kävellä ei ole lupaa):

Minimoimme sääntöjen mukaisesti:

Kaikki alueet sisältävät 2^n solua;
Koska Karnaughin kartta on neljässä muuttujassa, akselit sijaitsevat kartan reunoilla eivätkä ne ole näkyvissä (katso lisätietoja esimerkistä 5 muuttujan kartasta );
Koska Karnaughin kartta on neljässä muuttujassa, kaikki alueet symmetrisesti akseleihin nähden ovat vierekkäin (katso lisätietoja esimerkistä Maps in 5 muuttuja );
Alueet S3, S4, S5, S6 ovat mahdollisimman suuria;
Kaikki alueet leikkaavat (valinnainen);
Tässä tapauksessa on vain yksi järkevä vaihtoehto.

$f(X1,X2,X3,X4)=S1\vee S2\vee S3\vee S4\vee S5\vee S6=$

$=X3X4\ \vee \ X1X2\ \vee \ X2X4\ \vee \ X1X4\ \vee \ X1X3\ \vee \ X2X3$

Nyt saadun minimi-DNF:n mukaan on mahdollista rakentaa looginen piiri :

Disjunktiofunktiota toteuttavan kuuden tulon OR-elementin puuttuessa jouduttiin kaskadoimaan viiden ja kahden tulon elementit (D7, D8).

Tehdään min. CNF:

$f(X1,X2,X3,X4)=(S1)\ (S2)\ (S3)\ (S4)=$

$=(X1\vee X2\vee X3)(X1\vee X3\vee X4)(X2\vee X3\vee X4)(X1\vee X2\vee X4)$

Katso myös

DNF
KNF
SDNF
SKNF
Boolen funktioiden minimointi Quinen menetelmällä
Yhdistelmäpiirien minimointi
fi:Espresson heuristinen logiikan minimointi
Quine-McCluskey-menetelmä

Muistiinpanot

↑ Givone D. Rosser R. (1983), s. 67-76.
↑ Veitch E. W. (toukokuu 1952).
↑ Karnaugh M. (marraskuu 1953).
↑ 1 2 Givone D. Rosser R. (1983), s. 69.
↑ 1 2 Givone D. Rosser R. (1983), s. 75.

Lähteet

Veitch EW (toukokuu 1952) Kaaviomenetelmä totuusfunktioiden yksinkertaistamiseksi. Proceedings, Association for Computing Machinery, Pittsburgh, Pa., 2. toukokuuta 3. 1952, pp. 127-133. DOI: 10.1145/609784.609801.
Karnaugh M. (marraskuu 1953) Karttamenetelmä yhdistelmälogiikkapiirien synteesiin . Transactions of American Institute of Electrical Engineers, osa I: Viestintä ja elektroniikka. 72(5): 593-599. DOI: 10.1109/TCE.1953.6371932.
Tokheim R. Digitaalisen elektroniikan perusteet: Per. englannista. — M.: Mir, 1988. — 392 s., ill. (Luku 4, sivut 88-95)
Givone D. Rosser R. Mikroprosessorit ja mikrotietokoneet: Alkukurssi: Per. englannista. - M .: Mir, 1983. - 464 s., ill.

Linkit

Karnaugh-karttojen käyttö käytännön sovelluksissa , Liikennevaloohjausjärjestelmän kehittäminen.

Ohjelmisto

Karnaugh Minimizer , kaupallinen Windows-sovellus (usein ei toimi oikein, esimerkiksi tälle yhtälölle: 0,1,5,8,10,13).
Logic Minimizer , kaupallinen Windows-sovellus, mutta voidaan saada toimimaan Unixissa.
Kmap Minizer Online -sovellus (Flash).
GKMap , ilmainen ohjelmisto osoitteessa SourceForge.net .
Karnaugh Map Minimizer , ilmainen (mutta usein buginen) ohjelmisto osoitteessa SourceForge.net .
Gorgeous Karnaugh , Gorgeous Karnaughin kaupallinen Karnaughin minimointiohjelmisto.

Video

Carnot-kortit. Luento . Youtube.