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:
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
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Šablona:Sup množina jedniček, které spolu můžeme minimalizovat.