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.