Booleova algebra

Booleova algebra, nazvaná podle irského matematika George Boolea, je struktura $ \mathbb{B} = (B, \wedge, \vee, \textbf{1}, \textbf{0}, -) $, kde $ B $ je neprázdný nosič, $ \wedge, \vee $ jsou binární operátory, 0 je nejmenší a 1 největší prvek, $ - $ je unární operátor na B a platí axiomy:
$ B_1 $ asociativita $ \wedge, \vee $
$ B_2 $ komutativita $ \wedge, \vee $
$ B_3 $ distributivita $ \wedge, \vee $
$ B_4 $ komplementarita $ a \wedge -a = 0, a \vee -a = 1 $
$ B_5 $ absorpce $ a \vee (a \wedge b) = a, a \wedge (a \vee b) = a $
$ B_6 $ nedegenerovanost $ \textbf{0} \neq \textbf{1} $

Poslední z uvedených axiomů způsobuje, že triviální svaz tvořený jednoprvkovou množinou (0 = 1) není BA.

Booleova algebra je distributivní komplementární svaz, tedy pro každý prvek z nosiče existuje právě jeden jeho komplement (doplněk) takový, který splňuje $ a \wedge -a = 0 \wedge a \vee -a = 1 $. Uvedené operace, tedy průsek, spojení a operaci $ - $ pro doplněk, označujeme jako booleovská operace.

Dualita operací

Algebraická dualita

Máme-li formuli $ \varphi $ v jazyce $ (\wedge, \vee, \textbf{1}, \textbf{0}, -) $, pak její dualitu $ d(\varphi) $ vytvoříme tak, že nahradíme $ \wedge $ za $ \vee $, $ \vee $ za $ \wedge $,1 za 0 a 0 za 1. Je-li tedy $ \langle\mathbb{B}, \wedge, \vee, \textbf{1}, \textbf{0}, -\rangle $ Booleova algebra, pak je Booleova algebra i $ \langle\mathbb{B}, \vee, \wedge, \textbf{0}, \textbf{1}, -\rangle $. Formule $ \varphi $ platí v každé BA, jestliže v každé BA platí její dualita $ d(\varphi) $. Stačí nám tedy dokazovat jen polovinu vět, zbytek dostaneme díky této vlastnosti.

Stoneova dualita

Stoneova dualita, pojmenovaná po Marshallu Stoneovi dává do souvislosti Booleovy algebry a kompaktní totálně nesouvislé topologické prostory.

Formule a zákony platné v Booleově algebře

$ a \leq b \equiv a \wedge b = a \equiv a \vee b = b $
$ a - b \equiv a \wedge -b $
$ a \vartriangle b \equiv a - b \vee b - a $ (symetrický rozdíl)
$ --a = a $
$ -a = -b \rightarrow a = b $
$ a \leq b \leftrightarrow -b \leq -a $

Zákon idempotence

$ a \wedge a = a $
$ a \vee a = a $

Zákon pohlcení

$ a \wedge (a \vee b) = a $
$ a \vee (a \wedge b) = a $

Zákony de Morganovy

$ -(a \wedge b) = -a \vee -b $
$ -(a \vee b) = -a \wedge -b $

Monotonie

Jestliže $ a_1 < a_2 $ a $ b_1 < b_2 $, pak v každé Booleově algebře platí:
$ a_1 \vee b_1 \leq a_2 \vee b_2 $
$ a_1 \wedge b_1 \leq a_2 \wedge b_2 $
$ -a_2 \leq -a_1 $

Isomorfismus BA

Dvě Booleovy algebry $ \mathbb{B} $ a $ \mathbb{C} $ jsou isomorfní (značíme $ \mathbb{B} \cong \mathbb{C} $) právě tehdy, když $ (\mathbb{B}, \leq) $ a $ (\mathbb{C}, \leq) $ jsou isomorfní jako uspořádání.

Podalgebra

Libovolnou neprázdnou podmnožinu C uzavřenou na booleovské operace algebry $ \mathbb{B} $ (operace podalgebry $ \mathbb{C} $ jsou zúžením operací algebry $ \mathbb{B} $ na množinu C) nazýváme podalgebrou Booleovy algebry $ \mathbb{B} $. Každá podalgebra Booleovy algebry je také Booleova algebra. Každá podalgebra obsahuje 0 a 1, samu sebe a triviální algebru jako své podalgebry.

Mohutnost Booleovy algebry

Mohutnost Booleovy algebry odpovídá mohutnosti její nosné množiny. Je-li $ \kappa $ nekonečná, pak existuje Booleova algebra mohutnosti $ \kappa $. Pro každou mohutnost X existuje Booleova algebra.

Zdroje

  • BALCAR B., ŠTĚPÁNEK P. Teorie množin, Kapitola IV. Academia, Praha, 1986.