Algebra Boole’a

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 – struktura algebraiczna  w której  i  są działaniami dwuargumentowymi,  jest operacją jednoargumentową, a 0 i 1 są wyróżnionymi różnymi elementami zbioru  spełniająca następujące warunki dla wszystkich 
 {| cellpadding=5
| 
| 
| łączność
|-
| 
| 
| przemienność
|-
| 
| 
| absorpcja
|-
| 
| 
| rozdzielność
|-
| 
| 
| pochłanianie
|}

Oznaczenia 

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ń . 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).

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 
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  a 1 przez  Dzięki prawom de Morgana można też z aksjomatyki wyeliminować działanie  lub  (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:
  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 
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 
Niech  będzie algebrą Boole’a. Dla wszystkich  zachodzi:
 
 
 
 

 
 

 
 

prawa De Morgana:
 
 

podwójne przeczenie:

Uporządkowanie 
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 
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ść 
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 
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

Działania nieskończone 
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ść 
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 
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żą:
 twierdzenie Balcara-Franka.
 twierdzenie Fichtenholza-Kantorowicza

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ść  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 
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 
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ą  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 
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ż 
 funkcja boolowska

Przypisy

Bibliografia

Linki zewnętrzne 
 
  Boolean algebra , Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].

Boole’a
Struktury dwóch działań wewnętrznych
Logika matematyczna
Rodziny zbiorów
Byłe Dobre Artykuły