Booleova algebra: Porovnání verzí
| Řádek 1: | Řádek 1: | ||
| − | Booleova algebra | + | 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_1</math> '''asociativita''' <math>\wedge, \vee</math><br /> | ||
<math>B_2</math> '''komutativita''' <math>\wedge, \vee</math><br /> | <math>B_2</math> '''komutativita''' <math>\wedge, \vee</math><br /> | ||
| Řádek 5: | Řádek 5: | ||
<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_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 /> | <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 /> | 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'''. | 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'''. | ||
| Řádek 15: | Řádek 16: | ||
<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)<br /> | <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 | + | <math>--a = a</math><br /><math>-a = -b \rightarrow a = b</math><br /> |
| − | Monotonie:<br /> | + | <math>a \leq b \leftrightarrow -b \leq -a</math><br /><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> | + | '''Zákony de Morganovy''':<br /> |
| + | <math>-(a \wedge b) = -a \vee -b</math><br /><math>-(a \vee b) = -a \wedge -b</math><br /><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> | ||
==Mohutnost Booleovy algebry== | ==Mohutnost Booleovy algebry== | ||
Verze z 27. 9. 2014, 15:57
Booleova algebra, nazvaná podle irského matematika George Boolea, je struktura 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} = (B, \wedge, \vee, \textbf{1}, \textbf{0}, -)}
, kde 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 B}
je neprázdný nosič, 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 \wedge, \vee}
jsou binární operátory, 0 je nejmenší a 1 největší prvek, 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 -}
je unární operátor na B a platí axiomy:
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 B_1}
asociativita 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 \wedge, \vee}
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 B_2}
komutativita 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 \wedge, \vee}
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 B_3}
distributivita 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 \wedge, \vee}
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 B_4}
komplementarita 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 \wedge -a = 0, a \vee -a = 1}
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 B_5}
absorpce 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 \vee (a \wedge b) = a, a \wedge (a \vee 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 B_6}
nedegenerovanost 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 \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 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 \wedge -a = 0 \wedge a \vee -a = 1}
. Uvedené operace, tedy průsek, spojení a operaci 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 -}
pro doplněk, označujeme jako booleovská operace.
Obsah
Dualita operací
Máme-li formuli 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 \varphi} v jazyce 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 (\wedge, \vee, \textbf{1}, \textbf{0}, -)} , pak její dualitu 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 d(\varphi)} vytvoříme tak, že nahradíme 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 \wedge} za 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 \vee} , 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 \vee} za 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 \wedge} ,1 za 0 a 0 za 1. Formule 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 \varphi} platí v každé BA, jestliže v každé BA platí její dualita 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 d(\varphi)} . 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
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}
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 \vartriangle b \equiv a - b \vee b - a}
(symetrický rozdíl)
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 = 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 -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ákony de Morganovy:
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 \wedge b) = -a \vee -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 \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í:
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_1 \vee b_1 \leq a_2 \vee b_2}
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_1 \wedge b_1 \leq a_2 \wedge b_2}
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_2 \leq -a_1}
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.