Karnaughova mapa

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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:

Q = (\bar{x} \cdot \bar{y} \cdot \bar{z}) + (\bar{x} \cdot y \cdot \bar{z}) + (x \cdot \bar{y}  \cdot \bar{z})

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

Q_1 = \bar{y} \cdot \bar{z}
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

Q_2 = \bar{x} \cdot \bar{z}

Výsledná funkce bude tedy vypadat takto

Q(x,y,z) =  (\bar{y} \cdot \bar{z}) + (\bar{x} \cdot \bar{z})

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

Logo Wikimedia Commons Obrázky, zvuky či videa k tématu Karnaughova mapa ve Wikimedia Commons