Algebra Boole’a

(c) I, KSmrq, CC-BY-SA-3.0

Diagram Hassego dla algebry Boole’a podzbiorów zbioru trójelementowego

Diagramy Vienna dla operatorów algebry Boole’a

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.

Definicja

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

${\displaystyle a\cup (b\cup c)=(a\cup b)\cup c}$	${\displaystyle a\cap (b\cap c)=(a\cap b)\cap c}$	łączność
${\displaystyle a\cup b=b\cup a}$	${\displaystyle a\cap b=b\cap a}$	przemienność
${\displaystyle a\cup (a\cap b)=a}$	${\displaystyle a\cap (a\cup b)=a}$	absorpcja
${\displaystyle a\cup (b\cap c)=(a\cup b)\cap (a\cup c)}$	${\displaystyle a\cap (b\cup c)=(a\cap b)\cup (a\cap c)}$	rozdzielność
${\displaystyle a\;\cup \sim a=1}$	${\displaystyle a\;\cap \sim a=0}$	pochłanianie

Oznaczenia

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 ,-)}$. 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).

Spotykane są też inne kombinacje tychże symboli lub wręcz inne symbole (na przykład & w miejsce ${\displaystyle \cap ,}$ lub ${\displaystyle a'}$ zamiast ${\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

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 ${\displaystyle \sim (x\cup (\sim x))}$ a 1 przez ${\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: ${\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: ${\displaystyle \sim (\sim (x\cup y)\;\cup \sim (x\;\cup \sim y))=x}$

Istnieją też systemy z jednym aksjomatem.

Przykłady

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 ${\displaystyle {\mathcal {F}}}$ jest ciałem podzbiorów zbioru ${\displaystyle X,}$ to ${\displaystyle ({\mathcal {F}},\cup ,\cap ,{}',\varnothing ,X)}$ jest algebrą Boole’a (gdzie ${\displaystyle {}'}$ oznacza operację dopełnienia).

Niech ${\displaystyle {\mathcal {Z}}}$ będzie zbiorem zdań w rachunku zdań. Niech ${\displaystyle \equiv }$ będzie relacją dwuargumentową na zbiorze ${\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 ${\displaystyle {\mathcal {Z}}.}$ Na zbiorze ${\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 ${\displaystyle X}$ (tzn. wynik nie zależy od wyboru reprezentantów klas abstrakcji), a ${\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 ${\displaystyle \mathbf {Z} }$ będzie zbiorem zdań w ustalonym alfabecie ${\displaystyle \tau }$ i niech ${\displaystyle T\subseteq \mathbf {Z} }$ będzie niesprzeczną teorią w tym samym języku. Relację dwuargumentową ${\displaystyle \equiv }$ na zbiorze ${\displaystyle \mathbf {Z} }$ można wprowadzić przez określenie

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

Wówczas ${\displaystyle \equiv }$ jest relacją równoważności na zbiorze ${\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 ${\displaystyle (\mathbf {Z} /\equiv ,\cup ,\cap ,\sim ,[\psi \wedge \neg \psi ]_{\equiv },[\psi \vee \neg \psi ]_{\equiv })}$ jest algebrą Boole’a.

Własności

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

${\displaystyle a\cup a=a}$

${\displaystyle a\cap a=a}$

${\displaystyle a\cup 0=a}$

${\displaystyle a\cap 1=a}$

${\displaystyle a\cup 1=1}$

${\displaystyle a\cap 0=0}$

${\displaystyle \sim 0=1}$

${\displaystyle \sim 1=0}$

prawa De Morgana:

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

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

podwójne przeczenie:

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

Uporządkowanie

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

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

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

Ideały, algebry ilorazowe i homomorfizmy

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

${\displaystyle {\big (}\forall a,b\in I{\big )}{\big (}a\cup b\in I{\big )},}$ oraz

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

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

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

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

oraz

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

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

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

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

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

${\displaystyle [a]\vee [b]:=[a\cup b],}$

${\displaystyle [a]\wedge [b]:=[a\cap b],}$

${\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 ${\displaystyle (B/_{\approx _{I}},\vee ,\wedge ,\neg ,[0],[1])}$ jest algebrą Boole’a. Algebra ta jest nazywana algebrą ilorazową i jest oznaczana przez ${\displaystyle \mathbb {B} /I.}$

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

${\displaystyle h(a\cup b)=h(a)\cup ^{*}\;h(b),}$

${\displaystyle h(a\cap b)=h(a)\cap ^{*}h(b),}$

${\displaystyle h(\sim a)\;=\sim ^{*}h(a).}$

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

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

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

Autodualność

Niech ${\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 ${\displaystyle \mathbb {C} }$ jest algebrą Boole’a izomorficzną z wyjściową algebrą ${\displaystyle \mathbb {B} .}$ Kanoniczny izomorfizm d tych dwóch algebr jest swoją własną odwrotnością (jest inwolucją zbioru B) i jest dany wzorem:

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

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

Algebry wolne

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

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

Zbiór ${\displaystyle X\subseteq B}$ o własności opisanej powyżej jest nazywany zbiorem wolnych generatorów algebry ${\displaystyle \mathbb {B} .}$ Jeśli moc zbioru ${\displaystyle X}$ jest ${\displaystyle \kappa ,}$ to mówimy, że ${\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 ${\displaystyle 2^{2^{n}}}$ elementów (dla ${\displaystyle n=0,1,2,\dots }$). Algebra mocy ${\displaystyle 2^{2^{n}}}$ jest izomorficzna z ciałem wszystkich podzbiorów zbioru z ${\displaystyle 2^{n}}$ elementami i jako taka ma ${\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:

${\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

Działania nieskończone

Ponieważ w algebrze Boole’a istnieje porządek częściowy, to dla zbioru ${\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 ${\displaystyle A}$ (gdy istnieje) jest oznaczany przez ${\displaystyle \bigcup A,}$ a jego kres dolny (gdy istnieje) jest oznaczany przez ${\displaystyle \bigcap A.}$ Jeśli natomiast symbolami dla tych operacji są ${\displaystyle +,\cdot ,}$ to kresy oznaczane są przez ${\displaystyle \sum A,}$ ${\displaystyle \prod A.}$

Dla zbioru pustego:

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

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

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

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

• ${\displaystyle b=\bigcup A}$ wtedy i tylko wtedy, gdy

${\displaystyle (\forall a\in A)(a\leqslant b)}$ oraz

${\displaystyle {\big (}\forall c\leqslant b{\big )}{\big (}c\neq 0\Rightarrow (\exists a\in A)(a\cap c\neq 0){\big )},}$

• ${\displaystyle b=\bigcap A}$ wtedy i tylko wtedy, gdy

${\displaystyle (\forall a\in A)(b\leqslant a)}$ oraz

${\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ść

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

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

Jeśli ${\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 ${\displaystyle {\mathcal {K}},}$ jest rodziną wszystkich zbiorów ${\displaystyle A\in {\mathcal {B}},}$ które są pierwszej kategorii, to ${\displaystyle {\mathcal {K}}}$ jest ideałem w algebrze ${\displaystyle {\mathcal {B}}}$ i algebra ilorazowa ${\displaystyle {\mathcal {B}}/{\mathcal {K}}}$ jest zupełna. Podobnie dla rodziny ${\displaystyle {\mathcal {L}}}$ wszystkich borelowskich zbiorów miary zero.

Zbiory niezależne

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

${\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żą:

• twierdzenie Balcara-Franka.
• twierdzenie Fichtenholza-Kantorowicza

Funkcje kardynalne

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ść ${\displaystyle c(\mathbb {B} )}$ algebry Boole’a ${\displaystyle \mathbb {B} }$ jest to supremum mocy antyłańcuchów w ${\displaystyle \mathbb {B} .}$
• Długość ${\displaystyle \mathrm {length} (\mathbb {B} )}$ algebry Boole’a ${\displaystyle \mathbb {B} }$ to

${\displaystyle \mathrm {length} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} }$ jest łańcuchem ${\displaystyle {\big \}}}$

• Głębokość ${\displaystyle \mathrm {depth} (\mathbb {B} )}$ algebry Boole’a ${\displaystyle \mathbb {B} }$ to

${\displaystyle \mathrm {depth} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} }$ jest dobrze uporządkowanym łańcuchem ${\displaystyle {\big \}}.}$

• Nieporównywalność ${\displaystyle \mathrm {Inc} (\mathbb {B} )}$ algebry Boole’a ${\displaystyle \mathbb {B} }$ to

${\displaystyle \mathrm {Inc} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} }$ oraz ${\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 ${\displaystyle \pi (\mathbb {B} )}$ algebry Boole’a ${\displaystyle \mathbb {B} }$ to

${\displaystyle \pi (\mathbb {B} )=\min {\big \{}|A|:A\subseteq \mathbb {B} \setminus \{0\}}$ oraz ${\displaystyle {\big (}\forall b\in B\setminus \{0\}{\big )}{\big (}\exists a\in A{\big )}{\big (}a\leqslant b{\big )}{\big \}}.}$

Reprezentacja

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 ${\displaystyle \mathbb {B} }$ jest izomorficzna z ciałem otwarto-domkniętych podzbiorów przestrzeni ultrafiltrów na ${\displaystyle \mathbb {B} ,}$ tzw. przestrzeni Stone’a algebry ${\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 ${\displaystyle (P(X),\cup ,\cap ,{}',\varnothing ,X)}$ dla pewnego ${\displaystyle X.}$

Historia

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

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ą ${\displaystyle (P,\oplus ,\odot ,0,1),}$ w którym mnożenie spełnia warunek

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

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

${\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 ${\displaystyle a\oplus a=0.}$

Wynika stąd, że:

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

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

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

to ${\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 ${\displaystyle (B,\oplus ,\odot ,0,1)}$ będzie pierścieniem Boole’a. Jeżeli zdefiniuje się operacje ${\displaystyle \cup ,\cap }$ i ${\displaystyle \sim }$ na ${\displaystyle B}$ przez

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

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

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

Dalsze struktury związane z algebrami Boole’a

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 ${\displaystyle a\;\cup \sim a=1.}$

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

• monadyczne algebry Boole’a z dodatkowym działaniem jednoargumentowym ${\displaystyle \exists ,}$
• topologiczne algebry Boole’a z dodatkowym operatorem wnętrza.

Zobacz też

• funkcja boolowska

Przypisy

Bibliografia

• Zofia Adamowicz, Paweł Zbierski: Logic of mathematics. A modern course of classical logic. Nowy Jork: A Wiley-Interscience Publication. John Wiley & Sons, Inc., 1997, seria: Pure and Applied Mathematics. ISBN 0-471-06026-7.
• Garrett Birkhoff, Thomas C. Bartee: Współczesna algebra stosowana. Warszawa: Państwowe Wydawnictwo Naukowe, 1983, seria: Matematyka dla Politechnik. ISBN 83-01-04560-4.
• Thomas Jech: Set theory. Berlin: Springer-Verlag, 1997. ISBN 3-540-63048-1.
• Winfried Just, Martin Weese: Discovering modern set theory. T. 2: Set-theoretic tools for every mathematician. Providence, RI: American Mathematical Society, 1997, seria: Graduate Studies in Mathematics, 18. ISBN 0-8218-0528-2.
• Sabine Koppelberg: Handbook of Boolean algebras. J. Donald Monk i Robert Bonnet (red.). T. 1,2,3. Amsterdam: North-Holland Publishing Co., 1989. ISBN 0-444-70261-X.
• Kazimierz Kuratowski, Andrzej Mostowski: Teoria mnogości: wraz ze wstępem do opisowej teorii mnogości. Wyd. 3. Warszawa: Państwowe Wydawnictwo Naukowe (PWN), 1978, seria: Monografie Matematyczne 27.
• J. Donald Monk: Cardinal invariants on Boolean algebras. Basel: Birkhäuser Verlag, 1996, seria: Progress in Mathematics, 142. ISBN 3-7643-5402-X.
• Helena Rasiowa: Wstęp do matematyki współczesnej. Warszawa: Państwowe Wydawnictwo Naukowe, 1973, seria: Biblioteka Matematyczna t. 30.
• Roman Sikorski: Boolean Algebras (wydanie 3). Springer Verlag; Ergebnisse der Mathematik und ihrer Grenzgebiete. Neue Folge. Band 25, 1969 (wyd. 1 – 1960).
• Helena Rasiowa, Roman Sikorski: The mathematics of metamathematics. Warszawa: Państwowe Wydawnictwo Naukowe (PWN), 1963, seria: Monografie Matematyczne 41.

Linki zewnętrzne

• J. DonaldJ.D. Monk J. DonaldJ.D., The Mathematics of Boolean Algebra, [w:] Stanford Encyclopedia of Philosophy [online], CSLI, Stanford University, 11 lipca 2018, ISSN 1095-5054 [dostęp 2018-08-03]  (ang.). (Matematyka algebry Boole’a)