Booleova algebra: Porovnání verzí
| Řádek 10: | Řádek 10: | ||
==Dualita operací== | ==Dualita operací== | ||
| − | |||
=== Algebraická dualita === | === 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. | 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]]. | Stoneova dualita, pojmenovaná po [[Marshall Stone|Marshallu Stoneovi]] dává do souvislosti Booleovy algebry a kompaktní totálně nesouvislé [[Topologický prostor|topologické prostory]]. | ||
Verze z 9. 11. 2014, 23:18
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 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, je unární operátor na B a platí axiomy:
asociativita
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 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
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.
Obsah
Dualita operací
Algebraická dualita
Máme-li formuli v jazyce , pak její dualitu vytvoříme tak, že nahradíme za , 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. Je-li tedy 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 \langle\mathbb{B}, \wedge, \vee, \textbf{1}, \textbf{0}, -\rangle} Booleova algebra, pak je Booleova algebra i . 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.
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}
(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 \leq b \leftrightarrow -b \leq -a}
Zákon idempotence
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 = a}
Zákon pohlcení
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 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 < a_2}
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_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_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 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} \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 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}} (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} .
Zdroje
- BALCAR B., ŠTĚPÁNEK P. Teorie množin, Kapitola IV. Academia, Praha, 1986.