Booleova algebra pracuje s proměnnými, které mohou mít jen dvě hodnoty – 0 (nepravda, nízké napětí) a 1 (pravda, vysoké napětí). Popisuje, jak se z nich skládají logické funkce, a je matematickým základem všech číslicových obvodů: procesorů, pamětí i síťových prvků. Podle ŠVP se probírá ve 2. ročníku předmětu Počítačové sítě: žák má umět zjednodušit (minimalizovat) logickou funkci algebraickou metodou a vyjádřit ji pouze pomocí členů NAND.
Základní logické operace
| Operace | Zápis | Význam | Logický člen |
|---|---|---|---|
| negace (NOT) | A | obrátí hodnotu | invertor |
| logický součin (AND, konjunkce) | A⋅B nebo AB | 1 jen tehdy, když jsou obě proměnné 1 | AND |
| logický součet (OR, disjunkce) | A+B | 1, když je aspoň jedna proměnná 1 | OR |
| negovaný součin (NAND) | A⋅B | negace AND – 0 jen tehdy, když jsou obě 1 | NAND |
| negovaný součet (NOR) | A+B | negace OR – 1 jen tehdy, když jsou obě 0 | NOR |
| výhradní součet (XOR) | A⊕B | 1, když se proměnné liší | XOR |
Pravdivostní tabulka
Logickou funkci lze úplně popsat pravdivostní tabulkou – pro každou kombinaci vstupů uvede hodnotu výstupu. Funkce n proměnných má 2n řádků.
| A | B | NOT A | AND | OR | NAND | NOR | XOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
Zákony Booleovy algebry
| Zákon | Pro součin | Pro součet |
|---|---|---|
| neutrální prvek | A⋅1=A | A+0=A |
| agresivní prvek | A⋅0=0 | A+1=1 |
| idempotence | A⋅A=A | A+A=A |
| doplněk | A⋅A=0 | A+A=1 |
| dvojí negace | A=A | |
| komutativní | AB=BA | A+B=B+A |
| asociativní | (AB)C=A(BC) | (A+B)+C=A+(B+C) |
| distributivní | A(B+C)=AB+AC | A+BC=(A+B)(A+C) |
| absorpce | A(A+B)=A | A+AB=A |
| absorpce negace | A(A+B)=AB | A+AB=A+B |
Nejdůležitější jsou De Morganovy zákony, které převádějí součin na součet a naopak:
De Morganův zákon pro součin:
A⋅B=A+B
De Morganův zákon pro součet:
A+B=A⋅B
Platí pro libovolný počet proměnných: negace součinu je součet negací, negace součtu je součin negací.
Zápis funkce z pravdivostní tabulky
Funkci zadanou tabulkou zapíšeme v úplné normální disjunktivní formě (součet součinů): pro každý řádek, kde je výstup 1, vytvoříme součin všech proměnných – proměnnou s hodnotou 0 zapíšeme negovanou, s hodnotou 1 bez negace. Tyto součiny sečteme.
Příklad 1 – funkce „většina“. Výstup Y je 1, když jsou aspoň dva ze tří vstupů A, B, C rovny 1.
| A | B | C | Y | součin |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 1 | ABC |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | ABC |
| 1 | 1 | 0 | 1 | ABC |
| 1 | 1 | 1 | 1 | ABC |
Y=ABC+ABC+ABC+ABC
Minimalizace algebraickou metodou
Minimalizace zjednoduší výraz tak, aby obvod potřeboval co nejméně logických členů a vstupů. Algebraická metoda používá zákony Booleovy algebry – nejčastěji vytýkání a doplněk A+A=1.
Příklad 2.
Y=AB+AB=A(B+B)=A⋅1=A
Příklad 3.
Y=ABC+ABC+ABC
- Z prvních dvou členů vytkneme BC: BC(A+A)=BC.
- Zbude Y=BC+ABC=B(C+AC).
- Podle absorpce negace je C+CA=C+A.
- Výsledek: Y=B(C+A)=AB+BC.
Příklad 4 – minimalizace funkce „většina“. Člen ABC přičteme ještě dvakrát (idempotence ABC+ABC=ABC výraz nezmění) a sdružíme ho s každým z ostatních:
Y=(ABC+ABC)+(ABC+ABC)+(ABC+ABC)
Z každé závorky vytkneme společnou dvojici a použijeme X+X=1:
Y=BC+AC+AB
Místo čtyř trojvstupových součinů stačí tři dvouvstupové.
Příklad 5 – De Morgan.
Y=A+B=A⋅B=AB
Realizace pomocí členů NAND
Člen NAND je univerzální – samotnými členy NAND lze vytvořit libovolnou logickou funkci. Výrobci proto často staví obvody jen z jednoho typu členu (NAND se v technologii CMOS vyrábí nejsnáze). Totéž platí pro NOR.
Negace z NAND – oba vstupy členu spojíme:
A=A⋅A
Součin z NAND – za člen NAND zařadíme druhý NAND zapojený jako invertor:
A⋅B=A⋅B
Součet z NAND – podle De Morganova zákona nejprve negujeme oba vstupy:
A+B=A⋅B
Převod funkce na členy NAND
- Funkci minimalizujeme a zapíšeme jako součet součinů.
- Celý výraz dvakrát negujeme (hodnota se nezmění).
- Spodní negaci rozložíme De Morganovým zákonem – součet se změní na součin negací.
- Každý negovaný součin je jeden člen NAND.
Příklad 6 – funkce „většina“ z členů NAND.
Y=AB+AC+BC=AB+AC+BC=AB⋅AC⋅BC
Schéma tedy tvoří tři dvouvstupové členy NAND se vstupy (A, B), (A, C) a (B, C), jejichž výstupy vedou do jednoho třívstupového členu NAND, na jehož výstupu je Y. Obvod potřebuje jen jeden typ členu.
Příklad 7. Funkci Y=A+BC převedeme na NAND:
Y=A+BC=A⋅BC
Potřebujeme: invertor (NAND se spojenými vstupy) pro A, invertor pro B, dvouvstupový NAND se vstupy B a C a výstupní dvouvstupový NAND se vstupy A a BC – celkem čtyři členy NAND.
Otázky k opakování
- Kolik řádků má pravdivostní tabulka funkce čtyř proměnných? 24=16
- Zapište oba De Morganovy zákony. AB=A+B a A+B=A⋅B
- Zjednodušte Y=A+AB. Y=A (absorpce)
- Zjednodušte Y=AB+AB+AB. A(B+B)+AB=A+AB=A+B
- Proč se člen NAND označuje jako univerzální? samotnými členy NAND lze vytvořit negaci, součin i součet, a tedy libovolnou logickou funkci
- Jak z členu NAND vytvoříte invertor? spojením obou vstupů: A⋅A=A
- Vyjádřete Y=AB+C pouze pomocí NAND. Y=AB⋅C – NAND (A, B), invertor pro C a výstupní NAND