Booleova algebra

Booleova algebra je algebraická struktura se dvěma binárními a jednou unární operací, která zobecňuje vlastnosti množinových a logických operací. Je nazvána podle britského matematika George Boolea. Mimo oblast algebry se pojem Booleova algebra zužuje na dvouprvkovou Booleovu algebru^[1] a používá se pro reprezentaci pravdivostních hodnot a logických funkcí. Klíčový význam mají Booleovy algebry také pro metodu forsingu.

Booleova algebra je definována jako distributivní komplementární svaz.^[2]

Jinou ekvivalentní definicí je následující. Booleova algebra je šestice (A, ∧, ∨, −, 0, 1), kde A je neprázdná množina, 0 ∈ A je nejmenší, 1 ∈ A největší prvek, − je unární operace (doplněk neboli komplement) a ∧, ∨ jsou binární operace (průsek a spojení) na A, splňující následující axiomy.

Komutativita:	${\displaystyle x\lor y=y\lor x}$	${\displaystyle x\land y=y\land x}$
Distributivita:	${\displaystyle x\lor (y\land z)=(x\lor y)\land (x\lor z)}$	${\displaystyle x\land (y\lor z)=(x\land y)\lor (x\land z)}$
Neutralita 0 a 1:	${\displaystyle x\lor 0=x}$	${\displaystyle x\land 1=x}$
Komplementarita:	${\displaystyle x\lor -x=1}$	${\displaystyle x\land -x=0}$

Někdy se uvádí ještě axiom nedegenerovanosti: ${\displaystyle 0\neq 1}$. Při jeho zavedení pak triviální svaz tvořený jednoprvkovou množinou není Booleovou algebrou.

Pro Booleovu algebru A a každé x, y, z ∈ A platí:

• asociativita: (x ∨ y) ∨ z = x ∨ (y ∨ z), (x ∧ y) ∧ z = x ∧ (y ∧ z)
• absorpce: x ∨ (x ∧ y) = x, x ∧ (x ∨ y) = x
• agresivita nuly: x ∧ 0 = 0
• agresivita jedničky: x ∨ 1 = 1
• idempotence: x ∨ x = x, x ∧ x = x
• absorpce negace: x ∨ (−x ∧ y) = x ∨ y, x ∧ (−x ∨ y) = x ∧ y
• dvojitá negace: −(−x) = x
• De Morganovy zákony: −x ∧ −y = −(x ∨ y), −x ∨ −y = −(x ∧ y)
• 0 a 1 jsou vzájemně komplementární: −0 = 1, −1 = 0

Booleovy algebry musí splňovat více axiomů, než svazy, a proto je jejich struktura jednotnější. Například každá konečná Booleova algebra má ${\displaystyle 2^{n}}$ prvků pro nějaké ${\displaystyle n>0}$ a je izomorfní s direktním součinem ${\displaystyle n}$ dvouprvkových Booleových algeber.

Dvouprvková algebra je algebra nad množinou A = {0, 1}, kde operace jsou dány přirozeným způsobem, tj. 0 a 1 jsou vzájemně komplementární a protože platí 0 < 1, průsek (infimum) je menší z operandů, spojení (supremum) je větší z operandů:

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle x\lor y}$	${\displaystyle x\land y}$
0	0	0	0
0	1	1	0
1	0	1	0
1	1	1	1

Nejjednodušší Booleova algebra obsahuje pouze jeden prvek, neboli 0 = 1 (zde nejde o spor, nýbrž o dvojí značení jednoho prvku). Všechny operace dávají stejný výsledek (jiné zde ani neexistují), proto se nazývá triviální. Tato algebra samozřejmě může existovat jedině tehdy, když nepoužijeme axiom nedegenerovanosti.

U množinových algeber je algebra definována nad množinou všech podmnožin (potenční množinou) libovolné množiny S, tzn. A = 2^S, nejmenším prvkem 0 je prázdná množina, největším prvkem 1 je celá množina S a operace odpovídají průniku, sjednocení a doplňku do množiny S.

Nekonečné Booleovy algebry mohou být atomární, kdy pod každým nenulovým prvkem ${\displaystyle x}$ je atom ${\displaystyle a}$; atom je prvek, pod kterým již nic neleží, tj. neexistuje ${\displaystyle y}$ takové, že ${\displaystyle 0\prec y\prec a}$. Existují naopak bezatomární algebry, které nemají žádné atomy. Příkladem bezatomárních algeber jsou husté Booleovy algebry, v nichž pro každé ${\displaystyle a\prec b}$ existuje ${\displaystyle x}$ takové, že ${\displaystyle a\prec x\prec b}$.

Poznámka: Jako v každém svazu se používá symbol ${\displaystyle a\preceq b}$ pro ${\displaystyle a\land b=a}$ (nebo ekvivalentně ${\displaystyle a\lor b=b}$) a symbol ${\displaystyle a\prec b}$ pro ostré uspořádání, tj. relaci „${\displaystyle a\preceq b}$ a zároveň ${\displaystyle a\neq b}$“.

Prakticky používanými příklady Booleových algeber jsou algebry výroků (či obecněji Lindenbaumovy algebry formulí) a množinové algebry.

• U algeber výroků v dvouhodnotové logice je A = {nepravda, pravda} a operace odpovídají konjunkci, disjunkci a negaci; pokud ztotožníme 0 = nepravda, 1 = pravda, algebra přejde na výše uvedenou dvouprvkovou algebru nad množinou A = {0, 1}
• Lindenbaumovy algebry jsou definovány nad množinou A všech tříd ekvivalence formulí daného jazyka a operace jsou stejné jako u algeber výroků.

• kolektiv autorů, 1977. Aplikovaná matematika. Redakce Kutinová, Blanka; Nečas, Jiří. Praha: SNTL – Nakladatelství technické literatury, n.p.. 1318 s. (Oborové encyklopedie). 
• ROBERT, Faure; HEURGONOVÁ, Edith. Uspořádání a Booleovy algebry. Praha: Academia, 1984. 

• Booleova logika
• Forsing
• De Morganovy zákony

• Obrázky, zvuky či videa k tématu Booleova algebra na Wikimedia Commons