Algebra Boole'a –
struktura algebraiczna
stosowana w
matematyce
,
informatyce
teoretycznej oraz
elektronice cyfrowej
. Jej nazwa pochodzi od nazwiska
angielskiego
matematyka,
filozofa
i logika
George'a Boole'a
. Teoria algebr Boole'a jest działem matematyki na styku teorii
porządków częściowych
,
algebry
,
logiki matematycznej
i
topologii
.
Typowymi przykładami algebr Boole'a są:
rodzina
wszystkich
podzbiorów
ustalonego
zbioru
wraz 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 to 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
:
Oznaczenia
Różne oznaczeniaSuma | 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
teorio-mnogoś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 teorio-kratowych).
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 ˜.
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ń:
|  | 0 | 1 |
---|
0 | 0 | 0 |
---|
1 | 0 | 1 |
---|
| | | | | | |
Algebra ta stanowi podstawę elektroniki cyfrowej.
Jeśli
jest
ciałem podzbiorów
zbioru X, 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 X 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 X (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 h 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 X 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
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
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
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ę
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ą

Bibliografia
- 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. .
- Garrett Birkhoff, Thomas C. Bartee: Współczesna algebra stosowana. Warszawa: Państwowe Wydawnictwo Naukowe, 1983, seria: Matematyka dla Politechnik. .
-
Thomas Jech
: Set theory. Berlin: Springer-Verlag, 1997. .
- Winfried Just, Martin Weese: Discovering modern set theory. T. 2: Set-theoretic tools for every mathematician. Providence, RI:
American Mathematical Society
, 1997. .
- Sabine Koppelberg: Handbook of Boolean algebras. J. Donald Monk i Robert Bonnet (red.). T. 1,2,3. Amsterdam: North-Holland Publishing Co., 1989. .
-
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. .
-
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).
Zobacz też
Wystąpił problem z bazą danych.
Spróbuj ponownie poprzez naciśnięcie przycisku "Odśwież".
Przepraszamy za powstały problem.