Booleova algebra

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čů.

Obsah

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 2ⁿ, kde n je rovno pozici číslice, pozici značíme zprava a číslujeme od 0.

(111100)₂ = 1.2⁵ + 1.2⁴ + 1.2³ + 1.2² + 0.2¹ + 0.2⁰ = (60)₁₀

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í.

A	B	AND	NAND	OR	NOR	neg. A	neg. B
0	0	0	1	0	1	1	1
0	1	0	1	1	0	1	0
1	0	0	1	1	0	0	1
1	1	1	0	1	0	0	0

Pravdivostní tabulka pro funkce AND, NAND, OR, NOR a NOT

Základní pravidla Booleovy algebry

Zákony agresivnosti hodnot 0 a 1
a + 1 = 1	a . 0 = 0
Zákony neutrálnosti hodnot 0 a 1
a + 0 = a	a . 1 = a
Zákony komutativní
a + b = b + a	ab = ba
Zákony asociativní
a + (b + c) = (a + b) + c	a(bc) = (ab)c
Zákony distributivní
a(b + c) = ab + ac	a + 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í

Funkce	Vstupní proměnné a 0 1 0 1 b 0 0 1 1	Název funkce	Logický člen	Algebraický výraz
f₀	0 0 0 0	konstanta		0
f₁	0 1 1 1	logický součet	OR	a + b
f₂	1 0 1 1	implikace		\(\overline{a}+b\)
f₃	1 1 0 1	implikace		\(a+\overline{b}\)
f₄	1 1 1 0	Shefferova funkce	NAND	\(\overline{a}+\overline{b} = \overline{ab}\)
f₅	0 0 0 1	logický součin	AND	ab
f₆	0 0 1 0	inhibice		\(\overline{a}b\)
f₇	0 1 0 0	inhibice		\(a\overline{b}\)
f₈	1 0 0 0	Pieceova funkce	NOR	\(\overline{a}.\overline{b}=\overline{a+b}\)
f₉	0 1 0 1	identita		a
f₁₀	0 0 1 1	identita		b
f₁₁	1 0 0 1	ekvivalence		\(a.b+\overline{a}.\overline{b}\)
f₁₂	0 1 1 0	neekvivalence	Exclusive-OR	\(\overline{a}.b+a.\overline{b}\)
f₁₃	1 0 1 0	negace	NOT	\(\overline{a}\)
f₁₄	1 1 0 0	negace	NOT	\(\overline{b}\)
f₁₅	1 1 1 1	konstanta		1

Literatura

Introduction to Boolean Algebra