Booleova algebra

Vydáno: 06. 02. 2012; Poslední aktualizace: 16. 10. 2026; 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 Claude Elwood Shannon ve své diplomové práci ukázal, že Booleovu algebru lze přímo využít pro návrh a analýzu reléových a spínacích obvodů. Tím položil teoretické základy digitální elektroniky.

Dvojková soustava

Dvojková číselná soustava začala mít praktický význam, až v době prvních počítačů. Obsahuje pouze dvě číslice: 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

Binární číslo 111100 převedené do desítkové soustavy je tedy 60.

Logické značky

Značení logických funkcí je různé v závislosti na oblasti využití, nejběžnější shrnuje následující tabulka.

OperaceAlgebraProgramování
ANDA·BA && B
ORA+BA | B
NOT¬A!A
XORA ⊕ BA ^ B

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.
Negace logického součtu (NOR) – pokud jsou všechny vstupní hodnoty 0 vrací 1, jinak 0.
Exkluzivní disjunkce nebo exkluzivní OR (XOR) – vrací hodnotu 1 právě tehdy, když jsou vstupy různé.
Funkce XNOR (ekvivalence) – vrací 1 tehdy, když jsou oba vstupy stejné.

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

ABANDNANDORNORXORneg. Aneg. B
000101011
010110110
100110101
111010000
Pravdivostní tabulka pro funkce AND, NAND, OR, NOR, XOR a NOT


Hradla NAND a NOR jsou univerzální hradla. Pomocí samotných NAND nebo samotných NOR lze realizovat libovolnou logickou funkci.

Základní pravidla Booleovy algebry

Zákony dominance 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 XNOR\(a.b+\overline{a}.\overline{b}\)
f12 0 1 1 0neekvivalenceXOR\(\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
  • Implikace A ⇒ B je nepravdivá pouze tehdy, když A = 1 a současně B = 0.

Literatura

  1. Introduction to Boolean Algebra
  2. Boolean Algebra and Logic Gates
  3. Booleova algebra v Encyklopedii fyziky
  4. Boolean functions and their applications in cryptography. ISBN 978-3-662-48863-8

Další kapitoly

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *

Web používá Akismet ke snížení množství spamu. Zjistěte, jak jsou zpracovávány údaje z komentářů.