Algebra Boole’a – Wikipedia, wolna encyklopedia

Diagram Hassego dla algebry Boole’a podzbiorów zbioru trójelementowego
Diagramy Venna dla operatorów algebry 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]:

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 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]
Różne oznaczenia
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ń:

0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a a
0 1
1 0

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:

prawa De Morgana:

podwójne przeczenie:

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:

Zobacz też

[edytuj | edytuj kod]

Przypisy

[edytuj | edytuj kod]
  1. a b Algebra Boole’a, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-03-26].
  2. 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]