In der abstrakten Algebra, einer Algebra von Boolean oder dem Gitter von Boolean ist ein ergänztes verteilendes Gitter. Dieser Typ der algebraischen Struktur gewinnt wesentliche Eigenschaften sowohl von Satz-Operationen als auch von Logikoperationen. Eine Boolean Algebra kann als eine Generalisation einer Macht-Satz-Algebra oder ein Feld von Sätzen gesehen werden. Es ist auch ein spezieller Fall der Algebra von De Morgan und Algebra von Kleene.

Geschichte

Der Begriff "Algebra von Boolean" ehrt George Boole (1815-1864), einen autodidaktischen englischen Mathematiker. Er hat das algebraische System am Anfang in einer kleinen Druckschrift, Die Mathematische Analyse der Logik, veröffentlicht 1847 als Antwort auf eine andauernde öffentliche Meinungsverschiedenheit zwischen Augustus De Morgan und William Hamilton, und später als ein wesentlicheres Buch, Die Gesetze des Gedankens, veröffentlicht 1854 eingeführt. Die Formulierung von Boole unterscheidet sich davon, das oben in etwas wichtiger Hinsicht beschrieben ist. Zum Beispiel waren Verbindung und Trennung in Boole nicht ein Doppelpaar von Operationen. Algebra von Boolean ist in den 1860er Jahren in Zeitungen erschienen, die von William Jevons und Charles Sanders Peirce geschrieben sind. Die erste systematische Präsentation der Algebra von Boolean und verteilenden Gitter wird zu 1890-Vorlesungen von Ernst Schröder geschuldet. Die erste umfassende Behandlung der Algebra von Boolean in Englisch ist 1898 von A. N. Whitehead Universale Algebra. Die Algebra von Boolean als eine axiomatische algebraische Struktur im modernen axiomatischen Sinn beginnt mit einem 1904-Vortrag von Edward Vermilye Huntington. Algebra von Boolean ist volljährig als ernste Mathematik mit der Arbeit des Steins von Marschall in den 1930er Jahren, und mit der 1940-Gitter-Theorie von Garrett Birkhoff gekommen. In den 1960er Jahren, Paul Cohen, Dana Scott, und haben andere tief neue Ergebnisse in der mathematischen axiomatischen und Logikmengenlehre mit Sprössen der Algebra von Boolean gefunden, nämlich zwingend und GeBoolean-schätzten Modelle.

Definition

Eine Boolean Algebra ist ein sechs-Tupel-, der aus einem Satz A besteht, ausgestattet mit zwei binären Operationen  (genannt "treffen sich" oder "und"),  (genannt "schließen sich an" oder "oder"), eine unäre Operation ¬ (genannt "Ergänzung" oder "nicht") und zwei Elemente 0 und 1 (manchmal angezeigt durch die Symbole  und , beziehungsweise), solch, dass für alle Elemente a, b und c von A, die folgenden Axiome halten:

::

Eine Boolean Algebra mit nur einem Element wird eine triviale Algebra von Boolean oder eine degenerierte Algebra von Boolean genannt. (Einige Autoren verlangen 0 und 1, verschiedene Elemente zu sein, um diesen Fall auszuschließen.)

Es folgt aus den letzten drei Paaren von Axiomen oben (Identität, distributivity und Ergänzungen) das

:: = b  wenn und nur wenn ein  b = b.

Die Beziehung  definiert durch einen  b wenn, und nur wenn die obengenannten gleichwertigen Bedingungen halten, ist eine teilweise Ordnung mit kleinstem Element 0 und größtem Element 1. Das Entsprechen eines  b und der Verbindungslinie ein  b zwei Elemente fällt mit ihrem infimum und Supremum beziehungsweise in Bezug auf  zusammen.

Als in jedem begrenzten Gitter befriedigen die Beziehungen  und  die ersten drei Paare von Axiomen oben; das vierte Paar ist gerade distributivity. Da die Ergänzungen in einem verteilenden Gitter einzigartig sind, die Involution ¬ es zu definieren, genügt, um ¬ als die Ergänzung von a zu definieren.

Der Satz von Axiomen ist im Sinn Selbstdoppel-, dass, wenn man  mit  und 0 mit 1 in einem Axiom austauscht, das Ergebnis wieder ein Axiom ist. Deshalb, indem man diese Operation auf eine Algebra von Boolean (oder Gitter von Boolean) anwendet, erhält man eine andere Algebra von Boolean mit denselben Elementen; es wird seinen Doppel-genannt.

Beispiele

• Die einfachste nichttriviale Algebra von Boolean, die Zwei-Elemente-Algebra von Boolean, hat nur zwei Elemente, 0 und 1, und wird durch die Regeln definiert:

|

| Breite = "30" |

||

| Breite = "40" |

|| }\

:* Es hat Anwendungen in der Logik, 0 so falsch, 1 so wahr,  dolmetschend, wie und,  als oder, und ¬ als nicht. Ausdrücke, die Variablen und die Operationen von Boolean einschließen, vertreten Behauptungsformen, und, wie man zeigen kann, sind zwei solche Ausdrücke das gleiche Verwenden die obengenannten Axiome, wenn, und nur wenn die entsprechenden Behauptungsformen logisch gleichwertig sind.

:* Die Zwei-Elemente-Algebra von Boolean wird auch für das Stromkreis-Design in der Elektrotechnik verwendet; hier 0 und 1 vertreten die zwei verschiedenen Staaten von einem Bit in einem Digitalstromkreis, normalerweise hoher und niedriger Stromspannung. Stromkreise werden durch Ausdrücke beschrieben, die Variablen enthalten, und zwei solche Ausdrücke sind für alle Werte der Variablen gleich, wenn, und nur wenn die entsprechenden Stromkreise dasselbe Eingangsproduktionsverhalten haben. Außerdem kann jedes mögliche Eingangsproduktionsverhalten durch einen passenden Ausdruck von Boolean modelliert werden.

:* Die Zwei-Elemente-Algebra von Boolean ist auch in der allgemeinen Theorie von Algebra von Boolean wichtig, weil eine Gleichung, die mehrere Variablen einschließt, in allen Algebra von Boolean allgemein wahr ist, wenn, und nur wenn es in der Zwei-Elemente-Algebra von Boolean wahr ist (der durch einen trivialen Algorithmus der rohen Gewalt für kleine Zahlen von Variablen überprüft werden kann). Das kann zum Beispiel verwendet werden, um zu zeigen, dass die folgenden Gesetze (Einigkeitslehrsätze) in allen Algebra von Boolean allgemein gültig sind:

: ** (ein  b)  (¬ ein  c)  (b  c)  (ein  b)  (¬ ein  c)

: ** (ein  b)  (¬ ein  c)  (b  c)  (ein  b)  (¬ ein  c)

• Der Macht-Satz (Satz aller Teilmengen) jedes gegebenen nichtleeren Satzes S bildet eine Algebra von Boolean mit den zwei Operationen : =  (Vereinigung) und : =  (Kreuzung). Das kleinste Element 0 ist der leere Satz, und das größte Element 1 ist der Satz S selbst.
• Der Satz aller Teilmengen von S, die entweder begrenzt sind oder cofinite, ist eine Algebra von Boolean.
• Mit der Satzrechnung mit κ-Satz-Symbolen anfangend, bilden Sie die Algebra von Lindenbaum (d. h. die Menge der Aussagen in der Satzrechnung modulo Tautologie). Dieser Aufbau gibt eine Algebra von Boolean nach. Es ist tatsächlich die freie Algebra von Boolean auf κ Generatoren. Eine Wahrheitsanweisung in der Satzrechnung ist dann ein Algebra-Homomorphismus von Boolean von dieser Algebra bis die Zwei-Elemente-Algebra von Boolean.
• In Anbetracht jedes geradlinig bestellten Satzes L mit kleinstem Element ist die Zwischenraum-Algebra die kleinste Algebra von Teilmengen von L, der alle halb offenen Zwischenräume [a, b enthält), solch, dass in L und b zu sein, entweder in L oder gleich  ist. Zwischenraum-Algebra sind in der Studie von Algebra von Lindenbaum-Tarski nützlich; jede zählbare Algebra von Boolean ist zu einer Zwischenraum-Algebra isomorph.
• Für jede natürliche Zahl n bildet der Satz aller positiven Teiler von n ein verteilendes Gitter, wenn wir einen  b für einen b schreiben. Dieses Gitter ist eine Algebra von Boolean, wenn, und nur wenn n quadratfrei ist. Das kleinste Element 0 dieser Algebra von Boolean ist die natürliche Zahl 1; das größte Element 1 dieser Algebra von Boolean ist die natürliche Zahl n.
• Andere Beispiele von Algebra von Boolean entstehen aus topologischen Räumen: Wenn X ein topologischer Raum ist, dann die Sammlung aller Teilmengen X, die sowohl offene als auch geschlossene Formen eine Algebra von Boolean mit den Operationen  sind: =  (Vereinigung) und : =  (Kreuzung).
• Wenn R ein willkürlicher Ring ist und wir den Satz von zentralem idempotents durch = {e  R definieren: e = e, ab = xe, x  R\dann wird der Satz A eine Algebra von Boolean mit den Operationen e  f: = e + f - ef und e  f: = ef.

Homomorphismus und Isomorphismus

Ein Homomorphismus zwischen zwei Algebra von Boolean A und B ist eine Funktion f: Ein  B solch dass für den ganzen a, b in A:

: f (ein  b) = f (a)  f (b),

: f (ein  b) = f (a)  f (b),

: f (0) = 0,

: f (1) = 1.

Es folgt dann dem f (¬ a) = ¬ f (a) für alle in ebenso. Die Klasse aller Algebra von Boolean, zusammen mit diesem Begriff von morphism, bildet eine volle Unterkategorie der Kategorie von Gittern.

Ringe von Boolean

Jede Boolean Algebra (A, , ) verursacht einen Ring (A, +, ·) durch das Definieren + b: = (ein  ¬ b)  (b  ¬ a) = (ein  b)  ¬ (ein  b) (wird diese Operation symmetrischen Unterschied im Fall von Sätzen und XOR im Fall von der Logik genannt), und a · b: = ein  b. Das Nullelement dieses Rings fällt mit 0 der Algebra von Boolean zusammen; das multiplicative Identitätselement des Rings ist 1 der Algebra von Boolean. Dieser Ring hat das Eigentum dass a · = für alle in A; Ringe mit diesem Eigentum werden Ringe von Boolean genannt.

Umgekehrt, wenn Boolean klingelt, wird A gegeben, wir können es in eine Algebra von Boolean verwandeln, indem wir x  y definieren: = x + y + (x · y) und x  y: = x · y. Da diese zwei Aufbauten Gegenteile von einander sind, können wir sagen, dass jeder Ring von Boolean aus einer Algebra von Boolean, und umgekehrt entsteht. Außerdem, eine Karte f: Ein  B ist ein Homomorphismus von Algebra von Boolean, wenn, und nur wenn es ein Homomorphismus von Ringen von Boolean ist. Die Kategorien von Ringen von Boolean und Algebra von Boolean sind gleichwertig.

Ideale und Filter

Ein Ideal der Algebra von Boolean A ist eine Teilmenge I solch, dass für den ganzen x y in mir wir x  y darin haben, habe mir und für alle in uns einen  x in mir. Dieser Begriff des Ideales fällt mit dem Begriff des Ringideales im RingA von Boolean zusammen. Ein Ideal I von A werden erst genannt, wenn ich  A, und wenn ein  b in mir immer in mir oder b in mir einbeziehe. Außerdem für jeden ein  haben wir das ein -a = 0  I und dann ein  I oder-a  I für jeden ein  A, wenn ich erst bin. Ein Ideal I von A werden maximal genannt, wenn ich  A, und wenn das einzige Ideal, das richtig enthält, mich selbst bin. Für ein Ideal I, wenn ein  I und-a  I, dann werden ich  oder ich  {-a} in einem anderen Ideal J richtig enthalten. Folglich, dass ich nicht maximal ist und deshalb die Begriffe des maximalen und idealen Hauptideales in Algebra von Boolean gleichwertig sind. Außerdem fallen diese Begriffe mit dem Ring zusammen theoretische des maximalen und idealen Hauptideales in Boolean rufen A. an

Das Doppel-von einem Ideal ist ein Filter. Ein Filter der Algebra von Boolean A ist eine Teilmenge p solch, dass für den ganzen x y in p wir x  y in p haben und für alle in uns einen  x in p haben. Der Doppel-von einem maximalen (oder erst) Ideal in einer Algebra von Boolean ist Ultrafilter. Die Behauptung jeder Filter in einer Algebra von Boolean kann zu einem Ultrafilter erweitert werden, wird den Ultrafilterlehrsatz genannt und kann in ZF ohne das Axiom der Wahl nicht bewiesen werden, wenn ZF entspricht. Der Ultrafilterlehrsatz hat viele equivalen Formulierungen: Jede Algebra von Boolean hat einen Ultrafilter, jedes Ideal in einer Algebra von Boolean kann zu einem Hauptideal usw. erweitert werden.

Darstellungen

Es kann gezeigt werden, dass jede begrenzte Algebra von Boolean zur Algebra von Boolean aller Teilmengen eines begrenzten Satzes isomorph ist. Deshalb ist die Zahl der Elemente jeder begrenzten Algebra von Boolean eine Macht zwei.

Der berühmte Darstellungslehrsatz des Steins für Algebra von Boolean stellt fest, dass jede Algebra von Boolean A zur Algebra von Boolean aller Clopen-Sätze in einigen (kompakter völlig getrennter Hausdorff) topologischer Raum isomorph ist.

Axiomatics

Der erste axiomatization von Gittern/Algebra von Boolean wurde im Allgemeinen von Alfred North Whitehead 1898 gegeben. 1933 hat der amerikanische Mathematiker Edward Vermilye Huntington (1874-1952) den folgenden eleganten axiomatization für die Algebra von Boolean dargelegt. Es verlangt gerade, dass eine binäre Operation + und ein unäres funktionelles Symbol n, als 'Ergänzung' gelesen wird, die die folgenden Gesetze befriedigen:

1. Commutativity: x + y = y + x.
2. Associativity: (x + y) + z = x + (y + z).
3. Gleichung von Huntington: n (n (x) + y) + n (n (x) + n (y)) = x.

Herbert Robbins hat sofort gefragt: Wenn die Gleichung von Huntington durch seinen Doppel-zum Witz ersetzt wird:

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

(1), (2), und (4) bilden eine Basis für die Algebra von Boolean? (1), (2), und (4) eine Algebra von Robbins rufend, wird die Frage dann: Ist jede Algebra von Robbins eine Algebra von Boolean? Diese Frage (der gekommen ist, um als die Vermutung von Robbins bekannt zu sein) ist offen seit Jahrzehnten geblieben, und ist eine Lieblingsfrage von Alfred Tarski und seinen Studenten geworden.

1996 arbeitet William McCune am Argonne Nationalen Laboratorium, aufbauend früher durch Larry Wos, Steve Winker und Bob Veroff, haben auf die Frage von Robbins bejahend geantwortet: Jede Algebra von Robbins ist eine Algebra von Boolean. Entscheidend für den Beweis von McCune war das automatisierte vernünftig urteilende Programm EQP, den er entworfen hat. Für eine Vereinfachung des Beweises von McCune, sieh Dahn (1998).

Generalisationen

Das Entfernen der Voraussetzung der Existenz einer Einheit von den Axiomen von Algebra-Erträgen von Boolean "hat Algebra von Boolean verallgemeinert". Formell ist ein verteilendes Gitter B ein verallgemeinertes Gitter von Boolean, wenn es ein kleinstes Element 0 und für irgendwelche Elemente a und b in solchem B hat, dass ein  b, dort ein Element x solch dass ein  x = 0 und ein  x = b besteht. Das Definieren eines  b als der einzigartige solcher x, dass (ein  b)  x = a und (ein  b)  x = 0, wir sagen, dass die Struktur (B, , , , 0) eine verallgemeinerte Algebra von Boolean ist, während (B, , 0) ein verallgemeinertes Halbgitter von Boolean ist. Verallgemeinerte Boolean Gitter sind genau die Ideale von Gittern von Boolean.

Eine Struktur, die alle Axiome für Algebra von Boolean außer den zwei distributivity Axiomen befriedigt, wird ein orthocomplemented Gitter genannt. Gitter von Orthocomplemented entstehen natürlich in der Quant-Logik als Gitter von geschlossenen Subräumen für trennbare Räume von Hilbert.

Siehe auch

• Liste von Algebra-Themen von Boolean
• Gebiet von Boolean
• Boolean fungieren
• Logik von Boolean
• Boolean rufen an
• GeBoolean-schätzte Funktion
• Kanonische Form (Algebra von Boolean)
• Vollenden Sie Boolean Algebra
• Die Gesetze von De Morgan
• Finitary boolean fungieren
• Das Zwingen (der Mathematik)
• Freie Boolean Algebra
• Algebra von Heyting
• Hyperwürfel-Graph
• Karnaugh stellen kartografisch dar
• Gesetze der Form
• Logiktor
• Logischer Graph
• Logische Matrix
• Satzlogik
• Boolean Zwei-Elemente-Algebra
• Venn-Diagramm
• Bedingte Ereignis-Algebra

Referenzen

• . Sieh Abschnitt 2.5.
• . Sieh Kapitel 2.

.......

• . In 3 Volumina. (Vol.1:ISBN 978-0-444-70261-6, Vol.2:ISBN 978-0-444-87152-7, Vol.3:ISBN 978-0-444-87153-4)

..

• . Nachgedruckt durch Veröffentlichungen von Dover, 1979.

Links

• Boolean Algebra von AllAboutCircuits
• Enzyklopädie von Stanford der Philosophie: "Die Mathematik der Boolean Algebra," durch den Mönch von J. Donald.
• McCune W., 1997. Algebra von Robbins Sind Boolean GLAS 19 (3), 263 — 276
• "Boolean Algebra" durch Eric W. Weisstein, Wolfram-Demonstrationsprojekt, 2007.

Eine Monografie verfügbar gratis online:

• Burris, Stanley N.; Sankappanavar, H. P., 1981. Ein Kurs in der Universalen Algebra. Springer-Verlag. Internationale Standardbuchnummer 3-540-90578-2.