Karnaughova mapa

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

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:

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

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

${\displaystyle Q_{2}={\bar {x}}\cdot {\bar {z}}}$

Výsledná funkce bude tedy vypadat takto

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

Řešení s neurčitými stavy

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ší 2ⁿ množina jedniček, které spolu můžeme minimalizovat.

Související články

• Grayův kód
• Svobodova mapa
• Konečný automat

Externí odkazy

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