Algebra Boole'a (struktura)

W matematyce , A Boole'a , czasem logiczny pierścień , jest algebraiczna struktura badano w szczególności logikę matematycznej . Algebrę Boole'a można zdefiniować jako konkretną uporządkowaną strukturę , określoną strukturę algebraiczną lub (unitarny) pierścień, w którym każdy element jest równy swojemu kwadratowi.

Dla każdego zbioru zbiór jego części jest algebrą Boole'a, związanym z nim porządkiem jest włączenie, a prawa pierścienia są symetryczną różnicą i przecięciem . Innym przykładem jest zbiór formuł rachunku zdań , które prowadzą do równoważności (w logice klasycznej) (na pewnej liczbie zmiennych o dowolnej liczności), przy czym porządek związany jest relacją konsekwencji logicznej, a prawa pierścieniowe wyłączną dysjunkcję i koniunkcję .

Definicje

Algebra Boole'a jako krata

Algebra Boole'a E to krata z większymi i mniejszymi elementami , z których każda z dwóch operacji na dolnej granicy i górnej granicy jest dystrybucyjna względem drugiej i której każdy element ma dopełnienie. Innymi słowy :

• ( E , ≤) jest zbiorem uporządkowanym  ;
• Dwa elementy , b z E mają górną granicę, znany w sekwencji A ∨ B , a dolna granica zaznaczono w sekwencji A ∧ b (to jest kratownica );
• Jest mniejszy element, odnotowany w sekwencji 0 (często jest to również odnotowywane ), i większy element odnotowany w sekwencji 1 (często jest również odnotowywany );⊥{\ displaystyle \ bot}⊤{\ displaystyle \ top}
• Działanie rozdzielające jest ∧ na działanie ∨, a operacja jest ∨ rozdzielcze na działanie ∧, to znaczy dla wszystkich a , b i c w E  :

a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ), a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c );

• dla każdego elementu A z E , istnieje element a ' z E , zwanej uzupełnieniem od E i zaspokajaniu:

a ∧ a ' = 0 i a ∨ a' = 1.

Zatem algebra Boole'a jest kratą rozdzielczą, ograniczoną (najmniejszym i największym elementem) i uzupełnioną. Wystarczyłoby podać jedno z praw rozdzielczych, jedno angażujące drugie w kratkę (patrz powiązany artykuł).

Pokazujemy, że każdy element ma niepowtarzalne dopełnienie. Rzeczywiście, jeśli a 1 i a ' są uzupełnieniami a , korzystając z właściwości dopełnień, rzędu i rozdzielności otrzymujemy:

a 1 = ( a ∧ a ' ) ∨ a 1 = ( a ∨ a 1 ) ∧ ( a' ∨ a 1 ) = a ' ∨ a 1

to znaczy a ' ≤ a 1 . W ten sam sposób a 1 = a ' ∧ a 1 , więc a 1 ≤ a' , stąd równość.

Przez unikalność dodatku do wniosku, że jest związany z jego dopełnieniem jest inwolucji ( a „” = ). Wymienia 0 i 1 . Również poprzez wyjątkowość dopełnienia i dystrybucję pokazujemy, że przejście do wymiany dopełniacza ∧ i ∨, są to prawa De Morgana (patrz następny akapit).

Na podstawie aksjomatów rzędu wnioskujemy, że operacje ∧ i ∨ są asocjacyjne , przemienne , że 0 jest neutralne dla ∨ i absorbujące dla ∧, że 1 jest neutralne dla ∧ i absorbujące dla ∨ oraz że te operacje są idempotentne .

Algebra Boole'a jako struktura algebraiczna

Uprzednio uporządkowana struktura jest kratą i dlatego można ją zdefiniować algebraicznie, bezpośrednio w kategoriach dwóch operacji binarnych, które są dolną i górną granicą, jednoargumentowej operacji przechodzenia do dopełnienia i dwóch stałe 0 i 1. Algebrę Boole'a można zatem zdefiniować jako strukturę ( E , ∧, ∨, (.) ', 0, 1) spełniającą wszystkie elementy a , b i c elementu E :

Krata rozdzielcza z mniejszymi i większymi elementami
( a ∧ b ) ∧ c = a ∧ ( b ∧ c )	i	( a ∨ b ) ∨ c = a ∨ ( b ∨ c )	(skojarzenie)
a ∧ b = b ∧ a	i	a ∨ b = b ∨ a	(przemienność)
a ∧ a = a	i	a ∨ a = a	(idempotencja)
1 ∧ a = a	i	0 ∨ a = a	(element neutralny)
0 ∧ a = 0	i	1 ∨ a = 1	(element chłonny)
a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c )	i	a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c )	(dystrybucja)
Komplement
a ∧ a ' = 0	i	a ∨ a ' = 1	(komplement)
a '' = a			(uzupełnij niewolę)
( a ∧ b ) '= a ' ∨ b '	i	( a ∨ b ) '= a ' ∧ b '	(Prawa De Morgana)

Prawa absorpcji są wyprowadzane z dystrybucji przez prawa elementów neutralnych, absorbujących i przemienności ( a ∧ ( a ∨ b ) = ( a ∨ 0) ∧ ( a ∨ b ) = a ∨ (0 ∧ b ) = a ∨ 0 = a )

a ∧ ( a ∨ b ) = a

i

a ∨ ( a ∧ b ) = a

(wchłanianie)

Relację porządku można zdefiniować na dwa sposoby (zwrotność porządku wyprowadzana jest z idempotencji, antysymetria z przemienności i przechodniość asocjatywności dla operacji w zabawie):

a ≤ b jest równoważne a ∧ b = a

a ≤ b jest równoważne a ∨ b = b

Ten system aksjomatów jest łatwy w użyciu do demonstracji, ale jest bardzo zbędny. Gdy znajdujemy definicję sieci w kategoriach relacji porządku z aksjomatów kratowych, nieważność dopełnienia, prawa De Morgana i fakt, że 0 i 1 są absorbujące, są wyprowadzane z innych aksjomatów, jak w poprzednim akapicie. Jedną z możliwości (między innymi) jest ograniczenie się do jedynych aksjomatów elementu neutralnego, dopełnienia, przemienności i dystrybutywności.

Symetria systemu aksjomatów uwydatnia dwoistość algebr Boole'a.

Algebra Boole'a jako pierścień

Równoważnie algebrę Boole'a można również zdefiniować jako pierścień Boole'a , czyli pierścień, w którym każdy element jest idempotentny . Struktura ( E , +, •, 0, 1) jest więc pierścieniem boolowskim, jeśli spełnia tożsamości:

( a + b ) + c = a + ( b + c )	(skojarzenie +)
a + b = b + a	(przemienność +)
0 + a = a	(element neutralny +)
Każdy element a ma swoje przeciwieństwo , oznaczone przez −a  :
(- a ) + a = 0	(naprzeciwko)
( a • b ) • c = a • ( b • c )	(asocjatywność •)
1 • a = a	(element neutralny •)
a • ( b + c ) = a • b + a • c	(dystrybucja po lewej)
( b + c ) • a = b • a + c • a	(prawo dystrybucyjne)
a • a = a	(idempotencja)

Z idempotencji iloczynu wnioskujemy, obliczając na dwa sposoby ( a + a ) 2 (rozkłady) i upraszczając, że każdy element jest swoim własnym przeciwieństwem, to znaczy, że pierścień boolowski ma cechę 2:

a + a = 0

(element jest swoim przeciwieństwem)

Pierścień jest więc algebrą nad ciałem dwuelementowym .

Z idempotencji zawsze wnioskujemy, obliczając na dwa sposoby ( a + b ) 2 , że a • b + b • a = 0, a więc przemienność mnożenia, zgodnie z poprzednią własnością:

a • b = b • a

(przemienność •)

Prawa pierścieni różnią się od praw algebry Boole'a z poprzedniego akapitu, w szczególności tylko mnożenie jest rozdzielne po dodaniu.

Z algebry Boole'a ( E , ∧, ∨, 0, 1) otrzymujemy pierścień Boole'a ustawiając

• a • b = a ∧ b
• a + b = ( a ∧ b ' ) ∨ ( a' ∧ b )

stałe 0 i 1 są zachowywane. Weryfikacja tożsamości pierścieni odbywa się bezpośrednio, przy użyciu tożsamości algebry Boole'a z poprzedniego akapitu.

I odwrotnie, z pierścienia Boole'a ( E , +, •, 0, 1) otrzymujemy algebrę Boole'a ustawiając:

• a ∧ b = a • b
• a ' = 1 + a
• a ∨ b = a + b + a • b

i sprawdzenie, czy neutralne elementy 0 i 1 są rzeczywiście najmniejszymi i największymi elementami. W szczególności w pierścieniu boolowskim znajdujemy strukturę uporządkowaną według:

• a ≤ b wtedy i tylko wtedy, gdy a = a • b

Tutaj również weryfikacja tożsamości algebry jest wykonywana w prosty sposób, przy użyciu tożsamości pierścienia Boole'a (włączając przemienność i charakterystykę 2).

Poniżej nazywamy algebrę lub pierścień Boole'a jedną podobną do drugiej.

Przykłady algebr Boole'a

Jeśli 0 = 1, algebra Boole'a ma tylko jeden element, mówi się, że jest zdegenerowana lub trywialna .

Dwuelementowa algebra Boole'a

Niezdegenerowana algebra Boole'a ma co najmniej dwa odrębne elementy 0 i 1, a najprostszą algebrą Boole'a jest algebra dwuelementowa. Możemy to postrzegać jako zbiór dwóch wartości prawdy {Fałsz, Prawda} logiki klasycznej. Jako pierścień jest Z / 2 Z , a ze względu na idempotencję prawa mnożenia jest jedynym pierścieniem boolowskim integrującym , a więc jedynym, który jest ciałem .

Algebra Boole'a części zbioru

Zbiór części dowolnego zbioru A , uporządkowanych przez włączenie, jest algebrą Boole'a. Dolna granica to przecięcie, górna granica związek, dopełnienie przejście do komplementarnego w A , zbiór pusty i A to elementy neutralne, a dodatek symetryczna różnica. Kiedy A jest puste, algebra Boole'a jest zdegenerowana. Kiedy A jest singletonem , znajdujemy dwuelementową algebrę Boole'a z poprzedniego akapitu.

Algebra Lindenbauma

Zbiór formuł rachunku zdań ilorazowych przez relację równoważności logicznej (dwa formuły zdań są równoważne, gdy mają tę samą tablicę prawdy ), przy czym relacja dedukcyjna jako relacja porządku jest (w logice klasycznej) algebrą Boole'a.

Mówiąc bardziej ogólnie, dla dowolnej teorii T rachunku predykatów, zbiór zdań (formuł zamkniętych) języka tej teorii, ilorazowany przez relację równoważności w T i jako relację porządku, relację dedukcji w T , jest algebrą Boole'a, algebra Lindenbaum teoria T .

Dolna granica jest określona przez koniunkcję, górna przez dysjunkcję, a dopełnienie przez negację. Klasa równoważności zdania zawsze fałszywego daje punkt neutralny dla dysjunkcji, a klasa równoważności zdania zawsze prawdziwego daje punkt neutralny dla koniunkcji. Dodatek wynika z wyłącznej dysjunkcji.

Algebra Lindenbauma rachunku zdań na nieskończoność, na przykład policzalnych, zmiennych różni się od zbioru części zbioru, ponieważ każdy element ma niezerową ścisłą dolną granicę (w połączeniu ze zmienną zdaniową nieobecną w formuła), co nie ma miejsca w przypadku singletonów dla zbioru części zbioru.

Dwoistość

Biorąc pod uwagę wyrażenie boolowskie napisane tylko ze stałymi i algebraicznymi operacjami na sieciach (0, 1, ∧, ∨, () '), wyrażenie dualne tego wyrażenia jest otrzymane przez zamianę górnej granicy ∨ i dolnej granicy ∧ z' na z jednej strony, 0 i 1 z drugiej strony. Na przykład, oto wyrażenie na dodanie pierścieni boolowskich (różnica symetryczna) i jego podwójne wyrażenie:

podwójny ( a ∧ b ' ) ∨ ( a' ∧ b ) to ( a ∨ b ' ) ∧ ( a' ∨ b )

Ta definicja jest uogólniona na instrukcje przez podstawienie. W przypadku drugiej definicji jako kraty algebraicznej, aksjomaty algebry Boole'a są przedstawione parami, przy czym jeden z nich jest zdaniem dualnym drugiego. W konsekwencji, każdemu twierdzeniu algebr Boole'a sformułowanym w tym języku odpowiada twierdzenie dualne: jest to zasada dualności dla algebr Boole'a.

Na przykład, prawa absorpcji są dwojakie: wystarczy więc udowodnić jedno i wywnioskować, że drugie jest twierdzeniem o dualności.

Dualizm przekształca porządek w jego odwrotny porządek: podwójna forma a ≤ b ( a ∧ b = a ) to a ≥ b ( a ∨ b = a ).

Sprawdzamy, czy dwoistość wyrażenia logicznego f ( p 1 , ..., p n ) to (f ( p ' 1 , ..., p' n )) '.

Podalgebry

Logiczna podalgebrą jest podpierścień z logicznego Algebra jako pierścień jednostkowych, to jest (w tym szczególnym przypadku) stabilny podzbioru dodawania, mnożenia i posiadające ten sam element mnożnikowy obojętne. Pokazujemy, że podalgebry Boole'a są podzbiorami algebr Boole'a zawierającymi 0 i 1, stabilnymi przez górną granicę, dolną granicę i komplementarność (fakt, że podalgebra ma, jako podpierścień, ten sam multiplikatywny punkt neutralny, jest niezbędny dla stabilności poprzez przełączanie do uzupełnienia, które należy zapewnić). Aby sprawdzić, czy podzbiór algebry Boole'a jest podalgebrą, wystarczy sprawdzić stabilność przez dopełnienie za pomocą jednej z dwóch operacji ∧, ∨ i że 0 lub 1 należy do tego podzbioru.

Przykładem podalgebry boolowskiej zbioru części zbioru nieskończonego jest zbiór skończonych i ko-skończonych (tj. Skończonych dopełnień) części tego samego zbioru.

Jeśli F jest ścisłym podzbiorem E , zbiór części F jest algebrą Boole'a, która jest podzbiorem zbioru części E , ale która nie jest podalgebrą Boole'a, ponieważ elementy maksymalne ( E i F ) nie są tak samo, jak uzupełnienia.

Morfizmy

Morfizmy algebry Boole'a są typowymi (jednostkowymi) morfizmami pierścieniowymi dla struktury pierścienia Boole'a.

Równoważnie, to morfizmy kratowe przechodzą do dopełnienia (wystarczy wtedy sprawdzić, czy górne lub dolne granice są przestrzegane przez prawa De Morgana).

Ukończ algebrę Boole'a

Każdy skończony podzbiór algebry Boole'a ma górną granicę i dolną granicę.

Mówi się, że algebra Boole'a jest kompletna, jeśli jest pełną kratą , tj. Jeśli wszystkie jej podzbiory (skończone lub nieskończone) mają górną granicę i dolną granicę (w rzeczywistości wystarczy jedna z dwóch hipotez).

Przykłady i kontrprzykłady:

• każda skończona algebra Boole'a jest oczywiście kompletna;
• algebra Boole'a części zbioru jest kompletna: każda rodzina podzbiorów ma górną granicę, która jest sumą tych podzbiorów, i dolną granicę, która jest przecięciem tych podzbiorów;
• algebra Boole'a skończonych lub ko- skończonych części zbioru nieskończonego nie jest kompletna;
• algebra Lindenbauma rachunku zdań na nieskończoność zmiennych.
• Dowolna algebra Boole'a A jest podalgebrą pełnej algebry Boole'a B, tak że każdy element B jest górną granicą części A. B nazywa się uzupełnieniem A. Jest unikalne dla izomorfizmu w pobliżu.

Atomy

W algebrze Boole'a pojęcie atomu jest tym, co odpowiada singletonom w algebrze Boole'a części zbioru. Jednak algebra Boole'a niekoniecznie zawiera atomy.

Definicja

Atom z Boole'a B jest elementem mającą inne surowe dolnej granicy od 0:

a jest atomem wtedy i tylko wtedy, gdy dla dowolnego elementu x z B , 0 ≤ x ≤ a ⇒ ( x = 0 lub x = a ).

Jest natychmiastowe, że singletony są atomami algebry Boole'a części zbioru. Ta ostatnia ma również tę właściwość, że każdy niezerowy pierwiastek jest zredukowany o co najmniej jeden atom: mówi się, że taka algebra Boole'a jest atomowa . Istnieją również algebry Boole'a bez atomów, takie jak algebra Lindenbauma rachunku zdań na nieskończoność zmiennych.

Skończone algebry Boole'a

Każda skończona algebra Boole'a jest izomorficzna ze zbiorem części skończonego zbioru, który jest zbiorem atomów algebry. Jego liczność to zatem potęga 2.

Ideały i filtry

Ideały algebry Boole'a są ideałami algebry jako pierścienia przemiennego. Stabilność ideału przez pomnożenie przez dowolny element algebry powoduje, że ideał jest początkową sekcją uporządkowanej struktury. Możemy scharakteryzować ideały w kategoriach kraty  ; podzbiór I z E jest ideałem algebry Boole'a ( E , ≤, ∧, ∨, 0, 1), gdy spełnia:

• 0 ∈ I
• ∀ x , y ∈ I x ∨ y ∈ I  ;
• ∀ x ∈ I ∀ y ∈ E ( y ≤ x ⇒ y ∈ I ).

Ideał właściwy jest ideałem różnym od całej algebry, koniecznie nie zawiera elementu maksymalnego 1. Nie może zatem zawierać elementu x i jego uzupełnienia 1 + x .

Podwójne pojęcie ideału właściwego to filtr  : podzbiór algebry jest filtrem, jeśli zbiór jego uzupełnień jest ideałem. Dokładniej, podzbiór F z E jest filtrem algebry Boole'a ( E , ≤, ∧, ∨, 0, 1), gdy spełnia:

• 1 ∈ F i 0 ∉ F  ;
• ∀ x , y ∈ F x ∧ y ∈ F  ;
• ∀ x ∈ F ∀ y ∈ E ( y ≥ x ⇒ y ∈ F ).

Odwzorowanie, które z elementem x wiąże jego dopełnienie x ', ustanawia bijekcję między filtrami i ideałami.

Maksymalna idealny jest idealny maksymalny w sensie inkluzji wśród właściwych ideałów. Podwójna koncepcja to ultrafiltr  : ultrafiltr jest filtrem maksymalnym w sensie włączenia, a także jest zbiorem uzupełnień ideału maksymalnego.

Twierdzenie o maksymalnym ideale lub twierdzenie Krulla stwierdza, że ​​każdy ideał jest zawarty w ideale maksymalnym. W przypadku algebr Boole'a daje przez dualność twierdzenie o ultrafiltrze: każdy filtr jest zawarty w ultrafiltrze.

Iloraz z logicznego Algebra przez maksymalną ideału jest pole z dwoma elementami {0, 1}, jedyny logicznego pierścienia, który jest pole, związane kanoniczne morfizmem ma zatem wartość {0, 1}.

Ogólnie rzecz biorąc, w danej algebrze Boole'a jest to równoważne dać sobie maksymalny ideał, ultrafiltr lub morfizm tej algebry Boole'a w {0,1}, jądro takiego morfizmu jest ideałem maksymalnym, a zbiór elementy o wartości 1 przez ten morfizm jako ultrafiltr.

Twierdzenie Stone'a

Widzieliśmy, że skończona algebra Boole'a jest izomorficzna ze zbiorem części zbioru, w tym przypadku z jego atomami. Twierdzenie Stone'a o reprezentacji umożliwia uogólnienie tego wyniku na dowolną algebrę Boole'a w tym sensie, że w ogólnym przypadku algebra Boole'a jest izomorficzna z podalgebrą zbioru części zbioru.

Konieczne jest rozważenie podalgebr: algebra Lindebauma rachunku zdań na nieskończoność zmiennych zdaniowych lub izomorficznie algebra Boole'a swobodnie generowana przez nieskończoność pierwiastków nie jest atomowa (patrz wyżej ), dlatego nie może być izomorficzna ze zbiorem części zestawu.

Zgodnie z powszechnym podejściem w teorii pierścieni , dany zbiór można wybrać jako zbiór maksymalnych ideałów algebry Boole'a A lub, w przypadku algebr Boole'a, jako zbiór S ( A ) homomorfizmów tej algebry w {0 1}, zwana przestrzeń kamienia z A . Następnie sprawdzamy, czy poniższa mapa jest iniekcyjnym morfizmem A w zbiorze ? ( S ( A )) części przestrzeni Kamienia:

φ:W→P.(S(W))x↦{godz∈S(W)∣godz(x)=1}{\ Displaystyle \ varphi: {\ początek {tablica} {lcl} A i \ do i {\ mathcal {P}} \ lewo (S (A) \ prawej) \\ x i \ mapsto & \ {h \ w S (A) \ mid h (x) = 1 \} \ end {tablica}}}

Kiedy weźmiemy pod uwagę S (A) jako podzbiór 2 A , zbiór funkcji z A w {0,1} wyposażonych w topologię iloczynu , S (A) jest przestrzenią Stone , tj. Całkowicie nieciągłą przestrzenią zwartą . Przyjmuje jako otwartą podstawę swoje otwarte-zamknięte części (clopen). Obraz morfizmu jest więc dokładnie zbiorem otwartego-zamkniętego S (A). φ{\ displaystyle \ varphi}

I odwrotnie, jeśli X jest przestrzenią Kamienia, to zbiór jego otwarto-zamkniętych wyposażonych w zwykłe operacje na zbiorach tworzy algebrę Boole'a.

Na tym podwójnym korespondencyjny reprezentacji Stone'a twierdzenie ustanawia functorially się równoważność między kategorii algebr Boole'a i że miejsc kamienia.

Uwagi i odniesienia

1. Patrz Cori i Lascar 1993 , str.  96 dla tej charakterystyki.
2. Ten system aksjomatów dla algebr Boole'a jest podany w Givant i Halmos 2009 , s.  10.
3. z Givant i Halmos 2009 , s.  10, charakterystyka wynikająca „zasadniczo” z EV Huntingtona  (en) , w: Zestawy niezależnych postulatów algebry logiki , Transactions of the American Mathematical Society, vol. 5 (1904), str.  288–309  ; Huntington dał jeszcze kilka.
4. Definicja algebry Boole'a w Cori i Lascar 1993 , s.  91.
5. Takie użycie znaku „+” jest sprzeczne z pewną tradycją przedstawiania rachunku Boole'a , który zauważa „+” operację „∨”, a prawo zaznacza, że ​​„+” jest zakreślone lub zaznaczone XOR.⊕{\ displaystyle \ oplus}
6. Givant i Halmos 2009 , s.  10.
7. Cori i Lascar 1993 , s.  99.
8. Givant i Halmos 2009 , s.  188-192, Cori i Lascar 1993 , s.  120-126.

Zobacz też

Powiązane artykuły

• Algebra Boole'a wolna  (in)
• Kamienna przestrzeń
• Twierdzenie Stone'a o reprezentacji
• Prawa myśli
• Lista tematów związanych z algebrą Boole'a

Bibliografia

• René Cori i Daniel Lascar , Logika matematyczna I. Rachunek zdań, algebry Boole'a, rachunek predykatów ,1993[ szczegóły wydań ] , rozdz.  2.
• (en) Steven Givant i Paul Halmos , Wprowadzenie do algebr boolowskich , Springer ,2009, 574,  str. ( ISBN  978-0-387-40293-2 ).
• Daniel Ponasse, Logika matematyczna , Rozdział V: Aspekt algebraiczny - struktura pierścieni Boole'a, edytor OCDL, Paryż, 1967.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">