Tekst źródłowy strony Algebra Boole’a

[[Plik:Hasse diagram of powerset of 3.svg|mały|[[Diagram Hassego]] dla algebry Boole’a podzbiorów zbioru trójelementowego]]
[[Plik:Boolean logic.svg|mały|[[Diagram Venna|Diagramy Venna]] dla operatorów algebry Boole’a]]

'''Algebra Boole’a''' – typ [[Struktura matematyczna|struktury algebraicznej]], rodzaj [[algebra ogólna|algebry ogólnej]] definiowany [[aksjomat]]ami. Uogólniają one właściwości typowych przykładów takich struktur z [[Logika matematyczna|logiki matematycznej]] i [[Teoria mnogości|teorii mnogości]] jak<ref name="epwn" />:
* dwuelementowa algebra [[Wartość logiczna|wartości logicznych]] {0, 1} z działaniami [[koniunkcja (logika)|koniunkcji]], [[alternatywa|alternatywy]] i [[negacja|negacji]];
* [[Rodzina zbiorów|rodzina]] wszystkich [[Podzbiór|podzbiorów]] ustalonego [[Zbiór|zbioru]] ([[zbiór potęgowy]]) wraz z działaniami na zbiorach jako operacjami algebry.

Teoria algebr Boole’a to dział [[Matematyka|matematyki]] z pogranicza [[Algebra abstrakcyjna|algebry abstrakcyjnej]], [[Teoria porządku|teorii porządku]] i [[Logika|logiki]]. Jest stosowana w różnych działach matematyki jak [[topologia]], w [[Informatyka (teoretyczna)|informatyce teoretycznej]] i [[Elektronika cyfrowa|elektronice cyfrowej]]{{fakt|data=2024-03}}. Nazwa pochodzi od nazwiska [[George Boole|George’a Boole’a]]<ref name=":0">{{Cytuj |tytuł = Słownik terminologiczny informacji naukowej |data = 1979 |inni = Maria Dembowska (red. nacz.) |miejsce = Wrocław–Warszawa–Kraków–Gdańsk |wydawca = Zakład Narodowy imienia Ossolińskich |s = 24}}</ref>.

== Definicja ==
'''Algebra Boole’a''' – struktura algebraiczna <math>\mathbb B := (B,\cup,\cap,\sim,0,1),</math> w której:
* <math>\cup</math> i <math>\cap</math> są [[Działanie dwuargumentowe|działaniami dwuargumentowymi]],
* <math>\sim</math> jest operacją jednoargumentową,
* 0 i 1 są wyróżnionymi różnymi elementami zbioru <math>B,</math>
* dla wszystkich <math>a,b,c\in B</math> spełnione są następujące warunki<ref name="epwn">{{Encyklopedia PWN | tytuł = Algebra Boole’a | id = 3879484 | data dostępu = 2023-03-26 }}</ref>:
: {| cellpadding=5
|1.
| <math>a \cup (b \cup c) = (a \cup b) \cup c</math>
| <math>a \cap (b \cap c) = (a \cap b) \cap c</math>
| [[łączność (matematyka)|łączność]]
|-
|2.
| <math>a \cup b = b \cup a</math>
| <math>a \cap b = b \cap a</math>
| [[przemienność]]
|-
|3.
| <math>a \cup (a \cap b) = a</math>
| <math>a \cap (a \cup b) = a</math>
| absorpcja
|-
|4.
| <math>a \cup (b \cap c) = (a \cup b) \cap (a \cup c)</math>
| <math>a \cap (b \cup c) = (a \cap b) \cup (a \cap c)</math>
| [[rozdzielność]]
|-
|5.
| <math>a\; \cup \sim a = 1</math>
| <math>a\; \cap \sim a = 0</math>
| pochłanianie
|}

=== Oznaczenia ===
{| class="wikitable" style="float:right;"
|+ Różne oznaczenia
! Suma
! Iloczyn
! Negacja
|-
| <math>\cup</math>
| <math>\cap</math>
| <math>\sim</math>
|-
| <math>+</math>
| <math>\cdot</math>
| <math>\overline{a}</math>
|-
| <math>+</math>
| <math>\cdot</math>
| <math>-</math>
|-
| <math>\lor</math>
| <math>\land</math>
| <math>\lnot</math>
|-
| <math>|</math>
| <math>\&</math>
| <math>!</math>
|-
| <math>OR</math>
| <math>AND</math>
| <math>NOT</math>
|}

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

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

W badaniach [[teoria mnogości|teoriomnogościowych]] aspektów algebr Boole’a przeważa tradycja używania oznaczeń <math>(+,\cdot,-)</math>{{fakt|data=2015-12}}. Ten sam system został też wybrany za wiodący przez redaktorów [[monografia|monografii]] ''Handbook of Boolean Algebras''.

Z kolei symbole <math>\wedge,\vee</math> zgodne z oznaczeniami w teorii [[Krata (matematyka)|krat]] są częściej używane w kontekstach algebraicznych (i teoriokratowych){{fakt|data=2015-12}}.

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

=== Minimalna aksjomatyzacja ===
Powyższa (tradycyjna) definicja algebry Boole’a nie jest minimalna, np.{{fakt|data=2024-03}}:
* 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 <math>\sim (x \cup (\sim x))</math> a 1 przez <math>(x \cup (\sim x));</math>
* dzięki [[Prawa De Morgana|prawom de Morgana]] można też z aksjomatyki wyeliminować działanie <math>\cap</math> lub <math>\cup;</math>
* wszystkie działania można tak naprawdę zastąpić jednym – [[Dysjunkcja (Sheffera)|dysjunkcją]] (NAND) lub [[binegacja|binegacją]] (NOR).

Istnieją równoważne, ale oszczędniejsze definicje algebry Boole’a. Przykładowy układ niezależnych aksjomatów to:
* <math>\cup</math> jest przemienne
* <math>\cup</math> jest łączne
* [[aksjomat Huntingtona]]: <math>\sim(\sim x \cup y)\; \cup \sim (\sim x\; \cup \sim y) = x.</math>

Inny taki układ to:
* <math>\cup</math> jest przemienne
* <math>\cup</math> jest łączne
* [[aksjomat Robbinsa]]: <math>\sim(\sim(x \cup y)\; \cup \sim(x\; \cup \sim y)) = x</math>

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ń:
{|
|-
| width="70"|
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! <math>\cdot</math> || 0 || 1
|-
! 0
| 0 || 0
|-
! 1
| 0 || 1
|}
|
| width="30"|
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! <math>+</math> || 0 || 1
|-
! 0
| 0 || 1
|-
! 1
| 1 || 1
|}
|
| width="40"|
|
{| border="1" cellpadding="4" cellspacing="0"
|-
! a || <math>\sim</math> a
|-
! 0
| 1
|-
! 1
| 0
|}
|}

Algebra ta stanowi podstawę [[Elektronika cyfrowa|elektroniki cyfrowej]].

Jeśli <math>\mathcal F</math> jest [[Ciało zbiorów|ciałem podzbiorów]] zbioru <math>X,</math> to <math>(\mathcal F,\cup,\cap,{}',\varnothing,X)</math> jest algebrą Boole’a (gdzie <math>{}'</math> oznacza operację [[Dopełnienie zbioru|dopełnienia]]).

Niech <math>\mathcal Z</math> będzie zbiorem [[Zdanie logiczne|zdań]] w [[Rachunek zdań|rachunku zdań]]. Niech <math>\equiv</math> będzie [[Relacja dwuargumentowa|relacją dwuargumentową]] na zbiorze <math>\mathcal Z</math> określoną jako:
: <math>\varphi\equiv\psi</math> wtedy i tylko wtedy, gdy <math>\varphi\Leftrightarrow\psi</math> jest [[Tautologia (logika)|tautologią]] rachunku zdań.

Można sprawdzić, że <math>\equiv</math> jest [[relacja równoważności|relacją równoważności]] na zbiorze <math>\mathcal Z.</math> Na zbiorze <math>X</math> wszystkich [[Relacja równoważności|klas abstrakcji]] <math>[\varphi]</math> relacji <math>\equiv</math> można wprowadzić operacje <math>\cup,\cap,\sim</math> przez następujące formuły:
: <math>[\varphi] \cup [\psi] := [\varphi\vee\psi],</math>
: <math>[\varphi] \cap [\psi] := [\varphi\wedge\psi],</math>
: <math>\sim[\varphi] := [\neg\varphi].</math>

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

Algebry Lindenbauma-Tarskiego rozważa się również dla [[Rachunek predykatów pierwszego rzędu|języków pierwszego rzędu]]. Niech <math>\mathbf Z</math> będzie zbiorem [[Zdanie logiczne#Zdania w logice pierwszego rzędu|zdań]] w ustalonym alfabecie <math>\tau</math> i niech <math>T\subseteq \mathbf Z</math> będzie niesprzeczną teorią w tym samym języku. Relację dwuargumentową <math>\equiv</math> na zbiorze <math>\mathbf Z</math> można wprowadzić przez określenie
: <math>\varphi\equiv\psi</math> wtedy i tylko wtedy, gdy <math>T\vdash\varphi\Leftrightarrow\psi.</math>

Wówczas <math>\equiv</math> jest relacją równoważności na zbiorze <math>\mathbf Z.</math> Podobnie jak wcześniej:
: <math>[\varphi] \cup [\psi] := [\varphi\vee\psi],</math>
: <math>[\varphi] \cap [\psi] := [\varphi\wedge\psi],</math>
: <math>\sim[\varphi] := [\neg\varphi].</math>

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

== Własności ==
Niech <math>\mathbb B = (B,\cup,\cap,\sim,0,1)</math> będzie algebrą Boole’a. Dla wszystkich <math>a,b\in B</math> zachodzi:
: <math>a \cup a = a</math>
: <math>a \cap a = a</math>
: <math>a \cup 0 = a</math>
: <math>a \cap 1 = a</math>
:
: <math>a \cup 1 = 1</math>
: <math>a \cap 0 = 0</math>
:
: <math>\sim 0 = 1</math>
: <math>\sim 1 = 0</math>

[[prawa De Morgana]]:
: <math>\sim (a \cup b) = (\sim a) \cap (\sim b)</math>
: <math>\sim (a \cap b) = (\sim a) \cup (\sim b)</math>

[[Prawo podwójnej negacji|podwójne przeczenie]]:
: <math>\sim (\sim a) = a</math>

=== Uporządkowanie ===
W zbiorze <math>B</math> wprowadza się '''porządek boole’owski''' <math>\leqslant{:}</math>
: <math>a\leqslant b</math> ''wtedy i tylko wtedy, gdy'' <math>a\cap b=a</math>

Tak zdefiniowana [[relacja (matematyka)|relacja]] <math>\leqslant</math> jest [[Częściowy porządek|częściowym porządkiem]] na zbiorze <math>B.</math> Zbiór <math>B</math> z relacją ≤ jest [[krata rozdzielna|kratą rozdzielną]].

=== Ideały, algebry ilorazowe i homomorfizmy ===
Niepusty zbiór <math>I\subseteq B</math> jest '''[[Ideał (teoria mnogości)|ideałem]] w algebrze <math>\mathbb B</math>''', jeśli są spełnione następujące dwa warunki:
: <math>\big(\forall a,b\in I\big)\big(a \cup b\in I\big),</math> oraz
: <math>\big(\forall a \in B, b\in I\big)\big((a\leqslant b)\ \Rightarrow\ (a\in I)\big).</math>

Każdy ideał zawiera element <math>0.</math> Ideał, który nie zawiera elementu <math>1,</math> nazywany jest '''ideałem właściwym'''. Jedynym niewłaściwym ideałem jest całe <math>B.</math>

Pojęciem dualnym jest pojęcie [[Filtr (matematyka)|filtru]]: niepusty zbiór <math>F\subseteq B</math> jest '''filtrem''' w algebrze <math>\mathbb B,</math> jeśli:
: <math>\big(\forall a,b\in F\big)\big(a\cap b\in F\big)</math>

oraz
: <math>\big(\forall a\in F,b\in B\big)\big((a\leqslant b)\ \Rightarrow\ (b\in F)\big).</math>

Każdy filtr zawiera element <math>1.</math> Filtr, który nie zawiera elementu <math>0,</math> nazywany jest '''filtrem właściwym'''. Jedynym niewłaściwym filtrem jest całe <math>B.</math>

Niech <math>I\subseteq B</math> będzie właściwym ideałem w algebrze <math>\mathbb B.</math> Niech <math>\approx_I</math> będzie relacją dwuczłonową na <math>B</math> taką, że
: <math>a\approx_I b</math> wtedy i tylko wtedy, gdy <math>(a\cap (\sim b)) \cup (b\cap (\sim a)) \in I.</math>

Wówczas <math>\approx_I</math> jest relacją równoważności na <math>B.</math> W zbiorze <math>B/\approx_I</math> klas abstrakcji tej relacji można zdefiniować działania <math>\vee,\wedge,\neg{:}</math>
: <math>[a] \vee [b] := [a\cup b],</math>
: <math>[a] \wedge [b] := [a\cap b],</math>
: <math>\neg [a] := [\sim a].</math>

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

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

Jeśli dodatkowo <math>h</math> jest [[funkcja wzajemnie jednoznaczna|funkcją wzajemnie jednoznaczną]] z <math>B</math> na <math>B^*,</math> to funkcja <math>h</math> zwana jest '''[[izomorfizm]]em''' algebr Boole’a.

Jeśli <math>I</math> jest ideałem w algebrze <math>\mathbb B,</math> to odwzorowanie <math>a\mapsto [a]_{\approx_I}\colon \mathbb B\to \mathbb B/I</math> jest homomorfizmem.

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

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

dla dowolnego <math>x \in B.</math>

=== Algebry wolne ===
Algebra Boole’a <math>\mathbb B</math> jest '''wolna''', jeśli pewien zbiór <math>X\subseteq B</math> ma następującą własność:
: dla każdej algebry Boole’a <math>\mathbb{B}^* := (B^*,\cup^*,\cap^*,\sim^*,0^*,1^*)</math> i każdego odwzorowania <math>f\colon X\to B^*</math> istnieje '''dokładnie jeden''' homomorfizm <math>h\colon B\to B^*</math> z algebry <math>\mathbb B</math> w algebrę <math>\mathbb{B}^*,</math> przedłużający <math>f</math> (czyli taki, że <math>h\upharpoonright X=f</math>).

Zbiór <math>X\subseteq B</math> o własności opisanej powyżej jest nazywany '''zbiorem wolnych generatorów''' algebry <math>\mathbb B.</math> Jeśli [[moc zbioru]] <math>X</math> jest <math>\kappa,</math> to mówimy, że <math>\mathbb B</math> jest '''wolną algebrą Boole’a z <math>\kappa</math> generatorami'''.

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

[[Zbiór przeliczalny|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:
: <math>(\forall b\in B\setminus\{0\})(\exists a\in B\setminus \{0\})(a\leqslant b\ \wedge\ a\neq b)</math>

=== Zupełne algebry Boole’a ===
==== Działania nieskończone ====
Ponieważ w algebrze Boole’a istnieje porządek częściowy, to dla zbioru <math>A\subseteq B</math> można rozpatrywać jego [[Kresy dolny i górny|kresy]] (które istnieją lub nie).

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

Dla zbioru pustego:
: <math>\bigcup \varnothing = 0</math> oraz <math>\bigcap \varnothing = 1.</math>

Zakładając istnienie odpowiednich kresów, zachodzą wzory de Morgana:
: <math>\sim\bigcup A = \bigcap\{\sim a:a\in A\}</math> oraz <math>\sim\bigcap A = \bigcup\{\sim a:a\in A\}.</math>

Ponadto jeśli <math>\varnothing\neq A\subseteq B,</math> to:
* <math>b=\bigcup A</math> wtedy i tylko wtedy, gdy
: <math>(\forall a\in A)(a\leqslant b)</math> oraz
: <math>\big(\forall c\leqslant b\big)\big(c\neq 0\Rightarrow (\exists a\in A)(a\cap c\neq 0)\big),</math>
* <math>b=\bigcap A</math> wtedy i tylko wtedy, gdy
: <math>(\forall a\in A)(b\leqslant a)</math> oraz
: <math>\big(\forall c\neq 0\big)\big(c\cap b=0\Rightarrow (\exists a\in A)(c\cap (\sim a)\neq 0)\big).</math>

==== Zupełność ====
Następujące dwa stwierdzenia są równoważne dla algebry Boole’a <math>\mathbb B{:}</math>
* każdy podzbiór <math>\mathbb B</math> ma kres górny;
* każdy podzbiór <math>\mathbb B</math> ma kres dolny.

Algebry, w których każdy zbiór ma kres górny (tzn. takie dla których porządek boole’owski <math>\leqslant</math> jest [[porządek zupełny|zupełny]]), są nazywane '''zupełnymi algebrami Boole’a'''. Zupełne algebry Boole’a są szczególnie ważne w teorii [[forsing]]u; są one też przykładami [[Krata (matematyka)|krat zupełnych]].

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

Jeśli <math>\mathcal B</math> jest <math>\sigma</math>-[[Przestrzeń mierzalna|ciałem]] [[zbiór borelowski|borelowskich]] podzbiorów [[liczby rzeczywiste|prostej rzeczywistej]] (a więc jest to <math>\sigma</math>-zupełna algebra Boole’a) oraz <math>\mathcal K,</math> jest rodziną wszystkich zbiorów <math>A\in \mathcal B,</math> które są [[zbiór pierwszej kategorii|pierwszej kategorii]], to <math>\mathcal K</math> jest ideałem w algebrze <math>\mathcal B</math> i algebra ilorazowa <math>\mathcal B/\mathcal K</math> jest zupełna. Podobnie dla rodziny <math>\mathcal L</math> wszystkich borelowskich [[Zbiór miary zero|zbiorów miary zero]].

=== Zbiory niezależne ===
Podzbiór <math>X</math> algebry Boole’a <math>\mathbb{B}</math> nazywany jest '''niezależnym''', gdy dla dowolnych zbiorów skończonych <math>\{x_1, \dots, x_n\}, \{y_1,\dots, y_m\}\subseteq X</math>
: <math>x_1\cap x_2\cap \ldots\cap x_n\cap (\sim y_1)\cap (\sim y_2)\cap \ldots+(\sim y_m)=0.</math>

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ę [[funkcja kardynalna|funkcji kardynalnych]]. Przykładami takich funkcji kardynalnych są następujące funkcje.
* '''Celularność''' <math>c(\mathbb B)</math> algebry Boole’a <math>\mathbb B</math> jest to supremum mocy [[antyłańcuch#Antyłańcuchy w algebrach Boole’a|antyłańcuchów]] w <math>\mathbb B.</math>
* '''Długość''' <math>\mathrm{length}(\mathbb B)</math> algebry Boole’a <math>\mathbb B</math> to
: <math>\mathrm{length}(\mathbb B)=\sup\big\{|A|:A\subseteq \mathbb B</math> jest [[łańcuch (teoria mnogości)|łańcuchem]] <math>\big\}</math>
* '''Głębokość''' <math>\mathrm{depth}(\mathbb B)</math> algebry Boole’a <math>\mathbb B</math> to
: <math>\mathrm{depth}(\mathbb B)=\sup\big\{ |A|:A\subseteq \mathbb B</math> jest [[Dobry porządek|dobrze uporządkowanym]] łańcuchem <math>\big\}.</math>
* '''Nieporównywalność''' <math>\mathrm{Inc}(\mathbb B)</math> algebry Boole’a <math>\mathbb B</math> to
: <math>\mathrm{Inc}(\mathbb B)=\sup\big\{ |A|:A\subseteq \mathbb B</math> oraz <math>\big(\forall a,b\in A\big)\big(a\neq b\ \Rightarrow \neg (a\leqslant b\ \vee \ b\leqslant a)\big)\big\}.</math>
* '''Pseudo-ciężar''' <math>\pi(\mathbb B)</math> algebry Boole’a <math>\mathbb B</math> to
: <math>\pi(\mathbb B)=\min\big\{ |A|:A\subseteq \mathbb B\setminus \{0\}</math> oraz <math>\big(\forall b\in B\setminus \{0\}\big)\big(\exists a\in A\big)\big(a\leqslant b\big)\big\}.</math>

== 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 <math>\mathbb B</math> jest izomorficzna z ciałem [[zbiór otwarto-domknięty|otwarto-domkniętych]] podzbiorów przestrzeni [[Filtr (matematyka)|ultrafiltrów]] na <math>\mathbb B,</math> tzw. [[przestrzeń Stone’a|przestrzeni Stone’a]] algebry <math>\mathbb B.</math> Twierdzenie Stone’a nie może być udowodnione przy użyciu tylko [[Aksjomaty Zermela-Fraenkla|aksjomatyki Zermela-Fraenkla]] – wymaga ono założenia pewnej formy [[Aksjomat wyboru|aksjomatu wyboru]] (rozszerzalności ideałów w algebrach Boole’a do [[Ideał pierwszy (teoria pierścieni)|ideałów pierwszych]]).

Każda ''skończona'' algebra Boole’a jest izomorficzna z ''całym'' [[zbiór potęgowy|zbiorem potęgowym]] <math>(P(X), \cup, \cap, {}', \varnothing, X)</math> dla pewnego <math>X.</math>

== Historia ==
=== XIX wiek ===
Nazwa „algebra Boole’a” pochodzi od nazwiska [[George Boole|George’a Boole’a]] (1815–1864), angielskiego matematyka samouka. Wprowadził on algebraiczne ujęcie [[logika matematyczna|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 [[William Stanley Jevons|Williamowi Jevonsowi]] i [[Charles Sanders Peirce|Charlesowi Peirce’owi]], których prace opublikowane zostały w latach sześćdziesiątych XIX wieku. W 1890 w ''Vorlesungen'' (Wykłady) [[Ernst Schröder|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).

=== XX wiek ===
Algebra Boole’a jako aksjomatyczna struktura algebraiczna pojawiła się w 1904 roku w pracach [[Edward Vermilye Huntington|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 [[forsing]]u 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ą <math>(P,\oplus,\odot,0,1),</math> w którym mnożenie spełnia warunek
: <math>a\odot a=a</math> dla każdego elementu <math>a.</math>

W pierścieniu Boole’a każdy element jest rzędu 2, to znaczy spełnia równość: <math>a \oplus a = 0</math> Dowód:
: <math>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</math>

więc <math>a \oplus a = 0.</math>

Wynika stąd, że:
: <math>a \odot (1 \oplus a) = 0</math> oraz <math>a \oplus (1 \oplus a) = 1.</math>

Niech <math>\mathbb B = (B,\cup,\cap,\sim,0,1)</math> będzie algebrą Boole’a. Jeżeli w zbiorze <math>B</math> określi się operację [[Alternatywa rozłączna|alternatywy wykluczającej]] (różnicy symetrycznej) <math>\oplus</math> przez
: <math>a \oplus b = (a\cap (\sim b))\cup(b\cap (\sim a)),</math>

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

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

to <math>\mathbb B := (B,\cup,\cap,\sim,0,1)</math> będzie algebrą Boole’a spełniającą
: <math>a \oplus b = (a\cap (\sim b)) \cup (b\cap (\sim a)).</math>

== Dalsze struktury związane z algebrami Boole’a ==
Uogólnieniem algebr Boole’a są '''algebry pseudoboolowskie''', zwane też [[Algebra Heytinga|algebrami Heytinga]], w których z aksjomatów usunięte jest prawo wyłączonego środka <math>a\; \cup \sim a = 1.</math>

Rozpatrywane są też algebry Boole’a z dodatkowymi strukturami. Należą do nich:
* [[Monadyczna algebra Boole’a|monadyczne algebry Boole’a]] z dodatkowym działaniem jednoargumentowym <math>\exists,</math>
* [[algebra Heytinga#Reprezentacja algebr Heytinga w topologicznych algebrach Boole’a|topologiczne algebry Boole’a]] z dodatkowym operatorem wnętrza.

== Zobacz też ==
* [[funkcja boolowska]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę |nazwisko=Adamowicz |imię=Zofia |autor link=Zofia Adamowicz |nazwisko2=Zbierski |imię2=Paweł |autor link2=Paweł Zbierski |tytuł=Logic of mathematics. A modern course of classical logic |url=https://archive.org/details/logicofmathemati0000adam |seria=Pure and Applied Mathematics |wydawca=A Wiley-Interscience Publication. John Wiley & Sons, Inc. |miejsce=Nowy Jork |rok=1997 |isbn=0-471-06026-7}}
* {{cytuj książkę |nazwisko=Birkhoff |imię=Garrett |autor link=Garrett Birkhoff |nazwisko2=Bartee |imię2=Thomas C. |tytuł=Współczesna algebra stosowana |seria=Matematyka dla Politechnik |wydawca=Państwowe Wydawnictwo Naukowe |miejsce=Warszawa |rok=1983 |isbn=8301045604}}
* {{cytuj książkę |nazwisko=Jech |imię=Thomas |autor link=Thomas Jech |tytuł=Set theory |wydawca=Springer-Verlag |miejsce=Berlin |rok=1997 |isbn= 3-540-63048-1}}
* {{cytuj książkę |nazwisko=Just |imię=Winfried |nazwisko2=Weese |imię2=Martin |tytuł=Discovering modern set theory |tom=2 |tytuł tomu=Set-theoretic tools for every mathematician |seria=Graduate Studies in Mathematics, 18 |wydawca= [[Amerykańskie Towarzystwo Matematyczne|American Mathematical Society]] |miejsce=Providence, RI |rok=1997 |isbn= 0-8218-0528-2}}
* {{cytuj książkę |nazwisko=Koppelberg |imię=Sabine |tytuł=Handbook of Boolean algebras |inni=J. Donald Monk i Robert Bonnet (red.) |tom=1,2,3 |wydawca=North-Holland Publishing Co. |miejsce=Amsterdam |rok= 1989 |isbn=0-444-70261-X}}
* {{cytuj książkę |nazwisko=Kuratowski |imię=Kazimierz |autor link=Kazimierz Kuratowski |nazwisko2=Mostowski |imię2=Andrzej |autor link2=Andrzej Stanisław Mostowski |tytuł=Teoria mnogości: wraz ze wstępem do opisowej teorii mnogości |seria=Monografie Matematyczne 27 |wydanie=3 |wydawca=Państwowe Wydawnictwo Naukowe (PWN) |miejsce=Warszawa |rok=1978}}
* {{cytuj książkę |nazwisko=Monk |imię=J. Donald |autor link=J. Donald Monk |tytuł=Cardinal invariants on Boolean algebras |seria=Progress in Mathematics, 142 |wydawca=Birkhäuser Verlag |miejsce=Basel |rok=1996 |isbn=3-7643-5402-X}}
* {{cytuj książkę |nazwisko=Rasiowa |imię=Helena |autor link=Helena Rasiowa |tytuł=Wstęp do matematyki współczesnej |seria = [[Biblioteka Matematyczna]] t. 30 |wydawca=Państwowe Wydawnictwo Naukowe |miejsce=Warszawa |rok=1973}}
* {{cytuj książkę |nazwisko=Sikorski |imię=Roman |autor link=Roman Sikorski |tytuł=Boolean Algebras (wydanie 3) |wydawca=Springer Verlag; Ergebnisse der Mathematik und ihrer Grenzgebiete. Neue Folge. Band 25 |rok=1969 (wyd. 1 – 1960)}}
* {{cytuj książkę |nazwisko=Rasiowa |imię=Helena |autor link=Helena Rasiowa |nazwisko2=Sikorski |imię2=Roman |autor link2=Roman Sikorski |tytuł=The mathematics of metamathematics |seria=Monografie Matematyczne 41 |wydawca=Państwowe Wydawnictwo Naukowe (PWN) |miejsce=Warszawa |rok=1963}}

== Linki zewnętrzne ==
* {{otwarty dostęp}} Wiktor Bartol, ''[https://www.youtube.com/watch?v=ETNkQeXzeh0 Algebry Boole’a]'', [[Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej]] (MiNI [[Politechnika Warszawska|PW]]), kanał „Archipelag Matematyki” na [[YouTube]], 27 września 2017 [dostęp 2024-09-04].
* {{MathWorld | adres = BooleanAlgebra | tytuł = Boolean Algebra }} [dostęp 2024-03-25].
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/Boolean_algebra Boolean Algebra]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].
* {{SEP | url = boolalg-math/ | tytuł = The Mathematics of Boolean Algebra | autor = J. Donald Monk | data = 2018-07-11 | data dostępu = 2018-08-03 | tytuł polski = (Matematyka algebry Boole’a)}}
* {{paywall}} ''[https://www.rep.routledge.com/articles/thematic/boolean-algebra/v-1 Boolean algebra]'' {{lang|en}}, [[Routledge Encyclopedia of Philosophy]], rep.routledge.com [dostęp 2023-05-10].

{{Struktury algebraiczne}}
{{Teoria porządku}}
{{Algebra zbiorów}}
{{Systemy cyfrowe}}

{{Kontrola autorytatywna}}

[[Kategoria:Algebra przemienna|Boole’a]]
[[Kategoria:Struktury dwóch działań wewnętrznych]]
[[Kategoria:Logika matematyczna]]
[[Kategoria:Rodziny zbiorów]]
[[Kategoria:Byłe Dobre Artykuły]]