Carnotova mapa

Carnotova mapa ( Carnotova kostka , Carnotův diagram , Veitchova mapa ) je grafický způsob, jak znázornit booleovské funkce s cílem jejich pohodlné a vizuální ruční minimalizace [1] .

Je to jeden z ekvivalentních způsobů popisu nebo specifikace logických funkcí spolu s pravdivostní tabulkou nebo výrazy booleovské algebry . Transformace Karnaughovy mapy na pravdivostní tabulku nebo booleovskou formuli a naopak se provádí pomocí elementárního algoritmu.

Pohodlnost a jasnost takové reprezentace logické funkce je způsobena skutečností, že logické členy, na které lze aplikovat operace párového neúplného lepení a elementární absorpce , jsou seskupeny v Carnotově mapě do podoby vizuálně zřejmých obdélníkových polí obsahujících stejné hodnoty (nuly a jedničky) ve svých buňkách.

Karnaughovy mapy lze považovat za vývoj do roviny n - rozměrné booleovské krychle a rozměr této hyperkrychle se shoduje s počtem proměnných reprezentované funkce a každý vrchol hyperkrychle odpovídá jedna ku jedné. jedna buňka Karnaughovy mapy. Graficky je Karnaughova mapa znázorněna jako obdélník nebo čtverec buněk, jejichž počet je roven , a libovolné dvě sousední buňky svisle nebo vodorovně nebo jinými slovy v okolí von Neumanna popisují pojmy, které se liší pouze v jedné proměnné . - s logickou negací a bez logické negace . Také sousedí první a poslední řádek, sloupec zcela vlevo a vpravo, takže Carnotova tabulka je ve skutečnosti vývojem logické hyperkrychle na povrchu toroidu . Je možné sestavit různé mapy pro stejnou funkci, které splňují podmínku: geometrické okolí buněk ve smyslu von Neumanna je logické sousedství členů - to znamená, že Hammingova vzdálenost mezi členy sousedních buněk je rovna na 1. Kterákoli z těchto tabulek je stejně vhodná pro minimalizaci funkce, ale obvykle jsou proměnné v řádcích a sloupcích v Karnaughově mapě uspořádány podle reflexivního Grayova kódu kvůli mnemotechnické pomůcce a srozumitelnosti. $2^{n}$

Historie

Karnaughovy mapy zavedl v roce 1952 Edward V. Veitch [2] a v roce 1953 je vylepšil fyzik z Bellových laboratoří Maurice Karnaugh , aby se zjednodušil návrh digitálních systémů [3] .

Základní principy

Karnaughova mapa je pravdivostní tabulka formátovaná speciálním způsobem, vhodná pro vizuální ruční minimalizaci. Výsledkem minimalizace je buď disjunktivní normální forma (DNF) nebo konjunktivní normální forma (CNF). V prvním případě se pracuje s buňkami mapy, kde jsou jedničky, ve druhém - s buňkami, kde jsou nuly. V původní mapě, stejně jako v pravdivostní tabulce, každá jednotka odpovídá jednomu členu dokonalé disjunktivní normální formy (PDNF) a každá nula odpovídá jednomu členu dokonalé konjunktivní normální formy (CKNF) .

Blízké skupiny jedniček nebo nul na Karnaughově mapě jsou kombinovány do pravoúhlých oblastí nebo „lepidel“ podle velikosti buněk. Každá taková skupina v konečném logickém vzorci bude odpovídat jednomu členu (pokud předpokládáme, že logická operace „ OR “ je „součet“ a logická operace „ AND “ je „násobení“, pak jeden člen odpovídá jednomu termínu v v případě DNF, nebo na jeden faktor v případě CNF) obsahující proměnné, se toto seskupení obvykle nazývá "lepení" [4] . Práce s mapou tedy spočívá ve výběru optimální sady několika skupin jedniček (nul) a jejich převedení do logického výrazu. ${\displaystyle 2^{a}\times 2^{b))$ $nab$

Principy minimalizace

Hlavní metodou pro minimalizaci logických funkcí reprezentovaných jako SDNF nebo SKNF je operace párového neúplného lepení a elementární absorpce. Operace párového lepení se provádí mezi dvěma termíny obsahujícími stejné proměnné, jejichž výskyty (přímé a inverzní) jsou stejné pro všechny proměnné kromě jedné. V tomto případě mohou být všechny proměnné, kromě jedné, vyjmuty ze závorek a přímé a inverzní výskyty jedné proměnné zbývající v závorkách mohou být absorbovány. Například:

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

Podobně pro CNF:

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

Možnost absorpce vyplývá ze zřejmých rovností:

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

Hlavním úkolem při minimalizaci SDNF a SKNF je tedy hledání termínů vhodných pro lepení s následnou absorpcí, což pro funkce mnoha logických proměnných může být docela obtížný úkol. Karnaughovy mapy poskytují vizuální způsob, jak takové výrazy najít.

Booleovské funkce N proměnných, reprezentovaných jako SDNF nebo SKNF, mohou obsahovat pouze různé termíny. Všechny tyto elementární členy mohou být reprezentovány jako nějaká struktura topologicky ekvivalentní -rozměrné krychli a jakékoli dva členy spojené hranou jsou vhodné pro lepení a absorpci. $2^{n}$ $n$

Na obrázku je jednoduchá pravdivostní tabulka pro funkci dvou proměnných, 2-rozměrná krychle (čtverec) odpovídající této tabulce a dále 2-rozměrná krychle s označením členů SDNF a ekvivalentní tabulkou pro seskupení pojmů:

V případě funkce tří proměnných se musíme vypořádat s trojrozměrnou krychlí. To je složitější a méně vizuální, ale technicky možné. Obrázek ukazuje jako příklad pravdivostní tabulku pro booleovskou funkci tří proměnných a odpovídající krychli.

Jak je vidět z obrázku, pro trojrozměrný případ jsou možné složitější konfigurace termínů. Například čtyři členy, které patří ke stejné ploše krychle, jsou spojeny do jednoho členu s absorpcí dvou proměnných:

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

V obecném případě můžeme říci, že termíny patřící do jedné oné -rozměrné plochy hyperkrychle jsou slepeny do jednoho termínu, zatímco proměnné jsou absorbovány. $2^k$ $k$ $k$

Pro zjednodušení práce s booleovskými funkcemi velkého množství proměnných byl navržen následující pohodlný trik. Kostka, která je strukturou pojmů, je rozložena na rovinu, jak je znázorněno na obrázku. Tak je možné reprezentovat booleovské funkce s více než dvěma proměnnými ve formě ploché tabulky. Je třeba si uvědomit, že pořadí kódů termínů v tabulce (00 01 11 10) neodpovídá pořadí binárních čísel zapsaných v lexikografickém pořadí (00 01 10 11) a buňky umístěné v krajních sloupcích tabulky vedle sebe.

Podobně lze pracovat s logickými funkcemi většího počtu proměnných.

Styly zobrazení pro Carnotovy mapy

Tradičně existuje několik stylů prezentace Karnotových map. Záhlaví a levý sloupec často obsahují číselné hodnoty proměnných, stejně jako jsou uvedeny v pravdivostní tabulce (a). V tomto stylu je nejvíce zřejmé, že Karnaughova mapa je zvláštní formou reprezentace pravdivostní tabulky. Buňky Karnaughovy mapy však následují v trochu jiném pořadí než řádky v pravdivostní tabulce, protože v pravdivostní tabulce je zvykem uspořádat řádky v lexikografickém nárůstu binárních čísel. Například v Karnaughově mapě pro čtyři proměnné se pořadí buněk mapy a řádků pravdivostní tabulky bude shodovat, pokud se zamění třetí-čtvrtý sloupec a třetí-čtvrtý řádek mapy.

Každý řádek pravdivostní tabulky a každá buňka Karnaughovy mapy odpovídá jednomu členu DNF, takže výskyty proměnných (přímých a inverzních) mohou být uvedeny v záhlaví a levém sloupci mapy, jak vypadají v SDNF ( b). Existuje zkrácená verze tohoto prezentačního stylu, kde pomocné řádky a sloupce udávají, v jaké formě, přímé nebo inverzní, je každá proměnná prezentována v odpovídajícím řádku nebo sloupci mapy (c).

Konečně v některých případech čáry označují sloupce a řádky na okrajích mapy, kde je odpovídající proměnná znázorněna v přímém tvaru (d).

a) b) c) d)

Jak pracovat s Karnotovou mapou

Výchozí informací pro práci s Karnaughovou mapou je pravdivostní tabulka minimalizované funkce. Pravdivostní tabulka obsahuje kompletní informace o logické funkci s uvedením jejích hodnot na všech možných 2n sadách vstupních proměnných X 1 … X n . Karnaughova mapa také obsahuje 2 n buněk, z nichž každá je spojena s jedinečnou sadou vstupních proměnných X 1 … X n . Existuje tedy vzájemná korespondence mezi pravdivostní tabulkou a Karnaughovou mapou a Karnaughovu mapu lze považovat za vhodně formátovanou pravdivostní tabulku.

V této části je jako příklad použita funkce čtyř proměnných dané pravdivostní tabulkou znázorněnou na obr. 2. Obr. 2a. Carnotova mapa pro stejnou funkci je na Obr. 2b.

Principy lepení

Obdélníková oblast v Karnaughově mapě, která se skládá ze 2 k identických hodnot (jedniček nebo nul, podle toho, jakou formu potřebujete získat), se bude nazývat lepení , skupina nebo oblast . Rozložení všech nul (jedniček) v Carnotově mapě přes lepení se bude nazývat krycí . Pro minimalizaci Booleovské funkce je nutné zkonstruovat takové pokrytí Carnotovy mapy, aby počet lepení byl minimální a velikost každého lepení co největší. Chcete-li to provést, musíte dodržovat následující pravidla.

Buňky stejné Carnotovy mapy lze slepit jak jedničkami (a), tak nulami (b). První je nezbytný pro získání DNF , druhý je nezbytný pro získání CNF .

a) b)

Slepit lze pouze obdélníkové oblasti s počtem jedniček (nul), což je celá mocnina dvou (1, 2, 4, 8, 16, 32… buněk).

Doporučuje se zvolit maximální možné plochy lepení. Pokud plocha lepení není maximální možná, nebude to chyba, ale DNF (CNF) nebude minimum.

V některých situacích se v rozložení vytvoří izolovaná jednička nebo nula, které nelze zahrnout do žádné oblasti. V tomto případě jednotka (nula) drží pohromadě „se sebou“. Nemůžete ponechat "visící" jedničky (nuly), protože to povede k nesprávnému výrazu pro funkci.
Všechny jedničky (nuly) musí spadat do nějaké oblasti.

Oblast, která se má lepit, musí obsahovat stejné hodnoty - pouze jedničky nebo pouze nuly.

Pro Karnaughovy mapy s počtem proměnných 3 a 4 platí následující pravidlo: krajní buňky každé vodorovné a každé svislé se vzájemně ohraničují a lze je skládat do obdélníků (topologicky je Karnaughova mapa torus). Důsledkem tohoto pravidla je sousedství všech čtyř rohových buněk Karnaughovy mapy pro 4 proměnné. Pro Carnotovy mapy s méně než 3 proměnnými toto pravidlo nedává smysl, protože krajní buňky již spolu sousedí; pro Karnaughovy mapy s více než čtyřmi proměnnými jsou pravidla sousedství složitější.

Jedna buňka Karnotovy mapy může být zahrnuta do několika oblastí najednou. To vyplývá ze zřejmé vlastnosti booleovských funkcí: opakování již existujícího termínu (faktoru) nemá vliv na funkci: $A\vee A=A;A\cdot A=A.$

Buňku byste neměli zbytečně zapojovat do všech možných lepení, není to chyba, ale komplikuje to vzorec. Z hlediska minimalizace DNF ( CNF ) by měl být počet slepení co nejmenší (každé další slepení generuje další člen) a počet buněk ve slepení co největší (čím více buněk při lepení platí, že čím méně proměnných člen obsahuje, 2 k buněk generuje člen s n - k proměnnými) [4] .

Na rozdíl od SDNF a SKNF nejsou DNF a CNF vždy jedinečné. Pro některé funkce existuje několik vzájemně ekvivalentních DNF (CNF), které odpovídají různým způsobům pokrytí Karnaughovy mapy pravoúhlými oblastmi. Velmi často mají dvě různé DNF (CNF) stejnou složitost, což neumožňuje jednoznačnou volbu minimálního vzorce.

Karty s nejistým významem

V praxi nastávají případy, kdy pro některé hodnoty argumentů není definována booleovská funkce. Například funkce Boolean popisuje digitální zařízení, pro které jsou některé kombinace vstupních signálů fyzicky nemožné, nebo pro některé hodnoty vstupních signálů nezáleží na reakci zařízení. V takových případech se hovoří o „nejistých podmínkách“ a funkce tohoto druhu se nazývá „částečně definovaná“ nebo jednoduše „částečná“ [5] .

Obrázek ukazuje digitální zařízení F se čtyřmi binárními vstupy . Vstupní signály mohou být naměřené hodnoty senzorů, které pracují na obvodu, a proto mají pouze dvě hodnoty – „on“ (1) a „off“ (0). Předpokládejme, že vzhledem ke konstrukčním vlastnostem zařízení nemohou 2. a 4. snímač pracovat současně, to znamená, že kombinace signálů je fyzicky nemožná. V tomto případě nezáleží na hodnotě funkce ve čtyřech buňkách Karnotovy mapy, která je podmíněně znázorněna symbolem „×“. ${\displaystyle x_{1}...x_{4))$ $x_{2}x_{4}=11$

Takové buňky mohou být libovolně zahrnuty v jakémkoli lepení a také nemusí být zahrnuty v žádném lepení, to znamená, že mohou být volitelně definovány jako 1 nebo 0 [5] .

Převod mapy na vzorec

Po určení všech lepení na Karnaughově mapě je nutné výslednou Karnaughovu mapu převést do vzorce. Při tom se řídí následujícími zásadami:

Každé lepení na Karnaughově mapě je při lepení jedničkami DNF termín a při lepení nulami CNF faktor.
Pokud lepení pokrývá 2k buněk, pak bude odpovídat členu n–k faktorů v DNF a faktoru s nk členů v CNF. Například při minimalizaci funkce 4 proměnných bude slepení 4 jednotek odpovídat termínu dvou faktorů.
V Karnaughově mapě jsou pro každou proměnnou dvě zóny, z nichž každá zabírá přesně polovinu buněk mapy. V jedné zóně je proměnná přítomna v přímé formě, ve druhé - v inverzní formě. Leží-li lepení celé v jedné z těchto zón, příslušná proměnná je přítomna v termínu (faktoru). Pokud lepení leží současně ve dvou zónách, pak tato proměnná prodělává absorpci a není přítomna v termínu (faktoru).

Popis

Karnaughovu mapu lze sestavit pro libovolný počet proměnných, ale je vhodné pracovat maximálně s pěti proměnnými. Karnaughova mapa je v podstatě pravdivostní tabulka prezentovaná jako matice ve 2-rozměrné formě.

Každá buňka této mapy odpovídá jednomu řádku v klasické pravdivostní tabulce a je označena řadou proměnných s inverzí a bez ní. Nechť v pravdivostní tabulce pro funkci 4 proměnných například jeden z řádků vypadá takto: 0 1 1 0 | 1, pak bude mít buňka v Karnaughově mapě odpovídající tomuto řádku název a do této buňky se vloží 1. Označení názvů buněk v Karnaughově mapě se obvykle provádí dodatečným řádkem nahoře a dodatečným sloupcem vlevo. . $x_{1},x_{2},x_{3},x_{4},$ ${\overline {x}}_{1},x_{2},x_{3},{\overline {x}}_{4}$

Je nezbytné, aby v Carnotově mapě sousední buňky nutně měly sousední kódy ve smyslu Hammingovy vzdálenosti , to znamená, že Hammingova vzdálenost mezi sousedními buňkami je rovna 1 a liší se pouze stavem - s inverzí nebo bez, jedné a pouze jedna z proměnných. Sousední buňky jsou buňky vedle sebe vedle sebe, také buňky levého a pravého sloupce a buňky prvního a posledního řádku se považují za sousední buňky. Carnotova mapa v rovině je tedy topologicky ekvivalentní povrchu torusu v trojrozměrném prostoru nebo hypertoru v prostoru s rozměrem 1 větším, než je rozměr odpovídající vícerozměrné Karnotovy mapy.

Protože permutace proměnných v logické funkci nemění funkci samotnou, tedy například, nebo, což je totéž, permutace sloupců proměnných v pravdivostní tabulce nemění funkci, existuje několik možností pro zobrazení pravdivostní tabulky na Karnaughově mapě při zachování „sousedství“ buněk . V praxi se však Karnaughova mapa nejčastěji vyplňuje pomocí přírůstkového Grayova kódu k označení řádků a sloupců. Tento přístup zaručuje generování Karnotovy mapy s vyloučením subjektivních chyb. $F(x_{1},x_{2},x_{3},x_{4})=F(x_{4},x_{2},x_{3},x_{1})$

Po vyplnění mapy se na průsečíku řádku a sloupce zadá odpovídající hodnota z pravdivostní tabulky - 0 nebo 1. Po vyplnění mapy je spuštěna minimalizace.

Pokud je nutné získat minimální DNF , pak v Mapě uvažujeme pouze ty buňky, které obsahují jedničky, pokud je potřeba CNF , pak uvažujeme ty buňky, které obsahují nuly. Samotná minimalizace se provádí podle následujících pravidel (například DNF).

Spojíme sousední buňky obsahující jedničky do oblasti tak, že jedna oblast obsahuje ( celé číslo = 0 ... ) buňky (nezapomeňte, že krajní řádky a sloupce spolu sousedí), oblast by neměla obsahovat buňky obsahující nuly; $2^{n}$ $n$ $\infty$
Oblast musí být symetrická k ose (osám) (osy jsou umístěny po čtyřech buňkách);
Nesousedící oblasti umístěné symetricky k ose (osám) mohou být spojeny do jedné;
Oblast by měla být co největší a počet oblastí co nejmenší;
Regiony se mohou překrývat;
K dispozici je několik možností pokrytí.

Dále si vezmeme první oblast a uvidíme, které proměnné se v této oblasti nemění, zapište konjunkci těchto proměnných; pokud je neměnná proměnná nula, umístěte nad ni inverzi . Vezmeme další oblast, uděláme to samé jako u první a tak dále pro všechny oblasti. Konjunkce oblastí se spojují disjunkcí .
Například (pro Mapy pro 2 proměnné):

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

Pro CNF je vše stejné, pouze uvažujeme buňky s nulami, spojujeme neměnné proměnné v rámci stejné oblasti do disjunkcí (inverze jsou kladeny na jednotkové proměnné) a disjunkce oblastí jsou kombinovány do konjunkce. Tím je minimalizace dokončena. Takže pro Karnotovu mapu na obr. 1, výraz ve formátu DNF bude vypadat takto:

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

Ve formátu CNF:

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

Můžete také přepnout z DNF na CNF a zpět pomocí De Morganových zákonů .

Příklady

Příklad 1

Chlapec Kolja má matku, otce, dědečka a babičku. Kolja půjde na procházku na ulici, pokud mu to alespoň dva příbuzní dovolí.

Pro stručnost označme Koljovy příbuzné pomocí písmen:
máma - X1
táta - X2
dědeček - X3
babička - X4

Souhlasíme s označením souhlasu příbuzných za jedničku, nesouhlasu za nulu. Příležitost jít na procházku bude označena písmenem f, Kolja jde na procházku - f = 1, Kolja nejde na procházku - f = 0.
Udělejme pravdivostní tabulku:

Překreslíme pravdivostní tabulku ve 2-rozměrné podobě:

Přeuspořádejme v něm řádky a sloupce v souladu s Grayovým kódem (poslední a předposlední sloupec jsou prohozeny). Přijatá karta Karnot:

Vyplňte jej hodnotami z pravdivostní tabulky (první řádek neodpovídá pravdivostní tabulce, protože f=0 a není povoleno chodit):

Minimalizujeme v souladu s pravidly:

Všechny oblasti obsahují 2^n buněk;
Vzhledem k tomu, že Karnaughova mapa je ve čtyřech proměnných, jsou osy umístěny na okrajích mapy a nejsou viditelné (více podrobností viz příklad mapy v 5 proměnných );
Vzhledem k tomu, že Karnaughova mapa je ve čtyřech proměnných, všechny oblasti symetricky k osám spolu sousedí (podrobněji viz příklad Maps in 5 variables );
Oblasti S3, S4, S5, S6 jsou co největší;
Všechny oblasti se protínají (volitelné);
V tomto případě existuje pouze jedna racionální možnost.

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

Nyní, podle získaného minimálního DNF, je možné sestavit logický obvod :

Vzhledem k absenci šestivstupového prvku OR, který implementuje funkci disjunkce, bylo nutné kaskádovat pěti- a dvouvstupové prvky (D7, D8).

Udělejme 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)$

Viz také

DNF
KNF
SDNF
SKNF
Minimalizace booleovských funkcí Quineovou metodou
Minimalizace kombinačních obvodů
cs:Minimalizátor heuristické logiky espressa
Quine-McCluskeyova metoda

Poznámky

↑ Givone D. Rosser R. (1983), s. 67-76.
↑ Veitch E. W. (květen 1952).
↑ Karnaugh M. (listopad 1953).
↑ 1 2 Givone D. Rosser R. (1983), str. 69.
↑ 1 2 Givone D. Rosser R. (1983), str. 75.

Zdroje

Veitch EW (květen 1952) Metoda grafu pro zjednodušení funkcí pravdy. Proceedings, Association for Computing Machinery, Pittsburgh, Pa., 2., 3. května 1952, pp. 127-133. DOI:10.1145/609784.609801.
Karnaugh M. (listopad 1953) The Map Method for Synthesis of Combinational Logic Circuits . Transakce Amerického institutu elektrických inženýrů, část I: Komunikace a elektronika. 72(5): 593-599. DOI:10.1109/TCE.1953.6371932.
Tokheim R. Základy digitální elektroniky: Per. z angličtiny. — M.: Mir, 1988. — 392 s., ill. (Kapitola 4, strany 88–95)
Givone D. Rosser R. Mikroprocesory a mikropočítače: Úvodní kurz: Per. z angličtiny. - M .: Mir, 1983. - 464 s., ill.

Odkazy

Využití Karnaughových map v praktických aplikacích , Vývoj schématu řízení semaforů.

Software

Karnaugh Minimizer , komerční aplikace pro Windows (často nefunguje správně, například pro tuto rovnici: 0,1,5,8,10,13).
Logic Minimizer , komerční aplikace pro Windows, ale lze ji spustit na Unixu.
Minimalizátor Kmap Online aplikace (Flash).
GKMap , svobodný software na SourceForge.net .
Karnaugh Map Minimizer , bezplatný (ale často chybný) software na SourceForge.net .
Gorgeous Karnaugh , komerční software pro minimalizaci Karnaugha společnosti Gorgeous Karnaugh.

Video

Carnotovy karty. Přednáška . Youtube.