Algebra Boole’a

Algebra Boole’a

Algebra Boole’a to rodzaj struktury algebraicznej, definiowanej za pomocą aksjomatów. Te aksjomaty uogólniają cechy typowych przykładów takich struktur, które występują w logice matematycznej oraz teorii mnogości, takich jak:

• dwuelementowa algebra wartości logicznych {0, 1} z operacjami koniunkcji, alternatywy i negacji;
• zbiór wszystkich podzbiorów ustalonego zbioru (zbiór potęgowy) z operacjami na zbiorach jako działaniami algebry.

Teoria algebr Boole’a stanowi dziedzinę matematyki na pograniczu algebry abstrakcyjnej, teorii porządku oraz logiki. Jest szeroko stosowana w takich dziedzinach jak topologia, informatyka teoretyczna i elektronika cyfrowa. Nazwa tej teorii pochodzi od nazwiska George’a Boole’a.

Definicja

Algebra Boole’a to struktura algebraiczna:

B := (B, ∪, ∩, ∼, 0, 1),

w której:

• ∪ i ∩ są operacjami dwuargumentowymi,
• ∼ jest operacją jednoargumentową,
• 0 i 1 to wyróżnione różne elementy zbioru B,

dla wszystkich a, b, c ∈ B spełnione są następujące warunki:

Oznaczenia

W teorii algebr Boole’a istnieją co najmniej trzy różne tradycje oznaczania. W definicji przedstawionej powyżej użyto symboli ∪, ∩, ∼, jednak w praktyce często spotykane są także symbole +, ⋅, − oraz ∨, ∧, ¬. Operacje dwuargumentowe w algebrze Boole’a są zazwyczaj wprowadzane przez wybór jednej z par ( +, ⋅ ), ( ∨, ∧ ) lub ( ∪, ∩ ).

W oznaczeniach dla operacji jednoargumentowej występuje mniejsza różnorodność, można spotkać zarówno symbole +, ⋅, ∼, jak i ∨, ∧, ′.

System oznaczeń przedstawiony powyżej (i przyjęty w tym artykule) znajduje zastosowanie, między innymi, w podręczniku Heleny Rasiowej.

W kontekście teorii algebr Boole’a przeważa tradycja używania oznaczeń (+, ⋅, −). Ten sam system oznaczeń został uznany za wiodący w monografii „Handbook of Boolean Algebras”. Z kolei symbole ∧, ∨ są częściej używane w kontekstach algebraicznych.

W elektronice i informatyce często stosuje się terminy OR, AND oraz NOT zamiast ∪, ∩ i ∼. W języku C oraz w innych podobnych językach używa się symboli: |, &, !.

Minimalna aksjomatyzacja

Powyższa definicja algebry Boole’a nie jest minimalna; na przykład:

• Nie jest konieczne wprowadzenie symboli 0 i 1, mogą one wynikać z aksjomatów, a nie być niezbędne dla definicji. 0 można zastąpić przez ∼(x ∪ (∼x)), a 1 przez (x ∪ (∼x));
• Dzięki prawom de Morgana można również wyeliminować działanie ∩ lub ∪; wszystkie operacje można tak naprawdę zastąpić jednym – dysjunkcją (NAND) lub binegacją (NOR).

Istnieją oszczędniejsze definicje algebry Boole’a. Przykładowy zestaw aksjomatów to:

• ∪ jest przemienne,
• ∪ jest łączne,
• aksjomat Huntingtona: ∼(∼x ∪ y) ∪ ∼(∼x ∪ ∼y) = x.

Inny taki zestaw to:

• ∪ jest przemienne,
• ∪ jest łączne,
• aksjomat Robbinsa: ∼(∼(x ∪ y) ∪ ∼(x ∪ ∼y)) = x.

Istnieją także systemy z jednym aksjomatem.

Przykłady

Najprostsza algebra Boole’a składa się jedynie z dwóch elementów: 0 i 1. Operacje tej algebry definiuje się za pomocą następujących tabel działań:

Algebra ta stanowi fundament elektroniki cyfrowej.

Jeśli F jest ciałem podzbiorów zbioru X, to (F, ∪, ∩, ′, ∅, X) jest algebrą Boole’a (gdzie ′ oznacza operację dopełnienia).

Niech Z będzie zbiorem zdań w rachunku zdań. Niech ≡ będzie relacją dwuargumentową na zbiorze Z określoną jako:

φ ≡ ψ wtedy i tylko wtedy, gdy φ ⇔ ψ jest tautologią rachunku zdań.

Można wykazać, że ≡ jest relacją równoważności na zbiorze Z.

Na zbiorze X wszystkich klas abstrakcji [φ] relacji ≡ można wprowadzić operacje ∪, ∩, ∼ przez następujące formuły:

• [φ] ∪ [ψ] := [φ ∨ ψ],
• [φ] ∩ [ψ] := [φ ∧ ψ],
• ∼[φ] := [¬φ].

W ten sposób uzyskuje się poprawnie zdefiniowane operacje na zbiorze X, a (X, ∪, ∩, ∼, [p ∧ ¬p], [p ∨ ¬p]) jest algebrą Boole’a. Algebra ta nosi nazwę algebry Lindenbauma-Tarskiego.

Algebry Lindenbauma-Tarskiego rozważane są również dla języków pierwszego rzędu. Niech Z będzie zbiorem zdań w ustalonym alfabecie τ i niech T ⊆ Z będzie niesprzeczną teorią w tym samym języku. Relację dwuargumentową ≡ na zbiorze Z można wprowadzić przez określenie φ ≡ ψ wtedy i tylko wtedy, gdy T ⊢ φ ⇔ ψ.

Wówczas ≡ jest relacją równoważności na zbiorze Z. Podobnie jak wcześniej, można wprowadzić operacje ∪, ∩, ∼ przez odpowiednie formuły.

Można wykazać, że (Z/≡, ∪, ∩, ∼, [ψ ∧ ¬ψ], [ψ ∨ ¬ψ]) jest algebrą Boole’a.

Własności

Niech B = (B, ∪, ∩, ∼, 0, 1) będzie algebrą Boole’a. Dla wszystkich a, b ∈ B zachodzą:

• a ∪ a = a
• a ∩ a = a
• a ∪ 0 = a
• a ∩ 1 = a
• a ∪ 1 = 1
• a ∩ 0 = 0
• ∼0 = 1
• ∼1 = 0

Obowiązują również prawa de Morgana:

• ∼(a ∪ b) = (∼a) ∩ (∼b)
• ∼(a ∩ b) = (∼a) ∪ (∼b)

Podwójne zaprzeczenie:

• ∼(∼a) = a

Uporządkowanie

W zbiorze B wprowadza się porządek boole’owski ⩽, definiując go jako:

a ⩽ b wtedy i tylko wtedy, gdy a ∩ b = a. Tak zdefiniowana relacja ⩽ jest częściowym porządkiem na zbiorze B. Zbiór B z relacją ≤ stanowi kratę rozdzielną.

Ideały, algebry ilorazowe i homomorfizmy

Niepusty zbiór I ⊆ B jest ideałem w algebrze B, jeśli spełnia dwa warunki:

• ∀ a, b ∈ I (a ∪ b ∈ I),
• ∀ a ∈ B, b ∈ I (a ⩽ b ⇒ a ∈ I).

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ły zbiór B.

Pojęciem dualnym jest pojęcie filtru: niepusty zbiór F ⊆ B jest filtrem w algebrze B, jeśli:

• ∀ a, b ∈ F (a ∩ b ∈ F),
• ∀ a ∈ F, b ∈ B (a ⩽ b ⇒ b ∈ F).

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ły zbiór B.

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 B jest izomorficzna z ciałem otwarto-domkniętych podzbiorów przestrzeni ultrafiltrów na B, tzw. przestrzeni Stone’a algebry B.

Każda skończona algebra Boole’a jest izomorficzna z całym zbiorem potęgowym (P(X), ∪, ∩, ′, ∅, X) dla pewnego zbioru X.

Historia

XIX wiek

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 roku, Boole formułuje problem w bardziej dojrzały sposób, zauważając dualność operacji ∪ i ∩. Dalszy rozwój algebry 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 roku w „Vorlesungen” 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 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

Algebra Boole’a wiąże się z pojęciem pierścienia Boole’a. Pierścień Boole’a to pierścień przemienny z jedynką (P, ⊕, ⊙, 0, 1), w którym mnożenie spełnia warunek a ⊙ a = a dla każdego elementu a. W pierścieniu Boole’a każdy element jest rzędu 2, co oznacza, że spełnia równość a ⊕ a = 0.

Dowód:

a ⊕ a ⊕ a ⊕ a = (a ⊙ a) ⊕ (a ⊙ a) ⊕ (a ⊙ a) ⊕ (a ⊙ a) = (a ⊕ a) ⊙ (a ⊕ a) = a ⊕ a, więc a ⊕ a = 0.

Wynika stąd, że:

• a ⊙ (1 ⊕ a) = 0
• a ⊕ (1 ⊕ a) = 1.

Niech B = (B, ∪, ∩, ∼, 0, 1) będzie algebrą Boole’a. Jeżeli w zbiorze B określi się operację alternatywy wykluczającej (różnicy symetrycznej) ⊕ przez a ⊕ b = (a ∩ (∼b)) ∪ (b ∩ (∼a)), to (B, ⊕, ∩, 0, 1) będzie pierścieniem Boole’a. Za mnożenie przyjmuje się ∩.

I odwrotnie – niech (B, ⊕, ⊙, 0, 1) będzie pierścieniem Boole’a. Jeżeli zdefiniuje się operacje ∪, ∩, ∼ na B przez a ∪ b = (a ⊕ b) ⊕ (a ⊙ b), to B := (B, ∪, ∩, ∼, 0, 1) będzie algebrą Boole’a.

Dalsze struktury związane z algebrami Boole’a

Uogólnieniem algebr Boole’a są algebry pseudoboolowskie, zwane również algebrami Heytinga, w których z aksjomatów usunięte jest prawo wyłączonego środka a ∪ ∼a = 1. Rozpatrywane są także algebry Boole’a z dodatkowymi strukturami, takimi jak:

• monadyczne algebry Boole’a z dodatkowym działaniem jednoargumentowym ∃,
• 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. Brak numerów stron w książce
• Garrett Birkhoff, Thomas C. Bartee: Współczesna algebra stosowana. Warszawa: Państwowe Wydawnictwo Naukowe, 1983, seria: Matematyka dla Politechnik. ISBN 83-01-04560-4. Brak numerów stron w książce
• Thomas Jech: Set theory. Berlin: Springer-Verlag, 1997. ISBN 3-540-63048-1. Brak numerów stron w książce
• 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. Brak numerów stron w książce
• 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. Brak numerów stron w książce
• 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. Brak numerów stron w książce
• J. Donald Monk: Cardinal invariants on Boolean algebras. Basel: Birkhäuser Verlag, 1996, seria: Progress in Mathematics, 142. ISBN 3-7643-5402-X. Brak numerów stron w książce
• Helena Rasiowa: Wstęp do matematyki współczesnej. Warszawa: Państwowe Wydawnictwo Naukowe, 1973, seria: Biblioteka Matematyczna t. 30. Brak numerów stron w książce
• Roman Sikorski: Boolean Algebras (wydanie 3). Springer Verlag; Ergebnisse der Mathematik und ihrer Grenzgebiete. Neue Folge. Band 25, 1969 (wyd. 1 – 1960). Brak numerów stron w książce
• Helena Rasiowa, Roman Sikorski: The mathematics of metamathematics. Warszawa: Państwowe Wydawnictwo Naukowe (PWN), 1963, seria: Monografie Matematyczne 41. Brak numerów stron w książce

Linki zewnętrzne

Anglojęzyczne

Wiktor Bartol, Algebry Boole’a, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 27 września 2017 [dostęp 2024-09-04].

Polskojęzyczne

Eric W.E.W. Weisstein Eric W.E.W., Boolean Algebra, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2024-03-25].

Boolean Algebra (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].

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

Boolean algebra (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].