Algebra Boole’a


Algebra Boole’a w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania Diagram Hassego dla algebry Boole’a podzbiorów zbioru trójelementowego

Algebra Boole’a – pewien typ struktury algebraicznej, rodzaj algebry ogólnej stosowany w matematyce, informatyce teoretycznej oraz elektronice cyfrowej. Jej nazwa pochodzi od nazwiska matematyka, filozofa i logika George’a Boole’a. Teoria algebr Boole’a jest działem matematyki na pograniczu teorii częściowego porządku, algebry, logiki matematycznej i topologii.

Typowymi przykładami algebr Boole’a są: rodzina wszystkich podzbiorów ustalonego zbioru wraz z działaniami na zbiorach jako operacjami algebry oraz dwuelementowa algebra wartości logicznych {0, 1} z działaniami koniunkcji, alternatywy i negacji.

Spis treści

Definicja | edytuj kod

Algebra Boole’a – struktura algebraiczna B := ( B , , , , 0 , 1 ) , {\displaystyle \mathbb {B} :=(B,\cup ,\cap ,\sim ,0,1),} w której {\displaystyle \cup } i {\displaystyle \cap } działaniami dwuargumentowymi, {\displaystyle \sim } jest operacją jednoargumentową, a 0 i 1 są wyróżnionymi różnymi elementami zbioru B , {\displaystyle B,} spełniająca następujące warunki dla wszystkich a , b , c B : {\displaystyle a,b,c\in B{:}}

Oznaczenia | edytuj kod

Istnieją co najmniej trzy różne, szeroko rozpowszechnione tradycje oznaczeń w teorii algebr Boole’a. W definicji sformułowanej powyżej użyto symboli , , , {\displaystyle \cup ,\cap ,\sim ,} ale w częstym użyciu są również + , , {\displaystyle +,\cdot ,-} oraz , , ¬ . {\displaystyle \lor ,\land ,\lnot .} Symbole oznaczające operacje dwuczłonowe algebry Boole’a są prawie zawsze wprowadzane przez wybór jednej z par ( + , ) , {\displaystyle (+,\cdot ),} ( , ) {\displaystyle (\lor ,\land )} albo ( , ) . {\displaystyle (\cup ,\cap ).} W oznaczeniach operacji jednoargumentowej algebry istnieje mniejsza konsekwencja i można się spotkać zarówno z symbolami + , , , {\displaystyle +,\cdot ,\sim ,} jak i , , . {\displaystyle \lor ,\land ,{}'.}

System oznaczeń przedstawiony powyżej (i dalej przyjmowany w tym artykule) jest używany, między innymi, w podręczniku Heleny Rasiowej.

W badaniach teoriomnogościowych aspektów algebr Boole’a przeważa tradycja używania oznaczeń ( + , , ) {\displaystyle (+,\cdot ,-)} [potrzebny przypis]. Ten sam system został też wybrany za wiodący przez redaktorów monografii Handbook of Boolean Algebras.

Z kolei symbole , {\displaystyle \wedge ,\vee } zgodne z oznaczeniami w teorii krat są częściej używane w kontekstach algebraicznych (i teoriokratowych)[potrzebny przypis].

Spotykane są też inne kombinacje tychże symboli lub wręcz inne symbole (na przykład & w miejsce , {\displaystyle \cap ,} lub a {\displaystyle a'} zamiast a {\displaystyle \sim a} ). W elektronice i informatyce często stosuje się OR, AND oraz NOT w miejsce , {\displaystyle \cup ,} {\displaystyle \cap } oraz . {\displaystyle \sim .} W języku C oraz w językach nim inspirowanych używa się odpowiednio symboli: |, &, !.

Minimalna aksjomatyzacja | edytuj kod

Powyższa (tradycyjna) definicja algebry Boole’a nie jest minimalna, np. nie jest konieczne wprowadzanie w niej symboli 0 i 1. Mogą one być konsekwencją aksjomatyki, a nie niezbędną dla niej definicją. 0 można zastąpić przez ( x ( x ) ) {\displaystyle \sim (x\cup (\sim x))} a 1 przez ( x ( x ) ) . {\displaystyle (x\cup (\sim x)).} Dzięki prawom de Morgana można też z aksjomatyki wyeliminować działanie {\displaystyle \cap } lub . {\displaystyle \cup .} (W istocie wszystkie działania można tak naprawdę zastąpić jednym – dysjunkcją (NAND) lub binegacją (NOR).)

Istnieją równoważne, ale oszczędniejsze definicje algebry Boole’a. Przykładowy układ niezależnych aksjomatów to:

  • {\displaystyle \cup } jest przemienne
  • {\displaystyle \cup } jest łączne
  • aksjomat Huntingtona: ( x y ) ( x y ) = x . {\displaystyle \sim (\sim x\cup y)\;\cup \sim (\sim x\;\cup \sim y)=x.}

Inny taki układ to:

  • {\displaystyle \cup } jest przemienne
  • {\displaystyle \cup } jest łączne
  • aksjomat Robbinsa: ( ( x y ) ( x y ) ) = x {\displaystyle \sim (\sim (x\cup y)\;\cup \sim (x\;\cup \sim y))=x}

Istnieją też systemy z jednym aksjomatem.

Przykłady | edytuj kod

Najprostsza algebra Boole’a ma tylko dwa elementy, 0 i 1, a operacje tej algebry są zdefiniowane przez następujące tabele działań:

Algebra ta stanowi podstawę elektroniki cyfrowej.

Jeśli F {\displaystyle {\mathcal {F}}} jest ciałem podzbiorów zbioru X , {\displaystyle X,} to ( F , , , , , X ) {\displaystyle ({\mathcal {F}},\cup ,\cap ,{}',\varnothing ,X)} jest algebrą Boole’a (gdzie {\displaystyle {}'} oznacza operację dopełnienia).

Niech Z {\displaystyle {\mathcal {Z}}} będzie zbiorem zdań w rachunku zdań. Niech {\displaystyle \equiv } będzie relacją dwuargumentową na zbiorze Z {\displaystyle {\mathcal {Z}}} określoną jako:

φ ψ {\displaystyle \varphi \equiv \psi } wtedy i tylko wtedy, gdy φ ψ {\displaystyle \varphi \Leftrightarrow \psi } jest tautologią rachunku zdań.

Można sprawdzić, że {\displaystyle \equiv } jest relacją równoważności na zbiorze Z . {\displaystyle {\mathcal {Z}}.} Na zbiorze X {\displaystyle X} wszystkich klas abstrakcji φ {\displaystyle [\varphi ]} relacji {\displaystyle \equiv } można wprowadzić operacje , , {\displaystyle \cup ,\cap ,\sim } przez następujące formuły:

φ ψ := φ ψ , {\displaystyle [\varphi ]\cup [\psi ]:=[\varphi \vee \psi ],} φ ψ := φ ψ , {\displaystyle [\varphi ]\cap [\psi ]:=[\varphi \wedge \psi ],} φ := ¬ φ . {\displaystyle \sim [\varphi ]:=[\neg \varphi ].}

W ten sposób otrzymuje się poprawnie zdefiniowane operacje na zbiorze X {\displaystyle X} (tzn. wynik nie zależy od wyboru reprezentantów klas abstrakcji), a ( X , , , , p ¬ p , p ¬ p ) {\displaystyle (X,\cup ,\cap ,\sim ,[p\wedge \neg p],[p\vee \neg p])} jest algebrą Boole’a. Algebra ta jest nazywana algebrą Lindenbauma-Tarskiego.

Algebry Lindenbauma-Tarskiego rozważa się również dla języków pierwszego rzędu. Niech Z {\displaystyle \mathbf {Z} } będzie zbiorem zdań w ustalonym alfabecie τ {\displaystyle \tau } i niech T Z {\displaystyle T\subseteq \mathbf {Z} } będzie niesprzeczną teorią w tym samym języku. Relację dwuargumentową {\displaystyle \equiv } na zbiorze Z {\displaystyle \mathbf {Z} } można wprowadzić przez określenie

φ ψ {\displaystyle \varphi \equiv \psi } wtedy i tylko wtedy, gdy T φ ψ . {\displaystyle T\vdash \varphi \Leftrightarrow \psi .}

Wówczas {\displaystyle \equiv } jest relacją równoważności na zbiorze Z . {\displaystyle \mathbf {Z} .} Podobnie jak wcześniej:

φ ψ := φ ψ , {\displaystyle [\varphi ]\cup [\psi ]:=[\varphi \vee \psi ],} φ ψ := φ ψ , {\displaystyle [\varphi ]\cap [\psi ]:=[\varphi \wedge \psi ],} φ := ¬ φ . {\displaystyle \sim [\varphi ]:=[\neg \varphi ].}

Można pokazać, że ( Z / , , , , ψ ¬ ψ , ψ ¬ ψ ) {\displaystyle (\mathbf {Z} /\equiv ,\cup ,\cap ,\sim ,[\psi \wedge \neg \psi ]_{\equiv },[\psi \vee \neg \psi ]_{\equiv })} jest algebrą Boole’a.

Własności | edytuj kod

Niech B = ( B , , , , 0 , 1 ) {\displaystyle \mathbb {B} =(B,\cup ,\cap ,\sim ,0,1)} będzie algebrą Boole’a. Dla wszystkich a , b B {\displaystyle a,b\in B} zachodzi:

a a = a {\displaystyle a\cup a=a} a a = a {\displaystyle a\cap a=a} a 0 = a {\displaystyle a\cup 0=a} a 1 = a {\displaystyle a\cap 1=a} a 1 = 1 {\displaystyle a\cup 1=1} a 0 = 0 {\displaystyle a\cap 0=0} 0 = 1 {\displaystyle \sim 0=1} 1 = 0 {\displaystyle \sim 1=0}

prawa De Morgana:

( a b ) = ( a ) ( b ) {\displaystyle \sim (a\cup b)=(\sim a)\cap (\sim b)} ( a b ) = ( a ) ( b ) {\displaystyle \sim (a\cap b)=(\sim a)\cup (\sim b)}

podwójne przeczenie:

( a ) = a {\displaystyle \sim (\sim a)=a}

Uporządkowanie | edytuj kod

W zbiorze B {\displaystyle B} wprowadza się porządek boole’owski : {\displaystyle \leqslant {:}}

a b {\displaystyle a\leqslant b} wtedy i tylko wtedy, gdy a b = a {\displaystyle a\cap b=a}

Tak zdefiniowana relacja {\displaystyle \leqslant } jest częściowym porządkiem na zbiorze B . {\displaystyle B.} Zbiór B {\displaystyle B} z relacją ≤ jest kratą rozdzielną.

Ideały, algebry ilorazowe i homomorfizmy | edytuj kod

Niepusty zbiór I B {\displaystyle I\subseteq B} jest ideałem w algebrze B {\displaystyle \mathbb {B} } , jeśli są spełnione następujące dwa warunki:

( a , b I ) ( a b I ) , {\displaystyle {\big (}\forall a,b\in I{\big )}{\big (}a\cup b\in I{\big )},} oraz ( a B , b I ) ( ( a b )     ( a I ) ) . {\displaystyle {\big (}\forall a\in B,b\in I{\big )}{\big (}(a\leqslant b)\ \Rightarrow \ (a\in I){\big )}.}

Każdy ideał zawiera element 0. {\displaystyle 0.} Ideał, który nie zawiera elementu 1 , {\displaystyle 1,} nazywany jest ideałem właściwym. Jedynym niewłaściwym ideałem jest całe B . {\displaystyle B.}

Pojęciem dualnym jest pojęcie filtru: niepusty zbiór F B {\displaystyle F\subseteq B} jest filtrem w algebrze B , {\displaystyle \mathbb {B} ,} jeśli:

( a , b F ) ( a b F ) {\displaystyle {\big (}\forall a,b\in F{\big )}{\big (}a\cap b\in F{\big )}}

oraz

( a F , b B ) ( ( a b )     ( b F ) ) . {\displaystyle {\big (}\forall a\in F,b\in B{\big )}{\big (}(a\leqslant b)\ \Rightarrow \ (b\in F){\big )}.}

Każdy filtr zawiera element 1. {\displaystyle 1.} Filtr, który nie zawiera elementu 0 , {\displaystyle 0,} nazywany jest filtrem właściwym. Jedynym niewłaściwym filtrem jest całe B . {\displaystyle B.}

Niech I B {\displaystyle I\subseteq B} będzie właściwym ideałem w algebrze B . {\displaystyle \mathbb {B} .} Niech I {\displaystyle \approx _{I}} będzie relacją dwuczłonową na B {\displaystyle B} taką, że

a I b {\displaystyle a\approx _{I}b} wtedy i tylko wtedy, gdy ( a ( b ) ) ( b ( a ) ) I . {\displaystyle (a\cap (\sim b))\cup (b\cap (\sim a))\in I.}

Wówczas I {\displaystyle \approx _{I}} jest relacją równoważności na B . {\displaystyle B.} W zbiorze B / I {\displaystyle B/\approx _{I}} klas abstrakcji tej relacji można zdefiniować działania , , ¬ : {\displaystyle \vee ,\wedge ,\neg {:}}

a b := a b , {\displaystyle [a]\vee [b]:=[a\cup b],} a b := a b , {\displaystyle [a]\wedge [b]:=[a\cap b],} ¬ a := a . {\displaystyle \neg [a]:=[\sim a].}

Pokazuje się, że powyższe definicje są poprawne (tzn. wynik operacji nie zależy od wyboru reprezentantów z klas abstrakcji) oraz że ( B / I , , , ¬ , 0 , 1 ) {\displaystyle (B/_{\approx _{I}},\vee ,\wedge ,\neg ,[0],[1])} jest algebrą Boole’a. Algebra ta jest nazywana algebrą ilorazową i jest oznaczana przez B / I . {\displaystyle \mathbb {B} /I.}

Niech B := ( B , 0 , , , 0 , 1 ) {\displaystyle \mathbb {B} ^{*}:=(B^{*},\cup ^{*}0,\cap ^{*},\sim ^{*},0^{*},1^{*})} będzie algebrą Boole’a i niech h : B B {\displaystyle h\colon B\to B^{*}} będzie funkcją odwzorowującą B {\displaystyle B} w B . {\displaystyle B^{*}.} Mówimy, że funkcja h {\displaystyle h} jest homomorfizmem algebr Boole’a, jeśli zachowuje ona działania w algebrze, tzn. dla wszystkich a , b B {\displaystyle a,b\in B} zachodzą trzy równości:

h ( a b ) = h ( a ) h ( b ) , {\displaystyle h(a\cup b)=h(a)\cup ^{*}\;h(b),} h ( a b ) = h ( a ) h ( b ) , {\displaystyle h(a\cap b)=h(a)\cap ^{*}h(b),} h ( a ) = h ( a ) . {\displaystyle h(\sim a)\;=\sim ^{*}h(a).}

Jeśli dodatkowo h {\displaystyle h} jest funkcją wzajemnie jednoznaczną z B {\displaystyle B} na B , {\displaystyle B^{*},} to funkcja h {\displaystyle h} zwana jest izomorfizmem algebr Boole’a.

Jeśli I {\displaystyle I} jest ideałem w algebrze B , {\displaystyle \mathbb {B} ,} to odwzorowanie a a I : B B / I {\displaystyle a\mapsto [a]_{\approx _{I}}\colon \mathbb {B} \to \mathbb {B} /I} jest homomorfizmem.

Jeśli B := ( B , , , , 0 , 1 ) {\displaystyle \mathbb {B} ^{*}:=(B^{*},\cup ^{*},\cap ^{*},\sim ^{*},0^{*},1^{*})} jest algebrą Boole’a oraz h : B B {\displaystyle h\colon B\to B^{*}} jest homomorfizmem na B , {\displaystyle B^{*},} to h 1 ( 0 ) {\displaystyle h^{-1}(0^{*})} jest ideałem w algebrze B {\displaystyle \mathbb {B} } a algebra ilorazowa B / h 1 ( 0 ) {\displaystyle \mathbb {B} /h^{-1}(0^{*})} jest izomorficzna z B . {\displaystyle \mathbb {B} ^{*}.}

Autodualność | edytuj kod

Niech C = ( B , , , , 1 , 0 ) {\displaystyle \mathbb {C} =(B,\cap ,\cup ,\sim ,1,0)} (operacje {\displaystyle \cup } i {\displaystyle \cap } zostały zamienione rolami, podobnie jak stałe 0 i 1). Wtedy także C {\displaystyle \mathbb {C} } jest algebrą Boole’a izomorficzną z wyjściową algebrą B . {\displaystyle \mathbb {B} .} Kanoniczny izomorfizm d tych dwóch algebr jest swoją własną odwrotnością (jest inwolucją zbioru B) i jest dany wzorem:

d ( x ) := x {\displaystyle d(x):={}\sim x}

dla dowolnego x B . {\displaystyle x\in B.}

Algebry wolne | edytuj kod

Algebra Boole’a B {\displaystyle \mathbb {B} } jest wolna, jeśli pewien zbiór X B {\displaystyle X\subseteq B} ma następującą własność:

dla każdej algebry Boole’a B := ( B , , , , 0 , 1 ) {\displaystyle \mathbb {B} ^{*}:=(B^{*},\cup ^{*},\cap ^{*},\sim ^{*},0^{*},1^{*})} i każdego odwzorowania f : X B {\displaystyle f\colon X\to B^{*}} istnieje dokładnie jeden homomorfizm h : B B {\displaystyle h\colon B\to B^{*}} z algebry B {\displaystyle \mathbb {B} } w algebrę B , {\displaystyle \mathbb {B} ^{*},} przedłużający f {\displaystyle f} (czyli taki, że h X = f {\displaystyle h\upharpoonright X=f} ).

Zbiór X B {\displaystyle X\subseteq B} o własności opisanej powyżej jest nazywany zbiorem wolnych generatorów algebry B . {\displaystyle \mathbb {B} .} Jeśli moc zbioru X {\displaystyle X} jest κ , {\displaystyle \kappa ,} to mówimy, że B {\displaystyle \mathbb {B} } jest wolną algebrą Boole’a z κ {\displaystyle \kappa } generatorami.

Skończona algebra Boole’a jest wolna wtedy i tylko wtedy, gdy ma ona 2 2 n {\displaystyle 2^{2^{n}}} elementów (dla n = 0 , 1 , 2 , {\displaystyle n=0,1,2,\dots } ). Algebra mocy 2 2 n {\displaystyle 2^{2^{n}}} jest izomorficzna z ciałem wszystkich podzbiorów zbioru z 2 n {\displaystyle 2^{n}} elementami i jako taka ma n {\displaystyle n} wolnych generatorów.

Nieskończona przeliczalna algebra Boole’a jest wolna wtedy i tylko wtedy, gdy jest bezatomowa, tzn. każdy niezerowy element algebry zawiera przynajmniej dwa różne niezerowe elementy algebry. W zapisie formalnym:

( b B { 0 } ) ( a B { 0 } ) ( a b     a b ) {\displaystyle (\forall b\in B\setminus \{0\})(\exists a\in B\setminus \{0\})(a\leqslant b\ \wedge \ a\neq b)}

Zupełne algebry Boole’a | edytuj kod

Działania nieskończone | edytuj kod

Ponieważ w algebrze Boole’a istnieje porządek częściowy, to dla zbioru A B {\displaystyle A\subseteq B} można rozpatrywać jego kresy (które istnieją lub nie).

Jeśli dwuczłonowe operacje algebry Boole’a są oznaczane przez , {\displaystyle \cap ,\cup } (tak jak w tym artykule), to kres górny zbioru A {\displaystyle A} (gdy istnieje) jest oznaczany przez A , {\displaystyle \bigcup A,} a jego kres dolny (gdy istnieje) jest oznaczany przez A . {\displaystyle \bigcap A.} Jeśli natomiast symbolami dla tych operacji są + , , {\displaystyle +,\cdot ,} to kresy oznaczane są przez A , {\displaystyle \sum A,} A . {\displaystyle \prod A.}

Dla zbioru pustego:

= 0 {\displaystyle \bigcup \varnothing =0} oraz = 1. {\displaystyle \bigcap \varnothing =1.}

Zakładając istnienie odpowiednich kresów, zachodzą wzory de Morgana:

A = { a : a A } {\displaystyle \sim \bigcup A=\bigcap \{\sim a:a\in A\}} oraz A = { a : a A } . {\displaystyle \sim \bigcap A=\bigcup \{\sim a:a\in A\}.}

Ponadto jeśli A B , {\displaystyle \varnothing \neq A\subseteq B,} to:

  • b = A {\displaystyle b=\bigcup A} wtedy i tylko wtedy, gdy
( a A ) ( a b ) {\displaystyle (\forall a\in A)(a\leqslant b)} oraz ( c b ) ( c 0 ( a A ) ( a c 0 ) ) , {\displaystyle {\big (}\forall c\leqslant b{\big )}{\big (}c\neq 0\Rightarrow (\exists a\in A)(a\cap c\neq 0){\big )},}
  • b = A {\displaystyle b=\bigcap A} wtedy i tylko wtedy, gdy
( a A ) ( b a ) {\displaystyle (\forall a\in A)(b\leqslant a)} oraz ( c 0 ) ( c b = 0 ( a A ) ( c ( a ) 0 ) ) . {\displaystyle {\big (}\forall c\neq 0{\big )}{\big (}c\cap b=0\Rightarrow (\exists a\in A)(c\cap (\sim a)\neq 0){\big )}.}

Zupełność | edytuj kod

Następujące dwa stwierdzenia są równoważne dla algebry Boole’a B : {\displaystyle \mathbb {B} {:}}

  • każdy podzbiór B {\displaystyle \mathbb {B} } ma kres górny;
  • każdy podzbiór B {\displaystyle \mathbb {B} } ma kres dolny.

Algebry, w których każdy zbiór ma kres górny (tzn. takie dla których porządek boole’owski {\displaystyle \leqslant } jest zupełny), są nazywane zupełnymi algebrami Boole’a. Zupełne algebry Boole’a są szczególnie ważne w teorii forsingu; są one też przykładami krat zupełnych.

Niech κ {\displaystyle \kappa } będzie liczbą kardynalną, a B {\displaystyle \mathbb {B} } będzie algebrą Boole’a. Powiemy, że algebra B {\displaystyle \mathbb {B} } jest κ {\displaystyle \kappa } -zupełna, jeśli każdy zbiór A B {\displaystyle A\subseteq B} mocy mniejszej niż κ {\displaystyle \kappa } ma kres górny (tzn. A {\displaystyle \bigcup A} istnieje ilekroć 0 < | A | < κ {\displaystyle 0<|A|<\kappa } ). Równoważnie: algebra B {\displaystyle \mathbb {B} } jest κ {\displaystyle \kappa } -zupełna wtedy i tylko wtedy, gdy każdy zbiór A B , {\displaystyle A\subseteq B,} o mocy mniejszej niż κ , {\displaystyle \kappa ,} ma kres dolny (tzn. A {\displaystyle \bigcap A} ). Algebry 1 {\displaystyle \aleph _{1}} -zupełne są też nazywane algebrami σ {\displaystyle \sigma } -zupełnymi.

Jeśli B {\displaystyle {\mathcal {B}}} jest σ {\displaystyle \sigma } -ciałem borelowskich podzbiorów prostej rzeczywistej (a więc jest to σ {\displaystyle \sigma } -zupełna algebra Boole’a) oraz K , {\displaystyle {\mathcal {K}},} jest rodziną wszystkich zbiorów A B , {\displaystyle A\in {\mathcal {B}},} które są pierwszej kategorii, to K {\displaystyle {\mathcal {K}}} jest ideałem w algebrze B {\displaystyle {\mathcal {B}}} i algebra ilorazowa B / K {\displaystyle {\mathcal {B}}/{\mathcal {K}}} jest zupełna. Podobnie dla rodziny L {\displaystyle {\mathcal {L}}} wszystkich borelowskich zbiorów miary zero.

Zbiory niezależne | edytuj kod

Podzbiór X {\displaystyle X} algebry Boole’a B {\displaystyle \mathbb {B} } nazywany jest niezależnym, gdy dla dowolnych zbiorów skończonych { x 1 , , x n } , { y 1 , , y m } X {\displaystyle \{x_{1},\dots ,x_{n}\},\{y_{1},\dots ,y_{m}\}\subseteq X}

x 1 x 2 x n ( y 1 ) ( y 2 ) + ( y m ) = 0. {\displaystyle x_{1}\cap x_{2}\cap \ldots \cap x_{n}\cap (\sim y_{1})\cap (\sim y_{2})\cap \ldots +(\sim y_{m})=0.}

Do klasycznych twierdzeń dotyczących zbiorów niezależnych w algebrach Boole’a należą:

Funkcje kardynalne | edytuj kod

W badaniach i opisach algebr Boole’a często używa się funkcji kardynalnych. Przykładami takich funkcji kardynalnych są następujące funkcje.

  • Celularność c ( B ) {\displaystyle c(\mathbb {B} )} algebry Boole’a B {\displaystyle \mathbb {B} } jest to supremum mocy antyłańcuchów w B . {\displaystyle \mathbb {B} .}
  • Długość l e n g t h ( B ) {\displaystyle \mathrm {length} (\mathbb {B} )} algebry Boole’a B {\displaystyle \mathbb {B} } to
l e n g t h ( B ) = sup { | A | : A B {\displaystyle \mathrm {length} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} } jest łańcuchem } {\displaystyle {\big \}}}
  • Głębokość d e p t h ( B ) {\displaystyle \mathrm {depth} (\mathbb {B} )} algebry Boole’a B {\displaystyle \mathbb {B} } to
d e p t h ( B ) = sup { | A | : A B {\displaystyle \mathrm {depth} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} } jest dobrze uporządkowanym łańcuchem } . {\displaystyle {\big \}}.}
  • Nieporównywalność I n c ( B ) {\displaystyle \mathrm {Inc} (\mathbb {B} )} algebry Boole’a B {\displaystyle \mathbb {B} } to
I n c ( B ) = sup { | A | : A B {\displaystyle \mathrm {Inc} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} } oraz ( a , b A ) ( a b   ¬ ( a b     b a ) ) } . {\displaystyle {\big (}\forall a,b\in A{\big )}{\big (}a\neq b\ \Rightarrow \neg (a\leqslant b\ \vee \ b\leqslant a){\big )}{\big \}}.}
  • Pseudo-ciężar π ( B ) {\displaystyle \pi (\mathbb {B} )} algebry Boole’a B {\displaystyle \mathbb {B} } to
π ( B ) = min { | A | : A B { 0 } {\displaystyle \pi (\mathbb {B} )=\min {\big \{}|A|:A\subseteq \mathbb {B} \setminus \{0\}} oraz ( b B { 0 } ) ( a A ) ( a b ) } . {\displaystyle {\big (}\forall b\in B\setminus \{0\}{\big )}{\big (}\exists a\in A{\big )}{\big (}a\leqslant b{\big )}{\big \}}.}

Reprezentacja | edytuj kod

Twierdzenie Stone’a o reprezentacji algebr Boole’a mówi, że każda algebra Boole’a jest izomorficzna z pewnym ciałem zbiorów (traktowanym jako algebra Boole’a). Dokładniej mówiąc, algebra Boole’a B {\displaystyle \mathbb {B} } jest izomorficzna z ciałem otwarto-domkniętych podzbiorów przestrzeni ultrafiltrów na B , {\displaystyle \mathbb {B} ,} tzw. przestrzeni Stone’a algebry B . {\displaystyle \mathbb {B} .} Twierdzenie Stone’a nie może być udowodnione przy użyciu tylko aksjomatyki Zermela-Fraenkla – wymaga ono założenia pewnej formy aksjomatu wyboru (rozszerzalności ideałów w algebrach Boole’a do ideałów pierwszych).

Każda skończona algebra Boole’a jest izomorficzna z całym zbiorem potęgowym ( P ( X ) , , , , , X ) {\displaystyle (P(X),\cup ,\cap ,{}',\varnothing ,X)} dla pewnego X . {\displaystyle X.}

Historia | edytuj kod

Nazwa „algebra Boole’a” pochodzi od nazwiska George’a Boole’a (1815–1864), angielskiego matematyka samouka. Wprowadził on algebraiczne ujęcie logiki matematycznej w niewielkiej pracy The Mathematical Analysis of Logic (Matematyczna analiza logiki), opublikowanej w 1847 roku. W późniejszej książce The Laws of Thought (Prawa myśli), opublikowanej w 1854, Boole formułuje problem w bardziej dojrzały sposób, zauważając dualność operacji ∪ i ∩. Dalszy rozwój algebra Boole’a zawdzięcza Williamowi Jevonsowi i Charlesowi Peirce’owi, których prace opublikowane zostały w latach sześćdziesiątych XIX wieku. W 1890 w Vorlesungen (Wykłady) Ernsta Schrödera pojawia się pierwszy systematyczny wykład algebry Boole’a i krat rozdzielnych. Dokładniejsze badania algebr Boole’a podjął Alfred North Whitehead w wydanym w 1898 roku dziele Universal Algebra (Algebra ogólna). Algebra Boole’a jako aksjomatyczna struktura algebraiczna pojawiła się w 1904 roku w pracach Huntingtona. Garrett Birkhoff w Lattice Theory (1940) rozwinął teorię krat. W latach sześćdziesiątych Paul Cohen, Dana Scott i inni osiągnęli głębokie rezultaty w dziedzinie logiki matematycznej i aksjomatycznej teorii zbiorów, korzystając z metody forsingu osadzonej w teorii algebr Boole’a.

Pierścienie Boole’a | edytuj kod

Z pojęciem algebry Boole’a związane jest pojęcie pierścienia Boole’a. Pierścień Boole’a to pierścień przemienny z jedynką ( P , , , 0 , 1 ) , {\displaystyle (P,\oplus ,\odot ,0,1),} w którym mnożenie spełnia warunek

a a = a {\displaystyle a\odot a=a} dla każdego elementu a . {\displaystyle a.}

W pierścieniu Boole’a każdy element jest rzędu 2, to znaczy spełnia równość: a a = 0 {\displaystyle a\oplus a=0} Dowód:

a a a a = ( a a ) ( a a ) ( a a ) ( a a ) = ( a a ) ( a a ) = a a {\displaystyle a\oplus a\oplus a\oplus a=(a\odot a)\oplus (a\odot a)\oplus (a\odot a)\oplus (a\odot a)=(a\oplus a)\odot (a\oplus a)=a\oplus a}

więc a a = 0. {\displaystyle a\oplus a=0.}

Wynika stąd, że:

a ( 1 a ) = 0 {\displaystyle a\odot (1\oplus a)=0} oraz a ( 1 a ) = 1. {\displaystyle a\oplus (1\oplus a)=1.}

Niech B = ( B , , , , 0 , 1 ) {\displaystyle \mathbb {B} =(B,\cup ,\cap ,\sim ,0,1)} będzie algebrą Boole’a. Jeżeli w zbiorze B {\displaystyle B} określi się operację alternatywy wykluczającej (różnicy symetrycznej) {\displaystyle \oplus } przez

a b = ( a ( b ) ) ( b ( a ) ) , {\displaystyle a\oplus b=(a\cap (\sim b))\cup (b\cap (\sim a)),}

to ( B , , , 0 , 1 ) {\displaystyle (B,\oplus ,\cap ,0,1)} będzie pierścieniem Boole’a; za mnożenie {\displaystyle \odot } przyjmuje się . {\displaystyle \cap .}

I na odwrot – niech ( B , , , 0 , 1 ) {\displaystyle (B,\oplus ,\odot ,0,1)} będzie pierścieniem Boole’a. Jeżeli zdefiniuje się operacje , {\displaystyle \cup ,\cap } i {\displaystyle \sim } na B {\displaystyle B} przez

a b = ( a b ) ( a b ) , {\displaystyle a\cup b=(a\oplus b)\oplus (a\odot b),} a b = a b {\displaystyle a\cap b=a\odot b} i a = 1 a , {\displaystyle \sim a=1\oplus a,}

to B := ( B , , , , 0 , 1 ) {\displaystyle \mathbb {B} :=(B,\cup ,\cap ,\sim ,0,1)} będzie algebrą Boole’a spełniającą

a b = ( a ( b ) ) ( b ( a ) ) . {\displaystyle a\oplus b=(a\cap (\sim b))\cup (b\cap (\sim a)).}

Dalsze struktury związane z algebrami Boole’a | edytuj kod

Uogólnieniem algebr Boole’a są algebry pseudoboolowskie, zwane też algebrami Heytinga, w których z aksjomatów usunięte jest prawo wyłączonego środka a a = 1. {\displaystyle a\;\cup \sim a=1.}

Rozpatrywane są też algebry Boole’a z dodatkowymi strukturami. Należą do nich:

Zobacz też | edytuj kod

Bibliografia | edytuj kod

Linki zewnętrzne | edytuj kod

Kontrola autorytatywna (dziedzina matematyki):
Na podstawie artykułu: "Algebra Boole’a" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy