Karnaughova mapa

Z Wikipedie, otevřené encyklopedie
Jump to navigation Jump to search

Karnaughova mapa je metoda používaná pro minimalizaci logické funkce při její analýze. Jejím principem je zobrazení n-rozměrné tabulky hodnot do dvojrozměrné mapy. Z této mapy lze poté graficky vyčíst minimální funkci. Je pojmenována podle Maurice Karnaugha, který vylepšil diagram Edwarda Veitche.

Příklad[editovat | editovat zdroj]

Analyzuji logickou funkci závislou na třech parametrech (x, y, z). Pravdivostní tabulka je následující:

x y z Q
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

Matematický vzorec pro tuto funkci by se (bez minimalizace) dal tedy zapsat takto:

Pro minimalizaci této funkce nyní použijeme Karnaughovu mapu.

y
z
1 0 0 1
x 1 0 0 0

Výhoda zápisu do Karnaughovy mapy spočívá v tom, že oblasti ovlivněné každou z proměnných jsou na rozdíl od pravdivostní tabulky souvislé. Aby toto byla pravda, je nutné vnímat mapu tak, že za posledním sloupcem následuje opět sloupec první, čímž se propojí (do té doby nesouvislé) oblasti . Nyní definujeme vzorec podobně jako u pravdivostní tabulky s tím, že si všímáme souvislých oblastí.

y
z
1 0 0 1
x 1 0 0 0

Tato oblast je zcela nezávislá na x (může nabývat hodnoty 1 i 0), závisí pouze na y a z. Můžeme tedy napsat

y
z
1 0 0 1
x 1 0 0 0

Tato oblast je zcela nezávislá na y (může nabývat hodnoty 1 i 0), závisí pouze na x a z. Můžeme tedy napsat

Výsledná funkce bude tedy vypadat takto

Řešení s neurčitými stavy[editovat | editovat zdroj]

Při minimalizaci funkce, která obsahuje i neurčité stavy, tj. pokud máme výstupy, které nebudeme využívat. Můžeme je při minimalizaci použít tak, že je nahradíme 1 nebo 0 dle libosti, aby nám vznikla co největší 2n množina jedniček, které spolu můžeme minimalizovat.

Související články[editovat | editovat zdroj]