Algebry Boole'a zdefiniowane kanonicznie

Algebry Boole'a są modelami teorii równań dwóch wartości; ta definicja jest równoważna definicjom kraty i pierścienia.

Algebra Boole'a to bogata matematycznie gałąź algebry abstrakcyjnej . Stanford Encyclopaedia of Philosophy definiuje algebrę Boole'a jako „algebrę logiki dwuwartościowej z tylko spójnikami zdaniowymi lub równoważnie algebry zbiorów podlegających zsumowaniu i uzupełnieniu”. Tak jak teoria grup zajmuje się grupami , a algebra liniowa przestrzeniami wektorowymi , tak algebry Boole'a są modelami teorii równań dwóch wartości 0 i 1 (których interpretacja nie musi być numeryczna). Wspólne dla algebr, grup i przestrzeni wektorowych Boole'a jest pojęcie struktury algebraicznej , zbioru zamkniętego pewnymi operacjami spełniającymi określone równania.

takie jak grupa $całkowitych$ i grupa symetryczna $S n$ permutacji n obiektów, $istnieją$ również podstawowe przykłady algebr Boole'a, takie jak poniższe.

Algebra cyfr binarnych lub bitów 0 i 1 w ramach operacji logicznych, w tym alternatywy, koniunkcji i negacji. Zastosowania obejmują rachunek zdań i teorię obwodów cyfrowych.
Algebra zbiorów w ramach operacji na zbiorach, w tym suma , przecięcie i dopełnienie . Zastosowania są dalekosiężne, ponieważ teoria mnogości jest standardową podstawą matematyki .

Algebra Boole'a pozwala zatem zastosować metody algebry abstrakcyjnej do logiki matematycznej i logiki cyfrowej .

W przeciwieństwie do grup skończonego rzędu , które wykazują złożoność i różnorodność i których teoria pierwszego rzędu jest rozstrzygalna tylko w szczególnych przypadkach, wszystkie skończone algebry Boole'a mają te same twierdzenia i rozstrzygalną teorię pierwszego rzędu. Zamiast tego zawiłości algebry Boole'a są podzielone między strukturę algebr nieskończonych i algorytmiczną złożoność ich struktury składniowej .

Definicja

Algebra Boole'a zajmuje się teorią równań maksymalnej dwuelementowej algebry skończonej , zwanej prototypem Boole'a , oraz modelami tej teorii, zwanymi algebrami Boole'a . Terminy te są zdefiniowane w następujący sposób.

Algebra jest rodziną operacji na zbiorze, zwanym podstawowym zbiorem algebry. Przyjmujemy, że podstawowym zbiorem prototypu boolowskiego jest {0,1}.

$0$ Algebra jest skończona , gdy każda z jej operacji przyjmuje tylko skończenie wiele argumentów. Dla prototypu każdy argument operacji to albo albo $1$ , podobnie jak wynik operacji. Maksymalna taka algebra składa się ze wszystkich skończonych operacji na {0,1}.

$0$ Liczba argumentów przyjmowanych przez każdą operację nazywana jest liczbą operacji. Operację na {0,1} o arity $n$ , lub operację $n$ -argumentową, można zastosować do dowolnej z $2 n$ możliwych wartości jej $n$ argumentów. Dla każdego wyboru argumentów operacja może zwrócić lub $1$ , skąd jest $2 2 n n$ -argumentów.

$0$ $0$ Prototyp ma zatem dwie operacje bez argumentów, zwane operacjami zerowymi lub zerowymi , a mianowicie zero i jeden. Ma cztery operacje jednoargumentowe , z których dwie to operacje na stałych, kolejna to identyczność, a najczęściej używana, zwana negacją , zwraca przeciwieństwo swojego argumentu: $1$ jeśli , jeśli $1$ . Ma szesnaście operacji binarnych ; ponownie dwa z nich są stałe, inny zwraca swój pierwszy argument, jeszcze inny zwraca swój drugi, jeden nazywa się koniunkcją i zwraca 1, jeśli oba argumenty są równe 1, a w przeciwnym razie 0, inny nazywa się dysjunkcją i zwraca 0, jeśli oba argumenty są równe 0, a w przeciwnym razie 1 , i tak dalej. Liczba $(n +1)$ operacji -argumentowych w prototypie jest kwadratem liczby operacji $n$ -argumentowych, więc jest $162 = 256$ operacji trójnych, $2562 = 65 536$ operacji quaternary i tak dalej.

Rodzina jest indeksowana przez zestaw indeksów . W przypadku rodziny operacji tworzących algebrę indeksy nazywane są symbolami operacji , stanowiącymi język tej algebry. Operacja indeksowana przez każdy symbol jest nazywana denotacją lub interpretacją tego symbolu. Każdy symbol operacji określa prawdziwość jego interpretacji, stąd wszystkie możliwe interpretacje symbolu mają tę samą prawdziwość. Ogólnie rzecz biorąc, algebra może interpretować różne symbole za pomocą tej samej operacji, ale nie dotyczy to prototypu, którego symbole odpowiadają jej operacjom. Prototyp ma zatem $2 2 n n$ -arnych symboli operacji, zwanych symbolami operacji Boole'a i tworzących język algebry Boole'a. Tylko kilka operacji ma konwencjonalne symbole, takie jak $\neg$ dla negacji, $\land$ dla koniunkcji i $\lor$ dla alternatywy. Wygodnie jest przyjąć, że $i$ -ty $n$ -arny symbol to $n fi,$ jak to zrobiono poniżej w części dotyczącej tablic prawdy .

Teoria równań w danym języku składa się z równań między terminami zbudowanych ze zmiennych przy użyciu symboli tego języka. Typowe równania w języku algebry Boole'a to $x \land y = y \land x$ , $x \land x = x$ , $x \land\neg x = y \land\neg y$ , oraz $x \land y = x$ .

Algebra spełnia równanie, gdy równanie zachodzi dla wszystkich możliwych wartości jej zmiennych w tej algebrze, gdy symbole operacji są interpretowane zgodnie z specyfikacją tej algebry. Prawa algebry Boole'a to równania w języku algebry Boole'a spełnione przez prototyp. Pierwsze trzy z powyższych przykładów są prawami boolowskimi, ale nie czwartym, ponieważ $1\land0 \neq 1$ .

Teoria równań algebry jest zbiorem wszystkich równań spełnianych przez algebrę. Prawa algebry Boole'a stanowią zatem teorię równań prototypu Boole'a.

Modelem teorii jest algebra interpretująca symbole operacji w języku teorii i spełniająca równania teorii.

Algebra Boole'a to dowolny model praw algebry Boole'a.

Oznacza to, że algebra Boole'a jest zbiorem i rodziną operacji na nim, interpretujących symbole operacji Boole'a i spełniających te same prawa, co prototyp Boole'a.

Jeśli zdefiniujemy homolog algebry jako model teorii równań tej algebry, to algebrę Boole'a można zdefiniować jako dowolny homolog prototypu.

Przykład 1 . Prototyp Boole'a jest algebrą Boole'a, ponieważ trywialnie spełnia swoje własne prawa. Jest to zatem prototypowa algebra Boole'a. Początkowo nie nazwaliśmy tego tak, aby uniknąć pojawienia się kołowości w definicji.

Podstawa

Nie wszystkie operacje muszą być wyraźnie określone. Podstawą , z którego można uzyskać pozostałe operacje przez złożenie. „Algebrę Boole'a” można zdefiniować na podstawie dowolnej z kilku różnych podstaw. W powszechnym użyciu są trzy podstawy algebry Boole'a: podstawa kraty, podstawa pierścienia i podstawa obrysu Sheffera lub podstawa NAND. Podstawy te nadają podmiotowi odpowiednio charakter logiczny, arytmetyczny i oszczędny.

Podstawa kratowa powstała w XIX wieku dzięki pracom Boole'a , Peirce'a i innych poszukujących algebraicznej formalizacji logicznych procesów myślowych.
pierścienia pojawiła się w XX wieku wraz z pracami Zhegalkina i Stone'a i stała się podstawą wyboru dla algebraistów, którzy do tematu podeszli z doświadczenia w algebrze abstrakcyjnej . Większość podejść do algebry Boole'a zakłada podstawę kraty, godnym uwagi wyjątkiem jest Halmos [1963], którego doświadczenie w algebrze liniowej najwyraźniej przyciągnęło go do podstawy pierścienia.
Ponieważ wszystkie operacje skończone na {0,1} można zdefiniować za pomocą skoku Sheffera NAND (lub jego podwójnego NOR), wynikająca z tego podstawa ekonomiczna stała się podstawą wyboru do analizy układów cyfrowych , w szczególności macierzy bramek w elektronice cyfrowej .

Wspólnymi elementami podstaw sieci i pierścienia są stałe 0 i 1 oraz asocjacyjna przemienna operacja binarna , zwana spotkaniem $x \land y$ w bazie sieci i mnożeniem $xy$ w podstawie pierścienia. Rozróżnienie jest tylko terminologiczne. Baza kratowa ma dalsze operacje łączenia , $x \lor y$ i uzupełniania , $\neg x$ . Podstawa pierścienia ma zamiast tego operację arytmetyczną $x \oplus y$ dodawania (symbol $\oplus$ jest używany zamiast $+ , ponieważ temu drugiemu czasami$ podaje się Boole'owskie odczytanie łączenia).

Bycie bazą oznacza uzyskanie wszystkich innych operacji przez kompozycję, skąd dowolne dwie bazy muszą być wzajemnie przekładalne. Podstawa sieci przekłada $x \lor y$ na podstawę pierścienia jako $x \oplus y \oplus xy$ , a $\neg x$ jako $x \oplus1$ . I odwrotnie, podstawa pierścienia przekłada $x \oplus y$ na podstawę sieci jako $(x \lor y) \land\neg(x \land y)$ .

Obie te podstawy umożliwiają definiowanie algebr Boole'a za pomocą podzbioru właściwości równań operacji Boole'a. Dla podstawy kratowej wystarczy zdefiniować algebrę Boole'a jako kratę rozdzielczą spełniającą $x \land\neg x = 0$ i $x \lor\neg x = 1$ , zwaną dopełnioną siatką rozdzielczą. Podstawa pierścienia zamienia algebrę Boole'a w pierścień Boole'a , czyli pierścień spełniający $x 2 = x$ .

Emil Post podał warunek konieczny i wystarczający, aby zbiór operacji był podstawą niezerowych operacji boolowskich. Właściwość nietrywialna to taka, która jest wspólna dla niektórych, ale nie wszystkich operacji tworzących podstawę. Post wymienił pięć nietrywialnych właściwości operacji, które można zidentyfikować za pomocą pięciu klas Posta , z których każda została zachowana przez kompozycję, i wykazał, że zestaw operacji stanowi podstawę, jeśli dla każdej właściwości zestaw zawiera operację pozbawioną tej właściwości. (Odwrotność twierdzenia Posta, rozciągająca się na „jeżeli” na „ jeśli i tylko wtedy ”, jest łatwą obserwacją, że spośród tych pięciu właściwości obejmujących każdą operację na kandydującej bazie będzie również obowiązywać każda operacja utworzona przez złożenie z tego kandydującego , skąd przez nietrywialność tej właściwości kandydat nie będzie podstawą.) Pięć właściwości Posta to:

monotone , żadne przejście wejściowe 0-1 nie może spowodować przejścia wyjściowego 1-0;
afiniczny , możliwy do przedstawienia za pomocą wielomianów Zhegalkina , które nie mają wyrazów dwuliniowych lub wyższych, np. $x \oplus y \oplus1$ , ale nie $xy$ ;
self-dualny , tak że uzupełnienie wszystkich danych wejściowych uzupełnia wyjście, jak w przypadku $x$ lub operatora mediany $xy \oplus yz \oplus zx$ lub ich negacji;
strict (odwzorowanie wejścia samych zer na zero);
costrict (odwzorowanie wszystkich jedynek na jeden).

NAND (dual NOR) brakuje tego wszystkiego, tworząc w ten sposób podstawę samą w sobie.

Tablice prawdy

Operacje skończone na {0,1} można przedstawić jako tablice prawdy , myśląc o 0 i 1 jako wartościach prawdy fałsz i prawda . Można je ułożyć w jednolity i niezależny od aplikacji sposób, który pozwala nam nazwać je lub przynajmniej ponumerować indywidualnie. Nazwy te stanowią wygodny skrót dla operacji boolowskich. Nazwy $n$ -argumentowych operacji są liczbami binarnymi o długości $2 n$ bitów. Ponieważ takich operacji jest $2 2 n$ , nie można prosić o bardziej zwięzłe nazewnictwo. Zauważ, że każdą operację skończoną można nazwać funkcją przełączającą .

Ten układ i związane z nim nazewnictwo operacji jest tutaj w pełni zilustrowane dla liczb od 0 do 2.

Tabele prawdy dla operacji boolowskich o arity do 2

Stałe
${\ displaystyle {} ^ {0} \! f_ {0}}$	${\ displaystyle {} ^ {0} \! f_ {1}}$
0	1

Operacje jednoargumentowe
${\ displaystyle x_ {0}}$	${\ displaystyle {} ^ {1} \! f_ {0}}$	${\ displaystyle {} ^ {1} \! f_ {1}}$	${\ displaystyle {} ^ {1} \! f_ {2}}$	${\ displaystyle {} ^ {1} \! f_ {3}}$
0	0	1	0	1
1	0	0	1	1

Operacje binarne
${\ displaystyle x_ {0}}$	${\ displaystyle x_ {1}}$	${\ displaystyle {} ^ {2} \! f_ {1}}$	${\ displaystyle {} ^ {2} \! f_ {2}}$	${\ displaystyle {} ^ {2} \! f_ {3}}$	${\ displaystyle {} ^ {2} \! f_ {4}}$	${\ displaystyle {} ^ {2} \! f_ {5}}$	${\ displaystyle {} ^ {2} \! f_ {6}}$	${\ displaystyle {} ^ {2} \! f_ {7}}$	${\ displaystyle {} ^ {2} \! f_ {8}}$	${\ displaystyle {} ^ {2} \! f_ {9}}$	${\ displaystyle {} ^ {2} \! f_ {10}}$	${\ displaystyle {} ^ {2} \! f_ {11}}$	${\ displaystyle {} ^ {2} \! f_ {12}}$	${\ displaystyle {} ^ {2} \! f_ {13}}$	${\ displaystyle {} ^ {2} \! f_ {14}}$	${\ displaystyle {} ^ {2} \! f_ {15}}$
0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
0	1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

Tabele te są kontynuowane z wyższymi wartościami liczbowymi, z $2 n$ wierszami o arity $n$ , każdy wiersz podaje wycenę lub powiązanie n $zmiennych$ x $0, ... x n -1$ i każda kolumna z nagłówkiem $n f i$ podaje wartość $0 n fi i (x,..., x n -1)$ i $-$ tej $n$ -arnej operacji przy tej wartościowaniu. Operacje obejmują zmienne, na przykład $1 f 2$ to $x 0$ , podczas gdy $2 f 10$ to $x 0$ (jako dwie kopie jego jednoargumentowego odpowiednika), a $2 f 12$ to $x 1$ (bez jednoargumentowego odpowiednika). Negacja lub dopełnienie $\neg x 0$ pojawia się jako $1 f 1$ i ponownie jako $2 f 5$ , wraz z $2 f 3$ ( $\neg x 1$ , które nie pojawiło się na arity 1), dysjunkcja lub suma $0 x \lor x 1$ jako $2 f 14$ , koniunkcja lub przecięcie $0 x \land x 1$ jako $2 f 8$ , implikacja $0 x \to x 1 jako 2 f 13$ , różnica wyłączna lub symetryczna $0 x \oplus x 1$ jako $2 f 6$ , różnica zbioru $0 x - x 1$ jako $2 f 2$ i tak dalej.

Jako drobny szczegół ważniejszy bardziej ze względu na formę niż treść, operacje algebry są tradycyjnie zorganizowane w postaci listy. Chociaż indeksujemy tutaj operacje algebry Boole'a za pomocą operacji skończonych na {0,1}, powyższa tabela prawdy nieoczekiwanie porządkuje operacje najpierw według arity, a następnie według układu tabel dla każdej arity. Pozwala to zorganizować zbiór wszystkich operacji boolowskich w tradycyjnym formacie listy. Porządek na liście dla operacji danej arity jest określony przez następujące dwie reguły.

0

(i)

I

-ty wiersz w lewej połowie tabeli jest binarną reprezentacją

i

z najmniej znaczącym lub -tym bitem po lewej stronie (porządek „little-endian”, oryginalnie zaproponowany przez Alana Turinga , więc nie nierozsądne byłoby nazywanie go porządkiem Turinga).

(ii)

j

-ta kolumna w prawej połowie tabeli to binarna reprezentacja

j

, ponownie w porządku little-endian. W efekcie indeks dolny operacji jest tablicą prawdy tej operacji. Przez analogię do numeracji funkcji obliczalnych Gödla można by nazwać tę numerację operacji boolowskich numeracją Boole'a.

Podczas programowania w C lub Javie alternatywna bitowa jest oznaczana jako x | y , koniunkcja x & y oraz negacja ~ x . Program może zatem reprezentować na przykład operację $x \land(y \lor z)$ w tych językach jako x & ( y | z ) , mając wcześniej ustawione x = 0xaa , y = 0xcc , i z = 0xf0 („ 0x ” wskazuje, że następującą stałą należy odczytywać w postaci szesnastkowej lub o podstawie 16), albo przez przypisanie do zmiennych, albo zdefiniowaną jako makra. Te jednobajtowe (ośmiobitowe) stałe odpowiadają kolumnom dla zmiennych wejściowych w rozszerzeniu powyższych tabel do trzech zmiennych. Ta technika jest prawie powszechnie stosowana w sprzęcie do grafiki rastrowej, aby zapewnić elastyczne różnorodne sposoby łączenia i maskowania obrazów, przy czym typowe operacje są trójskładnikowe i działają jednocześnie na bitach źródłowych, docelowych i maskujących.

Przykłady

Wektory bitowe

Przykład 2 . Wszystkie wektory bitowe o danej długości tworzą algebrę Boole'a „punktowo”, co oznacza, że dowolna $n$ -argumentowa operacja Boole'a może być zastosowana do $n$ wektorów bitowych, jedna pozycja bitowa na raz. Na przykład potrójne OR trzech wektorów bitowych, każdy o długości 4, jest wektorem bitowym o długości 4 utworzonym przez oring trzech bitów w każdej z czterech pozycji bitowych, a zatem 0100∨1000∨1001 = $1101$ . Innym przykładem są powyższe tabele prawdy dla $n$ -argumentowych, których kolumnami są wszystkie wektory bitowe o długości $2 n$ , a zatem można je łączyć punktowo, skąd $n$ -ary operacje tworzą algebrę Boole'a. Działa to równie dobrze w przypadku wektorów bitowych o skończonej i nieskończonej długości, przy czym jedyną zasadą jest to, że wszystkie pozycje bitów są indeksowane przez ten sam zestaw, aby „odpowiednia pozycja” była dobrze zdefiniowana.

$0$ Atomy takiej algebry to wektory bitowe zawierające dokładnie jedną 1. Ogólnie rzecz biorąc, atomami algebry Boole'a są takie elementy $x$ , że $x \land y$ ma tylko dwie możliwe wartości, $x$ lub .

Algebra mocy

Przykład 3 . Potęgowa algebra zbiorów , zbiór $2 W$ wszystkich podzbiorów danego zbioru $W$ . To tylko przykład 2 w przebraniu, gdzie $W$ służy do indeksowania pozycji bitów. Dowolny podzbiór $X$ z $W$ może być postrzegany jako wektor bitowy mający jedynki tylko na tych pozycjach bitowych, które są indeksowane przez elementy $X$ . Zatem wektor zera jest pustym podzbiorem $W$ , podczas gdy wektor z wszystkimi jedynkami jest samym $W$ , przy czym są to odpowiednio stałe 0 i 1 algebry potęg. Odpowiednikiem dysjunkcji $x \lor y$ jest suma $X \cup Y$ , natomiast odpowiednikiem koniunkcji $x \land y$ jest przecięcie $X \cap Y$ . Negacja $\neg x$ staje się $~ X$ , uzupełnienie względem $W$ . Istnieje również różnica zbiorów $X ∖ Y = X \cap~ Y$ , różnica symetryczna $(X ∖ Y)\cup(Y ∖ X)$ , suma trójskładnikowa $X \cup Y \cup Z$ , i tak dalej. Atomy tutaj to singletony, te podzbiory z dokładnie jednym elementem.

Przykłady 2 i 3 są szczególnymi przypadkami ogólnej konstrukcji algebry zwanej iloczynem bezpośrednim , mającej zastosowanie nie tylko do algebr Boole'a, ale do wszystkich rodzajów algebr, włączając grupy, pierścienie itp. Iloczyn bezpośredni dowolnej rodziny $B i$ algebr Boole'a, gdzie $i$ mieści się w zakresie pewien zbiór indeksów $I (niekoniecznie skończony, a nawet policzalny$ $) (... xi,...)$ jest algebrą Boole'a składającą się ze wszystkich $I$ -krotek , których $i$ -ty element jest wzięty z $B i$ . Operacje iloczynu bezpośredniego to odpowiednie operacje algebr składowych działających w ich odpowiednich współrzędnych; w szczególności operacja $n f j$ produktu działa na $n$ $I$ - krotkach przez zastosowanie operacji $n f j$ z $B i$ do n $elementów$ w $i$ - tej współrzędnej n $krotek$ dla wszystkich $i$ w $I$ .

Kiedy wszystkie algebry mnożone razem w ten sposób są tą samą algebrą $A$ , iloczyn bezpośredni nazywamy potęgą bezpośrednią $A$ . Algebra Boole'a wszystkich 32-bitowych wektorów bitowych jest dwuelementową algebrą Boole'a podniesioną do 32. potęgi lub potęgową algebrą zbioru 32-elementowego, oznaczoną $232$ . Algebra Boole'a wszystkich zbiorów liczb całkowitych to $2 Z$ . Wszystkie algebry Boole'a, które do tej pory przedstawiliśmy, były bezpośrednimi potęgami dwuelementowej algebry Boole'a, co uzasadnia nazwę "algebra potęgowa".

Twierdzenia o reprezentacji

Można wykazać, że każda skończona algebra Boole'a jest izomorficzna z pewną algebrą potęgową. Stąd liczność (liczba elementów) skończonej algebry Boole'a jest potęgą $2$ , a mianowicie jedną z $1,2,4,8,...,2 n,...$ Nazywa się to twierdzeniem o reprezentacji , ponieważ daje wgląd w naturę skończonych algebr Boole'a, dając ich reprezentację jako algebry potęgowe.

To twierdzenie o reprezentacji nie rozciąga się na nieskończone algebry Boole'a: chociaż każda algebra potęgowa jest algebrą Boole'a, nie każda algebra Boole'a musi być izomorficzna z algebrą potęgową. W szczególności, podczas gdy nie może istnieć przeliczalnie nieskończonych algebr zbiorów potęg (najmniejszą algebrą zbiorów potęg nieskończonych jest algebra zbiorów potęg $2 N$ zbiorów liczb naturalnych, jak wykazał Cantor jako niepoliczalny ), istnieją różne przeliczalnie nieskończone algebry Boole'a.

Aby wyjść poza algebry potęgowe, potrzebujemy innego konstruktu. Podalgebrą algebry $A$ jest dowolny podzbiór $A$ zamknięty pod działaniem A $.$ Każda podalgebra algebry Boole'a $A$ musi nadal spełniać równania spełniające $A$ , ponieważ każde naruszenie stanowiłoby naruszenie samego $A.$ Stąd każda podalgebra algebry Boole'a jest algebrą Boole'a.

Podalgebrę potęgowej algebry zbiorów nazywamy ciałem zbiorów ; równoważnie ciało zbiorów jest zbiorem podzbiorów pewnego zbioru $W$ , w tym zbioru pustego i $W$ oraz zamkniętego pod skończoną sumą i dopełnieniem względem $W$ (a więc także pod skończonym przecięciem). Twierdzenie Birkhoffa [1935] o reprezentacji algebr Boole'a stwierdza, że każda algebra Boole'a jest izomorficzna z ciałem zbiorów. Teraz twierdzenie HSP Birkhoffa dla rozmaitości można przedstawić jako, że każda klasa modeli teorii równań klasy $C$ algebr jest homomorficznym obrazem podalgebry bezpośredniego iloczynu algebr $C$ . Zwykle potrzebne są wszystkie trzy z H, S i P; pierwsze z tych dwóch twierdzeń Birkhoffa pokazuje, że dla szczególnego przypadku rozmaitości algebr Boole'a homomorfizm można zastąpić izomorfizmem . Twierdzenie HSP Birkhoffa dla rozmaitości w ogólności staje się zatem twierdzeniem ISP Birkhoffa dla rozmaitości algebr Boole'a.

Inne przykłady

Gdy mówimy o zbiorze X liczb naturalnych, wygodnie jest postrzegać go jako ciąg $0 x, x 1, x 2,...$ bitów, gdzie $x i = 1$ wtedy i tylko wtedy, gdy $i \in X$ . Ten punkt widzenia ułatwi nam mówienie o podalgebrach potęgowej algebry $2 N$ , które ten punkt widzenia czyni algebrą Boole'a wszystkich ciągów bitów. Dobrze pasuje również do kolumn tabeli prawdy: kolumna czytana od góry do dołu stanowi ciąg bitów, ale jednocześnie może być traktowana jako zbiór tych wartościowań (przypisania do zmiennych po lewej stronie połowie tabeli), przy której funkcja reprezentowana przez tę kolumnę ma wartość 1.

$0$ Przykład 4 . Ostatecznie stałe sekwencje . Każda logiczna kombinacja ostatecznie stałych sekwencji jest ostatecznie stała; stąd tworzą one algebrę Boole'a. Możemy je zidentyfikować za pomocą liczb całkowitych, postrzegając sekwencje ostatecznie zerowe jako nieujemne liczby binarne (bit sekwencji jest bitem niskiego rzędu), a sekwencje ostatecznie jedynkowe jako ujemne liczby binarne (pomyśl o arytmetyce dopełnienia do dwóch z all-jedynkami sekwencja to $-1$ ). To sprawia, że liczby całkowite są algebrą Boole'a, gdzie suma to bitowe LUB, a dopełnienie to $-x-1$ . Istnieje tylko przeliczalnie wiele liczb całkowitych, więc ta nieskończona algebra Boole'a jest przeliczalna. Atomy są potęgami dwójki, a mianowicie 1,2,4,…. Innym sposobem opisania tej algebry jest zbiór wszystkich skończonych i koskończonych zbiorów liczb naturalnych, przy czym sekwencje ostatecznie zawierające wszystkie jedynki odpowiadają koskończonemu zbiory, czyli takie, które pomijają tylko skończenie wiele liczb naturalnych.

Przykład 5 . Sekwencja okresowa . Sekwencję nazywamy okresową, gdy istnieje pewna liczba $n > 0$ , zwana świadkiem okresowości, taka, że $x i = x i + n$ dla wszystkich $i \geq 0$ . Okres ciągu okresowego jest jego najmniejszym świadkiem. Negacja pozostawia kropkę niezmienioną, podczas gdy rozłączenie dwóch ciągów okresowych jest okresowe, z okresem co najwyżej najmniejszą wspólną wielokrotnością okresów dwóch argumentów (okres może wynosić zaledwie 1 , jak to się dzieje w przypadku sumy dowolnego ciągu $i$ jego komplement). Stąd okresowe sekwencje tworzą algebrę Boole'a.

$0$ Przykład 5 przypomina przykład 4, ponieważ jest policzalny, ale różni się tym, że jest pozbawiony atomów. To drugie jest spowodowane tym, że koniunkcja dowolnej niezerowej sekwencji okresowej $x$ z sekwencją o większym okresie jest ani ani $x$ . Można wykazać, że wszystkie przeliczalnie nieskończone algebry Boole'a bez atomów są izomorficzne, to znaczy, że aż do izomorfizmu istnieje tylko jedna taka algebra.

Przykład 6 . Sekwencja okresowa z okresem potęgi dwójki . To jest właściwa podalgebra przykładu 5 (właściwa podalgebra równa się przecięciu samej siebie z algebrą). Można je rozumieć jako operacje skończone, przy czym pierwszy okres takiej sekwencji daje tablicę prawdy operacji, którą reprezentuje. Na przykład tablica prawdy $x 0$ w tablicy operacji binarnych, a mianowicie $2 f 10$ , ma okres $2$ (więc można ją rozpoznać jako wykorzystującą tylko pierwszą zmienną), mimo że 12 operacji binarnych ma okres $4$ . Gdy okres wynosi $2 n$ , operacja zależy tylko od pierwszych $n$ zmiennych, w sensie, w jakim operacja jest skończona. Ten przykład jest również przeliczalnie nieskończoną algebrą Boole'a bez atomów. Stąd Przykład 5 jest izomorficzny z własną podalgebrą! Przykład 6, a tym samym przykład 5, stanowi swobodną algebrę Boole'a na przeliczalnie wielu generatorach, co oznacza algebrę Boole'a wszystkich operacji skończonych na przeliczalnie nieskończonym zbiorze generatorów lub zmiennych.

Przykład 7 . Ostatecznie sekwencje okresowe , sekwencje, które stają się okresowe po początkowym skończonym ataku bezprawia. Stanowią one właściwe rozszerzenie przykładu 5 (co oznacza, że przykład 5 jest właściwą podalgebrą przykładu 7), a także przykładu 4, ponieważ ciągi stałe są okresowe z okresem pierwszym. Sekwencje mogą się różnić pod względem tego, kiedy się ustalają, ale każdy skończony zestaw sekwencji ostatecznie ustali się nie później niż ich najwolniejszy do ustalenia element, skąd ostatecznie sekwencje okresowe są zamknięte pod wszystkimi operacjami boolowskimi i w ten sposób tworzą algebrę boolowską. Ten przykład ma takie same atomy i powłoki jak przykład 4, stąd nie jest pozbawiony atomów, a zatem nie jest izomorficzny z przykładem 5/6. Zawiera jednak nieskończoną bezatomową podalgebrę , a mianowicie Przykład 5, a więc nie jest izomorficzna z Przykładem 4, z której każda podalgebra musi być algebrą Boole'a skończonych zbiorów i ich dopełnień, a zatem atomową. Ten przykład jest izomorficzny z bezpośrednim iloczynem z przykładów 4 i 5, dostarczając jego innego opisu.

Przykład 8 . Bezpośredni iloczyn ciągu okresowego (przykład 5) z dowolną skończoną, ale nietrywialną algebrą Boole'a. (Trywialna jednoelementowa algebra Boole'a jest unikalną skończoną algebrą Boole'a bez atomów.) Przypomina to Przykład 7, ponieważ ma oba atomy i bezatomową podalgebrę , ale różni się tym, że ma tylko skończenie wiele atomów. Przykład 8 jest w rzeczywistości nieskończoną rodziną przykładów, po jednym dla każdej możliwej skończonej liczby atomów.

Te przykłady bynajmniej nie wyczerpują możliwych algebr Boole'a, nawet tych policzalnych. Rzeczywiście, istnieje niezliczona ilość nieizomorficznych przeliczalnych algebr Boole'a, które Jussi Ketonen [1978] całkowicie sklasyfikował pod względem niezmienników reprezentowanych przez pewne dziedzicznie policzalne zbiory.

Algebry Boole'a operacji boolowskich

Same $n$ -argumentowe operacje boolowskie tworzą potęgową algebrę zbiorów $2 W$ , a mianowicie gdy $W$ jest zbiorem $2 n$ wartościowań n $danych$ wejściowych. Pod względem systemu nazewnictwa operacji $n f i ,$ gdzie $i$ w systemie binarnym jest kolumną tabeli prawdy, kolumny można łączyć z operacjami boolowskimi o dowolnej liczbie liczbowej, aby uzyskać inne kolumny obecne w tabeli. Oznacza to, że możemy zastosować dowolną operację logiczną arity $m$ do $m$ Operację logiczną arity $n ,$ aby otrzymać operację logiczną arity $n$ dla dowolnych $m$ i $n$ .

Praktyczne znaczenie tej konwencji zarówno dla oprogramowania, jak i sprzętu polega na tym, że $n$ -argumentowe operacje boolowskie można przedstawić jako słowa o odpowiedniej długości. Na przykład każda z 256 trójskładnikowych operacji boolowskich może być reprezentowana jako bajt bez znaku. Dostępne operacje logiczne, takie jak AND i OR, można następnie wykorzystać do utworzenia nowych operacji. Jeśli przyjmiemy, że $x$ , $y$ i $z$ (na razie rezygnując ze zmiennych z indeksem dolnym) wynoszą odpowiednio $10101010$ , $11001100$ i $11110000 (170, 204 i 240 w systemie dziesiętnym,$ $0xaa$ , $0xcc$ i $0xf0$ w systemie szesnastkowym), ich koniunkcje parami są $x \land y = 10001000$ , $y \land z = 11000000$ , oraz $z \land x = 10100000$ , podczas gdy ich dysjunkcje parami to $x \lor y = 11101110$ , $y \lor z = 11111100$ , oraz $z \lor x = 11111010$ . Dysjunkcja trzech koniunkcji to $11101000$ , która jest również koniunkcją trzech koniunkcji. W ten sposób obliczyliśmy, za pomocą kilkunastu operacji logicznych na bajtach, że są to dwie operacje trójskładnikowe

{\ Displaystyle (x \ ziemia y) \ lor (y \ ziemia z) \ lor (z \ ziemia x)}

I

{\ Displaystyle (x \ lor y) \ ziemia (y \ lor z) \ ziemia (z \ lor x)}

są właściwie tą samą operacją. Oznacza to, że udowodniliśmy tożsamość równań

{\ Displaystyle (x \ ziemia y) \ lor (y \ ziemia z)\lor (z\land x)=(x\lor y)\land (y\lor z)\land (z\lor x)}

,

dla dwuelementowej algebry Boole'a. Zgodnie z definicją „algebry Boole'a” ta tożsamość musi zatem obowiązywać w każdej algebrze Boole'a.

Nawiasem mówiąc, ta trójskładnikowa operacja stała się podstawą trójskładnikowych algebr Boole'a Graua [1947], które aksjomatyzował w kategoriach tej operacji i negacji. Operacja jest symetryczna, co oznacza, że jej wartość jest niezależna od któregokolwiek z $3! = 6$ permutacji jego argumentów. Dwie połówki jej tablicy prawdy $11101000$ to tablice prawdy dla $\lor$ , $1110$ i $\land$ , $1000$ , więc operację można sformułować tak, jakby $z$ to $x \lor y$ inaczej $x \land y$ . Ponieważ jest symetryczny, równie dobrze można go sformułować jako if $x$ then $y \lor z$ else $y \land z$ , lub if $y$ then $z \lor x$ else $z \land x$ . Patrząc jako etykieta 8-wierzchołkowego 3-sześcianu, górna połowa jest oznaczona jako 1, a dolna połowa jako 0; z tego powodu nazwano go operatorem mediany , z ewidentnym uogólnieniem na dowolną nieparzystą liczbę zmiennych (nieparzystą, aby uniknąć remisu, gdy dokładnie połowa zmiennych wynosi 0).

Aksjomatyzacja algebr Boole'a

Technikę, której właśnie użyliśmy do udowodnienia tożsamości algebry Boole'a, można uogólnić na wszystkie tożsamości w systematyczny sposób, który można uznać za solidną i kompletną aksjomatyzację lub system aksjomatyczny równań logiki Boole'a . Zwyczajowe sformułowanie systemu aksjomatów składa się z zestawu aksjomatów, które „zalewają pompę” pewnymi początkowymi tożsamościami, wraz z zestawem reguł wnioskowania służących do wnioskowania o pozostałych tożsamościach z aksjomatów i wcześniej udowodnionych tożsamości. W zasadzie pożądane jest posiadanie skończenie wielu aksjomatów; jednak z praktycznego punktu widzenia nie jest to konieczne, ponieważ równie skuteczny jest posiadanie skończonego schematu aksjomatu mającego nieskończenie wiele przypadków, z których każdy, gdy jest użyty w dowodzie, można łatwo zweryfikować jako przypadek prawny, podejście, które tutaj stosujemy.

Tożsamości logiczne są twierdzeniami postaci $s = t$ , gdzie $s$ i $t$ są wyrazami $n$ -arnymi, przez co będziemy tutaj rozumieć wyrazy, których zmienne są ograniczone do $x 0$ do $x n-1$ . Wyrażeniem $n$ -arnym jest albo atom, albo aplikacja . Aplikacja $0 m f i (t,..., m -1) jest$ t parą składającą się z $m$ -operacji $m fi i$ listy lub $m$ -krotki $0 (t,..., t m -1)$ $m n$ -ary terminy zwane operandami .

Z każdym wyrazem związana jest liczba naturalna zwana jego wysokością . Atomy mają zerową wysokość, podczas gdy aplikacje mają wysokość jeden plus wysokość ich najwyższego operandu.

Czym jest atom? Konwencjonalnie atom jest albo stałą (0 lub 1), albo zmienną $x i,$ gdzie $0 \leq i < n$ . Dla techniki dowodowej wygodnie jest tutaj zdefiniować atomy jako operacje $n -arkowe$ $n f i$ , które chociaż traktowane tutaj jako atomy, to jednak oznaczają to samo, co zwykłe wyrazy dokładnej postaci $0 n fi (x, ..., x n -1)$ (dokładnie w tym, że zmienne muszą być wymienione w podanej kolejności bez powtórzeń lub pominięć). Nie jest to ograniczenie, ponieważ atomy tej postaci obejmują wszystkie zwykłe atomy, a mianowicie stałe 0 i 1, które powstają tutaj jako n $-$ ary operacje $n f 0$ i $n f -1$ dla każdego $n$ (w skrócie $2 2 n -1$ do $-1$ ), oraz zmienne $0 x,..., x n -1$ , jak widać z tablic prawdy, gdzie $x 0$ pojawia się zarówno jako operacja jednoargumentowa $1 f 2$ , jak i operacja binarna $2 f 10$ , podczas gdy $x 1$ pojawia się jako $2 f 12$ .

Poniższy schemat aksjomatów i trzy reguły wnioskowania aksjomatyzują algebrę Boole'a wyrazów n -arnych.

A1 .

m fa ja (n fa j 0,..., n fa j m -1) = n fi ja o ĵ

gdzie

(i o ĵ) v = ja ĵ v

, gdzie

ĵ

oznacza

j

transpozycję, określoną przez

(ĵ v) u = (jo u) v

.

R1 . Bez przesłanek wnioskować

t = t

.

R2 . Z

s = u

i

t = u

wywnioskować

s = t

, gdzie

s

,

t

i

u

są wyrazami

n -arnymi.

R3 . Z

00 s = t,..., s m -1 = t m -1

wywnioskować

00 m fa ja (s,..., s m -1) = m fa ja (t,..., t m ​​-1)

, gdzie wszystkie wyrazy

s i, t i

są

n

-ary.

Znaczenie warunku bocznego na A1 jest takie, że $io ĵ :$ jest tą $2 n$ -bitową liczbą, której $v$ -tym bitem jest $ĵ v$ -tym bitem $i$ , gdzie zakresy każdej wielkości to $u : m$ , $v 2 n$ , $j u : 2 2 n$ , i $ĵ v : 2 m$ . (Tak więc $j$ jest $m$ -krotką $2 n$ -bitowych liczb, podczas gdy $ĵ$ jako transpozycja $j$ jest $2 n$ -krotką $m$ -bitowych liczb. Zatem zarówno $j$ , jak i $ĵ$ zawierają $m 2 n$ bitów.)

A1 jest schematem aksjomatu, a nie aksjomatem, ponieważ zawiera metazmienne , a mianowicie $m$ , $i$ , $n$ oraz $j 0$ do $j m-1$ . Rzeczywiste aksjomaty aksjomatyzacji uzyskuje się przez ustawienie metazmiennych na określone wartości. Na przykład, jeśli weźmiemy $0 m = n = i = j = 1$ , możemy obliczyć dwa bity $i o ĵ$ z $i 1 = 0$ i $0 i = 1$ , więc $i o ĵ = 2$ (lub $10$ , gdy zapisujemy jako dwa -bitowa liczba). Wynikowy przypadek, a mianowicie $1 f 1 (1 f 1) = 1 f 2$ , wyraża znany aksjomat $\neg\neg x = x$ podwójnej negacji. Reguła R3 pozwala nam więc wywnioskować $\neg\neg\neg x = \neg x$ przyjmując, że $s 0$ wynosi $1 f 1 (1 f 1)$ lub $\neg\neg x 0$ , $t 0$ wynosi $1 f 2$ lub $x 0$ , a $m f i$ wynosi $1 f 1$ lub $\neg$ .

Dla każdego $m$ i $n$ istnieje tylko skończenie wiele aksjomatów tworzących A1 , mianowicie $2 2 m \times (2 2 n) m$ . Każda instancja jest określona przez $2 m + m 2 n$ bitów.

Traktujemy R1 jako regułę wnioskowania, nawet jeśli jest to aksjomat bez przesłanek, ponieważ jest to reguła niezależna od domeny, wraz z R2 i R3 , wspólna dla wszystkich aksjomatyzacji równań, czy to grup, pierścieni, czy jakiejkolwiek innej odmiany. Jedyną jednostką specyficzną dla algebr Boole'a jest schemat aksjomatu A1 . W ten sposób, mówiąc o różnych teoriach równań, możemy zepchnąć reguły na bok jako niezależne od poszczególnych teorii i ograniczyć uwagę do aksjomatów jako jedynej części systemu aksjomatów charakteryzującego daną teorię równań.

Ta aksjomatyzacja jest zupełna, co oznacza, że każde prawo Boole'a $s = t$ jest dowodliwe w tym systemie. Najpierw pokazuje się przez indukcję na wysokości $s$ , że każde prawo Boole'a, dla którego $t$ jest atomowe, jest możliwe do udowodnienia, używając R1 dla przypadku podstawowego (ponieważ różne atomy nigdy nie są równe) oraz A1 i R3 dla kroku indukcyjnego ( $s$ aplikacja). Ta strategia dowodzenia sprowadza się do rekurencyjnej procedury oceny $s$ w celu uzyskania atomu. Następnie, aby udowodnić $s = t$ w ogólnym przypadku, gdy $t$ może być zastosowaniem, wykorzystaj fakt, że jeśli $s = t$ jest tożsamością, to $s$ i $t$ muszą być obliczone na ten sam atom, nazwijmy go $u$ . Więc najpierw udowodnij $s = u$ i $t = u$ jak powyżej, to znaczy oceń $s$ i $t$ używając A1 , R1 i R3 , a następnie wywołaj R2, aby wywnioskować $s = t$ .

W A1 , jeśli potraktujemy liczbę $n m$ jako funkcję typu $m \to n$ , a $io ĵ m$ $n jako$ aplikację $m (n)$ , możemy zreinterpretować liczby $i$ , $j$ , $ĵ$ oraz jako funkcje typu $i : (m \to2)\to2$ , $jot : m \to((n \to2)\to2)$ , $ĵ : (n \to2)\to(m \to2)$ , oraz $ja o ĵ : (n \to2)\to2$ . Definicja $(io ĵ) v = i ĵ v ĵ$ w A1 przekłada się $) ĵ wtedy$ na $(io ĵ (v io = i (ĵ (v))$ $)$ , czyli jest zdefiniowane jako złożenie $i$ oraz rozumiane jako funkcje. Tak więc treść A1 sprowadza się do zdefiniowania zastosowania terminu, które ma być zasadniczo kompozycją, modulo potrzebę transpozycji $m$ -krotki $j$ , aby typy pasowały odpowiednio do kompozycji. Ta kompozycja należy do wspomnianej wcześniej kategorii zestawów mocy i ich funkcji Lawvere'a. W ten sposób przełożyliśmy diagramy komutacji tej kategorii, jako teorię równań algebr Boole'a, na równania konsekwencji A1 jako logicznej reprezentacji tego szczególnego prawa składu.

Podstawowa struktura kraty

Podstawą każdej algebry Boole'a $B$ jest częściowo uporządkowany zbiór lub poset $(B,\leq)$ . Relacja częściowego rzędu jest zdefiniowana przez $x \leq y$ tylko wtedy, gdy $x = x \land y$ , lub równoważnie, gdy $y = x \lor y$ . Mając zbiór $X$ elementów algebry Boole'a, górna granica na $X$ jest elementem $y$ takim, że dla każdego elementu $x$ z $X$ , $x \leq y$ , podczas gdy dolna granica na $X$ jest elementem $y$ takim, że dla każdego elementu $x$ z $X$ , $y \leq x$ .

Sup z $X$ to najmniejsza górna granica na $X$ $,$ a mianowicie górna granica na $X$ , która jest mniejsza lub równa każdej górnej granicy na X . Podwójnie an ( inf ) z $X$ jest największym dolnym ograniczeniem na $X.$ Sup $x$ i $y$ zawsze istnieje w podstawowej pozycji algebry Boole'a, będąc $x \lor y$ , podobnie istnieje ich inf, a mianowicie $x \land y$ . Pusty sup to 0 (dolny element), a pusty inf to 1 (górny). Wynika z tego, że każdy skończony zbiór ma zarówno sup, jak i inf. Nieskończone podzbiory algebry Boole'a mogą mieć lub nie mieć sup i / lub inf; w algebrze potęgowej zawsze to robią.

Dowolna pozycja $(B,\leq)$ taka, że każda para elementów $x, y$ ma zarówno sup, jak i inf, nazywana jest kratą . Piszemy $x \lor y$ dla sup i $x \land y$ dla inf. Podstawowa pozycja algebry Boole'a zawsze tworzy siatkę. Krata jest rozdzielna, gdy x $\land (y \lor z) = (x \land y) \lor (x \land z)$ , lub równoważnie, gdy $x \lor (y \land z) = (x \lor y) \land (x \lor z)$ , ponieważ jedno prawo implikuje drugie w sieci. Są to prawa algebry Boole'a, z których podstawowa pozycja algebry Boole'a tworzy siatkę rozdzielczą.

Dana krata z dolnym elementem 0 i górnym elementem 1, parę elementów $x, y$ nazywamy komplementarnymi, gdy $x \land y = 0$ i $x \lor y = 1$ , wtedy mówimy, że $y$ jest dopełnieniem $x$ i vice versa odwrotnie. Każdy element $x$ sieci rozdzielczej z górą i dołem może mieć co najwyżej jedno uzupełnienie. Kiedy każdy element sieci ma dopełnienie, kratę nazywamy dopełnieniem. Wynika z tego, że w uzupełnionej sieci rozdzielczej dopełnienie elementu zawsze istnieje i jest unikalne, co czyni uzupełnienie operacją jednoargumentową. Co więcej, każda dopełniona sieć rozdzielcza tworzy algebrę Boole'a i odwrotnie, każda algebra Boole'a tworzy dopełnioną siatkę rozdzielczą. Zapewnia to alternatywną definicję algebry Boole'a, a mianowicie jako dowolnej uzupełnionej sieci rozdzielczej. Każdą z tych trzech właściwości można aksjomatyzować za pomocą skończenie wielu równań, skąd te równania razem wzięte stanowią skończoną aksjomatyzację teorii równań algebr Boole'a.

W klasie algebr zdefiniowanej jako wszystkie modele zestawu równań, zwykle zdarza się, że niektóre algebry tej klasy spełniają więcej równań niż tylko tych potrzebnych do zakwalifikowania ich do klasy. Klasa algebr Boole'a jest niezwykła, ponieważ z jednym wyjątkiem każda algebra Boole'a spełnia dokładnie tożsamości Boole'a i nic więcej. Wyjątkiem jest jednoelementowa algebra Boole'a, która koniecznie spełnia każde równanie, nawet $x = y$ , i dlatego jest czasami nazywana niespójną algebrą Boole'a.

Homomorfizmy boolowskie

Homomorfizm Boole'a jest funkcją $h : A \to B$ między algebrami Boole'a $A, B$ taką, że dla każdej operacji Boole'a $m f i$ :

{\ Displaystyle h (^ {m} \!

Kategoria Bool algebr Boole'a ma jako obiekty wszystkie algebry Boole'a i jako morfizmy homomorfizmy Boole'a między nimi .

Istnieje unikalny homomorfizm od dwuelementowej algebry Boole'a 2 do każdej algebry Boole'a, ponieważ homomorfizmy muszą zachowywać dwie stałe, a to są jedyne elementy 2 . Algebrę Boole'a z tą właściwością nazywamy początkową algebrą Boole'a. Można wykazać, że dowolne dwie początkowe algebry Boole'a są izomorficzne, więc do izomorfizmu 2 jest początkową algebrą Boole'a.

W przeciwnym kierunku może istnieć wiele homomorfizmów od algebry Boole'a $B$ do 2 . $Każdy$ taki homomorfizm dzieli $B$ na te elementy odwzorowane na 1 i te na 0. Podzbiór $B$ składający się z pierwszego nazywa się ultrafiltrem B . Kiedy $B$ jest skończony, jego ultrafiltry łączą się w pary z jego atomami; jeden atom jest odwzorowany na 1, a reszta na 0. Każdy ultrafiltr $B$ składa się zatem z atomu $B$ i wszystkich pierwiastków nad nim; stąd dokładnie połowa pierwiastków $B$ znajduje się w ultrafiltrze, a ultrafiltrów jest tyle, ile jest atomów.

Dla nieskończonych algebr Boole'a pojęcie ultrafiltra staje się znacznie bardziej delikatne. Pierwiastki większe lub równe atomowi zawsze tworzą ultrafiltr, podobnie jak wiele innych zestawów; na przykład w algebrze Boole'a skończonych i koskończonych zestawów liczb całkowitych, zbiory koskończone tworzą ultrafiltr, mimo że żaden z nich nie jest atomem. Podobnie powerset liczb całkowitych ma wśród swoich ultrafiltrów zbiór wszystkich podzbiorów zawierających daną liczbę całkowitą; istnieje niezliczona ilość takich „standardowych” ultrafiltrów, które można identyfikować za pomocą samych liczb całkowitych, ale istnieje niezliczona liczba „niestandardowych” ultrafiltrów. Stanowią one podstawę do analizy niestandardowej , dostarczając reprezentacji dla takich klasycznie niespójnych obiektów, jak nieskończenie małe i funkcje delta.

Rozszerzenia nieskończone

Przypomnij sobie definicję sup i inf z powyższej sekcji dotyczącej leżącego u podstaw częściowego porządku algebry Boole'a. Kompletna algebra Boole'a to taka, której każdy podzbiór ma zarówno sup, jak i inf, nawet nieskończone podzbiory. Gaifman [1964] i Hales [1964] niezależnie wykazali, że nieskończenie wolne kompletne algebry Boole'a nie istnieją. Sugeruje to, że logika z operacjami nieskończonymi o zbiorze wielkości może mieć terminy obejmujące wiele klas - tak jak logika z operacjami skończonymi może mieć nieskończenie wiele terminów.

Istnieje jednak inne podejście do wprowadzania nieskończonych operacji boolowskich: po prostu usuń „finitarny” z definicji algebry Boole'a. Model teorii równań algebry wszystkich operacji na {0,1} arity aż do liczności modelu nazywany jest zupełną atomową algebrą Boole'a lub CABA . (Zamiast tego kłopotliwego ograniczenia arity moglibyśmy przyjąć dowolną arity, prowadzącą do innej niezręczności, że sygnatura byłaby wtedy większa niż jakikolwiek zbiór, to znaczy właściwa klasa. Jedną z zalet tego drugiego podejścia jest to, że upraszcza ono definicja homomorfizmu między CABA o różnej liczności .) Taką algebrę można równoważnie zdefiniować jako pełną algebrę Boole'a , czyli atomową , co oznacza, że każdy element jest sumą jakiegoś zbioru atomów. Wolne CABA istnieją dla wszystkich liczności zbioru $V$ generatorów , a mianowicie potęgowej algebry zbiorów 2 $2 V,$ co jest oczywistym uogólnieniem skończonych swobodnych algebr Boole'a. To zgrabnie ratuje nieskończoną logikę boolowską przed losem, na który wydawał się skazać wynik Gaifmana-Halesa.

Nieistnienie wolnych kompletnych algebr Boole'a można przypisać brakowi odpowiedniego rozszerzenia równań logiki Boole'a na wszystkie prawa, które powinny obowiązywać dla nieskończonej koniunkcji i alternatywy, w szczególności zaniedbanie rozdzielności w definicji pełnej algebry Boole'a. Kompletną algebrę Boole'a nazywamy całkowicie rozdzielczą , gdy dowolne koniunkcje rozkładają się na dowolne dysjunkcje i odwrotnie. Algebra Boole'a jest CABA wtedy i tylko wtedy, gdy jest kompletna i całkowicie rozdzielna, dając trzecią definicję CABA. Czwarta definicja jest jak każda algebra Boole'a izomorficzna z algebrą potęgową.

Pełen homomorfizm to taki, który zachowuje wszystkie istniejące supy, a nie tylko skończone supy, i podobnie dla infów. Kategoria CABA wszystkich CABA i ich zupełnych homomorfizmów jest dualna do kategorii zbiorów i ich funkcji, co oznacza, że jest równoważna z przeciwieństwem tej kategorii (kategorią wynikającą z odwrócenia wszystkich morfizmów). Sprawa nie jest taka prosta, aby kategoria Bool algebr Boole'a i ich homomorfizmów, którą w efekcie wykazał Marshall Stone (chociaż brakowało mu zarówno języka, jak i ram pojęciowych, aby wyraźnie uwidocznić dwoistość), była dualna w stosunku do kategorii całkowicie rozłączonych zwartych Hausdorffa przestrzenie , zwane dalej przestrzeniami kamiennymi .

Inną nieskończoną klasą pośrednią między algebrami Boole'a a kompletnymi algebrami Boole'a jest pojęcie sigma-algebry . Jest to definiowane analogicznie do pełnych algebr Boole'a, ale z sups i infs ograniczonymi do policzalnej arity. Oznacza to, że sigma-algebra jest algebrą Boole'a ze wszystkimi policzalnymi supami i infami. Ponieważ sups i infs mają ograniczoną liczność , w przeciwieństwie do sytuacji z kompletnymi algebrami Boole'a , wynik Gaifmana-Halesa nie ma zastosowania i istnieją wolne sigma-algebry . Jednak w przeciwieństwie do sytuacji z CABA, swobodna przeliczalnie generowana algebra sigma nie jest algebrą potęgową.

Inne definicje algebry Boole'a

Zetknęliśmy się już z kilkoma definicjami algebry Boole'a, jako modelu teorii równań algebry dwuelementowej, jako dopełnionej sieci rozdzielczej, jako pierścienia Boole'a oraz jako funktora zachowującego iloczyn z pewnej kategorii (Lawvere). Dwie kolejne definicje, o których warto wspomnieć, to:.

Stone (1936): Algebra Boole'a jest zbiorem wszystkich zbiorów domkniętych przestrzeni topologicznej . Nie jest ograniczeniem wymaganie, aby przestrzeń była całkowicie odłączoną zwartą przestrzenią Hausdorffa lub przestrzenią Stone'a , to znaczy każda algebra Boole'a powstaje w ten sposób, aż do izomorfizmu . Co więcej, jeśli dwie algebry Boole'a utworzone jako zbiory zamknięte dwóch przestrzeni Stone'a są izomorficzne, to samo przestrzenie Stone'a są również izomorficzne, co nie ma miejsca w przypadku dowolnych przestrzeni topologicznych. Jest to po prostu odwrotny kierunek wspomnianej wcześniej dualności z algebr Boole'a do przestrzeni Stone'a . Ta definicja jest uzupełniona następną definicją.

Johnstone (1982): Algebra Boole'a jest filtrowaną kolimitą skończonych algebr Boole'a.

(Kolistość w tej definicji można usunąć, zastępując „skończoną algebrę Boole'a” „skończonym zestawem potęg” wyposażonym w operacje logiczne standardowo interpretowane dla zbiorów potęg).

Aby spojrzeć na to z perspektywy, nieskończone zbiory powstają jako filtrowane współgranice zbiorów skończonych, nieskończone CABA jako filtrowane granice algebr zbiorów skończonej potęgi, a nieskończone przestrzenie Stone'a jako filtrowane granice zbiorów skończonych. Tak więc, jeśli ktoś zacznie od zbiorów skończonych i zapyta, w jaki sposób uogólniają się one na obiekty nieskończone, istnieją dwa sposoby: „dodanie” ich daje zbiory zwykłe lub indukcyjne, podczas gdy „mnożenie” ich daje przestrzenie Stone'a lub zbiory określone . Ten sam wybór istnieje dla algebr skończonych potęg jako liczb podwójnych zbiorów skończonych: dodawanie daje algebry Boole'a jako obiekty indukcyjne, podczas gdy mnożenie daje CABA lub algebry potęg jako obiekty określone.

Charakterystyczną cechą wyróżniającą jest to, że leżąca u podstaw topologia tak skonstruowanych obiektów, gdy jest zdefiniowana jako Hausdorff , jest dyskretna dla obiektów indukcyjnych i zwarta dla obiektów określonych. Topologia skończonych przestrzeni Hausdorffa jest zawsze zarówno dyskretna, jak i zwarta, podczas gdy dla przestrzeni nieskończonych „dyskretne” i „zwarte” wzajemnie się wykluczają. Tak więc, uogólniając algebry skończone (dowolnego rodzaju, nie tylko boolowskie) na algebry nieskończone, „dyskretne” i „zwarte” części firmy i trzeba wybrać, którą z nich zachować. Ogólna zasada, zarówno dla algebr skończonych, jak i nieskończonych, jest taka, że algebry skończone są dyskretne, podczas gdy ich liczby dualne są zwarte i zawierają operacje na nieskończonościach. Pomiędzy tymi dwoma skrajnościami istnieje wiele pośrednich nieskończonych algebr Boole'a, których topologia nie jest ani dyskretna, ani zwarta.

Zobacz też

Birkhoff, Garrett (1935). „O strukturze algebr abstrakcyjnych”. proc. Kamba. Phil. soc . 31 (4): 433–454. Bibcode : 1935PCPS...31..433B . doi : 10.1017/s0305004100013463 . ISSN 0008-1981 . S2CID 121173630 .
Boole, George (2003) [1854]. Badanie praw myśli . Książki Prometeusz. ISBN 978-1-59102-089-9 .
Dwinger, Filip (1971). Wprowadzenie do algebr Boole'a . Würzburg: Physica Verlag.
Gaifman, Haim (1964). „Nieskończone wielomiany logiczne, I” . Fundamenta Mathematicae . 54 (3): 229–250. doi : 10.4064/fm-54-3-229-250 . ISSN 0016-2736 .
Givant, Steven; Halmos, Paweł (2009). Wprowadzenie do algebr Boole'a . Teksty licencjackie z matematyki . Skoczek. ISBN 978-0-387-40293-2 .
Grau, AA (1947). „Trójskładnikowa algebra Boole'a” . Byk. Jestem. Matematyka soc . 33 (6): 567–572. doi : 10.1090/S0002-9904-1947-08834-0 .
Hales, Alfred W. (1964). „O nieistnieniu wolnych kompletnych algebr Boole'a” . Fundamenta Mathematicae . 54 : 45–66. doi : 10.4064/fm-54-1-45-66 . ISSN 0016-2736 .
Halmos, Paweł (1963). Wykłady z algebr Boole'a . van Nostranda. ISBN 0-387-90094-2 .
Givant, Steven; Halmos, Paweł (1998). Logika jako algebra . Ekspozycja matematyczna Dolcianiego. Amerykańskie Stowarzyszenie Matematyczne . ISBN 978-0-883-85327-6 .
Johnstone, Peter T. (1982). Kamienne Przestrzenie . Cambridge, Wielka Brytania: Cambridge University Press. ISBN 978-0-521-33779-3 .
Ketonen, Jussi (1978). „Struktura policzalnych algebr Boole'a”. Roczniki matematyki . 108 (1): 41–89. doi : 10.2307/1970929 . JSTOR 1970929 .
Koppelberg, Sabine (1989) „Ogólna teoria algebr Boole'a” w Monk, J. Donald i Bonnet, Robert, red., Handbook of Boolean Algebras, tom. 1 . Północna Holandia. ISBN 978-0-444-70261-6 .
Peirce, CS (1989) Pisma Charlesa S. Peirce'a: wydanie chronologiczne: 1879–1884 . Kloesel, CJW, wyd. Indianapolis: Indiana University Press. ISBN 978-0-253-37204-8 .
Lawvere, F. William (1963). „Semantyka funkcjonalna teorii algebraicznych” . Obrady Narodowej Akademii Nauk . 50 (5): 869–873. Bibcode : 1963PNAS...50..869L . doi : 10.1073/pnas.50.5.869 . PMC 221940 . PMID 16591125 .
Schröder, Ernst (1890–1910). Vorlesungen über die Algebra der Logik (exakte Logik), I–III . Lipsk: BG Teubner.
Sikorski, Roman (1969). Algebry Boole'a (wyd. 3). Berlin: Springer-Verlag. ISBN 978-0-387-04469-9 .
Kamień, MH (1936). „Teoria reprezentacji dla algebr Boole'a”. Transakcje Amerykańskiego Towarzystwa Matematycznego . 40 (1): 37–111. doi : 10.2307/1989664 . ISSN 0002-9947 . JSTOR 1989664 .
Tarski, Alfred (1983). Logika, semantyka, metamatematyka , Corcoran, J., wyd. Hackett. 1956 1. wydanie zredagowane i przetłumaczone przez JH Woodgera, Oxford Uni. Naciskać. Zawiera angielskie tłumaczenia następujących dwóch artykułów:
- Tarskiego, Alfreda (1929). „Sur les classs zamyka par rapport à surees opérations élémentaires”. Fundamenta Mathematicae . 16 : 195–97. ISSN 0016-2736 .
- Tarskiego, Alfreda (1935). „Zur Grundlegung der Booleschen Algebra, I” . Fundamenta Mathematicae . 24 : 177–98. doi : 10.4064/fm-24-1-177-198 . ISSN 0016-2736 .
Władimirow, DA (1969). булевы алгебры ( algebry Boole'a , tłumaczenie rosyjskie, niemieckie Boolesche Algebren 1974) . Nauka (niemieckie tłumaczenie Akademie-Verlag).

Bibliografia