Elektronická učebnice

Minimalizace logického výrazu

Zákony Booleovy algebry

Booleova algebra je algebra pracující s dvojhodnotovými výroky. Je to algebra stavů, nikoliv čísel.
Základem této algebry jsou vztahy pro negaci, logický součet a logický součin. Z těchto pravidel pak vyplývají další zákony.

Obr. 1: Zákony Booleovy algebry

Uvedená pravidla se dají rozšířit i na více proměnných. Důkazy o platnosti těchto pravidel můžeme získat úpravou algebraických výrazů nebo dosazováním konkrétních hodnot 0 a 1 za obecné proměnné, případně pomocí pravdivostních tabulek. Znalost Booleovy algebry je důležitá pro efektivní úpravu algebraických výrazů při jejich minimalizaci.

Minimalizace výrazů s využitím Booleovy algebry

DŮKAZ POMOCÍ PRAVDIVOSTNÍ TABULKY
Pravdivostní tabulka musí obsahovat všechny kombinace nezávisle proměnných, v našem případě tří proměnných a, b, c. Důkaz pravdivosti distributivního zákona: a + (b.c) = (a + b).(a + c)

Obr. 2: Důkaz platnosti distributivního zákona

ALGEBRAICKÉ VÝRAZY
Každou logickou funkci můžeme algebraicky vyjádřit jako logický součet logických součinů (v disjunktivním tvaru) nebo jako logický součin logických součtů (v konjunktivním tvaru). První způsob se používá v praxi častěji.

Obr. 3: Pravdivostní tabulka
Disjunktivní tvar logické funkce získáme z pravdivostní tabulky následujícím způsobem. V pravdivostní tabulce uvažujeme pouze ty řádky, ve kterých logická proměnná y nabývá hodnoty 1. Každému takovému řádku odpovídá jeden součinový člen. Vstupní proměnná, která má v příslušném řádku hodnotu 1, je v uvedeném součinu zastoupena původní hodnotou (přímou), proměnná mající hodnotu 0 je zastoupena svou negací. Pro logickou funkci v tabulce můžeme psát:

Konjunktivní tvar logické funkce sestavíme podobným způsobem. V tabulce uvažujeme pouze řádky, ve kterých má výstupní proměnná hodnotu 0. Každému řádku odpovídá jeden součtový člen. Vstupní proměnná, která má v příslušném řádku hodnotu 0, je v součtovém členu zastoupena původní hodnotou, proměnná mající hodnotu 1 je v něm zastoupena negací.

Poznámka: Algebraický výraz píšeme v takové podobě, aby byl co nejjednodušší. Rozhodujícím činitelem je počet 0 a 1 v tabulce. V případě, kdy převládají nuly, píšeme výraz za jedničky, tedy v podobě součtu součinů a naopak.
Standardní zápis logické funkce poznáme z toho, že v každém členu algebraického výrazu jsou obsaženy všechny vstupní proměnné. Standardní zápis může být ve tvaru disjunktivním i konjunktivním.

Minimalizace výrazů s využitím Karnaughovy mapy

Metoda minimalizace funkce pomocí Karnaughových map nahrazuje algebraické úpravy logických výrazů geometrickými postupy, které při dodržení několika formálních pravidel garantují získání nejjednoduššího konečného tvaru logického výrazu.

Logickou funkci v základním součtovém tvaru zjednodušujeme takto:

Sestaví se tabulka (Karnaughova mapa). Počet buněk této tabulky je roven počtu možných kombinací proměnných v logických součinech základního součtového tvaru. Každému políčku tabulky tak odpovídá jeden logický součin (jedna kombinace proměnných), přitom tabulka musí být sestavena tak, aby logické součiny v sousedních buňkách tabulky (horizontálně i vertikálně) se lišily pouze v jedné proměnné. Při vyplnění tabulky se do políček, která odpovídají logickým součinům realizovaným v dané funkci, zanese 1. Do ostatních buněk tabulky (tyto kombinace proměnných se nerealizují v dané funkci) se zanese 0. V zaplněné tabulce se hledají smyčky sjednocující 2, 4, 8, 16, … (mocniny základu 2) sousední buňky tabulky tak, aby z odpovídající skupiny logických součinů byly vyloučeny 1, 2, 3, 4, … proměnné. Zjednodušená logická funkce se zapíše jako logický součet logických součinů odpovídajících vyznačeným smyčkám.

Při vyznačování smyček se řídíme následujícími formálními pravidly:

Smyčka musí být čtverec nebo obdélník, obsahující jenom políčka vyplněná 1. Pokud obsahuje tabulka neznámé stavy x (-) a zahrnutí tohoto stavu nám pomůže k výhodnějšímu uzavření smyčky, zahrneme jej též do smyčky.
Počet políček uvnitř smyčky musí být celou mocninou čísla 2.
Jedno políčko může být v několika smyčkách - smyčky se mohou překrývat.
Při vytváření smyček se vrchní a spodní řádek počítají jako sousední (totéž platí pro krajní sloupce).
Počet smyček musí být co možná nejmenší.
Rozměry smyček musí být co možná největší (smyčka obsahuje co nejvíce políček).
Každé políčko obsahující 1 musí vejít alespoň do jedné smyčky (políčko, které nemá sousední políčko obsahující 1, tvoří samostatnou smyčku).
Všechny smyčky musí být při sestrojení konečného logického součtu použity.

Karnaughova mapa má různé tvary podle počtu vstupních proměnných. Popišme si nejprve mapu pro dvě proměnné - je to tabulka o dvou sloupcích a dvou řádcích. Každý prvek naší tabulky musí obsahovat jednu z 2ⁿ kombinací, které mohou nastat. Pro 2 proměnné (n=2) bude mapa obsahovat 4 buňky. Jednotlivé kombinace naznačíme nad každým sloupcem a vedle každého řádku proměnnou, sousední sloupec nebo řádek pak obsahuje negaci této proměnné, čímž získáme na souřadnicích všechny možné kombinace, které mohou v obvodu nastat a odpovídají všem řádkům pravdivostní tabulky.

Obr. 4: Pravdivostní tabulka pro dvě proměnné

Obr. 5: Karnaughova mapa pro dvě proměnné

V Karnaughově mapě začínáme nadepisovat řádky a sloupce negovanými proměnnými a poté změna nastává v sousedním řádku nebo sloupci zrušením negace. Řádky pravdivostní tabulky se přepíší postupně do řádků Karnaughovy mapy. Čísla uvedena v Karnaughově mapě pak odpovídají dekadickému vyjádření jedniček a nul na příslušném řádku pravdivostní tabulky. Potom tedy souřadnice BA nám udává, že proměnná A=0, B=0. Tato kombinace se nachází v prvním řádku pravdivostní tabulky, vyjádřeném číslem 0. Souřadnice BA znamená A=0, B=1, což představuje 3. řádek tabulky, dekadicky vyjádřeném číslem 2.

Pro tři proměnné bude tabulka obsahovat 4 sloupce a 2 řádky, celkem 2³=8 buněk. Nad každým sloupcem nadepíšeme kombinaci dvou proměnných a to tak, že každá sousední kombinace se oproti předchozí liší pouze v jedné změně (negací). Vedle prvního řádku bude nadepsaná třetí proměnná, která se nevyskytuje u sloupců a na dalším řádku její negace. Karnaughova mapa pro tři proměnné pak vypadá takto:

Obr. 6: Pravdivostní tabulka pro tři proměnné

Obr. 7: Karnaughova mapa pro tři proměnné

Obr. 8: Karnaughova mapa pro čtyři proměnné

Při sestavování Karnaughovy mapy pro čtyři proměnné se postupuje stejně jako u Karnaughovy mapy se třemi proměnnými. Nad sloupci budou nadepsány všechny kombinace dvou proměnných (AB) a vedle řádků pak kombinace dvou zbývajících proměnných (CD).

Do takto připravené tabulky pak můžeme dosadit hodnoty jedné z výstupních proměnných zadaných v pravdivostní tabulce. Do každé z buněk zapíšeme 0,1 nebo x (-) . Každá buňka opět odpovídá jednomu řádku pravdivostní tabulky a hodnota výstupní proměnné, kterou zapíšeme do určité buňky, se nachází právě na tomto řádku. Poté je možné provést uzavření do smyček a následnou minimalizaci. V tuto chvíli již zbývá jen vyhodnotit mapu a interpretovat logický výraz do potřebné podoby. Dostaneme tolik logických výrazů, kolik máme smyček. Čím větší smyčky se nám podařilo vytvořit, tím jednodušší tyto výrazy jsou. Námi hledaná logická funkce je logickým součtem (funkce OR) všech těchto výrazů.