Algebra Boole’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Algebra Boole'a)
Skocz do: nawigacja, szukaj
Diagram Hassego dla algebry Boole’a podzbiorów zbioru trójelementowego

Algebra Boole’aalgebra ogólna stosowana 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[edytuj]

Algebra Boole’a to 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

Oznaczenia[edytuj]

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 np. 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]

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[edytuj]

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]

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

prawa De Morgana:

podwójne przeczenie:

Uporządkowanie[edytuj]

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]

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 wolne[edytuj]

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]

Działania nieskończone[edytuj]

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żne[edytuj]

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]

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]

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 ZF – 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]

Nazwa „algebra Boole’a” pochodzi od nazwiska George’a Boole’a (18151864), 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[edytuj]

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ę 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ą

Zobacz też[edytuj]

Bibliografia[edytuj]

  • 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 8301045604.
  • 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. 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. 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 Grenzgebieterok. Neue Folge. Band 25, 1969 (wyd. 1 – 1960).