Booleova algebra

Booleova algebra, nazvaná podle irského matematika George Boolea, je struktura $\mathbb {B} =(B,\wedge ,\vee ,{\textbf {1}},{\textbf {0}},-)$, kde Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle B} je neprázdný nosič, Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle \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 Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle \wedge ,\vee }
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle B_{2}} komutativita $\wedge ,\vee$
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle B_{3}} distributivita $\wedge ,\vee$
$B_{4}$ komplementarita Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle a\wedge -a=0,a\vee -a=1}
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle B_{5}} absorpce $a\vee (a\wedge b)=a,a\wedge (a\vee b)=a$
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle B_{6}} nedegenerovanost Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle {\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 Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle 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 Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle 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

Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a \leq b \equiv a \wedge b = a \equiv a \vee b = b}
Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a - b \equiv a \wedge -b}
$a\vartriangle b\equiv a-b\vee b-a$ (symetrický rozdíl)
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle --a=a}
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle -a=-b\rightarrow a=b}
Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 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$
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle -(a\vee b)=-a\wedge -b}

Monotonie

Jestliže Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle a_{1}<a_{2}} a $b_{1}<b_{2}$, pak v každé Booleově algebře platí:
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle a_{1}\vee b_{1}\leq a_{2}\vee b_{2}}
$a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}$
Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle -a_{2}\leq -a_{1}}

Isomorfismus BA

Dvě Booleovy algebry Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \mathbb{B}} a Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \mathbb{C}} jsou isomorfní (značíme $\mathbb {B} \cong \mathbb {C}$) právě tehdy, když Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle (\mathbb{B}, \leq)} a Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle (\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 Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \mathbb{C}} jsou zúžením operací algebry Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \mathbb{B}} na množinu C) nazýváme podalgebrou Booleovy algebry Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \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 Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \kappa} nekonečná, pak existuje Booleova algebra mohutnosti Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \kappa} . Pro každou mohutnost X existuje Booleova algebra.

Zdroje

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