Booleova algebra: Porovnání verzí

Řá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 (BA), 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 />
 +
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'''.
  
==Formule a zákony platné v BA==
+
==Dualita operací==
 +
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'''. 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.
  
 +
==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 \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 - 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 />de Morganovy zákony:<br /><math>-(a \wedge b) = -a \vee -b</math><br /><math>-(a \vee b) = -a \wedge -b</math><br />
 +
Monotonie:<br />
 +
Jestliže a_1 < a_2 a b_1 < b_2, 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>
  
==Dualita operací==
+
==Mohutnost Booleovy algebry==
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 />
+
Mohutnost Booleovy algebry odpovídá mohutnosti její nosné množiny.
Formule <math>\varphi</math> platí v každé BA, jestliže v každé BA platí její dualita <math>d(\varphi)</math>.
+
 
 +
==Zdroje==
 +
BALCAR B., ŠTĚPÁNEK P. Teorie množin, Kapitola IV. Academia, Praha, 1986.

Verze z 27. 9. 2014, 16:48

Booleova algebra (BA), nazvaná podle irského matematika George Boolea, je struktura , kde je neprázdný nosič, jsou binární operátory, 0 je nejmenší a 1 největší prvek, je unární operátor na B a platí axiomy:
asociativita
komutativita
distributivita
komplementarita
absorpce
nedegenerovanost

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 . Uvedené operace, tedy průsek, spojení a operaci pro doplněk, označujeme jako booleovská operace.

Dualita operací

Máme-li formuli v jazyce , pak její dualitu vytvoříme tak, že nahradíme za , za ,1 za 0 a 0 za 1. Formule platí v každé BA, jestliže v každé BA platí její dualita . Stačí nám tedy dokazovat jen polovinu vět, zbytek dostaneme díky této vlastnosti.

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



(symetrický rozdíl)


de Morganovy zákony:


Monotonie:
Jestliže a_1 < a_2 a b_1 < b_2, pak v každé Booleově algebře platí:


Mohutnost Booleovy algebry

Mohutnost Booleovy algebry odpovídá mohutnosti její nosné množiny.

Zdroje

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