Boolesche Algebra (Struktur) - Boolean algebra (structure)

In der abstrakten Algebra ist eine Boolesche Algebra oder ein Boolesches Gitter ein komplementiertes Verteilungsgitter . Diese Art der algebraischen Struktur erfaßt wesentliche Eigenschaften beiden Sätze Operationen und logischen Operationen. Eine Boolesche Algebra kann als Verallgemeinerung einer Potenzmengenalgebra oder eines Mengenkörpers angesehen werden , oder ihre Elemente können als verallgemeinerte Wahrheitswerte angesehen werden . Es ist auch ein Sonderfall einer De Morgan-Algebra und einer Kleene-Algebra (mit Involution) .

Jede Booleschen Algebra gibt Anlass zu einem booleschen Ring , und umgekehrt, mit Ring Multiplikation mit entsprechender Verbindung oder treffen sie ∧, und Ring neben exklusiver Disjunktion oder symmetrische Differenz (nicht Disjunktion ∨). Die Theorie der Booleschen Ringe weist jedoch eine inhärente Asymmetrie zwischen den beiden Operatoren auf, während die Axiome und Theoreme der Booleschen Algebra die Symmetrie der Theorie ausdrücken, die durch das Dualitätsprinzip beschrieben wird .

Boolesches Gitter von Teilmengen

Geschichte

Der Begriff "Boolesche Algebra" ehrt George Boole (1815–1864), einen autodidaktischen englischen Mathematiker. Er stellte das algebraische System zunächst in einer kleinen Broschüre vor, The Mathematical Analysis of Logic , die 1847 als Reaktion auf eine anhaltende öffentliche Kontroverse zwischen Augustus De Morgan und William Hamilton veröffentlicht wurde , und später als umfangreicheres Buch, The Laws of Thought , veröffentlicht in 1854. Booles Formulierung unterscheidet sich in einigen wichtigen Punkten von der oben beschriebenen. Konjunktion und Disjunktion in Boole waren beispielsweise kein duales Operationspaar. Boolesche Algebra entstand in den 1860er Jahren in Papieren von William Jevons und Charles Sanders Peirce . Die erste systematische Darstellung der Booleschen Algebra und der Verteilungsgitter ist den Vorlesungen von Ernst Schröder von 1890 zu verdanken . Die erste umfassende Behandlung der Booleschen Algebra in englischer Sprache ist die Universal Algebra von AN Whitehead aus dem Jahr 1898 . Boolesche Algebra als axiomatische algebraische Struktur im modernen axiomatischen Sinne beginnt mit einer 1904 erschienenen Arbeit von Edward V. Huntington . Boolesche Algebra wurde mit den Arbeiten von Marshall Stone in den 1930er Jahren und mit Garrett Birkhoffs 1940er Gittertheorie als ernsthafte Mathematik erwachsen . In den 1960er Jahren fanden Paul Cohen , Dana Scott und andere tiefgreifende neue Ergebnisse in der mathematischen Logik und der axiomatischen Mengenlehre unter Verwendung von Ablegern der Booleschen Algebra, nämlich erzwingenden und Boolesch bewerteten Modellen .

Definition

Eine Boolesche Algebra ist ein Sechs- Tupel bestehend aus einer Menge A , ausgestattet mit zwei binären Operationen ¬ (genannt "Treffen" oder "und"), ∨ (genannt "Join" oder "oder"), einer unären Operation ¬ (genannt " Komplement" oder "nicht") und zwei Elemente 0 und 1 in A (genannt "unten" und "oben" oder "kleinstes" und "größtes" Element, auch bezeichnet durch die Symbole ⊥ bzw. ⊤), so dass für alle Elemente a , b und c von A , gelten die folgenden Axiome :

a ∨ ( bc ) = ( ab ) ∨ c a ∧ ( bc ) = ( ab ) ∧ c Assoziativität
ab = ba ab = ba Kommutativität
a ∨ ( ab ) = a a ∧ ( ab ) = a Absorption
a 0 = a a 1 = a Identität
a ∨ ( bc ) = ( ab ) ∧ ( ac )   a ∧ ( bc ) = ( ab ) ∨ ( ac )   Verteilbarkeit
a ∨ ¬ a = 1 a ∧ ¬ a = 0 ergänzt

Beachten Sie jedoch, dass das Absorptionsgesetz und sogar das Assoziativitätsgesetz aus der Menge der Axiome ausgeschlossen werden können, da sie von den anderen Axiomen abgeleitet werden können (siehe Bewiesene Eigenschaften ).

Eine Boolesche Algebra mit nur einem Element wird als triviale Boolesche Algebra oder als degenerierte Boolesche Algebra bezeichnet . (In älteren Werken verlangten einige Autoren, dass 0 und 1 unterschiedliche Elemente sind, um diesen Fall auszuschließen.)

Aus den letzten drei obigen Axiompaaren (Identität, Distributivität und Komplemente) oder aus dem Absorptionsaxiom folgt, dass

a = ba     genau dann, wenn     ab = b .

Die durch ab definierte Beziehung , wenn diese äquivalenten Bedingungen zutreffen, ist eine partielle Ordnung mit kleinstem Element 0 und größtem Element 1. Das Treffen ab und die Verbindung ab zweier Elemente fallen mit ihrem Infimum bzw. Supremum zusammen , bezüglich .

Die ersten vier Axiomenpaare bilden eine Definition eines beschränkten Gitters .

Aus den ersten fünf Axiomenpaaren folgt, dass jedes Komplement eindeutig ist.

Die Menge der Axiome ist selbstdual in dem Sinne, dass, wenn man in einem Axiom ∨ mit ∧ und 0 mit 1 vertauscht, das Ergebnis wieder ein Axiom ist. Wenn man diese Operation auf eine Boolesche Algebra (oder ein Boolesches Gitter) anwendet, erhält man daher eine andere Boolesche Algebra mit den gleichen Elementen; es wird sein Dual genannt .

Beispiele

0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
ein 0 1
¬ a 1 0
  • Es hat Anwendungen in der Logik und interpretiert 0 als falsch , 1 als wahr , ∧ als und , ∨ als oder und ¬ als nicht . Ausdrücke mit Variablen und booleschen Operationen stellen Anweisungsformen dar, und zwei solcher Ausdrücke können mit den obigen Axiomen genau dann als gleich dargestellt werden, wenn die entsprechenden Anweisungsformen logisch äquivalent sind .
  • Die aus zwei Elementen bestehende Boolesche Algebra wird auch für den Schaltungsentwurf in der Elektrotechnik verwendet ; hier repräsentieren 0 und 1 die zwei unterschiedlichen Zustände eines Bits in einer digitalen Schaltung , typischerweise Hoch- und Niederspannung . Schaltkreise werden durch Ausdrücke beschrieben, die Variablen enthalten, und zwei solcher Ausdrücke sind für alle Werte der Variablen genau dann gleich, wenn die entsprechenden Schaltkreise das gleiche Eingabe-Ausgabe-Verhalten aufweisen. Darüber hinaus kann jedes mögliche Eingabe-Ausgabe-Verhalten durch einen geeigneten Booleschen Ausdruck modelliert werden.
  • Die zweielementige Boolesche Algebra ist auch in der allgemeinen Theorie der Booleschen Algebra wichtig, da eine Gleichung mit mehreren Variablen im Allgemeinen in allen Booleschen Algebren genau dann wahr ist, wenn sie in der zweielementigen Booleschen Algebra wahr ist (was überprüft werden kann durch ein trivialer Brute-Force- Algorithmus für eine kleine Anzahl von Variablen). Damit lässt sich beispielsweise zeigen, dass die folgenden Gesetze ( Konsenssätze ) in allen Booleschen Algebren allgemein gültig sind:
    • ( ab ) ∧ (¬ ac ) ∧ ( bc ) ≡ ( ab ) ∧ ( ¬ ac )
    • ( ab ) ∨ (¬ ac ) ∨ ( bc ) ≡ ( ab ) ∨ (¬ ac )
  • Die Potenzmenge (Menge aller Teilmengen) einer beliebigen gegebenen nichtleeren Menge S bildet eine Boolesche Algebra, eine Algebra von Mengen , mit den beiden Operationen ∨ := ∪ (Vereinigung) und ∧ := ∩ (Schnittpunkt). Das kleinste Element 0 ist die leere Menge und das größte Element 1 ist die Menge S selbst.
  • Nach der Booleschen Algebra mit zwei Elementen ist die einfachste Boolesche Algebra diejenige, die durch die Potenzmenge zweier Atome definiert wird:
0 ein B 1
0 0 0 0 0
ein 0 ein 0 ein
B 0 0 B B
1 0 ein B 1
0 ein B 1
0 0 ein B 1
ein ein ein 1 1
B B 1 B 1
1 1 1 1 1
x 0 ein B 1
¬ x 1 B ein 0
  • Die Menge aller Teilmengen von S , die entweder endlich oder kofinit sind, ist eine Boolesche Algebra, eine Algebra von Mengen .
  • Bilden Sie ausgehend vom Aussagenkalkül mit κ Satzsymbolen die Lindenbaum-Algebra (d. h. die Menge der Sätze in der modulologischen Äquivalenz des Aussagenkalküls ). Diese Konstruktion ergibt eine Boolesche Algebra. Es ist tatsächlich die freie Boolesche Algebra auf κ-Generatoren. Eine Wahrheitszuordnung in der Aussagenlogik ist dann ein Boolescher Algebra-Homomorphismus von dieser Algebra zur zweielementigen Booleschen Algebra.
  • Bei einer gegebenen linear geordneten Menge L mit dem kleinsten Element ist die Intervallalgebra die kleinste Algebra von Teilmengen von L, die alle halboffenen Intervalle [ a , b ) enthält, so dass a in L und b entweder in L oder gleich ist . Intervallalgebren sind beim Studium der Lindenbaum-Tarski-Algebren nützlich ; jede abzählbare Boolesche Algebra ist isomorph zu einer Intervallalgebra.
Hasse-Diagramm der Booleschen Algebra der Teiler von 30.
  • Für jede natürliche Zahl n bildet die Menge aller positiven Teiler von n , die ab definieren, wenn a b teilt , ein Verteilungsgitter . Dieses Gitter ist eine Boolesche Algebra , wenn und nur wenn n ist Platz frei . Das untere und das oberste Element dieser Booleschen Algebra ist die natürliche Zahl 1 bzw. n . Das Komplement von a ist gegeben durch n / a . Das Treffen und das Verbinden von a und b wird durch den größten gemeinsamen Teiler (gcd) bzw. das kleinste gemeinsame Vielfache (lcm) von a bzw. b gegeben . Die Ringaddition a + b ist gegeben durch lcm( a , b )/gcd( a , b ). Das Bild zeigt ein Beispiel für n = 30. Als Gegenbeispiel wäre unter Berücksichtigung des nicht quadratfreien n = 60 der größte gemeinsame Teiler von 30 und seinem Komplement 2 2, während es das unterste Element 1 sein sollte.
  • Andere Beispiele für Boolesche Algebren ergeben sich aus topologischen Räumen : Wenn X ein topologischer Raum ist, dann bildet die Sammlung aller Teilmengen von X, die sowohl offene als auch geschlossene sind, eine Boolesche Algebra mit den Operationen ∨ := ∪ (Vereinigung) und ∧ := ∩ (Überschneidung).
  • Ist R ein beliebiger Ring und definieren wir die Menge der zentralen Idempotenten durch
    A = { eR  : e 2 = e , ex = xe , ∀ xR }
    dann wird die Menge A zu einer Booleschen Algebra mit den Operationen ef  : = e + f - ef und ef  : = ef .

Homomorphismen und Isomorphismen

Ein Homomorphismus zwischen zwei Booleschen Algebren A und B ist eine Funktion f  : AB mit für alle a , b in A :

f ( ab ) = f ( a ) ∨ f ( b ),
f ( ab ) = f ( a ) ∧ f ( b ),
f (0) = 0,
f (1) = 1.

Daraus folgt fa ) = ¬ f ( a ) für alle a in A . Die Klasse aller Booleschen Algebren bildet zusammen mit diesem Morphismusbegriff eine vollständige Unterkategorie der Kategorie der Gitter.

Ein Isomorphismus zwischen zwei Booleschen Algebren A und B ist ein Homomorphismus f  : AB mit einem inversen Homomorphismus, also ein Homomorphismus g  : BA mit der Zusammensetzung gf : AA ist die Identitätsfunktion auf A , und die Zusammensetzung fg : BB ist die Identitätsfunktion auf B . Ein Homomorphismus boolescher Algebren ist genau dann ein Isomorphismus, wenn er bijektiv ist .

Boolesche Ringe

Jede Boolesche Algebra ( A , ∧, ∨) führt zu einem Ring ( A , +, ·) durch Definition von a + b  := ( a ∧ ¬ b ) ∨ ( b ∧ ¬ a ) = ( ab ) . ¬ ( ab ) (diese Operation heißt symmetrische Differenz bei Mengen und XOR bei Logik) und a · b  := ab . Das Nullelement dieses Rings fällt mit der 0 der Booleschen Algebra zusammen; das multiplikative Identitätselement des Rings ist die 1 der Booleschen Algebra. Dieser Ring hat die Eigenschaft, dass a · a = a für alle a in A ; Ringe mit dieser Eigenschaft werden Boolesche Ringe genannt .

Umgekehrt können wir einen gegebenen Booleschen Ring A in eine Boolesche Algebra umwandeln, indem wir xy  := x + y + ( x · y ) und xy  := x · y definieren . Da diese beiden Konstruktionen Inverse zueinander sind, können wir sagen, dass jeder Boolesche Ring aus einer Booleschen Algebra entsteht und umgekehrt. Außerdem ist eine Abbildung f  : AB genau dann ein Homomorphismus von Booleschen Algebren, wenn sie ein Homomorphismus von Booleschen Ringen ist. Die Kategorien der Booleschen Ringe und Booleschen Algebren sind äquivalent.

Hsiang (1985) gab einen regelbasierten Algorithmus an, um zu überprüfen, ob zwei beliebige Ausdrücke in jedem Booleschen Ring denselben Wert bezeichnen. Ganz allgemein haben Boudet, Jouannaud und Schmidt-Schauß (1989) einen Algorithmus zum Lösen von Gleichungen zwischen beliebigen Booleschen Ringausdrücken angegeben . Durch die Ähnlichkeit von Booleschen Ringen und Booleschen Algebren haben beide Algorithmen Anwendungen im automatisierten Theorembeweisen .

Ideale und Filter

Ein Ideal der Boolesche Algebra A ist eine Teilmenge I so dass für alle x , y in I haben wir xy in I und für alle ein in A haben wir einx in I . Dieser Begriff der idealen fällt mit dem Begriff des Ring ideal in der Booleschen Ring A . Ein ideal ich von A heißt Primzahl , wenn ichA und wenn einb in I impliziert immer eine in I oder b in I . Außerdem gilt für jedes aA , dass a-a = 0 ∈ I und dann aI oder -aI für jedes aA , falls I prim ist. Ein idealer ich von A heißt maximal , wenn ichA und wenn das einzige Ideal richtig enthält I ist A selbst. Für ein ideales I , wenn aI und -aI , dann I ∪ { a } oder I ∪ { -a } richtig in einem anderen enthalten sind ideal J . Daher ist an I nicht maximal und daher sind die Begriffe Primideal und maximales Ideal in Booleschen Algebren äquivalent. Darüber hinaus stimmen diese Begriffe mit ringtheoretischen des Primideals und des maximalen Ideals im Booleschen Ring A überein .

Das Dual eines Ideals ist ein Filter . Ein Filter der Booleschen Algebra A ist eine Teilmenge p , so dass für alle x , y in p haben wir xy in p und für alle a in A haben wir einx in p . Das Dual eines maximalen (oder Primzahl ) Ideals in einer Booleschen Algebra ist Ultrafilter . Ultrafilter können alternativ als 2-wertige Morphismen von A bis zur Booleschen Algebra mit zwei Elementen beschrieben werden. Die Aussage , jeder Filter in einer Booleschen Algebra kann zu einer Ultrafiltrations verlängert wird der genannte Ultra Satz und kann nicht in bewiesen werden , ZF , wenn ZF ist konsistent . Innerhalb von ZF ist es strikt schwächer als das Auswahlaxiom . Das Ultrafilter-Theorem hat viele äquivalente Formulierungen: Jede Boolesche Algebra hat einen Ultrafilter , jedes Ideal in einer Booleschen Algebra kann zu einem Primideal erweitert werden usw.

Vertretungen

Es kann gezeigt werden, dass jede endliche Boolesche Algebra isomorph zur Booleschen Algebra aller Teilmengen einer endlichen Menge ist. Daher ist die Anzahl der Elemente jeder endlichen Booleschen Algebra eine Zweierpotenz .

Stones berühmtes Darstellungstheorem für Boolesche Algebren besagt, dass jede Boolesche Algebra A isomorph zur Booleschen Algebra aller clopen- Mengen in einem ( kompakten total unzusammenhängenden Hausdorff ) topologischen Raum ist.

Axiomatik

Die erste Axiomatisierung von Booleschen Gittern/Algebren im Allgemeinen wurde 1898 von dem englischen Philosophen und Mathematiker Alfred North Whitehead gegeben . Sie beinhaltete die obigen Axiome und zusätzlich x ∨1=1 und x ∧0=0. 1904 gab der amerikanische Mathematiker Edward V. Huntington (1874–1952) die wohl sparsamste Axiomatisierung nach ∧, ∨, ¬ und bewies sogar die Assoziativitätsgesetze (siehe Kasten). Er bewies auch, dass diese Axiome unabhängig voneinander sind. 1933 führte Huntington die folgende elegante Axiomatisierung für die Boolesche Algebra aus. Es erfordert nur eine binäre Operation + und ein unäres Funktionssymbol n , um als 'Komplement' gelesen zu werden, die die folgenden Gesetze erfüllen:

  1. Kommutativität : x + y = y + x .
  2. Assoziativität : ( x + y ) + z = x + ( y + z ).
  3. Huntington-Gleichung : n ( n ( x ) + y ) + n ( n ( x ) + n ( y )) = x .

Herbert Robbins fragte sofort: Wenn die Huntington-Gleichung durch ihre duale ersetzt wird, nämlich:

4. Robbins-Gleichung : n ( n ( x + y ) + n ( x + n ( y ))) = x ,

bilden (1), (2) und (4) eine Basis für die Boolesche Algebra? Wenn man (1), (2) und (4) eine Robbins-Algebra nennt , stellt sich die Frage: Ist jede Robbins-Algebra eine Boolesche Algebra? Diese Frage (die als Robbins-Vermutung bekannt wurde ) blieb jahrzehntelang offen und wurde zu einer Lieblingsfrage von Alfred Tarski und seinen Schülern. Im Jahr 1996 William McCune bei Argonne National Laboratory ist jeder Robbins Algebra eine Boolesche Algebra: von Larry Wos, Steve Winker auf früheren Arbeiten Bau und Bob Veroff, antwortete Robbins Frage bejaht. Ausschlaggebend für McCunes Beweis war das von ihm entwickelte Computerprogramm EQP . Für eine Vereinfachung des Beweises von McCune siehe Dahn (1998).

Es wurde weiter daran gearbeitet, die Zahl der Axiome zu reduzieren; siehe Minimale Axiome für Boolesche Algebra .

Verallgemeinerungen

Das Entfernen der Forderung der Existenz einer Einheit aus den Axiomen der Booleschen Algebra ergibt "verallgemeinerte Boolesche Algebren". Formal ist eine distributive Gitter B ist ein verallgemeinertes Boolesche Gitter, wenn es ein kleinstes Element 0 und für alle Elemente hat ein und b in B , so dass einb , gibt es ein Element x , so dass ein ∧ x = 0 und a ∨ x = b. Definieren wir a ∖ b als das eindeutige x mit (a ∧ b) ∨ x = a und (a ∧ b) ∧ x = 0, sagen wir, dass die Struktur (B,∧,∨,∖,0) ein verallgemeinertes Boolean . ist Algebra , während (B,∨,0) ein verallgemeinertes Boolesches Halbgitter ist . Verallgemeinerte Boolesche Gitter sind genau die Ideale von Booleschen Gittern.

Eine Struktur, die alle Axiome für Boolesche Algebren mit Ausnahme der beiden Distributivitätsaxiome erfüllt, wird als orthokomplementäres Gitter bezeichnet . Orthokomplementierte Gitter entstehen in der Quantenlogik natürlich als Gitter geschlossener Unterräume für separierbare Hilberträume .

Siehe auch

Anmerkungen

Verweise

zitierte Werke

  • Davey, BA; Priestley, HA (1990). Einführung in Gitter und Ordnung . Cambridge Mathematische Lehrbücher. Cambridge University Press.
  • Cohn, Paul M. (2003), Basic Algebra: Groups, Rings, and Fields , Springer, S. 51, 70–81, ISBN 9781852335878
  • Givant, Steven; Halmos, Paul (2009), Einführung in die Boolesche Algebren , Undergraduate Texts in Mathematics , Springer , ISBN 978-0-387-40293-2.
  • Goodstein, RL (2012), "Chapter 2: The self-dual system of axioms" , Boolesche Algebra , Courier Dover Publications, S. 21ff, ISBN 9780486154978
  • Huntington, Edward V. (1904). „Sätze unabhängiger Postulate für die Algebra der Logik“ . Transaktionen der American Mathematical Society . 5 (3): 288–309. doi : 10.1090/s0002-9947-1904-1500675-4 . JSTOR  1986459 .
  • Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), Axiome für Gitter und Boolesche Algebren , World Scientific, ISBN 978-981-283-454-6.
  • Stein, Marshall H. (1936). "Theorie der Darstellungen für Boolesche Algebra" . Transaktionen der American Mathematical Society . 40 : 37–111. doi : 10.1090/s0002-9947-1936-1501865-8 .
  • Whitehead, AN (1898). Eine Abhandlung über die universelle Algebra . Cambridge University Press. ISBN 978-1-4297-0032-0.

Allgemeine Referenzen

Externe Links