3. Minimalizace logické funkce algebraická a grafická

• 1. Předurčení minimalizace logické funkce
• 2. Algebraická minimalizace logické funkce na příkladě
• 3. Grafická minimalizace logické funkce na příkladě

---

1. Předurčení minimalizace logické funkce

• Minimalizace vychází z faktu, že jednu a tutéž logickou funkci lze zapsat mnoha způsoby. Pro začátek procesu obvykle potřebujeme funkci v tzv. kanonické formě (získané např. z pravdivostní tabulky):

  • Úplná součtová forma (ÚSNDP): Součet součinů (mintermů), kde se funkce rovná 1.
  • Úplná součinová forma (ÚSKNP): Součin součtů (maxtermů), kde se funkce rovná 0.

• Důvody pro minimalizaci:

  • Ekonomické: Méně součástek (integrovaných obvodů).
  • Technické: Menší spotřeba energie a menší tepelné ztráty.
  • Spolehlivost: Méně spojů znamená menší pravděpodobnost poruchy.

Název zákona	Součtová forma (OR)	Součinová forma (AND)
Axiomy	$0+0=0$ $0+1=1+0=1$ $1+1=1$	$1\cdot 1=1$ $1\cdot 0=0\cdot 1=0$ $0\cdot 0=0$
Zákon komutativní	$a+b=b+a$	$a\cdot b=b\cdot a$
Zákon asociativní	$a+(b+c)=(a+b)+c$	$a\cdot (b\cdot c)=(a\cdot b)\cdot c$
Zákon distributivní	$(a\cdot b)+(a\cdot c)=a\cdot (b+c)$	$(a+b)\cdot (a+c)=a+(b\cdot c)$
Zákon idempotence	$a+a=a$	$a\cdot a=a$
Zákon vyloučeného třetího	$a+\bar{a}=1$	$a\cdot \bar{a}=0$
Zákon agresivních hodnot	$a+1=1$	$a\cdot 0=0$
Zákon neutrálních hodnot	$a+0=a$	$a\cdot 1=a$
Zákon adsorpce	$a+a\cdot b=a$	$a\cdot (a+b)=a$
Zákon adsorpce negace	$a+\bar{a}\cdot b=a+b$	$a\cdot (\bar{a}+b)=a\cdot b$
Zákon dvojí negace	$\overline{\stackrel{ˉ}{a}}=a$
Zákony deMorganovy	$\overline{a+b}=\bar{a}\cdot \bar{b}$	$\overline{a\cdot b}=\bar{a}+\bar{b}$

---

2. Algebraická minimalizace logické funkce na příkladě

A	B	C	f (Výstup)	Algebraický zápis
0	0	0	0	(tento řádek ignorujeme)
0	0	1	1	$\to \bar{A}\cdot \bar{B}\cdot C$
0	1	0	0	(tento řádek ignorujeme)
0	1	1	1	$\to \bar{A}\cdot B\cdot C$
1	0	0	0	(tento řádek ignorujeme)
1	0	1	1	$\to A\cdot \bar{B}\cdot C$
1	1	0	0	(tento řádek ignorujeme)
1	1	1	1	$\to A\cdot B\cdot C$

• 2.1. Sestavení funkce:

  • Teď se podíváš jen na ty řádky, kde je v sloupci $f$ jednička (1). Ty řádky, kde je 0, tě pro tuhle metodu (ÚSNDP) vůbec nezajímají.
  • Funkci zapíšeš jako součet těchto čtyř mintermů:
  $$f=(\bar{A}\bar{B}C)+(\bar{A}BC)+(A\bar{B}C)+(ABC)$$

• 2.2. Minimalizace funkce

  • Následně je potřeba tuhle funkci minimalizovat. Tady jde o to najít členy, které se liší jen v jednom písmenku (jeden má pruh, druhý ne), a ty dát k sobě:

    1. Seskupení:

       $$f=\underset{1.\text{ dvojice}}{\underbrace{(\bar{A}\bar{B}C+\bar{A}BC)}}+\underset{2.\text{ dvojice}}{\underbrace{(A\bar{B}C+ABC)}}$$

    2. Vytýkání:

       $$f=\bar{A}C\cdot (\bar{B}+B)+AC\cdot (\bar{B}+B)$$

    3. Využití zákona o vyloučení třetího:

       $$f=\bar{A}C\cdot 1+AC\cdot 1$$ $$f=\bar{A}C+AC$$

    4. Druhé kolo vytýkání:

       $$f=C\cdot (\bar{A}+A)$$

    5. Finální zjednodušení:

       $$f=C\cdot 1$$
       • Výsledek: $f=C$

---

3. Grafická minimalizace logické funkce na příkladě

• 3.1 Sestavení Karnaughovy mapy

  A	B	C	f (Výstup)	Algebraický zápis
  0	0	0	1	$\bar{A}\bar{B}\bar{C}$
  0	0	1	0	-
  0	1	0	1	$\bar{A}B\bar{C}$
  0	1	1	1	$\bar{A}BC$
  1	0	0	0	-
  1	0	1	0	-
  1	1	0	1	$AB\bar{C}$
  1	1	1	1	$ABC$

1. Urči rozměr mřížky

   • Počet políček v mapě je vždy $2^n$, kde $n$ je počet vstupních proměnných.
   • 3 proměnné (A, B, C): Tabulka 2 × 4 (8 políček).
   • 4 proměnné (A, B, C, D): Tabulka 4 × 4 (16 políček).

2. Popiš souřadnice

3. Zapiš jedničky

   • Teď vezmi svou pravdivostní tabulku a podívej se, kde ti vyšel výstup $f=1$.
   • Najdi v mapě políčko, které odpovídá kombinaci vstupů (třeba $011$ je sloupec $\bar{A}B$ a řádek $C$).
   • Do toho políčka napiš 1.
   • Do všech ostatních políček, kde výstup není, napiš 0 (nebo je nechej prázdná).

   C \ AB	$\bar{A}\bar{B}$	$\bar{A}B$	$AB$	$A\bar{B}$
   $\bar{C}$	1	1	1	0
   $C$	0	1	1	0

• 3.2 Minimalizace (Grupování)

  • Tady musíme udělat dvě smyčky, abychom posbírali všechny jedničky. Pamatuj: chceme co největší balíčky!

  • Smyčka č. 1: Ten velký čtverec uprostřed (4 jedničky)

    • Zahrnuje sloupce $\bar{A}B$ a $AB$ v obou řádcích ($\bar{C}$ i $C$).
    • Vodorovně (A, B): Ve sloupcích $\bar{A}B$ a $AB$ vidíme, že B zůstává stejné (bez pruhu), ale A se mění. Takže A vypadává.
    • Svisle (C): Smyčka jde přes oba řádky ($\bar{C}$ i $C$), takže C vypadává.
    • Výsledek 1. smyčky: $B$

  • Smyčka č. 2: Ta dvojice vlevo nahoře (2 jedničky)

    • Zahrnuje sloupce $\bar{A}\bar{B}$ a $\bar{A}B$ v horním řádku ($\bar{C}$).
    • Poznámka: Jednu jedničku z prostředního bloku jsme použili znovu, abychom udělali větší smyčku (dvojici místo samotné jedničky).
    • Vodorovně (A, B): Ve sloupcích $\bar{A}\bar{B}$ a $\bar{A}B$ zůstává $\bar{A}$ stejné, ale B se mění. Takže B vypadává.
    • Svisle (C): Celá tahle smyčka leží jen v řádku $\bar{C}$, takže ten zůstává.
    • Výsledek 2. smyčky: $\bar{A}\bar{C}$

  • Finální výsledek

    • Teď ty dva výsledky prostě sečteš:

      $$f=B+\bar{A}\bar{C}$$

---

Další ukázka Karnaughovy mapy