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:

<m>(overline{a} + overline{b}) * (overline{b} + c)</m>

Karnaugh map

Řekněme že dostaneme zadanou funkci, např. pravdivostní tabulkou.

Podle ní vytvoříme karnaugovu mapu.

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.

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:

1. <m>A overline{C}</m>
2. <m>A overline{B}</m>
3. <m>B C overline{D}</m>

Vásledná minimalizované funkce je tedy <m>A overline{C} + A overline{B} + B C overline{D}</m>.

Řekněme že máme zadanou pravdivostní tabulku ke které máme nalézt minimální funkci.

Nepravdivé řádky zahodíme a pravdivé rozdělíme do skupin podle počtu jedniček.

Nyní se pokusíme spojit dvojice těch řádků kde se liší jen jeden bit. Tento bit označíme -.

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.

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).

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.

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 ⇒ <m>overline{A} B D</m>
• 0, 1, 8, 9 ⇒ -00- ⇒ <m>overline{B} overline{C}</m>
• 2, 6, 10, 14 ⇒ --10 ⇒ <m>C overline{D}</m>

Výsledná minimalizovaná funkce tedy bude <m>f(A, B, C, D) = overline{A} B D + overline{B} overline{C} + C overline{D}</m>

• 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)