Algebra Boole’a
Algebra Boole’a – typ struktury algebraicznej, rodzaj algebry ogólnej definiowany aksjomatami. Uogólniają one właściwości typowych przykładów takich struktur z logiki matematycznej i teorii mnogości jak[1]:
- dwuelementowa algebra wartości logicznych {0, 1} z działaniami koniunkcji, alternatywy i negacji;
- rodzina wszystkich podzbiorów ustalonego zbioru (zbiór potęgowy) wraz z działaniami na zbiorach jako operacjami algebry.
Teoria algebr Boole’a to dział matematyki z pogranicza algebry abstrakcyjnej, teorii porządku i logiki. Jest stosowana w różnych działach matematyki jak topologia, w informatyce teoretycznej i elektronice cyfrowej[potrzebny przypis]. Nazwa pochodzi od nazwiska George’a Boole’a[2].
Definicja
[edytuj | edytuj kod]Algebra Boole’a – struktura algebraiczna w której:
- i są działaniami dwuargumentowymi,
- jest operacją jednoargumentową,
- 0 i 1 są wyróżnionymi różnymi elementami zbioru
- dla wszystkich spełnione są następujące warunki[1]:
1. łączność 2. przemienność 3. absorpcja 4. rozdzielność 5. pochłanianie
Oznaczenia
[edytuj | edytuj kod]Suma | Iloczyn | Negacja |
---|---|---|
Istnieją co najmniej trzy różne, szeroko rozpowszechnione tradycje oznaczeń w teorii algebr Boole’a. W definicji sformułowanej powyżej użyto symboli ale w częstym użyciu są również oraz Symbole oznaczające operacje dwuczłonowe algebry Boole’a są prawie zawsze wprowadzane przez wybór jednej z par albo W oznaczeniach operacji jednoargumentowej algebry istnieje mniejsza konsekwencja i można się spotkać zarówno z symbolami jak i
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ń [potrzebny przypis]. Ten sam system został też wybrany za wiodący przez redaktorów monografii Handbook of Boolean Algebras.
Z kolei symbole 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 lub zamiast ). W elektronice i informatyce często stosuje się OR, AND oraz NOT w miejsce oraz W języku C oraz w językach nim inspirowanych używa się odpowiednio symboli: |, &, !.
Minimalna aksjomatyzacja
[edytuj | edytuj kod]Powyższa (tradycyjna) definicja algebry Boole’a nie jest minimalna, np.[potrzebny przypis]:
- 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 a 1 przez
- dzięki prawom de Morgana można też z aksjomatyki wyeliminować działanie lub
- 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:
- jest przemienne
- jest łączne
- aksjomat Huntingtona:
Inny taki układ to:
- jest przemienne
- jest łączne
- aksjomat Robbinsa:
Istnieją też systemy z jednym aksjomatem.
Przykłady
[edytuj | 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 jest ciałem podzbiorów zbioru to jest algebrą Boole’a (gdzie oznacza operację dopełnienia).
Niech będzie zbiorem zdań w rachunku zdań. Niech będzie relacją dwuargumentową na zbiorze określoną jako:
- wtedy i tylko wtedy, gdy jest tautologią rachunku zdań.
Można sprawdzić, że jest relacją równoważności na zbiorze Na zbiorze wszystkich klas abstrakcji relacji można wprowadzić operacje przez następujące formuły:
W ten sposób otrzymuje się poprawnie zdefiniowane operacje na zbiorze (tzn. wynik nie zależy od wyboru reprezentantów klas abstrakcji), a 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 będzie zbiorem zdań w ustalonym alfabecie i niech będzie niesprzeczną teorią w tym samym języku. Relację dwuargumentową na zbiorze można wprowadzić przez określenie
- wtedy i tylko wtedy, gdy
Wówczas jest relacją równoważności na zbiorze Podobnie jak wcześniej:
Można pokazać, że jest algebrą Boole’a.
Własności
[edytuj | edytuj kod]Niech będzie algebrą Boole’a. Dla wszystkich zachodzi:
Uporządkowanie
[edytuj | edytuj kod]W zbiorze wprowadza się porządek boole’owski
- wtedy i tylko wtedy, gdy
Tak zdefiniowana relacja jest częściowym porządkiem na zbiorze Zbiór z relacją ≤ jest kratą rozdzielną.
Ideały, algebry ilorazowe i homomorfizmy
[edytuj | edytuj kod]Niepusty zbiór jest ideałem w algebrze , jeśli są spełnione następujące dwa warunki:
- oraz
Każdy ideał zawiera element Ideał, który nie zawiera elementu nazywany jest ideałem właściwym. Jedynym niewłaściwym ideałem jest całe
Pojęciem dualnym jest pojęcie filtru: niepusty zbiór jest filtrem w algebrze jeśli:
oraz
Każdy filtr zawiera element Filtr, który nie zawiera elementu nazywany jest filtrem właściwym. Jedynym niewłaściwym filtrem jest całe
Niech będzie właściwym ideałem w algebrze Niech będzie relacją dwuczłonową na taką, że
- wtedy i tylko wtedy, gdy
Wówczas jest relacją równoważności na W zbiorze klas abstrakcji tej relacji można zdefiniować działania
Pokazuje się, że powyższe definicje są poprawne (tzn. wynik operacji nie zależy od wyboru reprezentantów z klas abstrakcji) oraz że jest algebrą Boole’a. Algebra ta jest nazywana algebrą ilorazową i jest oznaczana przez
Niech będzie algebrą Boole’a i niech będzie funkcją odwzorowującą w Mówimy, że funkcja jest homomorfizmem algebr Boole’a, jeśli zachowuje ona działania w algebrze, tzn. dla wszystkich zachodzą trzy równości:
Jeśli dodatkowo jest funkcją wzajemnie jednoznaczną z na to funkcja zwana jest izomorfizmem algebr Boole’a.
Jeśli jest ideałem w algebrze to odwzorowanie jest homomorfizmem.
Jeśli jest algebrą Boole’a oraz jest homomorfizmem na to jest ideałem w algebrze a algebra ilorazowa jest izomorficzna z
Autodualność
[edytuj | edytuj kod]Niech (operacje i zostały zamienione rolami, podobnie jak stałe 0 i 1). Wtedy także jest algebrą Boole’a izomorficzną z wyjściową algebrą Kanoniczny izomorfizm d tych dwóch algebr jest swoją własną odwrotnością (jest inwolucją zbioru B) i jest dany wzorem:
dla dowolnego
Algebry wolne
[edytuj | edytuj kod]Algebra Boole’a jest wolna, jeśli pewien zbiór ma następującą własność:
- dla każdej algebry Boole’a i każdego odwzorowania istnieje dokładnie jeden homomorfizm z algebry w algebrę przedłużający (czyli taki, że ).
Zbiór o własności opisanej powyżej jest nazywany zbiorem wolnych generatorów algebry Jeśli moc zbioru jest to mówimy, że jest wolną algebrą Boole’a z generatorami.
Skończona algebra Boole’a jest wolna wtedy i tylko wtedy, gdy ma ona elementów (dla ). Algebra mocy jest izomorficzna z ciałem wszystkich podzbiorów zbioru z elementami i jako taka ma 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:
Zupełne algebry Boole’a
[edytuj | edytuj kod]Działania nieskończone
[edytuj | edytuj kod]Ponieważ w algebrze Boole’a istnieje porządek częściowy, to dla zbioru można rozpatrywać jego kresy (które istnieją lub nie).
Jeśli dwuczłonowe operacje algebry Boole’a są oznaczane przez (tak jak w tym artykule), to kres górny zbioru (gdy istnieje) jest oznaczany przez a jego kres dolny (gdy istnieje) jest oznaczany przez Jeśli natomiast symbolami dla tych operacji są to kresy oznaczane są przez
Dla zbioru pustego:
- oraz
Zakładając istnienie odpowiednich kresów, zachodzą wzory de Morgana:
- oraz
Ponadto jeśli to:
- wtedy i tylko wtedy, gdy
- oraz
- wtedy i tylko wtedy, gdy
- oraz
Zupełność
[edytuj | edytuj kod]Następujące dwa stwierdzenia są równoważne dla algebry Boole’a
- każdy podzbiór ma kres górny;
- każdy podzbiór ma kres dolny.
Algebry, w których każdy zbiór ma kres górny (tzn. takie dla których porządek boole’owski 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 będzie liczbą kardynalną, a będzie algebrą Boole’a. Powiemy, że algebra jest -zupełna, jeśli każdy zbiór mocy mniejszej niż ma kres górny (tzn. istnieje ilekroć ). Równoważnie: algebra jest -zupełna wtedy i tylko wtedy, gdy każdy zbiór o mocy mniejszej niż ma kres dolny (tzn. ). Algebry -zupełne są też nazywane algebrami -zupełnymi.
Jeśli jest -ciałem borelowskich podzbiorów prostej rzeczywistej (a więc jest to -zupełna algebra Boole’a) oraz jest rodziną wszystkich zbiorów które są pierwszej kategorii, to jest ideałem w algebrze i algebra ilorazowa jest zupełna. Podobnie dla rodziny wszystkich borelowskich zbiorów miary zero.
Zbiory niezależne
[edytuj | edytuj kod]Podzbiór algebry Boole’a nazywany jest niezależnym, gdy dla dowolnych zbiorów skończonych
Do klasycznych twierdzeń dotyczących zbiorów niezależnych w algebrach Boole’a należą:
Funkcje kardynalne
[edytuj | 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ść algebry Boole’a jest to supremum mocy antyłańcuchów w
- Długość algebry Boole’a to
- jest łańcuchem
- Głębokość algebry Boole’a to
- jest dobrze uporządkowanym łańcuchem
- Nieporównywalność algebry Boole’a to
- oraz
- Pseudo-ciężar algebry Boole’a to
- oraz
Reprezentacja
[edytuj | 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 jest izomorficzna z ciałem otwarto-domkniętych podzbiorów przestrzeni ultrafiltrów na tzw. przestrzeni Stone’a algebry 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 dla pewnego
Historia
[edytuj | edytuj kod]XIX wiek
[edytuj | 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).
XX wiek
[edytuj | edytuj kod]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 | 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ą w którym mnożenie spełnia warunek
- dla każdego elementu
W pierścieniu Boole’a każdy element jest rzędu 2, to znaczy spełnia równość: Dowód:
więc
Wynika stąd, że:
- oraz
Niech będzie algebrą Boole’a. Jeżeli w zbiorze określi się operację alternatywy wykluczającej (różnicy symetrycznej) przez
to będzie pierścieniem Boole’a; za mnożenie przyjmuje się
I na odwrot – niech będzie pierścieniem Boole’a. Jeżeli zdefiniuje się operacje i na przez
- i
to będzie algebrą Boole’a spełniającą
Dalsze struktury związane z algebrami Boole’a
[edytuj | 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
Rozpatrywane są też algebry Boole’a z dodatkowymi strukturami. Należą do nich:
- monadyczne algebry Boole’a z dodatkowym działaniem jednoargumentowym
- topologiczne algebry Boole’a z dodatkowym operatorem wnętrza.
Zobacz też
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ a b Algebra Boole’a, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-03-26] .
- ↑ Słownik terminologiczny informacji naukowej, Maria Dembowska, Wrocław–Warszawa–Kraków–Gdańsk: Zakład Narodowy imienia Ossolińskich, 1979, s. 24 .
Bibliografia
[edytuj | edytuj kod]- 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
[edytuj | edytuj kod]- Eric W. Weisstein , 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. Donald Monk , 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].