Prostě zjednodušení funkce pomocí pravidel 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} $$
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ě.
Výraz je zapsán jako suma součinů:
$$ \overline{ab} + \overline{b} c $$
Výraz je zapsán jako součin sum:
$$ (\overline{a} + \overline{b}) * (\overline{b} + c) $$
Ř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:
Vásledná minimalizované funkce je tedy $A \overline{C} + A \overline{B} + B C \overline{D}$.
Ř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 -.
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.
1 | Řádky | Výsledek |
---|---|---|
0 | 0, 1, 8, 9 | -00- |
0, 2, 8, 10 | -0-0 | |
| |
|
| |
|
1 | 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.
Výsledná minimalizovaná funkce tedy bude $f(A, B, C, D) = \overline{A} B D + \overline{BC} + C \overline{D}$