Booleova algebra

Vydáno: 06. 02. 2012; Poslední aktualizace: 10. 09. 2023; Autor: Zdeněk Moravec

Logické obvody realizují logické funkce , které jsou definovány Booleovou algebrou , což je binární algebra, v níž jsou použity tyto logické funkce: AND (logický součin), OR (logický součet), NAND (negovaný logický součin), NOR (negovaný logický součet) a negace. Všechny operace jsou prováděny nad dvouprvkovou množinou hodnot { 0, 1 }.

Tuto algebru zavedl v 19. století George Boole jako zjednodušení zápisu matematických vět a důkazů. V roce 1937 tuto algebru použil Claude Elwood Shannon k popisu zapojení sítí relé a spínačů.

Dvojková soustava

Dvojková číselná soustava začala mít praktický význam, až v době prvních počítačů. Jsou v ní povolené dva znaky, 0 a 1.

Převod z desítkové soustavy do dvojkové

Postup je relativně jednoduchý, číslo dělíme dvěma, zapisujeme si zbytky po dělení a nakonec získané číslo otočíme. Příkladem může být převod čísla 60:

60 : 2 = 30 zbytek 0
30 : 2 = 15 zbytek 0
15 : 2 = 7 zbytek 1
7 : 2 = 3 zbytek 1
3 : 2 = 1 zbytek 1
1 : 2 = 0 zbytek 1

Takže desítkové číslo 60 je ve dvojkové soustavě 111100.

Převod z dvojkové soustavy do desítkové

Převod opačným směrem je také poměrně jednoduché, ukážeme si to na stejném příkladu, tzn. převedeme číslo 111100 do desítkové soustavy. Číslo si rozložíme na jednotlivé číslici, a provedeme součet součinu číslice a členu 2n, kde n je rovno pozici číslice, pozici značíme zprava a číslujeme od 0.

(111100)2 = 1.25 + 1.24 + 1.23 + 1.22 + 0.21 + 0.20 = (60)10

Pravdivostní tabulky základních logických funkcí

Negace (NOT) – získáme opak vstupu
Logický součin (AND) – pokud jsou všechny vstupní hodnoty 1 vrací 1, jinak 0.
Negovaný logický součin (NAND) – pokud jsou všechny vstupní hodnoty 1 vrací 0, jinak 1.
Logický součet (OR) – pokud jsou všechny vstupní hodnoty 0 vrací 0, jinak 1.
Negovaný logický součet (NOR) – pokud jsou všechny vstupní hodnoty 0 vrací 1, jinak 0.

Funkce si můžeme přehledně zobrazit pomocí tzv. pravdivostních tabulek. V tabulce dole obsaují první dva sloupce (A a B) vstupní hodnoty. Zbylé sloupce obsahují výsledné hodnoty jednotlivých funkcí.

ABANDNANDORNORneg. Aneg. B
00010111
01011010
10011001
11101000
Pravdivostní tabulka pro funkce AND, NAND, OR, NOR a NOT

Základní pravidla Booleovy algebry

Zákony agresivnosti hodnot 0 a 1
a + 1 = 1a . 0 = 0
Zákony neutrálnosti hodnot 0 a 1
a + 0 = aa . 1 = a
Zákony komutativní
a + b = b + aab = ba
Zákony asociativní
a + (b + c) = (a + b) + ca(bc) = (ab)c
Zákony distributivní
a(b + c) = ab + aca + bc = (a + b)(a + c)
Zákon dvojité negace
\(\overset{=}a\ =\ a\) 
Zákon o vyloučeném třetím
\(a+\overline{a}\ =\ 1\)\(a.\overline{a}\ =\ 0\)
Zákony absorpce
a + a = a
a + ab = a
a(a + b) = a
aa = a
Zákony absorpce negace
\(a+\overline{a}b\ =\ a + b \\
\overline{a} + ab\ =\ \overline{a}+b\)
\(a(\overline{a}+b)\ =\ ab \\
\overline{a}(a + b)\ =\ \overline{a}b\)
Zákony o vytvoření negace (zákony de Morganovy)
\(\overline{a+b}\ =\ \overline{a}.\overline{b}\)\(\overline{ab}\ =\ \overline{a} + \overline{b}\)

Příklady logických funkcí

FunkceVstupní proměnné a 0 1 0 1
b 0 0 1 1
Název funkceLogický členAlgebraický výraz
f 0 0 0 0 0konstanta 0
f1 0 1 1 1logický součetORa + b
f2 1 0 1 1implikace \(\overline{a}+b\)
f3 1 1 0 1implikace \(a+\overline{b}\)
f4 1 1 1 0Shefferova funkceNAND\(\overline{a}+\overline{b} = \overline{ab}\)
f5 0 0 0 1logický součinANDab
f6 0 0 1 0inhibice \(\overline{a}b\)
f 7 0 1 0 0inhibice \(a\overline{b}\)
f8 1 0 0 0Pieceova funkceNOR\(\overline{a}.\overline{b}=\overline{a+b}\)
f9 0 1 0 1identita a
f10 0 0 1 1identita b
f11 1 0 0 1ekvivalence \(a.b+\overline{a}.\overline{b}\)
f12 0 1 1 0neekvivalenceExclusive-OR\(\overline{a}.b+a.\overline{b}\)
f13 1 0 1 0negaceNOT\(\overline{a}\)
f14 1 1 0 0negaceNOT\(\overline{b}\)
f15 1 1 1 1konstanta 1

Literatura

  1. Introduction to Boolean Algebra

Další kapitoly

Leave a Reply

Tato stránka používá Akismet k omezení spamu. Podívejte se, jak vaše data z komentářů zpracováváme..