Boolesche Algebra mit zwei Elementen - Two-element Boolean algebra

In der Mathematik und der abstrakten Algebra ist die Zwei-Elemente-Boolesche Algebra die Boolesche Algebra, deren zugrunde liegende Menge (oder Universum oder Träger ) B die Boolesche Domäne ist . Die Elemente der Booleschen Domäne sind gemäß Konvention 1 und 0, so dass B  = {0, 1}. Paul Halmos 'Name für diese Algebra " 2 " hat in der Literatur einige Anhänger und wird hier verwendet.

Definition

B ist eine teilweise geordnete Menge und die Elemente von B sind auch seine Grenzen .

Ein Betrieb von arity n ist eine Zuordnung von B ⁿ zu B . Die Boolesche Algebra besteht aus zwei binären Operationen und einer unären Komplementation . Die binären Operationen wurden auf verschiedene Arten benannt und notiert. Hier werden sie 'Summe' und 'Produkt' genannt und mit dem Infix '+' bzw. '∙' notiert. Summe und Produkt pendeln und assoziieren , wie in der üblichen Algebra reeller Zahlen . Für die Reihenfolge der Operationen sind Klammern entscheidend, falls vorhanden. Andernfalls steht '∙' vor '+'. Daher wird A ∙ B + C als (A ∙ B) + C und nicht als A ∙ (B + C) analysiert . Die Ergänzung wird durch Schreiben eines Überstrichs über das Argument gekennzeichnet. Die numerische Analogon des Komplement von X 1 -  X . In der Sprache der universellen Algebra ist eine Boolesche Algebra eine Algebra vom Typ . ${\ displaystyle \ langle B, +,., {\ overline {..}}, 1,0 \ rangle}$ ${\ displaystyle \ langle 2,2,1,0,0 \ rangle}$

Jede Eins-zu-Eins-Entsprechung zwischen {0,1} und { True , False } ergibt die klassische zweiwertige Logik in Gleichungsform, wobei die Komplementation als NOT gelesen wird . Wenn 1 als wahr gelesen wird , wird '+' als ODER und '∙' als UND gelesen und umgekehrt, wenn 1 als falsch gelesen wird . Diese beiden Operationen definieren ein kommutatives Semiring , das als Boolesches Semiring bezeichnet wird .

Einige grundlegende Identitäten

2 kann als in der folgenden trivialen "Booleschen" Arithmetik begründet angesehen werden:

${\ displaystyle {\ begin {align} & 1 + 1 = 1 + 0 = 0 + 1 = 1 \\ & 0 + 0 = 0 \\ & 0 \ cdot 0 = 0 \ cdot 1 = 1 \ cdot 0 = 0 \\ & 1 \ cdot 1 = 1 \\ & {\ overline {1}} = 0 \\ & {\ overline {0}} = 1 \ end {align}}}$

Beachten Sie, dass:

• '+' und '∙' funktionieren genau wie in der numerischen Arithmetik, außer dass 1 + 1 = 1 ist. '+' und '∙' werden analog aus der numerischen Arithmetik abgeleitet; Setzen Sie einfach eine Zahl ungleich Null auf 1.
• Das Vertauschen von 0 und 1 und '+' und '∙' bewahrt die Wahrheit; Dies ist die Essenz der Dualität , die alle booleschen Algebren durchdringt.

Diese Boolesche Arithmetik reicht aus, um eine Gleichung von 2 einschließlich der Axiome zu verifizieren , indem jede mögliche Zuordnung von 0en und 1en zu jeder Variablen untersucht wird (siehe Entscheidungsverfahren ).

Die folgenden Gleichungen können nun überprüft werden:

${\ displaystyle {\ begin {align} & A + A = A \\ & A \ cdot A = A \\ & A + 0 = A \\ & A + 1 = 1 \\ & A \ cdot 0 = 0 \\ & {\ overline {\ overline {A}}} = A \ end {align}}}$

Jedes von '+' und '∙' verteilt sich über das andere:

• ${\ displaystyle \ A \ cdot (B + C) = A \ cdot B + A \ cdot C;}$
• ${\ displaystyle \ A + (B \ cdot C) = (A + B) \ cdot (A + C).}$

Dass '∙' über '+' verteilt ist, stimmt mit der Elementaralgebra überein , aber nicht '+' über '∙'. Aus diesem und anderen Gründen wird häufiger eine Summe von Produkten (die zu einer NAND- Synthese führen) verwendet als ein Produkt von Summen (was zu einer NOR- Synthese führt).

Jedes von '+' und '∙' kann in Bezug auf das andere und die Ergänzung definiert werden:

• ${\ displaystyle A \ cdot B = {\ overline {{\ overline {A}} + {\ overline {B}}}}$
• ${\ displaystyle A + B = {\ overline {{\ overline {A}} \ cdot {\ overline {B}}}.}$

Wir brauchen nur eine binäre Operation, und die Verkettung reicht aus, um sie zu bezeichnen. Daher genügen Verkettung und Overbar, um 2 zu notieren . Diese Schreibweise ist auch , dass von Quine ‚s Booleschen Ausdruck Schemen . Vermietung ( X ) bezeichnen das Komplement von X und "()" bezeichnet entweder 0 oder 1 Ausbeute der Syntax des primären Algebra G. Spencer-Brown ‚s Laws of Form .

Eine Basis für 2 ist ein Satz von Gleichungen, Axiome genannt , aus denen alle obigen Gleichungen (und mehr) abgeleitet werden können. Es gibt viele bekannte Grundlagen für alle Booleschen Algebren und damit für 2 . Eine elegante Basis, die nur mit Verkettung und Overbar notiert wird, ist:

1. ${\ displaystyle \ ABC = BCA}$ (Verkettung pendelt, Mitarbeiter)
2. ${\ displaystyle {\ overline {A}} A = 1}$ ( 2 ist ein komplementiertes Gitter mit einer Obergrenze von 1)
3. ${\ displaystyle \ A0 = A}$ (0 ist die Untergrenze ).
4. ${\ displaystyle A {\ overline {AB}} = A {\ overline {B}}}$ ( 2 ist ein Verteilungsgitter )

Wobei Verkettung = ODER, 1 = wahr und 0 = falsch oder Verkettung = UND, 1 = falsch und 0 = wahr. (Überstrich ist in beiden Fällen Negation.)

Wenn 0 = 1, sind (1) - (3) die Axiome für eine abelsche Gruppe .

(1) dient nur zum Nachweis, dass die Verkettung pendelt und assoziiert. Nehmen Sie zuerst an, dass (1) entweder von links oder von rechts assoziiert, und beweisen Sie dann die Kommutativität. Dann beweisen Sie Assoziation aus der anderen Richtung. Assoziativität ist einfach Assoziation von links und rechts kombiniert.

Auf dieser Basis sorgt für einen einfachen Ansatz zu beweisen, „Berechnung“ in genannt Laws of Form , dass Erlöse durch Ausdrücke auf 0 oder 1 ist , unter Berufung auf Axiome (2) vereinfacht - (4), und die elementaren Identitäten und das distributive Gesetz. ${\ displaystyle AA = A, {\ overline {\ overline {A}}} = A, 1 + A = 1}$

Metatheorie

Der Satz von De Morgan besagt, dass, wenn man in der angegebenen Reihenfolge Folgendes für eine Boolesche Funktion ausführt :

• Ergänzen Sie jede Variable;
• Tauschen Sie die Operatoren '+' und '∙' aus (achten Sie darauf, Klammern hinzuzufügen, um sicherzustellen, dass die Reihenfolge der Operationen gleich bleibt).
• Ergänzen Sie das Ergebnis,

Das Ergebnis entspricht logischerweise dem, mit dem Sie begonnen haben. Die wiederholte Anwendung des Satzes von De Morgan auf Teile einer Funktion kann verwendet werden, um alle Komplemente auf die einzelnen Variablen herunterzufahren.

Ein mächtiges und nicht triviales Metatheorem besagt, dass jeder Satz von 2 für alle Booleschen Algebren gilt. Umgekehrt gilt eine Identität, die für eine beliebige nichttriviale Boolesche Algebra gilt, auch für 2 . Daher wird der gesamte mathematische Inhalt der Booleschen Algebra durch 2 erfasst . Dieser Satz ist nützlich, weil jede Gleichung in 2 durch ein Entscheidungsverfahren verifiziert werden kann . Logiker bezeichnen diese Tatsache als " 2 ist entscheidbar ". Alle bekannten Entscheidungsverfahren erfordern eine Anzahl von Schritten, die eine Exponentialfunktion der Anzahl von Variablen N ist, die in der zu verifizierenden Gleichung erscheinen. Ob es eine Entscheidungsprozedur gibt, deren Schritte eine Polynomfunktion von N sind, fällt unter die P = NP- Vermutung.

Siehe auch

• boolsche Algebra
• Begrenzter Satz
• Gitter (Bestellung)
• Ordnungstheorie

Verweise

Weiterführende Literatur

Viele elementare Texte zur Booleschen Algebra wurden in den frühen Jahren des Computerzeitalters veröffentlicht. Vielleicht ist das Beste und noch in gedruckter Form:

• Mendelson, Elliot, 1970. Schaums Umriss der Booleschen Algebra . McGraw-Hill.

Die folgenden Punkte zeigen, wie die Boolesche Algebra mit zwei Elementen mathematisch nicht trivial ist.

• Stanford Encyclopedia of Philosophy : " Die Mathematik der Booleschen Algebra " von J. Donald Monk.
• Burris, Stanley N. und HP Sankappanavar, HP, 1981. Ein Kurs in universeller Algebra. Springer-Verlag. ISBN   3-540-90578-2 .