Algebra Boole'a

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 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 :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 ˜.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:Inny taki układ to:Istnieją też systemy z jednym aksjomatem.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 matematyka .php'>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: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ślenieWówczas jest relacją równoważności na zbiorze . Podobnie jak wcześniej:Można pokazać, że jest algebrą Boole a.Niech będzie algebrą Boole a. Dla wszystkich zachodzi:prawa De Morgana:podwójne przeczenie:W zbiorze wprowadza się porządek boole'owski :Tak zdefiniowana relacja jest częściowym porządkiem na zbiorze . Zbiór z relacją ≤ jest kratą rozdzielną.Niepusty zbiór jest ideałem w algebrze , jeśli są spełnione następujące dwa warunki: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 matematyka .php'>filtru: niepusty zbiór jest matematyka .php'>filtrem w algebrze , jeśli:orazKażdy matematyka .php'>filtr zawiera element . matematyka .php'>Filtr który nie zawiera elementu , nazywany jest matematyka .php'>filtrem właściwym. Jedynym niewłaściwym matematyka .php'>filtrem jest całe .Niech będzie właściwym ideałem w algebrze . Niech będzie relacją dwuczłonową na taką, żeWó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 .Niech (operacje i zostały zamienione rolami, podobnie jak matematyka .php'>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 matematyka .php'>inwolucją zbioru B) i jest dany wzorem:dla dowolnego Algebra Boole a jest wolna, jeśli pewien zbiór ma następującą własność 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 matematyka .php'>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: 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:Zakładając istnienie odpowiednich kresów, zachodzą wzory de Morgana:Ponadto, jeśli , toNastępujące dwa stwierdzenia są równoważne dla algebry Boole a :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 σ matematyka .php'>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 teoria_kategorii .php'>kategorii to jest ideałem w algebrze i algebra ilorazowa jest zupełna. Podobnie dla rodziny wszystkich borelowskich zbiorów matematyka .php'>miary zero.W badaniach i opisach algebr Boole a często używa się funkcji kardynalnych. Przykładami takich funkcji kardynalnych są następujące funkcje.Twierdzenie Stone'a o reprezentacji algebr Boole a mówi, że każda algebra Boole a jest izomorficzna z pewnym matematyka .php'>ciałem zbiorów (traktowanym jako algebra Boole a). Dokładniej mówiąc, algebra Boole a jest izomorficzna z matematyka .php'>ciałem otwarto-domkniętych podzbiorów matematyka .php'>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 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.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 warunekW 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:Niech będzie algebrą Boole a. Jeżeli w zbiorze określi się operację różnicy symetrycznej przezto 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 przezto będzie algebrą Boole a spełniającą