Karnaughová mapa

Karnaughová mapa :

Ďalšou metódou minimalizácie logickej funkcie pomocou špeciálnych tabuliek je metóda Karnaughovej mapy. Je to uniformná technika, pomocou ktorej dostaneme minimálny výraz logickej funkcie.

Systém Karnaughovej mapy je založený na pravidle Booleovej algebry, že dva členy logického výrazu, ktoré obsahujú tie isté premenné a líšia sa iba v jednej premennej sú redukovateľné, t.j. možno ich zjednodušiť tak, že vynecháme premennú v ktorej sa líšia, čiže :

Dva členy, ktoré sa líšia iba v jednej premennej sa nazývajú susediacimi členmi a v Karnaughovej mape sa nachádzajú vedľa seba.

Karnaughová mapa je zvláštnou formou pravdivostnej tabuľky logickej funkcie. Je to tabuľka vytvorená v poli štvorcov, kde každý štvorec reprezentuje jednu danú kombináciu vstupov. Karnaughová mapa sa napĺňa zapisovaním hodnôt funkcie pre každú z kombinácií.

Napríklad pre logickú funkciu

je pravdivostná tabuľka v ktorej sú na ľavej strane zapísané všetky kombinácie troch vstupných logických premenných A, B a C a na pravej strane pre výstupnú premennú Y zapísané jednotky iba pre tie kombinácie, ktoré sa nachádzajú na pravej strane logickej funkcie :

a karnaughová mapa tejto funkcie :

Každé dva susedné štvorce v Karnaughovej mape reprezentujú susedné kombinácie (kombinácie susedných členov), ktoré sa líšia iba v jednej premennej (00 01 11 10). Podobne kombinácia prvého riadku je susednou kombináciou posledného riadku. Tabuľka môže byť chápaná ako povrch guľe. Rohy tabuľky sú si susedné. Podobne ako rohy na hracej kocke.

Minimalizácia logickej funkcie pomocou Karnaughovej mapy :

Aby sme získali minimálnu funkciu pomocou Karnaughovej mapy musíme použiť a rešpektovať nasledovné pravidlá :

Skupiny susedných štvorcov, ktoré obsahujú jednotky sú označené v Karanughovej mape následovným spôsobom :

všetky jednotky zoskupíme do skupín,
skupina musí obsahovať 2ⁿ štvorcov (1,2,4,8,16…),
skupina musí mať tvar štvorca alebo obdĺžníka,
vytvárame čo najväčšie skupiny,
jeden štvorec môže byť zahrnutý do niekoľkých skupín,
krajne stĺpce a krajné riadky sú si susedné.

Počet štvorcov v každej skupine je párne číslo okrem prípadu, keď skupina obsahuje jeden štvorec a premenné sa budú nachádzať vo všetkých štvorcoch s rovnakou hodnotou (buď 0 alebo 1) alebo s hodnotou 1 v jednej polovici a 0 v druhej polovici.
Každá skupina vytvorí zjednodušený člen, ktorého premenné nie sú predmetom zmeny pri kombinácií štvorcov v skupine.
Premenné sú v člene spojené operáciou logického súčinu AND
Medzi členmi reprezentujúcimi skupiny je operácia logického súčtu OR

Príklady Karnaughovej mapy pre logické funkcie :

Príklad 1 :

Karnaughová mapa s označením skupín :

Skupiny boli označené podľa horeuvedených pravidiel 1 a 2. Podľa pravidla, že každá skupina vytvorí zjednodušený člen, ktorého premenné nie sú predmetom zmeny pri kombinácií štvorcov v skupine a premenné sú v člene spojené operáciou logického súčinu môžeme pre prvú skupinu napísať zjednodušený člen

(premenná A je nad modrou oblasťou iba v stave 1, čiže ostáva ako A, premenná B je nad modrou oblasťou aj v stave 1 aj v stave 0, čiže vypadáva, premenná C je v modrej oblasti iba v stave 1, čiže ostáva ako C)

Podobne pre druhú skupinu napísať zjednodušený člen

(premenná A je nad červenou oblasťou aj v stave 1 aj v stave 0, čiže vypadáva, premenná B je nad červenou oblasťou iba v stave 0, čiže ostáva ako negovaná, premenná C je v červenej oblasti iba v stave 1, čiže ostáva ako C)

Podľa pravidla, že medzi členmi reprezentujúcimi skupiny je operácia logického súčtu je možné tieto dva členy spojiť logickou operáciou OR a pre minimalizovanú funkciu napísať :

Táto logická funkcia je minimalizovaná čo sa týka členov, ale nie je minimalizovaná čo sa týka realizácie pomocou hradiel. Môže byť ďalej zjednodušená pomocou distributívneho zákona do tvaru :