Minimalizace logických výrazů

Algebraické metody

Prostě zjednodušení funkce pomocí pravidel Boolovy algebry.

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ů:

Úplná normální konjunktní forma (ÚNKF)

Výraz je zapsán jako součin sum:

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:

<m>A overline{C}</m>

<m>A overline{B}</m>

<m>B C overline{D}</m>

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

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 ⇒ <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>

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)