Karnaughova mapa

Předpokládejme, že jsme na základě analýzy požadavků na funkci konkrétního logického obvodu sestavili následující pravdivostní tabulku.

Tabulka popisuje logickou funkci dvou proměnných A, B. Jsou tedy možné 2 n = 4 vzájemné kombinace jejich logických hodnot. Proto má tabulka celkem čtyři řádky. Protože uvažujeme disfunkční funkci, budou mít jednotlivé kombinace konjunkční tvar, /A /B, /AB, A /B, AB. Jsou zapsány v prvním sloupci tabulky. Pro obě vstupní proměnné jsou vyhrazeny dva sloupce tabulky. Zapisují se v přímém tvaru, to znamená, že platnou inverzí proměnné označujeme hodnotou 0. Do jednotlivých řádků posledního sloupce zapisujeme hodnoty výstupní funkce.

Pokud některá funkce (některý řádek tabulky) nemusí být vyhodnocena, je vhodné odlišit příslušnou výstupní proměnnou symbolem X. V takovém případě se jedná o neúplně definovanou tabulku, která může podstatným způsobem zjednodušit jak algebraickou, tak Karnaughovu minimalizaci.

Algebraický zápis disfunkční funkce podle předchozí tabulky, je mechanickou záležitostí. Funkce je určena logickým součtem jednotlivých konjunkcí vstupních proměnných ze všech řádků, pro které má výstupní proměnná nabývat hodnoty.

Y = /A /B + A /B + AB
Při minimalizaci rovnic nejprve upravíme Y = A (/B + B) + /A /B. Využitím zákona /B + B = 1 zjednodušíme na Y = A + /A /B a úpravou na inverzní funkci se ukáže další možný postup /Y = /A (A +B). Nyní vidíme možnost uplatnění pravidla /A A = 0 a výsledek je /Y = /A B. Nakonec, opakovanou Shannonovou inverzí dostaneme konečný výsledek Y = A + /B, shodný s funkcí, na které jsme si ukazovali příklad Shannonova rozvoje.
Vidíme, že i když jde o jednoduchou úlohu, lze ji řešit několika způsoby. Ve složitějších případech je často těžko určit, která vede k lepšímu výsledku. Pro více než dvě proměnné je téměř vždy výhodnější použít mapu.

Každá mapa se skládá z určitého počtu ohraničených políček. Každé políčko mapy představuje jeden řádek pravdivostní tabulky. Do mapy však může být zapsána i obecná logická funkce. Jedinou podmínkou je, že musí být upravena do tvaru DNT. Není tedy třeba ji rozkládat na úroveň mintermu. Stačí, když jsou z ní odstraněny závorky. Tvar mapy musí v každém případě odpovídat plnému počtu proměnných logické funkce nebo pravdivostní tabulky.

Karnaughova mapa umožňuje:

• zápis disjunkční funkce nebo pravdivostní tabulky.

• její minimalizaci nebo jiné logické úpravy, příkladem možných úprav je rozvoj funkce až do úrovně UDNT.

• inverzi funkce.

• určení duální funkce, vzhledem k zápisu zpravidla v konjunkčním tvaru.

Vidíme, že díky mapě můžeme realizovat prakticky všechny operace, jimiž jsme se doposud zabývali na základě Booleovy algebry. Z toho vyplývá, že mezi algebraickým vyjádřením funkce, pravdivostní tabulkou a Karnaughovou mapou musí existovat systém vzájemného přiřazení jednotlivých proměnných a logických operátorů. Je zajištěn na úrovni elementárních konjunkcí UDNT, které jsou v mapě topologicky seřazeny v definovaném pořadí podle principu sousedních mintermu. Jednotlivá políčka mapy, se ve všech směrech (nahoru, dolů, doleva a doprava) mohou a musí odlišovat od druhého pouze inverzí jedné jediné proměnné. Tím je zcela zaručen definovaný souřadnicový systém mapy.

Aby byla zajištěna vzájemná kompatibilita, orientace ve všech mapách různého původu a nakonec také přehlednost vlastní práce, dodržuje se zásada umisťování mintermu se všemi proměnnými v inverzním tvary /A /B /C /D do levého horního rohu mapy. Tím je definována jednotná struktura mapy pro libovolný počet proměnných.

Pro názornost je v každém políčku vyznačeny tvary (přímý i inverzní) všech proměnných příslušného mintermu. Pro mapu o dvou proměnných platí pouze proměnné A, B. Pro mapu o třech proměnných zase proměnné A, B, C.
Ve skutečnosti prostor uvnitř každého políčka slouží k vepsání logické hodnoty jeho mintermu, adresa je určena souřadnicovým systémem proměnných, vyznačených na okraji mapy. Přitom se zapisují jen proměnné v přímém tvaru, za jejich inverze se považují všechna zbylá, neoznačená políčka na stejné vnější straně mapy.

Následující obrázky ukazují Karnaughovy mapy pro 2, 3 a 4 proměnné.
Mapa dvou proměnných, odpovídá dvourozměrnému plošnému znázornění.

Mapa tří proměnných, odpovídá třírozměrnému (kubickému) znázornění.

Mapa čtyř proměnných, odpovídá čtyřrozměrnému prostoru.

Pokud jde o způsob hodnotového vyjádření políčka, je zvykem, že se zapisuje pouze 1. Nevyplněný minterm se považuje za 0. Minterm neúplně definované tabulky se většinou označuje jako velké písmeno X.
Cílem souřadnosti mintermu pochopitelně není zavést souřadný systém mapy. Ten je nutnou podmínkou k tomu, aby pomocí mapy bylo možno realizovat logické operace.

• U mapy dvou proměnných lze jednou souřadnou definovat všechny mintermy v příslušném sloupci nebo řádku, protože všechny obsahují tutéž proměnnou ve shodném (přímém) nebo inverzním tvaru.

• U mapy tří proměnných lze obdobným způsobem, jednu proměnnou, definovat všechny (podobné) mintermy jednoho řádku a dvou sloupců.

• U mapy čtyř proměnných stačí pro obdobný popis jedna proměnná jak pro dva řádky, tak pro dva sloupce.

Tato skutečnost umožňuje při minimalizaci funkce v určitých případech chápat a používat taková políčka mapy, která vytvářejí sdružené řetězce mintermu (souvislé plochy sudého počtu mintermu se shodnýma hodnotami 1) jako vyjádření DNT jejich společné funkce. Přitom se podle rozsahu řetězce vylučuje jedna, dvě či tři proměnné a tedy i patřičným způsobem se zjednodušuje celý zápis funkce.