====== Minimalizace logických výrazů ======
===== Algebraické metody =====
Prostě zjednodušení funkce pomocí pravidel [[wp>Boolean algebra (structure)|Boolovy algebry]].
$$ \overline{xy} z + \overline{x}yz + x y \overline{z} $$
$$ \overline{x} z (y + \overline{y}) + x y \overline{z} $$
$$ \overline{x} z + x y \overline{z} $$
===== Normální formy =====
Dvě duležité formy, v jakých se s logickými výrazy pracuje: disjunktní a konjunktní. Úplná normální forma je taková, která ještě nebyla minimalizována. Po minimalizaci mluvíme o minimální normální formě.
==== Úplná normální disjunktní forma (ÚNDF) ====
Výraz je zapsán jako suma součinů:
$$ \overline{ab} + \overline{b} c $$
==== Úplná normální konjunktní forma (ÚNKF) ====
Výraz je zapsán jako součin sum:
$$ (\overline{a} + \overline{b}) * (\overline{b} + c) $$
Pomůcka: konjuktní forma => K, tzn. krát, odtud součin
===== Karnaughova mapa =====
[[wp>Karnaugh map]]
Řekněme že dostaneme zadanou funkci, např. pravdivostní tabulkou.
^ A ^ B ^ C ^ D ^ //f//(A, B, C, D) ^
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Podle ní vytvoříme karnaugovu mapu.
| | |^ A || |
| | 0 | 0 | 1 | 1 | |
| ::: | 0 | 0 | 1 | 1 ^ D |
^ C | 0 | 0 | 0 | 1 ^ ::: |
^ ::: | 0 | 1 | 1 | 1 | |
| | ^ B || | |
Mapu chápeme tak, že A má hodnotu 1 ve sloupcích 3 a 4 a hodnotu 0 ve sloupcích 1 a 2. Konkrétní hodnota v jednom poli je funkční hodnota z předchozí tabulky.
V této tabulce teď budeme hledat ostrovy jedniček. Ostrovy musí být obdélníkové, délka jejich stran musí být mocniny dvou, mohou se překrývat a musíme jimi pokrýt všechny jedničky. A ideálně by jich mělo být co nejméně. Tabulka je navíc jakoby toroid, což má za následek to, že ostrovy mohou být tvořeny přes hrany i vrcholy (klidně všechny 4) tabulky.
| | |^ A || |
| | 0 | 0 | 1 || |
| ::: | 0 | 0 | ::: |^ D |
^ C | 0 | 0 | 0 | 1 ^ ::: |
^ ::: | 0 | 1 | 1 | 1 | |
| | ^ B || | |
| | |^ A || |
| | 0 | 0 | 1 | 1 | |
| ::: | 0 | 0 | 1 | ::: ^ D |
^ C | 0 | 0 | 0 | ::: ^ ::: |
^ ::: | 0 | 1 | 1 | ::: | |
| | ^ B || | |
| | |^ A || |
| | 0 | 0 | 1 | 1 | |
| ::: | 0 | 0 | 1 | 1 ^ D |
^ C | 0 | 0 | 0 | 1 ^ ::: |
^ ::: | 0 | 1 || 1 | |
| | ^ B || | |
Teď zapíšeme pro každý ostrov pravidlo. Pokud je proměnná pro oblast stále 1, sepíšeme ji, pokud je stále 0, sepíšeme její negaci. To vylývá z toho, že pokud proměnná zasahuje do oblasti jak v 0, tak v 1, nemá proměnná na výslednou hodnotu žádný vliv.
Pro jednotlivé ostrovy to tedy bude:
- $ A \overline{C} $
- $ A \overline{B} $
- $ B C \overline{D} $
Vásledná minimalizované funkce je tedy $A \overline{C} + A \overline{B} + B C \overline{D}$.
===== Quine McCluskey =====
Řekněme že máme zadanou pravdivostní tabulku ke které máme nalézt minimální funkci.
^ # ^ A ^ B ^ C ^ D ^ //f//(A, B, C, D) ^
^ 0 | 0 | 0 | 0 | 0 | 1 |
^ 1 | 0 | 0 | 0 | 1 | 1 |
^ 2 | 0 | 0 | 1 | 0 | 1 |
^ 3 | 0 | 0 | 1 | 1 | 0 |
^ 4 | 0 | 1 | 0 | 0 | 0 |
^ 5 | 0 | 1 | 0 | 1 | 1 |
^ 6 | 0 | 1 | 1 | 0 | 1 |
^ 7 | 0 | 1 | 1 | 1 | 1 |
^ 8 | 1 | 0 | 0 | 0 | 1 |
^ 9 | 1 | 0 | 0 | 1 | 1 |
^ 10 | 1 | 0 | 1 | 0 | 1 |
^ 11 | 1 | 0 | 1 | 1 | 0 |
^ 12 | 1 | 1 | 0 | 0 | 0 |
^ 13 | 1 | 1 | 0 | 1 | 0 |
^ 14 | 1 | 1 | 1 | 0 | 1 |
^ 15 | 1 | 1 | 1 | 1 | 0 |
Nepravdivé řádky zahodíme a pravdivé rozdělíme do skupin podle počtu jedniček.
^ 1 ^ # ^ ABCD ^
^ 0 ^ 0 | 0000 |
^ 1 ^ 1 | 0001 |
^ ::: ^ 2 | 0010 |
^ ::: ^ 8 | 1000 |
^ 2 ^ 5 | 0101 |
^ ::: ^ 6 | 0110 |
^ ::: ^ 9 | 1001 |
^ ::: ^ 10 | 1010 |
^ 3 ^ 7 | 0111 |
^ ::: ^ 14 | 1110 |
Nyní se pokusíme spojit dvojice těch řádků kde se liší jen jeden bit. Tento bit označíme -.
Stačí vždy kontrolovat jen proti řádkům z následující skupiny.
^ 1 ^ Řádky ^ Výsledek ^
^ 0 | 0, 1 | 000- |
^ ::: | 0, 2 | 00-0 |
^ ::: | 0, 8 | -000 |
^ 1 | 1, 5 | 0-01 |
^ ::: | 1, 9 | -001 |
^ ::: | 2, 6 | 0-10 |
^ ::: | 2, 10 | -010 |
^ ::: | 8, 9 | 100- |
^ ::: | 8, 10 | 10-0 |
^ 2 | 5, 7 | 01-1 |
^ ::: | 6, 7 | 011- |
^ ::: | 6, 14 | -110 |
^ ::: | 10, 14 | 1-10 |
Teď uděláme ještě jednou to samé, ale z předchozí tabulky. Pozor, pomlčky chápejte jako "třetí hodnotu" bitu. Pravděpodobně vzniknout duplicity, ty škrtneme.
Stačí se koukat po první pomlčce zleva -- vyhledejte si výraz, který má pomlčku na stejném místě.
^ 1 ^ Řádky ^ Výsledek ^
^ 0 | 0, 1, 8, 9 | -00- |
^ ::: | 0, 2, 8, 10 | -0-0 |
^ ::: | 0, 8, 1, 9 | -00- |
^ ::: | 0, 8, 2, 10 | -0-0 |
^ 1 | 2, 6, 10, 14 | %%--10%% |
^ ::: | 2, 6, 10, 14 | %%--10%% |
Všimněte si, že některé řádky (1, 5; 5, 7; 6, 7) nebyly použity. Ty, a řádky z poslední tabulky zapíšeme do nové tabulky, ve které vyznačíme které řádky to byly.
Pro přepis na minimalizovanou funkci použijeme metodu mřížky implikantů (jinou možností je například Petrickova funkce).
^ Řádky ^ 0 ^ 1 ^ 2 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 14 ^
^ 1, 5 | | ✔ | | ✔ | | | | | | |
^ 5, 7 | | | | ✔ | | ✔ | | | | |
^ 6, 7 | | | | | ✔ | ✔ | | | | |
^ 0, 1, 8, 9 | ✔ | ✔ | | | | | ✔ | ✔ | | |
^ 0, 2, 8, 10 | ✔ | | ✔ | | | | ✔ | | ✔ | |
^ 2, 6, 10, 14 | | | ✔ | | ✔ | | | | ✔ | ✔ |
Najdeme ty sloupce, které mají jen jedno označené políčko (9, 14 -- tato pravidla jsou tzv. nesporné implikanty), od nich škrtneme calý řádek, a pokud při tom škrtneme další označená políčka, tak i jejich sloupec.
^ Řádky ^ 0 ^ 1 ^ 2 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 14 ^
^ 1, 5 | | ✔ | | ✔ | | | | | | |
^ 5, 7 | | | | ✔ | | ✔ | | | | |
^ 6, 7 | | | | | ✔ | ✔ | | | | |
^ 0, 1, 8, 9 | ✔ | ✔ | | | | | ✔ ^ ✔ | | |
^ 0, 2, 8, 10 | ✔ | | ✔ | | | | ✔ | | ✔ | |
^ 2, 6, 10, 14 | | | ✔ | | ✔ | | | | ✔ ^ ✔ |
Neškrtnuté tedy zůstaly jen sloupce 5 a 7. Zbytek se pokusíme za použití stejných škrtacích pravidel (vodorovně, pak svisle) vyškrtat všechna zbylá pravidla (sloupce) za použití co nejméně vodorovných škrtnutí. V tomto případě zcela zřejmě na řádku 5, 7.
Dohromady jsme tedy škrtli tři řádky, podíváme se do předchozích tabulek které binární hodnoty představovaly. Proměnné v nich znegujeme tak aby byly všechny 1.
* 5, 7 ⇒ 01-1 ⇒ $\overline{A} B D$
* 0, 1, 8, 9 ⇒ -00- ⇒ $\overline{BC}$
* 2, 6, 10, 14 ⇒ %%--10%% ⇒ $C \overline{D}$
Výsledná minimalizovaná funkce tedy bude $f(A, B, C, D) = \overline{A} B D + \overline{BC} + C \overline{D}$
===== Shrnutí (jak to uvést) =====
* logické výrazy slouží například k popisu logické funkce, např. logického obvodu
* uvádíme ve dvou normálních formách: normální disjunktní forma (součet součinů), normální konjunktní forma (součin součtů)
* úplná normální forma: obsahuje všechny jednotlivé stavy, kdy funkce poskytuje kladný výstup
* minimální normální forma: obsahuje jen podstatné informace
* převod z úplné do minimální: minimalizace
* booleovská algebra (absorbce negace, de morgan, ...)
* karnaughova mapa: umět ukázat např jen na dvou proměnných
* quine-mccluskey: umět popsat, říct, že nevede k minimalizaci, je potřeba nakonec použít ještě např. tabulku implikantů
* obě metody využívají teorémy booleovy algebry (consensus, sousednost, nejlépe umět, když to budete zmiňovat)