Booleova algebra: Porovnání verzí

Aktuální verze z 10. 12. 2014, 16:15

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.

Obsah

1 Dualita operací
- 1.1 Algebraická dualita
- 1.2 Stoneova dualita
2 Formule a zákony platné v Booleově algebře
3 Podalgebra
4 Mohutnost Booleovy algebry
5 Zdroje

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.

@@ Řádek 1: / Řádek 1: @@
-Booleova algebra (BA), nazvaná podle irského matematika [[George Boole|George Boolea]], je '''struktura''' <math>\mathbb{B} = (B, \wedge, \vee, 1, 0, -)</math>, kde B je neprázdný nosič, <math>\wedge, \vee</math> jsou binární operátory, 0 je nejmenší a 1 největší prvek, - je unární operátor na B a platí axiomy:<br />
+Booleova algebra, nazvaná podle irského matematika [[George Boole|George Boolea]], je '''struktura''' <math>\mathbb{B} = (B, \wedge, \vee, \textbf{1}, \textbf{0}, -)</math>, kde <math>B</math> je neprázdný nosič, <math>\wedge, \vee</math> jsou binární operátory, '''0''' je nejmenší a '''1''' největší prvek, <math>-</math> je unární operátor na B a platí axiomy:<br />
-<math>B_1</math> '''asociativita''' <math>\wedge, \vee</math><br /><math>B_2</math> '''komutativita''' <math>\wedge, \vee</math><br /><math>B_3</math> '''distributivita''' <math>\wedge, \vee</math><br /><math>B_4</math> '''komplementarita''' <math>a \wedge -a = 0, a \vee -a = 1</math><br /><math>B_5</math> '''absorpce''' <math>a \vee (a \wedge b) = a, a \wedge (a \vee b) = a</math><br /><math>B_6</math> '''nedegenerovanost''' <math>0 \neq 1</math><br />Poslední z uvedených axiomů způsobuje, že triviální [[Svaz|svaz]] tvořený jednoprvkovou množinou (0 = 1) není BA.<br />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 axiom <math>B_4</math>.<br />
+<math>B_1</math> '''asociativita''' <math>\wedge, \vee</math><br />
+<math>B_2</math> '''komutativita''' <math>\wedge, \vee</math><br />
+<math>B_3</math> '''distributivita''' <math>\wedge, \vee</math><br />
+<math>B_4</math> '''komplementarita''' <math>a \wedge -a = 0, a \vee -a = 1</math><br /><math>B_5</math> '''absorpce''' <math>a \vee (a \wedge b) = a, a \wedge (a \vee b) = a</math><br />
+<math>B_6</math> '''nedegenerovanost''' <math>\textbf{0} \neq \textbf{1}</math><br /><br />
-==Formule a zákony platné v BA==
+Poslední z uvedených axiomů způsobuje, že triviální [[Svaz|svaz]] tvořený jednoprvkovou množinou ('''0''' = '''1''') není BA.<br /><br />
+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 <math>a \wedge -a = 0 \wedge a \vee -a = 1</math>. Uvedené operace, tedy průsek, spojení a operaci <math>-</math> pro doplněk, označujeme jako '''booleovská operace'''.
+==Dualita operací==
+=== Algebraická dualita ===
+Máme-li formuli <math>\varphi</math> v jazyce <math>(\wedge, \vee, \textbf{1}, \textbf{0}, -)</math>, pak její '''dualitu''' <math>d(\varphi)</math> vytvoříme tak, že nahradíme <math>\wedge</math> za <math>\vee</math>, <math>\vee</math> za <math>\wedge</math>,'''1''' za '''0''' a '''0''' za '''1'''. Je-li tedy <math>\langle\mathbb{B}, \wedge, \vee, \textbf{1}, \textbf{0}, -\rangle</math> Booleova algebra, pak je Booleova algebra i <math>\langle\mathbb{B}, \vee, \wedge, \textbf{0}, \textbf{1}, -\rangle</math>. Formule <math>\varphi</math> platí v každé BA, jestliže v každé BA platí její dualita <math>d(\varphi)</math>. Stačí nám tedy dokazovat jen polovinu vět, zbytek dostaneme díky této vlastnosti.
+=== Stoneova dualita ===
+[[Stoneova dualita|Stoneova dualita]], pojmenovaná po [[Marshall Stone|Marshallu Stoneovi]] dává do souvislosti Booleovy algebry a kompaktní totálně nesouvislé [[Topologický prostor|topologické prostory]].
+== Formule a zákony platné v Booleově algebře==
 <math>a \leq b \equiv a \wedge b = a \equiv a \vee b = b</math><br />
 <math>a - b \equiv a \wedge -b</math><br />
-<math>a \vartriangle b \equiv a - b \vee b - a</math> (symetrický rozdíl)
+<math>a \vartriangle b \equiv a - b \vee b - a</math>     (symetrický rozdíl)<br />
+<math>--a = a</math><br /><math>-a = -b \rightarrow a = b</math><br />
+<math>a \leq b \leftrightarrow -b \leq -a</math><br />
+=== Zákon idempotence===
+<math>a \wedge a = a</math><br/><math>a \vee a = a</math>
+===Zákon pohlcení===
+<math>a \wedge (a \vee b) = a</math><br/><math>a \vee (a \wedge b) = a</math>
-==Dualita operací==
+=== Zákony de Morganovy===
-Máme-li formuli <math>\varphi</math> v jazyce <math>(\wedge, \vee, 1, 0, -)</math>, pak její '''dualitu''' <math>d(\varphi)</math> vytvoříme tak, že nahradíme <math>\wedge</math> za <math>\vee</math>, <math>\vee</math> za <math>\wedge</math>,1 za 0 a 0 za 1.<br />
+<math>-(a \wedge b) = -a \vee -b</math><br /><math>-(a \vee b) = -a \wedge -b</math><br /><br />
-Formule <math>\varphi</math> platí v každé BA, jestliže v každé BA platí její dualita <math>d(\varphi)</math>.
+=== Monotonie===
+Jestliže <math>a_1 < a_2</math> a <math>b_1 < b_2</math>, pak v každé Booleově algebře platí:<br />
+<math>a_1 \vee b_1 \leq a_2 \vee b_2</math><br />
+<math>a_1 \wedge b_1 \leq a_2 \wedge b_2</math><br />
+<math>-a_2 \leq -a_1</math><br/><br/>
+===Isomorfismus BA===
+Dvě Booleovy algebry <math>\mathbb{B}</math> a <math>\mathbb{C}</math> jsou '''isomorfní''' (značíme <math>\mathbb{B} \cong \mathbb{C}</math>) právě tehdy, když <math>(\mathbb{B}, \leq)</math> a <math>(\mathbb{C}, \leq)</math> jsou isomorfní jako uspořádání.
+==Podalgebra==
+Libovolnou neprázdnou podmnožinu C uzavřenou na booleovské operace algebry <math>\mathbb{B}</math> (operace podalgebry <math>\mathbb{C}</math> jsou zúžením operací algebry <math>\mathbb{B}</math> na množinu C) nazýváme '''podalgebrou Booleovy algebry <math>\mathbb{B}</math>'''.
+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 <math>\kappa</math> nekonečná, pak existuje Booleova algebra mohutnosti <math>\kappa</math>. Pro každou mohutnost X existuje Booleova algebra.
+==Zdroje==
+* BALCAR B., ŠTĚPÁNEK P. Teorie množin, Kapitola IV. Academia, Praha, 1986.
+[[Kategorie:Struktury a algebry]]