Algebra Boole’a

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.

Definicja

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

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

Oznaczenia

Różne oznaczenia

Suma	Iloczyn	Negacja
$\cup$	$\cap$	$\sim$
$+$	$\cdot$	${\overline {a}}$
$+$	$\cdot$	$-$
$\lor$	$\land$	$\lnot$
$|$	$\&$	$!$
$OR$	$AND$	$NOT$

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

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ń $(+,\cdot ,-)$.^{[potrzebny przypis]} Ten sam system został też wybrany za wiodący przez redaktorów monografii Handbook of Boolean Algebras.

Z kolei symbole $\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 $\cap$, lub $a^{\prime }$ zamiast $\;\sim a$). W elektronice i informatyce często stosuje się OR, AND oraz NOT w miejsce $\cup$, $\cap$ oraz $\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 $\sim (x\cup (\sim x))$ a 1 przez $(x\cup (\sim x))$. Dzięki prawom de Morgana można też z aksjomatyki wyeliminować działanie $\cap$ lub $\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:

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

Inny taki układ to:

• $\cup \;$ jest przemienne
• $\cup \;$ jest łączne
• aksjomat Robbinsa: $\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ń:

$\cdot$ 0 1 0 0 0 1 0 1

$+$ 0 1 0 0 1 1 1 1

a $\sim$ a 0 1 1 0

Algebra ta stanowi podstawę elektroniki cyfrowej.

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

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

$\varphi \equiv \psi$ wtedy i tylko wtedy, gdy$\varphi \Leftrightarrow \psi$ jest tautologią rachunku zdań.

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

$[\varphi ]\cup [\psi ]:=[\varphi \vee \psi ]$,

$[\varphi ]\cap [\psi ]:=[\varphi \wedge \psi ]$,

$\sim [\varphi ]:=[\neg \varphi ]$.

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

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

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

$[\varphi ]\cup [\psi ]:=[\varphi \vee \psi ]$,

$[\varphi ]\cap [\psi ]:=[\varphi \wedge \psi ]$,

$\sim [\varphi ]:=[\neg \varphi ]$.

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

Własności

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

$a\cup a=a\$

$a\cap a=a\$

$a\cup 0=a\$

$a\cap 1=a\$

$a\cup 1=1\$

$a\cap 0=0\$

$\sim 0=1\$

$\sim 1=0\$

prawa De Morgana:

$\sim (a\cup b)=(\sim a)\cap (\sim b)\$

$\sim (a\cap b)=(\sim a)\cup (\sim b)\$

podwójne przeczenie:

$\sim (\sim a)=a\$

Uporządkowanie

W zbiorze $B\;$ wprowadza się porządek boole'owski $\leqslant$:

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

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

Ideały, algebry ilorazowe i homomorfizmy

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

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

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

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

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

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

oraz

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

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

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

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

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

$[a]\vee [b]:=[a\cup b]$,

$[a]\wedge [b]:=[a\cap b]$,

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

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

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

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

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

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

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

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

Autodualność

Niech ${\mathbb {C} }=(B,\cap ,\cup ,\sim ,1,0)$ (operacje $\cup$ i $\cap$ zostały zamienione rolami, podobnie jak stałe 0 i 1). Wtedy także $\mathbb {C}$ jest algebrą Boole’a izomorficzną z wyjściową algebrą $\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):=\;\sim x$

dla dowolnego $x\in B$.

Algebry wolne

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

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

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

Skończona algebra Boole’a jest wolna wtedy i tylko wtedy, gdy ma ona $2^{2^{n}}\;$ elementów (dla $n=0,1,2,\ldots$). Algebra mocy $2^{2^{n}}\;$ jest izomorficzna z ciałem wszystkich podzbiorów zbioru z $2^{n}\;$ elementami i jako taka ma $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: $(\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 $A\subseteq B$ można rozpatrywać jego kresy (które istnieją lub nie).

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

Dla zbioru pustego:

$\bigcup \varnothing =0$ oraz $\bigcap \varnothing =1$.

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

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

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

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

$(\forall a\in A)(a\leqslant b)$ oraz

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

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

$(\forall a\in A)(b\leqslant a)$ oraz

${\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 ${\mathbb {B} }$:

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

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

Zbiory niezależne

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

$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 Fichtenholza-Kantorowicza
• twierdzenie Balcara-Franka.

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

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

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

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

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

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

$\pi ({\mathbb {B} })=\min {\big \{}|A|:A\subseteq {\mathbb {B} }\setminus \{0\}$ oraz ${\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 ${\mathbb {B} }$ jest izomorficzna z ciałem otwarto-domkniętych podzbiorów przestrzeni ultrafiltrów na ${\mathbb {B} }$, tzw. przestrzeni Stone’a algebry ${\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),\cup ,\cap ,{}^{\prime },\varnothing ,X)$ dla pewnego $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ą $(P,\oplus ,\odot ,0,1)$, w którym mnożenie spełnia warunek

$a\odot a=a$ dla każdego elementu $a\;$.

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

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

Wynika stąd, że:

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

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

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

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

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

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

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

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

Zobacz też

• funkcja boolowska
• monadyczna algebra Boole’a

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. ISBN 0-8218-0528-2.Nieznane pola: "series".
• 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. ISBN 3-7643-5402-X.Nieznane pola: "series".
• 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 Grenzgebieterok. Neue Folge. Band 25, 1969 (wyd. 1 – 1960).

Linki zewnętrzne

• J. Donald Monk: The Mathematics of Boolean Algebra (ang.). Stanford Encyclopedia of Philosophy, 2014. [dostęp 2017-12-30].

en:Boolean algebra (structure) fr:Algèbre de Boole (structure) ko:불 대수 he:אלגברה בוליאנית (מבנה אלגברי) zh:布尔代数

This article "Algebra Boole’a" is from Wikipedia. The list of its authors can be seen in its historical.

📰 Article(s) of the same category(ies)

• Forma zdaniowa sprzeczna
• Obliczalność zbioru twierdzeń

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• Algebra Boole’a in English