Carnot térkép

A Carnot-térkép ( Carnot- kocka , Carnot- diagram , Veitch-térkép ) a Boole-függvények grafikus ábrázolásának módja, amelyek kényelmes és vizuális manuális minimalizálását célozzák [1] .

Ez az egyik ekvivalens módja a logikai függvények leírásának vagy megadásának igazságtáblázattal vagy Boole-algebrai kifejezésekkel együtt . A Karnaugh-térkép igazságtáblává vagy Boole-formulává alakítását és fordítva egy elemi algoritmus végzi.

A logikai függvény ilyen ábrázolásának kényelme és áttekinthetősége annak köszönhető, hogy a páronkénti hiányos ragasztás és az elemi abszorpció műveletei alkalmazható logikai tagok a Carnot térképen láthatóan látható téglalap alakú tömbök formájában vannak csoportosítva, amelyek ugyanazok az értékek (nullák és egyesek) a celláikban.

A Karnaugh-térképek egy n - dimenziós Boole-kocka síkjára történő fejlesztésnek tekinthetők , és ennek a hiperkockának a dimenziója egybeesik az ábrázolt függvény változóinak számával, és a hiperkocka minden csúcsa egy az egyhez felel meg a karnaugh-i térkép egyik cellája. Grafikusan a Karnaugh-térkép cellák téglalapja vagy négyzete, amelyek száma egyenlő -vel , és bármely két szomszédos cella függőlegesen vagy vízszintesen, vagy más szóval a Neumann-környékben olyan kifejezéseket ír le, amelyek csak egy változóban különböznek egymástól. - logikai tagadással és logikai tagadással. Szintén szomszédos az első és az utolsó sor, a táblázat bal és jobb szélső oszlopa, tehát a Carnot-tábla valójában egy logikai hiperkocka továbbfejlesztése egy toroid felületén . Ugyanarra a funkcióra sokféle, a feltételt kielégítő térképet lehet készíteni: a cellák geometriai szomszédsága a Neumann-féle értelemben a kifejezések logikai szomszédsága - vagyis a szomszédos cellák tagjai közötti Hamming-távolság egyenlő. A táblázatok bármelyike egyaránt kényelmes a függvény minimalizálására, de a Karnaugh-térkép soraiban és oszlopaiban a változók általában a reflexív Gray-kód szerint vannak rendezve , az emlékezés és a láthatóság miatt. $2^{n}$

Történelem

A karnaugh-térképeket 1952-ben Edward V. Veitch [2] vezette be, és 1953-ban a Bell Labs fizikusa, Maurice Karnaugh fejlesztette tovább a digitális rendszerek tervezésének egyszerűsítése érdekében [3] .

Alapelvek

A Karnaugh térkép egy különleges módon formázott igazságtáblázat, amely alkalmas vizuális kézi minimalizálásra. A minimalizálás eredménye vagy diszjunktív normál forma (DNF) vagy konjunktív normál forma (CNF). Az első esetben a munka a térkép azon celláival történik, ahol egyesek vannak, a másodikban pedig azokkal a cellákkal, ahol nullák vannak. Az eredeti térképen, valamint az igazságtáblázatban minden egység a tökéletes diszjunktív normálforma (PDNF) egy tagjának felel meg, és minden nulla a tökéletes konjunktív normálforma (CKNF) egy tagjának felel meg .

A Karnaugh térképen a közeli egyesek vagy nullák csoportjai téglalap alakú területekké vagy „ragasztásokká” vannak kombinálva a cellák mérete alapján. A végső logikai képletben minden ilyen csoport egy tagnak felel meg (ha feltételezzük, hogy a logikai „ VAGY ” művelet „összegzés”, a logikai „ ÉS ” művelet pedig „szorzás”, akkor egy tag egy tagnak felel meg a DNF esetében, vagy CNF esetén egy tényezőre) tartalmazó változókat, ezt a csoportosítást általában "ragasztásnak" nevezik [4] . Így a térképpel való munka az egyesek (nullák) optimális halmazának kiválasztásával és logikai kifejezéssé való konvertálásával jár. ${\displaystyle 2^{a}\times 2^{b))$ $nab$

A minimalizálás elvei

Az SDNF -ként vagy SKNF - ként ábrázolt logikai függvények minimalizálásának fő módszere a páronkénti hiányos ragasztás és az elemi abszorpció művelete. A páros ragasztás művelete két azonos változót tartalmazó tag között történik, amelyek előfordulása (direkt és inverz) egy kivételével minden változóra azonos. Ebben az esetben egy kivételével minden változó kivehető a zárójelekből, és egy zárójelben maradó változó direkt és inverz előfordulása felvehető. Például:

${\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}.$

Hasonlóképpen a CNF esetében:

$({\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}.$

Az abszorpció lehetősége a nyilvánvaló egyenlőségekből következik:

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

Így az SDNF és SKNF minimalizálásában a fő feladat a ragasztásra alkalmas kifejezések keresése utólagos abszorpcióval, ami sok logikai változó függvényében elég nehéz feladat lehet. A Karnaugh-térképek vizuális módot nyújtanak az ilyen kifejezések megtalálására.

Az N változóból álló logikai függvények , amelyeket SDNF vagy SKNF formában képviselnek, legfeljebb különböző kifejezéseket tartalmazhatnak. Mindezek az elemi tagok egy -dimenziós kockával topológiailag ekvivalens struktúraként ábrázolhatók , és bármely két éllel összekapcsolt tag alkalmas ragasztásra és abszorpcióra. $2^{n}$ $n$

Az ábra egy egyszerű igazságtáblázatot mutat két változó függvényéhez, egy ennek a táblázatnak megfelelő 2 dimenziós kockát (négyzetet), valamint egy 2 dimenziós kockát az SDNF tagok megjelölésével és egy ekvivalens táblázatot a kifejezések csoportosítására:

Három változóból álló függvény esetén egy háromdimenziós kockával kell számolni. Ez bonyolultabb és kevésbé vizuális, de technikailag lehetséges. Példaként az ábra egy három változóból álló Boole-függvény igazságtáblázatát és a megfelelő kockát mutatja be.

Amint az ábrán látható, a háromdimenziós esetre a kifejezések bonyolultabb konfigurációi is lehetségesek. Például egy kocka ugyanazon lapjához tartozó négy tagot két változó abszorpciójával egy taggá egyesítik:

${\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}$

Általános esetben azt mondhatjuk, hogy a hiperkocka egyik dimenziós felületéhez tartozó kifejezések egy tagba vannak ragasztva, míg a változók elnyelődnek. $2^k$ $k$ $k$

A nagyszámú változó Boole-függvényeivel végzett munka egyszerűsítésére a következő kényelmes trükköt javasoltuk. A kockát, amely egy terminus szerkezete, az ábrán látható módon egy síkra bontjuk. Így lehetővé válik a logikai függvények kettőnél több változóval történő ábrázolása lapos táblázat formájában. Emlékeztetni kell arra, hogy a táblázatban a kódok kifejezések sorrendje (00 01 11 10) nem egyezik a lexikográfiai sorrendben (00 01 10 11) írt bináris számok sorrendjével, és a szélső oszlopokban található cellák sorrendje. az asztalok egymás mellett helyezkednek el.

Hasonlóképpen több változó logikai függvényeivel is dolgozhat.

Ábrázolási stílusok Carnot térképekhez

Hagyományosan többféle stílus létezik a Karnot térképek bemutatására. Gyakran a fejléc és a bal oldali oszlop tartalmazza a változók számértékeit, ahogyan azok az igazságtáblázatban (a) is megjelennek. Ebben a stílusban a legnyilvánvalóbb, hogy a Karnaugh-térkép az igazságtáblázat-ábrázolás sajátos formája. A Karnaugh-térkép cellái azonban némileg más sorrendben következnek, mint az igazságtáblázat sorai, mivel az igazságtáblázatban a bináris számok lexikográfiai növekedésében szokás elrendezni a sorokat. Például egy négy változós Karnaugh-térképen az igazságtáblázat térképcelláinak és sorainak sorrendje egybeesik, ha a térkép harmadik-negyedik oszlopait és harmadik-negyedik sorait felcserélik.

Az igazságtáblázat minden sora és a Karnaugh-térkép minden cellája a DNF egy tagjának felel meg, így a változók (közvetlen és inverz) előfordulásait a térkép fejlécében és bal oldali oszlopában lehet jelezni, ahogy az SDNF-ben ( b). Ennek a megjelenítési stílusnak van egy rövidített változata, ahol a segédsorok és oszlopok jelzik, hogy az egyes változók milyen formában, direkt vagy inverz formában jelennek meg a térkép megfelelő sorában vagy oszlopában (c).

Végül néhány esetben a vonalak oszlopokat és sorokat jelölnek a térkép szélein, ahol a megfelelő változó közvetlen formában (d) van ábrázolva.

a) b) c) d)

Hogyan kell dolgozni a Karnot térképpel

A Karnaugh-térképpel való munka kezdeti információja a minimalizált függvény igazságtáblázata . Az igazságtábla teljes információt tartalmaz a logikai függvényről, megadva annak értékeit az összes lehetséges 2 n X 1 … X n bemeneti változókészleten . A Karnaugh-térkép 2 n cellát is tartalmaz, amelyek mindegyikéhez egyedi X 1 … X n bemeneti változók tartoznak . Így az igazságtáblázat és a Karnaugh-térkép között egy az egyben megfelelés van, és a Karnaugh-térkép egy megfelelően formázott igazságtáblázatnak tekinthető.

Ebben a részben a 2. ábrán látható igazságtáblázat által megadott négy változó függvényét használjuk példaként. 2a. A Carnot térkép ugyanerre a függvényre az ábrán látható. 2b.

Ragasztási elvek

A Karnaugh térképen egy téglalap alakú területet, amely 2 k azonos értékből áll (egyesek vagy nullák, attól függően, hogy milyen formát kell beszereznie), ragasztásnak , csoportnak vagy területnek nevezzük . Az összes nulla (egyes) eloszlását a Carnot-térképen a ragasztások között borításnak nevezzük . A Boole-függvény minimalizálása érdekében a Carnot-térképnek olyan lefedettségét kell megszerkeszteni, hogy a ragasztások száma minimális legyen, és az egyes ragasztások mérete a lehető legnagyobb legyen. Ehhez be kell tartania a következő szabályokat.

Ugyanazon Carnot térkép celláit egyesekkel (a) és nullákkal (b) is felragaszthatjuk. Az első a DNF , a második a CNF eléréséhez szükséges .

a) b)

Csak téglalap alakú területeket ragaszthat fel annyi egyessel (nullával), amely kettő egész hatványa (1, 2, 4, 8, 16, 32… cella).

Javasoljuk, hogy a lehető legtöbb ragasztási területet válassza ki. Ha a ragasztási terület nem a lehető legnagyobb, akkor ez nem hiba, de a DNF (CNF) nem lesz a minimum.

Egyes helyzetekben az elrendezésben izolált egy vagy nulla keletkezik, amely nem szerepelhet egyetlen területen sem. Ebben az esetben az egység (nulla) összeragad „önmagával”. Nem hagyhat "függő" egyeseket (nullákat), mert ez a függvény hibás kifejezéséhez vezet.
Minden egyesnek (nullának) valamilyen területre kell esnie.

A ragasztandó területnek ugyanazokat az értékeket kell tartalmaznia - csak egyeseket vagy csak nullákat.

A 3-as és 4-es számú változót tartalmazó Karnaugh-térképekre a következő szabály érvényes: az egyes vízszintes és függőleges szélső cellák határolják egymást, és téglalapokká kombinálhatók (topológiailag a Karnaugh-térkép egy tórusz). Ennek a szabálynak a következménye a Karnaugh-térkép mind a négy sarokcellája szomszédossága 4 változó esetén. A 3-nál kevesebb változót tartalmazó Carnot-leképezéseknél ennek a szabálynak nincs értelme, mivel a szélső cellák már határosak egymással; a négynél több változót tartalmazó Karnaugh-térképek esetében a szomszédsági szabályok bonyolultabbak.

A Karnot térkép egy cellája egyszerre több területet is tartalmazhat. Ez a Boole-függvények nyilvánvaló tulajdonságából következik: egy már létező tag (tényező) ismétlődése nem befolyásolja a függvényt: $A\vee A=A;A\cdot A=A.$

Nem szabad feleslegesen minden lehetséges ragasztásba beletenni egy cellát, ez nem hiba, de bonyolítja a képletet. A DNF ( CNF ) minimalitás szempontjából a ragasztások száma a lehető legkisebb legyen (minden további ragasztás további tagot generál), és a ragasztásban a cellák száma minél nagyobb legyen (minél több cella van a ragasztásnál minél kevesebb változót tartalmaz a kifejezés A 2 k cella n - k változós tagot generál ) [4] .

Az SDNF-től és az SKNF-től eltérően a DNF és a CNF nem mindig egyedi. Egyes funkciókhoz több, egymással egyenértékű DNF (CNF) létezik, amelyek megfelelnek a Karnaugh-térkép téglalap alakú területekkel való lefedésének különböző módjainak. Nagyon gyakran két különböző DNF (CNF) ugyanolyan bonyolultságú, ami nem teszi lehetővé a minimális képlet egyértelmű megválasztását.

Bizonytalan jelentésű kártyák

A gyakorlatban vannak olyan esetek, amikor az argumentumok egyes értékeinél a Boole-függvény nincs megadva. Például egy logikai függvény olyan digitális eszközt ír le, amelynél a bemeneti jelek egyes kombinációi fizikailag lehetetlenek, vagy a bemeneti jelek bizonyos értékei esetében az eszköz reakciója nem számít. Ilyen esetekben "bizonytalan feltételekről" beszélünk, és egy ilyen függvényt "részlegesen meghatározott"-nak vagy egyszerűen "részlegesnek" neveznek [5] .

Az ábrán egy F digitális eszköz látható négy bináris bemenettel . A bemeneti jelek olyan érzékelők leolvasásai lehetnek, amelyek egy áramkörön működnek, és ezért csak két értékük van - „be” (1) és „kikapcsolva” (0). Tételezzük fel, hogy a készülék tervezési adottságai miatt a 2. és 4. szenzor nem tud egyszerre működni, vagyis a jelek kombinálása fizikailag lehetetlen. Ebben az esetben nem számít a függvény értéke a Karnot térkép négy cellájában, amit feltételesen a "×" jel mutat. ${\displaystyle x_{1}...x_{4))$ $x_{2}x_{4}=11$

Az ilyen cellák tetszőlegesen beépíthetők bármilyen ragasztásba, és nem is, azaz tetszőlegesen 1 vagy 0 [5] definiálhatók .

Térkép átalakítása képletté

Ha a Karnaugh-térkép összes ragasztását meghatároztuk, a kapott Karnaugh-térképet képletté kell alakítani. Ennek során a következő alapelvek vezérlik őket:

A Karnaugh térképen minden egyes ragasztás DNF-kifejezést jelent, ha egyesekkel ragaszt, és CNF-tényezőt, ha nullákkal.
Ha a ragasztás 2k sejtet fed le, akkor a DNF-ben egy n–k faktorból álló tagnak, a CNF-ben pedig egy nk tagú tényezőnek fog megfelelni. Például 4 változó függvényének minimalizálása esetén 4 egység ragasztása két tényezős tagnak felel meg.
A Karnaugh térképen minden változóhoz két zóna tartozik, amelyek mindegyike pontosan a térkép celláinak felét foglalja el. Az egyik zónában a változó közvetlen formában van jelen, a másikban - inverz formában. Ha a ragasztás teljes egészében ezen zónák egyikében van, akkor a megfelelő változó a kifejezésben (tényezőben) szerepel. Ha a ragasztás egyidejűleg két zónában van, akkor ez a változó abszorpciót tapasztal, és nincs jelen a kifejezésben (tényezőben).

Leírás

Egy Karnaugh-térkép tetszőleges számú változóra készíthető, de kényelmes, ha legfeljebb öt változóval dolgozhatunk. Lényegében a Karnaugh-térkép egy igazságtáblázat, amely mátrixként jelenik meg kétdimenziós formában.

Ennek a térképnek minden cellája egy sornak felel meg a klasszikus igazságtáblázatban, és változók sorával jelöljük inverzióval és anélkül. Például adja meg az igazságtáblázatot egy 4 változóból álló függvényhez az egyik sor így néz ki: 0 1 1 0 | 1, akkor a Karnaugh térképen az ennek a sornak megfelelő cellának lesz neve , és ebbe a cellába kerül az 1. A cellanevek jelzését a Karnaugh térképen általában egy további sor a tetején és egy további oszlop a bal oldalon hajtja végre. . $x_{1},x_{2},x_{3},x_{4},$ ${\overline {x}}_{1},x_{2},x_{3},{\overline {x}}_{4}$

Lényeges, hogy a Carnot-térképen a szomszédos celláknak szükségszerűen szomszédos kódjaik legyenek a Hamming-távolság értelmében, azaz a szomszédos cellák közötti Hamming-távolság egyenlő 1-gyel, és csak az egyik állapotában térjenek el egymástól – inverzióval vagy anélkül. és csak az egyik változó. A szomszédos cellák az egymással szomszédos cellák, valamint a bal és a jobb szélső oszlop cellái, valamint az első és az utolsó sor cellái is szomszédos celláknak minősülnek. Így egy Carnot-térkép egy síkon topológiailag egyenértékű egy tórusz felületével a háromdimenziós térben, vagy egy hipertóruszsal egy olyan térben, amelynek mérete 1-el nagyobb, mint a megfelelő többdimenziós Karnot-térkép dimenziója.

Mivel a változók permutációja egy logikai függvényben magát a függvényt nem változtatja meg, azaz például, vagy ami ugyanaz, az igazságtáblázatban a változók oszlopainak permutációja nem változtatja meg a függvényt, több lehetőség is van az igazságtáblázat megjelenítéséhez egy Karnaugh-térképen, miközben fenntartja a sejtek "szomszédságát". A gyakorlatban azonban a Karnaugh-térképet leggyakrabban egy növekményes Gray-kóddal töltik ki a sorok és oszlopok kijelölésére. Ez a megközelítés garantálja a Karnot térkép létrehozását a szubjektív hibák elkerülésével. $F(x_{1},x_{2},x_{3},x_{4})=F(x_{4},x_{2},x_{3},x_{1})$

A térkép kitöltésekor a sor és az oszlop metszéspontjában a megfelelő érték kerül be az igazságtáblázatból - 0 vagy 1. A térkép kitöltése után elindul a minimalizálás.

Ha szükséges a minimális DNF elérése , akkor a Térképen csak azokat a cellákat vesszük figyelembe, amelyekben egyesek vannak, ha CNF -re van szükség , akkor azokat a cellákat, amelyek nullákat tartalmaznak. Maga a minimalizálás a következő szabályok szerint történik (például DNF).

Az egyeseket tartalmazó szomszédos cellákat egy területté egyesítjük úgy, hogy az egyik terület ( integer = 0 ... ) cellákat tartalmazzon (ne feledjük, hogy a szélső sorok és oszlopok szomszédosak), a terület ne tartalmazzon nullákat tartalmazó cellákat; $2^{n}$ $n$ $\infty$
A területnek szimmetrikusnak kell lennie a tengely(ek)re (a tengelyek négy cellánként helyezkednek el);
A tengely(ek)re szimmetrikusan elhelyezkedő, nem szomszédos régiók egyesíthetők;
A terület legyen a lehető legnagyobb, a területek száma pedig a lehető legkisebb;
A régiók átfedhetik egymást;
Számos lefedettségi lehetőség áll rendelkezésre.

Ezután vesszük az első területet, és megnézzük, mely változók nem változnak ezen a területen, írjuk ki ezeknek a változóknak a konjunkcióját ; ha a nem változó változó nulla, tedd rá az inverziót . Vegyük a következő területet, ugyanazt csináljuk, mint az elsőnél, és így tovább minden területen. A területek konjunkcióit a diszjunkció kombinálja .
Például (a Maps 2 változóhoz):

{\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}

A CNF esetében minden ugyanaz, csak a nullákkal rendelkező cellákat tekintjük, az ugyanazon a területen belüli változatlan változókat diszjunkcióba vonjuk (az inverziókat egységváltozók fölé írjuk), a régiók diszjunkcióit pedig konjunkcióvá. Ezzel befejeződik a minimalizálás. Tehát az ábrán látható Karnot térképhez. 1, a kifejezés DNF formátumban így fog kinézni:

$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 formátumban:

$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}).$

A De Morgan törvényei segítségével DNF-ről CNF-re és vissza is válthat .

Példák

1. példa

A fiú Kolya-nak anyja, apja, nagyapja és nagymamája van. Kolja akkor és csak akkor megy sétálni az utcára, ha legalább két rokona megengedi neki.

A rövidség kedvéért jelöljük Kolya rokonait betűkkel:
anya - X1
apa - X2
nagypapa - X3
nagymama - X4

Állapodjunk meg, hogy a hozzátartozók beleegyezését egynek, a nézeteltérést nullának jelöljük. A séta lehetőségét f betűvel jelöljük, Kolja sétálni megy - f = 1, Kolja nem megy sétálni - f = 0.
Készítsünk igazságtáblázatot:

Rajzoljuk át az igazságtáblázatot 2 dimenziós formában:

Rendezzük át benne a sorokat és oszlopokat a Gray kódnak megfelelően (az utolsó és az utolsó előtti oszlop felcserélődik). Megkapott Karnot kártya:

Töltsük meg az igazságtáblázat értékeivel (az első sor nem felel meg az igazságtáblázatnak, mivel f=0 és nincs járási engedély):

A szabályoknak megfelelően minimalizáljuk:

Minden terület 2^n sejtet tartalmaz;
Mivel a Karnaugh-térkép négy változóból áll, a tengelyek a térkép határain helyezkednek el, és nem láthatók (további részletekért lásd az 5 változós térkép példáját );
Mivel a Karnaugh-térkép négy változóból áll, a tengelyekre szimmetrikusan minden terület szomszédos egymással (további részletekért lásd az 5 változós térképek példáját );
Az S3, S4, S5, S6 régiók a lehető legnagyobbak;
Minden terület metszi egymást (opcionális);
Ebben az esetben csak egy racionális lehetőség van.

$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$

Most a kapott minimális DNF-nek megfelelően lehetséges egy logikai áramkör felépítése :

A diszjunkciós funkciót megvalósító hat bemenetes VAGY elem hiánya miatt szükségessé vált az öt- és kétbemenetes elemek (D7, D8) kaszkádolása.

Csináljunk 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)$

Lásd még

DNF
KNF
SDNF
SKNF
Boole-függvények minimalizálása Quine-módszerrel
A kombinált áramkörök minimalizálása
hu:Espresso heurisztikus logikai minimalizáló
Quine-McCluskey módszer

Jegyzetek

↑ Givone D. Rosser R. (1983), p. 67-76.
↑ Veitch E. W. (1952. május).
↑ Karnaugh M. (1953. november).
↑ 1 2 Givone D. Rosser R. (1983), p. 69.
↑ 1 2 Givone D. Rosser R. (1983), p. 75.

Források

Veitch EW (1952. május) Egy diagram módszer az igazságfüggvények egyszerűsítésére. Proceedings, Association for Computing Machinery, Pittsburgh, Pa., 1952. május 2., 3., pp. 127-133. DOI:10.1145/609784.609801.
Karnaugh M. (1953. november) The Map Method for Synthesis of Combinational Logic Circuits . Az American Institute of Electrical Engineers tranzakciói, I. rész: Kommunikáció és elektronika. 72(5): 593-599. DOI:10.1109/TCE.1953.6371932.
Tokheim R. A digitális elektronika alapjai: Per. angolról. — M.: Mir, 1988. — 392 p., ill. (4. fejezet, 88-95. oldal)
Givone D. Rosser R. Mikroprocesszorok és mikroszámítógépek: Bevezető tanfolyam: Per. angolról. - M .: Mir, 1983. - 464 p., ill.

Linkek

Karnaugh térképek használata gyakorlati alkalmazásokban , Közlekedési lámpák vezérlési rendszerének kidolgozása.

Szoftver

Karnaugh Minimizer , Kereskedelmi Windows alkalmazás (gyakran nem működik megfelelően, például ennél az egyenletnél: 0,1,5,8,10,13).
Logic Minizer , Kereskedelmi Windows-alkalmazás, de Unix rendszeren is futtatható.
Kmap Minizer Online alkalmazás (Flash).
GKMap , ingyenes szoftver a SourceForge.net oldalon .
Karnaugh Map Minizer , ingyenes (de gyakran hibás) szoftver a SourceForge.net oldalon .
Gorgeous Karnaugh , a Gorgeous Karnaugh kereskedelmi Karnaugh minimalizálási szoftvere.

Videó

Carnot kártyák. Előadás . Youtube.