Booleova algebra

Tento druh algebry zavedl v 19. století anglický matematik George Boole (1815 - 1864). Zpočátku se jednalo pouze o zjednodušení zápisu matematických vět a jejich důkazů a o metodu, jak zpřehlednit práci s logickými výroky. V roce 1937 obhájil diplomovou práci mladý americký budoucí inženýr Claude Elwood Shannon (1916 - 2001) a v ní ukázal, jak Booleovu algebru použít k popisu a konstrukci složitých sítí přepínačů (elektromagnetických relé).

Booleovu algebru lze chápat jako nauku o operacích na množině obsahující dvě logické konstanty 0 a 1 a dále logické proměnné, které se označují malými písmeny (např. a, b, c, x, y, z, , , , …). Booleova algebra používá tento základní soubor operací:

1.    logický součin - běžně se označuje operátorem  (a, a zároveň, AND), v technické praxi se označuje tečkou resp. vynecháním tečky;

2.    logický součet - běžně se označuje operátorem  (nebo, OR), v praxi se běžně používá symbol +;

3.    negace - značí se buď symbolem před operandem a nebo vodorovnou čárkou nad operandem.

Vzhledem k tomu, že logická proměnná může nabývat pouze dvou hodnot 0 a 1, není Booleova algebra algebrou čísel, ale algebrou stavů. Logické funkce se velmi často pro přehlednost zapisují pomocí pravdivostní tabulky. Pro n proměnných, z nichž každá může nabývat dvou stavů, dostáváme celkem  kombinací. Pro n proměnných tedy existuje celkem  funkcí.

Pro dvě proměnné tedy dostáváme celkem  funkcí (viz tab. 4).

a	b
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

tab. 4

Řada funkcí, které jsou definovány v tab. 4, se běžně nepoužívá. Některé z nich ale mají natolik zajímavé vlastnosti, že se označují speciálními symboly:

1.    ,  - identické funkce (tzv. triviální identity):  identicky rovna 0,  identicky rovna 1 pro všechny hodnoty vstupních proměnných;

2.     - funkce AND;

3.     - funkce OR (slučovací nebo);

4.     - funkce NAND (negace AND);

5.     - funkce NOR (negace OR);

6.     - funkce XOR (vylučovací nebo);

Rozdíl mezi významem OR a XOR pochopíme asi nejlépe na příkladu z praxe. Ve větě „Mléko se prodává v papírových krabicích nebo v plastových láhvích.“ je nebo použito ve významu OR - slučovací nebo. Mléko se totiž může prodávat „v krabicích a taky v láhvích“.

Ve větě „Dneska večer půjdu do kina nebo do divadla.“ je nebo použito ve smyslu XOR - vylučovací nebo. Navštívím jen jedno představení - „buď kino a nebo divadlo“ (ale ne obě najednou).

7.     - funkce ekvivalence;

8.     - funkce implikace  (ta se ovšem v digitální technice nepoužívá).

Pro tři proměnné a, b a c platí v Booleově algebře zákony, které jsou vypsány v tab. 5.

	Logický součin	Logický součet
Komutativní zákony
Asociativní zákony
Distributivní zákony
Zákony vyloučeného třetího
Zákony neutrality
Zákony agresivity
Zákony o idempotenci prvků
De Morganovy zákony
Zákon dvojité negace
Princip duality

tab. 5

Pozor na distributivní zákon pro logický součin (tj. na výraz ) - ten v algebře reálných čísel neexistuje!

Jak logické funkce (např. z funkce z tab. 4), tak i platnost zákonů Booleovy algebry (sepsaných v tab. 5) lze rozšířit na více proměnných.

Např.  lze na základě asociativního zákona psát ve tvaru , ve kterém jsou oba logické součty () aplikovány vždy na dvě proměnné. Po aplikaci prvního logického součtu máme  a následně provedeme logický součet .