pierścień logiczny - Boolean ring

W matematyce , A logiczny pierścień R jest pierścieniem , dla którego x 2 = x dla wszystkich x w B , to jest pierścień, który składa się tylko z elementów idempotentnych . Przykładem jest pierścień liczb całkowitych modulo 2 .

Każdy pierścień Boole'a daje początek algebrze Boole'a , z mnożeniem pierścienia odpowiadającym koniunkcji lub spotkaniu ∧ i dodawaniu pierścienia do wyłącznej alternatywy lub różnicy symetrycznej (nie alternatywy ∨, która stanowiłaby semiring ). Pierścienie Boole'a zostały nazwane na cześć założyciela algebry Boole'a, George'a Boole'a .

Notacje

Istnieją co najmniej cztery różne i niezgodne systemy notacji dla pierścieni i algebr Boole'a:

  • W algebrze przemiennej standardową notacją jest użycie x  +  y = ( x  ∧ ¬  y ) ∨ (¬  x  ∧  y ) dla sumy pierścieniowej x i y , a xy = x  ∧  y dla ich iloczynu.
  • W logice , wspólne oznaczenie jest użycie x  ∧  y do spotykają (sam produkt) oraz zastosowanie pierścienia x  ∨  y do łączenia, ponieważ chodzi o zapisie pierścieniowej (podano tylko wyżej) x  +  y  +  xy .
  • W teorii mnogości i logice często używa się x  ·  y dla spotkania, a x  +  y dla połączenia x  ∨  y . To użycie + różni się od użycia w teorii pierścieni.
  • Rzadką konwencją jest używanie xy jako iloczynu i x  ⊕  y jako sumy pierścienia, aby uniknąć niejednoznaczności +.

Historycznie, termin „pierścień Boole'a” był używany w znaczeniu „pierścień Boole'a prawdopodobnie bez tożsamości”, a „algebra Boole'a” był używany do oznaczania pierścienia Boole'a z tożsamością. Istnienie identyczności jest konieczne, aby uznać pierścień za algebrę nad ciałem dwóch elementów : w przeciwnym razie nie może być homomorfizmu (jednostkowego) pierścienia ciała dwóch elementów w pierścieniu Boole'a. (Jest to to samo, co dawne użycie terminów „pierścień” i „algebra” w teorii miary ).

Przykłady

Jednym z przykładów pierścienia Boole'a jest zbiór potęg dowolnego zbioru X , gdzie dodawanie w pierścieniu jest różnicą symetryczną , a mnożenie jest przecięciem . Jako inny przykład, możemy również rozważyć zbiór wszystkich skończonych lub koskończonych podzbiorów X , ponownie z symetryczną różnicą i przecięciem jako operacjami. Bardziej ogólnie w tych operacjach każde pole zbiorów jest pierścieniem logicznym. Według twierdzenia Stone'a o reprezentacji każdy pierścień Boole'a jest izomorficzny z polem zbiorów (traktowanym jako pierścień z tymi operacjami).

Związek z algebrami Boole'a

Diagramy Venna dla operacji logicznych koniunkcji, alternatywy i dopełnienia

Ponieważ operacja łączenia ∨ w algebrze Boole'a jest często zapisywana addytywnie, w tym kontekście sensowne jest oznaczenie dodawania pierścienia przez ⊕, symbol często używany do oznaczenia wyłączności lub .

Mając pierścień logiczny R , dla x i y w R możemy zdefiniować

x ∧ Y = oksy ,
x ∨ y = x ⊕ Y ⊕ XY ,
¬ x = 1 ⊕ x .

Operacje te następnie spełniają wszystkie aksjomaty dla spełnienia, złączenia i uzupełnień w algebrze Boole'a . W ten sposób każdy pierścień Boole'a staje się algebrą Boole'a. Podobnie, każda algebra Boole'a staje się pierścieniem Boole'a w ten sposób:

XY = x ∧ Y ,
x ⊕ Y = ( x ∨ y ) ∧ Ź ( x ∧ y ).

Jeśli pierścień Boole'a jest tłumaczony na algebrę Boole'a w ten sposób, a następnie algebra Boole'a jest tłumaczona na pierścień, wynikiem jest oryginalny pierścień. Analogiczny wynik ma początek od algebry Boole'a.

Odwzorowanie między dwoma pierścieniami Boole'a jest homomorfizmem pierścienia wtedy i tylko wtedy, gdy jest homomorfizmem odpowiednich algebr Boole'a. Co więcej, podzbiór pierścienia Boole'a jest ideałem pierścienia ( ideał pierwszego pierścienia, ideał maksymalnego pierścienia) wtedy i tylko wtedy, gdy jest ideałem rzędu ( ideał pierwszego rzędu, ideał maksymalnego rzędu) algebry Boole'a. Pierścień iloraz z logicznego pierścienia modulo jest pierścień idealne, odpowiada Algebra czynnikiem odpowiadającym Boole'a modulo odpowiedniej kolejności ideału.

Właściwości pierścieni logicznych

Każdy pierścień logiczny R spełnia x ⊕ x = 0 dla wszystkich x w R , ponieważ wiemy

x ⊕ x = ( x ⊕ x ) 2 = x 2 ⊕ x 2 ⊕ x 2 ⊕ x 2 = x ⊕ x ⊕ x ⊕ x

a ponieważ ( R ,⊕) jest grupą abelową, możemy odjąć x ⊕ x od obu stron tego równania, co daje x ⊕ x = 0. Podobny dowód pokazuje, że każdy pierścień Boole'a jest przemienny :

x ⊕ Y = ( x ⊕ r ) 2 = x 2 ⊕ XY ⊕ yx ⊕ r 2 = x ⊕ XY ⊕ yx ⊕ Y

a to daje xy ⊕ yx = 0, co oznacza xy = yx (przy użyciu pierwszej właściwości powyżej).

Własność x ⊕ x = 0 pokazuje, że każdy pierścień Boole'a jest algebrą asocjacyjną nad ciałem F 2 z dwoma elementami, dokładnie w jeden sposób. W szczególności, każdy ograniczony logiczny pierścień ma na liczność do potęgi dwójki . Nie każda unitarna algebra asocjacyjna nad F 2 jest pierścieniem Boole'a: rozważmy na przykład pierścień wielomianowy F 2 [ X ].

Pierścień ilorazowy R / I dowolnego pierścienia Boole'a R modulo dowolny I jest ponownie pierścieniem Boole'a. Podobnie każdy podpierścień pierścienia Boole'a jest pierścieniem Boole'a.

Każda lokalizacja pierścienia Boole'a R przez zbiór jest pierścieniem Boole'a, ponieważ każdy element w lokalizacji jest idempotentny.

Pierścień ilość ilorazów (w sensie Utumi i Lambek ) z logicznego pierścień B jest pierścieniem logiczne, ponieważ każda częściowa endomorfizm jest idempotent.

Każdy ideał pierwszy P w pierścieniu boolowskim R jest maksymalny : pierścień ilorazowy R / P jest domeną integralną, a także pierścieniem boolowskim, a więc jest izomorficzny z polem F 2 , które pokazuje maksymalizację P . Ponieważ ideały maksymalne są zawsze pierwsze, ideały pierwsze i ideały maksymalne pokrywają się w pierścieniach logicznych.

Pierścienie Boole'a są regularnymi pierścieniami von Neumanna .

Pierścienie logiczne są absolutnie płaskie: oznacza to, że każdy moduł nad nimi jest płaski .

Każdy skończenie wygenerowany ideał pierścienia Boole'a jest zasadniczy (w rzeczywistości ( x , y ) = ( x  +  y  +  xy )).

Zjednoczenie

Unifikacja w pierścieniach Boole'a jest rozstrzygalna , to znaczy istnieją algorytmy do rozwiązywania dowolnych równań na pierścieniach Boole'a. Zarówno unifikacja, jak i dopasowanie w skończenie generowanych wolnych pierścieniach boolowskich są NP-zupełne , a oba są NP-twarde w skończenie prezentowanych pierścieniach boolowskich. (W rzeczywistości, ponieważ każdy problem unifikacji f ( X ) = g ( X ) w pierścieniu boolowskim można przepisać jako problem dopasowania f ( X ) + g ( X ) = 0, problemy są równoważne.)

Unifikacja w pierścieniach Boole'a jest unitarna jeśli wszystkie niezinterpretowane symbole funkcji są nullą i skończoną w przeciwnym wypadku (tzn. jeśli symbole funkcji nie występujące w sygnaturze pierścieni Boole'a są wszystkimi stałymi to istnieje najogólniejszy unifikator , w przeciwnym razie minimalny kompletny zestaw unifikatorów jest skończona).

Zobacz też

Uwagi

Bibliografia

Dalsza lektura

Zewnętrzne linki