Otwórz menu główne
Diagram Hassego dla algebry Boole’a podzbiorów zbioru trójelementowego

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.

DefinicjaEdytuj

Algebra Boole’a – struktura algebraiczna   w której   i  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  

    łączność
    przemienność
    absorpcja
    rozdzielność
    pochłanianie

OznaczeniaEdytuj

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 aksjomatyzacjaEdytuj

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ładyEdytuj

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ściEdytuj

Niech   będzie algebrą Boole’a. Dla wszystkich   zachodzi:

 
 
 
 
 
 
 
 

prawa De Morgana:

 
 

podwójne przeczenie:

 

UporządkowanieEdytuj

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 homomorfizmyEdytuj

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

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 wolneEdytuj

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’aEdytuj

Działania nieskończoneEdytuj

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

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żneEdytuj

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 kardynalneEdytuj

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  

ReprezentacjaEdytuj

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  

HistoriaEdytuj

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’aEdytuj

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’aEdytuj

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

BibliografiaEdytuj

  • 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ętrzneEdytuj