Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:minimalizace

Minimalizace logických výrazů

Algebraické metody

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} $$

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

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:

  1. $ A \overline{C} $
  2. $ A \overline{B} $
  3. $ 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)
/var/www/wiki/data/pages/pitel/isz/minimalizace.txt · Poslední úprava: 19. 01. 2018, 13.15:07 autor: pitel