Boolesche Algebra

In der Mathematik und mathematischen Logik ist die Boolesche Algebra ein Teilgebiet der Algebra . Sie unterscheidet sich in zweierlei Hinsicht von der Elementaralgebra . Erstens sind die Werte der Variablen die Wahrheitswerte „ wahr“ und „falsch“ , üblicherweise mit 1 und 0 bezeichnet, während in der Elementaralgebra die Werte der Variablen Zahlen sind. Zweitens verwendet die Boolesche Algebra logische Operatoren wie die Konjunktion ( und ), bezeichnet mit ∧ , die Disjunktion ( oder ), bezeichnet mit ∨ , und die Negation ( nicht ), bezeichnet mit ¬ . Die Elementaralgebra hingegen verwendet arithmetische Operatoren wie Addition, Multiplikation, Subtraktion und Division. Die Boolesche Algebra ist daher eine formale Methode zur Beschreibung logischer Operationen, analog zur Beschreibung numerischer Operationen in der Elementaralgebra.

Die Boolesche Algebra wurde von George Boole in seinem ersten Buch „The Mathematical Analysis of Logic “ (1847) eingeführt ^{[ 1 ]} und in seinem Werk „An Investigation of the Laws of Thought “ (1854) ausführlicher dargestellt . ^{[ 2 ]} Laut Huntington wurde der Begriff „Boolesche Algebra“ erstmals 1913 von Henry M. Sheffer vorgeschlagen ^{[ 3 ]} , obwohl Charles Sanders Peirce dem ersten Kapitel seines Buches „The Simplest Mathematics“ bereits 1880 den Titel „A Boolian [ sic ] Algebra with One Constant“ gab. ^{[ 4 ]} Die Boolesche Algebra war grundlegend für die Entwicklung der digitalen Elektronik und ist in allen modernen Programmiersprachen implementiert . Sie findet auch Anwendung in der Mengenlehre und Statistik . ^{[ 5 ]}

Ein Vorläufer der Booleschen Algebra war Gottfried Wilhelm Leibniz ’ Begriffsalgebra. Die Verwendung des Binärsystems im Zusammenhang mit dem I Ging war zentral für Leibniz’ „characteristica universalis“ . Sie legte letztlich den Grundstein für die Begriffsalgebra. ^{[ 6 ]} Leibniz’ Begriffsalgebra ist deduktiv äquivalent zur Booleschen Mengenalgebra. ^{[ 7 ]}

Die Boolesche Algebra entstand vor den modernen Entwicklungen in der abstrakten Algebra und der mathematischen Logik ; sie wird jedoch als mit den Ursprüngen beider Gebiete verbunden angesehen. ^{[ 8 ]} In einem abstrakten Kontext wurde die Boolesche Algebra im späten 19. Jahrhundert von Jevons , Schröder , Huntington und anderen perfektioniert, bis sie dem modernen Verständnis einer (abstrakten) mathematischen Struktur entsprach . ^{[ 8 ]} Beispielsweise wird die empirische Beobachtung, dass man Ausdrücke in der Mengenalgebra manipulieren kann , indem man sie in Ausdrücke der Booleschen Algebra übersetzt, in modernen Begriffen damit erklärt, dass die Mengenalgebra eine Boolesche Algebra ist (beachten Sie den unbestimmten Artikel ). Tatsächlich bewies M. H. Stone 1936 , dass jede Boolesche Algebra isomorph zu einem Mengenkörper ist . ^{[ 9 ] [ 10 ]}

In den 1930er Jahren beobachtete Claude Shannon bei seinen Untersuchungen von Schaltkreisen , dass sich die Regeln der Booleschen Algebra auch in diesem Kontext anwenden ließen ^{[ 11 ].} Er führte daraufhin die Schaltalgebra ein , um Schaltungen mithilfe logischer Gatter algebraisch zu analysieren und zu entwerfen . Da Shannon bereits über den abstrakten mathematischen Apparat verfügte, formulierte er seine Schaltalgebra als zweielementige Boolesche Algebra . In der modernen Schaltungstechnik ist es kaum notwendig, andere Boolesche Algebren zu betrachten, weshalb die Begriffe „Schaltalgebra“ und „Boolesche Algebra“ oft synonym verwendet werden. ^{[ 12 ] [ 13 ] [ 14 ]}

Die effiziente Implementierung Boolescher Funktionen ist ein grundlegendes Problem beim Entwurf kombinatorischer Logikschaltungen . Moderne Werkzeuge zur elektronischen Entwurfsautomatisierung für VLSI-Schaltungen ( Very-Large-Scale Integration ) verwenden häufig eine effiziente Darstellung Boolescher Funktionen, die als (reduzierte geordnete) binäre Entscheidungsdiagramme (BDD) bekannt ist, für die Logiksynthese und formale Verifikation . ^{[ 15 ]}

Logische Sätze, die sich in der klassischen Aussagenlogik ausdrücken lassen, haben eine äquivalente Formulierung in der Booleschen Algebra. Daher wird der Begriff „Boolesche Logik“ mitunter synonym für die so angewandte Aussagenlogik verwendet. ^{[ 16 ] [ 17 ] [ 18 ]} Die Boolesche Algebra allein reicht jedoch nicht aus, um logische Formeln mit Quantoren , wie sie beispielsweise in der Prädikatenlogik erster Stufe vorkommen, vollständig abzubilden .

Obwohl die Entwicklung der mathematischen Logik nicht Booles Programm folgte, wurde die Verbindung zwischen seiner Algebra und Logik später im Rahmen der algebraischen Logik , die auch die algebraischen Systeme vieler anderer Logiken untersucht, gefestigt . ^{[ 8 ]} Das Problem, zu bestimmen, ob die Variablen einer gegebenen Booleschen (aussagenlogischen) Formel so belegt werden können, dass die Formel den Wert „wahr“ ergibt, wird als Boolesches Erfüllbarkeitsproblem (SAT) bezeichnet und ist für die theoretische Informatik von Bedeutung, da es das erste Problem ist, dessen NP-Vollständigkeit nachgewiesen wurde . Das eng verwandte Berechnungsmodell, bekannt als Boolescher Schaltkreis, setzt die Zeitkomplexität (eines Algorithmus ) in Beziehung zur Schaltkreiskomplexität .

Während Ausdrücke in der elementaren Algebra hauptsächlich Zahlen bezeichnen, repräsentieren sie in der Booleschen Algebra die Wahrheitswerte falsch und wahr . Diese Werte werden durch die Bits 0 und 1 dargestellt. Sie verhalten sich nicht wie die ganzen Zahlen 0 und 1, für die 1 + 1 = 2 gilt , sondern können mit den Elementen des zweielementigen Körpers GF(2) identifiziert werden , also der Arithmetik modulo 2 , für die 1 + 1 = 0 gilt . Addition und Multiplikation entsprechen dann in der Booleschen Algebra den Operationen XOR (exklusives Oder) bzw. AND (Konjunktion), wobei die Disjunktion x ∨ y (inklusives Oder) als x + y − xy und die Negation ¬x als 1 − x definiert werden kann . In GF(2) kann − durch + ersetzt werden , da beide dieselbe Operation bezeichnen. Allerdings ermöglicht diese Art der Formulierung von Booleschen Operationen die Anwendung der üblichen arithmetischen Operationen für ganze Zahlen (dies kann nützlich sein, wenn eine Programmiersprache verwendet wird, in der GF(2) nicht implementiert ist).

Die Boolesche Algebra befasst sich auch mit Funktionen , deren Werte im Intervall {0,1} liegen . Eine Bitfolge ist ein häufig verwendetes Beispiel für eine solche Funktion. Ein weiteres gängiges Beispiel ist die Gesamtheit der Teilmengen einer Menge E : Für eine Teilmenge F von E kann man die Indikatorfunktion definieren , die innerhalb von F den Wert 1 und außerhalb von F den Wert 0 annimmt . Das allgemeinste Beispiel sind die Elemente einer Booleschen Algebra , wobei alle oben genannten Beispiele Instanzen davon sind.

Wie in der elementaren Algebra kann der rein gleichungstheoretische Teil der Theorie entwickelt werden, ohne explizite Werte für die Variablen zu berücksichtigen. ^{[ 19 ]}

Während die elementare Algebra vier Grundrechenarten kennt (Addition, Subtraktion, Multiplikation und Division), besitzt die Boolesche Algebra nur drei: Konjunktion , Disjunktion und Negation . Diese werden durch die entsprechenden binären Operatoren AND ( ) und OR ( ) sowie den unären Operator NOT ( ) ausgedrückt, die zusammenfassend als Boolesche Operatoren bezeichnet werden . ^{[ 20 ]} Variablen in der Booleschen Algebra, die die logischen Werte 0 und 1 speichern, heißen Boolesche Variablen . Sie dienen dazu, entweder „wahr“ oder „falsch“ zu speichern. ^{[ 21 ]} Die grundlegenden Operationen mit Booleschen Variablen x und y sind wie folgt definiert:${\displaystyle \land }$${\displaystyle \lor }$${\displaystyle \neg }$

Alternativ können die Werte von x ∧ y , x ∨ y und ¬ x durch Tabellierung ihrer Werte mit Wahrheitstabellen wie folgt ausgedrückt werden : ^{[ 22 ]}

${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\vee y}$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

${\displaystyle x}$ ${\displaystyle \neg x}$ 0 1 1 0

Bei der Verwendung in Ausdrücken werden die Operatoren gemäß den Vorrangregeln angewendet. Wie in der elementaren Algebra werden Ausdrücke in Klammern zuerst ausgewertet, entsprechend den Vorrangregeln. ^{[ 23 ]}

Werden die Wahrheitswerte 0 und 1 als ganze Zahlen interpretiert, können diese Operationen mit den gewöhnlichen arithmetischen Operationen (wobei x + y die Addition und xy die Multiplikation verwendet) oder mit den Minimum-/Maximum-Funktionen ausgedrückt werden:

${\displaystyle {\begin{aligned}x\wedge y&=xy=\min(x,y)\\x\vee y&=x+y-xy=x+y(1-x)=\max(x,y)\\\neg x&=1-x\end{aligned}}}$

Man könnte meinen, dass nur die Negation und eine der beiden anderen Operationen grundlegend sind, da es folgende Identitäten gibt, die es erlauben, die Konjunktion in Bezug auf die Negation und die Disjunktion zu definieren und umgekehrt ( De Morgansche Gesetze ): ^{[ 24 ]}

${\displaystyle {\begin{aligned}x\wedge y&=\neg (\neg x\vee \neg y)\\x\vee y&=\neg (\neg x\wedge \neg y)\end{aligned}}}$

Zu den aus den Grundoperationen zusammengesetzten Operationen gehören unter anderem die folgenden:

Materialbedingung :	${\textstyle x\rightarrow y=\neg {x}\vee y}$
Material-Bikonditional :	${\textstyle x\leftrightarrow y=(x\land y)\lor (\neg x\land \neg y)=(x\lor \neg y)\land (\neg x\lor y)}$
Exklusives Oder ( XOR ):	${\textstyle x\oplus y=\neg (x\leftrightarrow y)=(x\vee y)\wedge \neg (x\wedge y)=(x\vee y)\wedge (\neg x\vee \neg y)=(x\wedge \neg y)\vee (\neg x\wedge y)}$

Aus diesen Definitionen ergeben sich die folgenden Wahrheitstabellen, die die Werte dieser Operationen für alle vier möglichen Eingaben angeben.

Sekundäre Operationen. Tabelle 1

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle x\rightarrow y}$	${\displaystyle x\oplus y}$	${\displaystyle x\leftrightarrow y,x\equiv y}$
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

Material bedingt

Die erste Operation, x  →  y oder C xy , wird als materielle Implikation bezeichnet . Ist x wahr, so entspricht das Ergebnis des Ausdrucks x  →  y dem von y (z. B. ist x wahr und y falsch, so ist auch x  →  y falsch). Ist x jedoch falsch, kann der Wert von y ignoriert werden; die Operation muss aber einen booleschen Wert zurückgeben , und es gibt nur zwei Möglichkeiten. Per Definition ist x  →  y also wahr , wenn x falsch ist ( die Relevanzlogik verwirft diese Definition, indem sie eine Implikation mit einer falschen Prämisse als etwas anderes als wahr oder falsch betrachtet).

Exklusives Oder ( XOR )

Die zweite Operation, x  ⊕  y oder J xy , wird als exklusives Oder (oft abgekürzt als XOR) bezeichnet, um sie von der Disjunktion als inklusiver Operation zu unterscheiden. Sie schließt die Möglichkeit aus, dass sowohl x als auch y wahr sind (siehe z. B. Tabelle): Sind beide wahr, ist das Ergebnis falsch. Arithmetisch definiert ist sie die Addition, wobei modulo 2 gleich 1 + 1 = 0 ist.

Logische Äquivalenz

Die dritte Operation, das Komplement des Exklusiv-Oders, ist die Äquivalenz oder boolesche Gleichheit: x  ≡  y oder E xy ist genau dann wahr, wenn x und y denselben Wert haben. Daher kann x  ⊕  y als sein Komplement als x  ≠  y verstanden werden und ist genau dann wahr, wenn x und y verschieden sind. Somit ist sein Gegenstück in der Arithmetik modulo 2 x + y . Das Gegenstück der Äquivalenz in der Arithmetik modulo 2 ist x + y + 1.

Ein Gesetz der Booleschen Algebra ist eine Identität wie x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z zwischen zwei Booleschen Termen. Ein Boolescher Term ist definiert als ein Ausdruck, der aus Variablen und den Konstanten 0 und 1 mithilfe der Operationen ∧, ∨ und ¬ gebildet wird. Das Konzept lässt sich auf Terme mit anderen Booleschen Operationen wie ⊕, → und ≡ erweitern, doch sind solche Erweiterungen für die Zwecke, denen die Gesetze dienen, nicht notwendig. Zu diesen Zwecken gehört die Definition einer Booleschen Algebra als jedes Modell der Booleschen Gesetze sowie die Ableitung neuer Gesetze aus bestehenden, wie beispielsweise die Ableitung von x ∨ ( y ∧ z ) = x ∨ ( z ∧ y ) aus y ∧ z = z ∧ y (siehe Abschnitt „Axiomatisierung der Booleschen Algebra “).

Die Boolesche Algebra erfüllt viele der gleichen Gesetze wie die gewöhnliche Algebra, wenn man ∨ mit der Addition und ∧ mit der Multiplikation gleichsetzt. Insbesondere gelten die folgenden Gesetze für beide Arten von Algebra: ^{[ 25 ] [ 26 ]}

Assoziativität von ∨ :		${\displaystyle x\vee (y\vee z)}$	${\displaystyle =(x\vee y)\vee z}$
Assoziativität von ∧ :		${\displaystyle x\wedge (y\wedge z)}$	${\displaystyle =(x\wedge y)\wedge z}$
Kommutativität von ∨ :		${\displaystyle x\vee y}$	${\displaystyle =y\vee x}$
Kommutativität von ∧ :		${\displaystyle x\wedge y}$	${\displaystyle =y\wedge x}$
Distributivität von ∧ über ∨ :		${\displaystyle x\wedge (y\vee z)}$	${\displaystyle =(x\wedge y)\vee (x\wedge z)}$
Identität für ∨ :		${\displaystyle x\vee 0}$	${\displaystyle =x}$
Identität für ∧ :		${\displaystyle x\wedge 1}$	${\displaystyle =x}$
Annihilator für ∧ :		${\displaystyle x\wedge 0}$	${\displaystyle =0}$

Folgende Gesetze gelten in der Booleschen Algebra, nicht aber in der gewöhnlichen Algebra:

Annihilator für ∨ :		${\displaystyle x\vee 1}$	${\displaystyle =1}$
Idempotenz von ∨ :		${\displaystyle x\vee x}$	${\displaystyle =x}$
Idempotenz von ∧ :		${\displaystyle x\wedge x}$	${\displaystyle =x}$
Absorption 1:		${\displaystyle x\wedge (x\vee y)}$	${\displaystyle =x}$
Absorption 2:		${\displaystyle x\vee (x\wedge y)}$	${\displaystyle =x}$
Distributivität von ∨ über ∧ :		${\displaystyle x\vee (y\wedge z)}$	${\displaystyle =(x\vee y)\wedge (x\vee z)}$

Setzt man im dritten Gesetz oben x = 2, zeigt sich, dass es sich nicht um ein gewöhnliches algebraisches Gesetz handelt, da 2 × 2 = 4. Die übrigen fünf Gesetze lassen sich durch die Anwendung gewöhnlicher Algebra widerlegen, indem man alle Variablen gleich 1 setzt. Beispielsweise wäre im ersten Absorptionsgesetz die linke Seite 1(1 + 1) = 2 , während die rechte Seite 1 wäre (und so weiter).

Alle bisher behandelten Gesetze bezogen sich auf Konjunktion und Disjunktion. Diese Operationen haben die Eigenschaft, dass die Änderung eines der Argumente entweder die Ausgabe unverändert lässt oder die Ausgabe sich in gleicher Weise wie die Eingabe ändert. Äquivalent dazu führt die Änderung einer beliebigen Variablen von 0 auf 1 niemals zu einer Änderung der Ausgabe von 1 auf 0. Operationen mit dieser Eigenschaft werden als monoton bezeichnet . Daher bezogen sich die bisherigen Axiome alle auf die monotone Boolesche Logik. Nichtmonotonie tritt über das Komplement ¬ wie folgt in Erscheinung. ^{[ 5 ]}

Die Komplementoperation wird durch die folgenden zwei Gesetze definiert.

${\displaystyle {\begin{aligned}&{\text{Komplement 1}}&x\wedge \neg x&=0\\&{\text{Komplement 2}}&x\vee \neg x&=1\end{aligned}}}$

Alle Eigenschaften der Negation, einschließlich der nachfolgenden Gesetze, folgen allein aus den beiden oben genannten Gesetzen. ^{[ 5 ]}

Sowohl in der gewöhnlichen als auch in der Booleschen Algebra funktioniert die Negation durch Vertauschen von Elementpaaren; daher erfüllt sie in beiden Algebren das Gesetz der doppelten Negation (auch Involutionsgesetz genannt).

${\displaystyle {\begin{aligned}&{\text{Doppelte Negation}}&\neg {(\neg {x})}&=x\end{aligned}}}$

Aber während die gewöhnliche Algebra die beiden Gesetze erfüllt

${\displaystyle {\begin{aligned}(-x)(-y)&=xy\\(-x)+(-y)&=-(x+y)\end{aligned}}}$

Die Boolesche Algebra erfüllt die De Morganschen Gesetze :

${\displaystyle {\begin{aligned}&{\text{De Morgan 1}}&\neg x\wedge \neg y&=\neg {(x\vee y)}\\&{\text{De Morgan 2}}&\neg x\vee \neg y&=\neg {(x\wedge y)}\end{aligned}}}$

Die oben aufgeführten Gesetze definieren die Boolesche Algebra, da sie den Rest des Themas implizieren. Die Komplementargesetze 1 und 2 genügen zusammen mit den monotonen Gesetzen für diesen Zweck und können daher als ein mögliches vollständiges Gesetzsystem bzw. als Axiomatisierung der Booleschen Algebra betrachtet werden. Jedes Gesetz der Booleschen Algebra folgt logisch aus diesen Axiomen. Darüber hinaus können Boolesche Algebren als Modelle dieser Axiome definiert werden, wie sie in § Boolesche Algebren behandelt werden .

Das Aufschreiben weiterer Gesetze der Booleschen Algebra kann weder neue Konsequenzen dieser Axiome nach sich ziehen, noch ein Modell dieser Axiome ausschließen. Im Gegenteil: In einer Liste, die einige, aber nicht alle dieser Gesetze enthält, könnten Boolesche Gesetze enthalten sein, die nicht aus den aufgeführten Gesetzen folgen, und darüber hinaus gäbe es Modelle der aufgeführten Gesetze, die keine Booleschen Algebren sind.

Diese Axiomatisierung ist keineswegs die einzige und auch nicht unbedingt die natürlichste, da nicht darauf geachtet wurde, ob einige Axiome aus anderen folgten. Vielmehr entschied man sich dafür, die Suche zu beenden, sobald genügend Gesetze gefunden worden waren (siehe dazu auch § Axiomatisierung der Booleschen Algebra) . Alternativ kann der Zwischenbegriff des Axioms ganz umgangen werden, indem man ein Boolesches Gesetz direkt als eine beliebige Tautologie definiert , also als eine Gleichung, die für alle Werte ihrer Variablen zwischen 0 und 1 gilt. ^{[ 27 ] [ 28 ]} Es lässt sich zeigen, dass alle diese Definitionen der Booleschen Algebra äquivalent sind.

Prinzip: Wenn {X, R} eine partiell geordnete Menge ist , dann ist auch {X, R(inverse)} eine partiell geordnete Menge.

Die Wahl der Symbole für die Werte der Booleschen Algebra ist nichts Besonderes. 0 und 1 könnten in α und β umbenannt werden , und solange dies einheitlich gehandhabt wird, bliebe es immer noch Boolesche Algebra, wenn auch mit einigen offensichtlichen kosmetischen Unterschieden.

Angenommen, 0 und 1 würden in 1 und 0 umbenannt. Dann bliebe es weiterhin Boolesche Algebra, und es würden dieselben Werte verarbeitet. Allerdings wäre sie nicht mehr identisch mit der ursprünglichen Booleschen Algebra, da sich ∨ nun wie ∧ verhält und umgekehrt. Es gibt also weiterhin einige kosmetische Unterschiede, die die geänderte Notation verdeutlichen, obwohl weiterhin 0 und 1 verwendet werden.

Wenn aber zusätzlich zu den Namen der Werte auch die Namen der beiden binären Operationen vertauscht werden, ist nichts mehr davon erkennbar. Das Endergebnis ist vom Ausgangszustand nicht zu unterscheiden. Die Spalten für x ∧ y und x ∨ y in den Wahrheitstabellen haben zwar ihre Plätze getauscht, aber dieser Tausch ist unerheblich .

Wenn sich Werte und Operationen so paarweise zusammensetzen lassen, dass beim gleichzeitigen Vertauschen aller Paare nichts Wesentliches verändert wird, nennt man die Elemente jedes Paares zueinander dual . So sind beispielsweise 0 und 1 dual, und ∧ und ∨ sind ebenfalls dual. Das Dualitätsprinzip , auch De Morgansche Dualität genannt , besagt, dass die Boolesche Algebra unverändert bleibt, wenn alle dualen Paare vertauscht werden.

Eine Änderung, die im Rahmen dieses Austauschs nicht erforderlich war, war die Komplementierung. Die Komplementierung ist eine selbstduale Operation. Die Identitätsoperation x (Kopie der Eingabe in die Ausgabe) ist ebenfalls selbstdual. Ein komplexeres Beispiel für eine selbstduale Operation ist ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) . Es gibt keine selbstduale binäre Operation, die von beiden Argumenten abhängt. Die Komposition von selbstdualen Operationen ist wieder eine selbstduale Operation. Wenn beispielsweise f ( x , y , z ) = ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) , dann ist f ( f ( x , y , z ), x , t ) eine selbstduale Operation mit vier Argumenten x , y , z , t .

Das Dualitätsprinzip lässt sich gruppentheoretisch dadurch erklären , dass es genau vier Funktionen gibt, die bijektive Abbildungen ( Automorphismen ) der Menge der Booleschen Polynome auf sich selbst darstellen: die Identitätsfunktion, die Komplementärfunktion, die Dualfunktion und die kontraduale (komplementierte Dual-)Funktion. Diese vier Funktionen bilden unter Funktionskomposition eine Gruppe , die isomorph zur Kleinschen Vierergruppe ist und auf der Menge der Booleschen Polynome operiert . Walter Gottschalk bemerkte daher, dass ein treffenderer Name für dieses Phänomen das Prinzip (oder Quadrat ) der Quaternalität wäre . ^{[ 5 ] : 21–22}

Ein Venn-Diagramm ^{[ 29 ]} kann zur Darstellung einer booleschen Operation mithilfe schattierter, sich überlappender Bereiche verwendet werden. Für jede Variable gibt es einen Bereich; in den hier gezeigten Beispielen sind alle Bereiche kreisförmig. Das Innere und Äußere des Bereichs x entsprechen den Werten 1 (wahr) bzw. 0 (falsch) für die Variable x . Die Schattierung gibt den Wert der Operation für jede Kombination von Bereichen an, wobei dunkel für 1 und hell für 0 steht (manche Autoren verwenden die umgekehrte Konvention).

Die drei Venn-Diagramme in der folgenden Abbildung stellen jeweils die Konjunktion x ∧ y , die Disjunktion x ∨ y und das Komplement ¬ x dar .

Bei der Konjunktion ist der Bereich innerhalb beider Kreise schattiert, um anzuzeigen, dass x ∧ y gleich 1 ist, wenn beide Variablen gleich 1 sind. Die anderen Bereiche bleiben unschattiert, um anzuzeigen, dass x ∧ y für die anderen drei Kombinationen gleich 0 ist.

Das zweite Diagramm stellt die Disjunktion x ∨ y dar , indem die Bereiche schattiert werden, die innerhalb eines oder beider Kreise liegen. Das dritte Diagramm stellt das Komplement ¬ x dar , indem der Bereich außerhalb des Kreises schattiert wird .

Obwohl wir die Venn-Diagramme für die Konstanten 0 und 1 nicht dargestellt haben, sind sie trivial: Sie bestehen jeweils aus einem weißen und einem dunklen Kästchen, die keinen Kreis enthalten. Wir könnten jedoch für x einen Kreis in diese Kästchen einfügen. In diesem Fall würde jedes Kästchen eine Funktion mit einem Argument x darstellen, die unabhängig von x denselben Wert zurückgibt – eine sogenannte konstante Funktion. Hinsichtlich ihrer Ausgabewerte sind Konstanten und konstante Funktionen nicht zu unterscheiden. Der Unterschied besteht darin, dass eine Konstante keine Argumente benötigt (nulläre Operation ) , während eine konstante Funktion ein Argument benötigt, das sie ignoriert ( unäre Operation).

Venn-Diagramme eignen sich gut zur Visualisierung von Gesetzen. Die Kommutativitätsgesetze für ∧ und ∨ lassen sich anhand der Symmetrie der Diagramme erkennen: Eine nicht kommutative binäre Operation hätte kein symmetrisches Diagramm, da das Vertauschen von x und y einer horizontalen Spiegelung des Diagramms gleichkäme und ein Verstoß gegen die Kommutativität somit als Verletzung der Symmetrie erscheinen würde.

Die Idempotenz von ∧ und ∨ lässt sich visualisieren, indem man die beiden Kreise zusammenschiebt und feststellt, dass die schattierte Fläche dann sowohl für ∧ als auch für ∨ den gesamten Kreis bildet.

Um das erste Absorptionsgesetz, x ∧ ( x ∨ y ) = x , zu sehen, beginnen Sie mit dem mittleren Diagramm für x ∨ y und beachten Sie, dass der schattierte Bereich, der mit dem x- Kreis übereinstimmt, dem gesamten x- Kreis entspricht. Für das zweite Absorptionsgesetz, x ∨ ( x ∧ y ) = x , beginnen Sie mit dem linken Diagramm für x ∧ y und beachten Sie, dass durch Schattieren des gesamten x -Kreises nur der x- Kreis schattiert wird, da die vorherige Schattierung innerhalb des x- Kreises lag.

Das Gesetz der doppelten Negation kann man sehen, indem man die Schattierung im dritten Diagramm für ¬ x ergänzt, die den x- Kreis schattiert .

Um das erste De Morgansche Gesetz, (¬x ) ∧ ( ¬y ) = ¬( x ∨ y ) , zu veranschaulichen, beginnen wir mit dem mittleren Diagramm für x ∨ y und ergänzen dessen Schattierung so, dass nur die Fläche außerhalb beider Kreise schattiert ist. Dies entspricht der Beschreibung der rechten Seite des Gesetzes. Das Ergebnis ist dasselbe, als würden wir die Fläche schattieren, die sowohl außerhalb des x- Kreises als auch außerhalb des y- Kreises liegt, also die Konjunktion ihrer äußeren Bereiche. Dies entspricht der Beschreibung der linken Seite des Gesetzes.

Das zweite De Morgansche Gesetz, (¬ x ) ∨ (¬ y ) = ¬( x ∧ y ) , funktioniert analog, wenn die beiden Diagramme vertauscht werden.

Das erste Komplementärgesetz, x ∧ ¬x = 0 , besagt, dass sich das Innere und Äußere des x- Kreises nicht überschneiden. Das zweite Komplementärgesetz, x ∨ ¬x = 1 , besagt, dass alles entweder innerhalb oder außerhalb des x- Kreises liegt.

Digitale Logik ist die Anwendung der Booleschen Algebra von 0 und 1 auf elektronische Hardware, bestehend aus Logikgattern, die zu einem Schaltplan verbunden sind. Jedes Gatter implementiert eine Boolesche Operation und wird schematisch durch ein Symbol dargestellt, das die Operation angibt. Die Symbole für Konjunktion (UND-Gatter), Disjunktion (ODER-Gatter) und Komplement (Inverter) sind wie folgt: ^{[ 30 ]}

Die Linien links von jedem Gatter stellen Eingangsleitungen oder -anschlüsse dar . Der Eingangswert wird durch eine Spannung an der Zuleitung angezeigt. Bei sogenannter „aktiv-hoch“-Logik entspricht 0 einer Spannung nahe Null oder Masse, während 1 einer Spannung nahe der Versorgungsspannung entspricht; bei aktiv-niedrig ist dies umgekehrt. Die Linie rechts von jedem Gatter stellt den Ausgangsanschluss dar, der üblicherweise denselben Spannungskonventionen wie die Eingangsanschlüsse folgt.

Die Komplementierung wird mit einem Inverter-Gatter realisiert. Das Dreieck symbolisiert die Operation, die das Eingangssignal einfach auf den Ausgang kopiert; der kleine Kreis am Ausgang kennzeichnet die eigentliche Invertierung, die das Eingangssignal komplementiert. Die Konvention, einen solchen Kreis an einem beliebigen Port anzubringen, bedeutet, dass das durch diesen Port fließende Signal auf dem Weg komplementiert wird, unabhängig davon, ob es sich um einen Eingangs- oder Ausgangsport handelt.

Das Dualitätsprinzip , auch De Morgansche Gesetze genannt , besagt, dass die Komplementierung aller drei Eingänge eines UND-Gatters dieses in ein ODER-Gatter umwandelt und umgekehrt, wie in Abbildung 4 unten dargestellt. Die Komplementierung beider Eingänge eines Inverters hingegen ändert dessen Funktion nicht.

Allgemeiner lässt sich jede der acht Teilmengen der drei Eingänge eines UND- oder ODER-Gatters komplementieren. Die daraus resultierenden sechzehn Möglichkeiten führen zu nur acht Booleschen Operationen, nämlich solchen mit einer ungeraden Anzahl von Einsen in ihrer Wahrheitstabelle. Es gibt acht solcher Operationen, da das „ungerade Bit“ entweder 0 oder 1 sein und an einer von vier Positionen in der Wahrheitstabelle stehen kann. Da es sechzehn binäre Boolesche Operationen gibt, bleiben acht Operationen mit einer geraden Anzahl von Einsen in ihren Wahrheitstabellen übrig. Zwei davon sind die Konstanten 0 und 1 (als binäre Operationen, die beide Eingänge ignorieren); vier sind die Operationen, die nichttrivial von genau einem ihrer beiden Eingänge abhängen, nämlich x , y , ¬x und ¬y ; und die verbleibenden zwei sind x ⊕ y (XOR) und sein Komplement x ≡ y .

Der Begriff „Algebra“ bezeichnet sowohl ein Gebiet, nämlich die Algebra selbst , als auch ein Objekt, nämlich eine algebraische Struktur . Während sich der obige Abschnitt mit der Booleschen Algebra befasst hat, behandelt dieser Abschnitt mathematische Objekte, die als Boolesche Algebren bezeichnet werden und allgemein als beliebige Modelle der Booleschen Gesetze definiert sind. Wir beginnen mit einem Spezialfall, der ohne Bezugnahme auf die Gesetze definierbar ist, nämlich konkreten Booleschen Algebren, und geben anschließend die formale Definition des allgemeinen Begriffs an.

Eine konkrete Boolesche Algebra oder ein Mengenkörper ist jede nichtleere Menge von Teilmengen einer gegebenen Menge X, die bezüglich der Mengenoperationen Vereinigung , Schnittmenge und Komplement bezüglich X abgeschlossen ist . ^{[ 5 ]}

(Historisch gesehen musste X selbst ebenfalls nicht leer sein, um die degenerierte oder einelementige Boolesche Algebra auszuschließen. Diese stellt die einzige Ausnahme von der Regel dar, dass alle Booleschen Algebren dieselben Gleichungen erfüllen, da die degenerierte Algebra jede Gleichung erfüllt. Dieser Ausschluss steht jedoch im Widerspruch zur bevorzugten rein gleichungsbasierten Definition der „Booleschen Algebra“, da es keine Möglichkeit gibt, die einelementige Algebra allein anhand von Gleichungen auszuschließen – 0 ≠ 1 zählt nicht, da es sich um eine negierte Gleichung handelt. Daher erlauben moderne Autoren die degenerierte Boolesche Algebra und lassen X leer.)

Beispiel 1. Die Potenzmenge 2 ^X von X , bestehend aus allen Teilmengen von X. Hierbei kann X eine beliebige Menge sein: leer, endlich, unendlich oder sogar überabzählbar .

Beispiel 2. Die leere Menge und X. Diese zweielementige Algebra zeigt, dass eine konkrete Boolesche Algebra auch dann endlich sein kann, wenn sie aus Teilmengen einer unendlichen Menge besteht. Man sieht, dass jeder Körper von Teilmengen von X die leere Menge und X enthalten muss . Daher ist kein kleineres Beispiel möglich, außer der entarteten Algebra, die man erhält, indem man X leer setzt, sodass die leere Menge und X zusammenfallen.

Beispiel 3. Die Menge der endlichen und koendlichen Mengen von ganzen Zahlen, wobei eine koendliche Menge genau dann eine ist, wenn sie nur endlich viele ganze Zahlen auslässt. Diese Menge ist offensichtlich abgeschlossen unter Komplementbildung und auch unter Vereinigung, da die Vereinigung einer koendlichen Menge mit einer beliebigen Menge wieder koendlich ist, während die Vereinigung zweier endlicher Mengen endlich ist. Die Schnittmenge verhält sich wie die Vereinigung, nur dass „endlich“ und „koendlich“ vertauscht sind. Dieses Beispiel ist abzählbar unendlich, da es nur abzählbar viele endliche Mengen von ganzen Zahlen gibt.

Beispiel 4. Um den in Beispiel 2 dargestellten Punkt zu verdeutlichen, betrachten wir ein Venn-Diagramm, das aus n geschlossenen Kurven besteht, welche das Diagramm in 2 ^ⁿ Regionen unterteilen . Sei X die (unendliche) Menge aller Punkte in der Ebene, die nicht auf einer Kurve liegen, aber irgendwo innerhalb des Diagramms. Das Innere jeder Region ist somit eine unendliche Teilmenge von X , und jeder Punkt in X gehört genau zu einer Region. Dann ist die Menge aller 2 ^ⁿ möglichen Vereinigungen von Regionen (einschließlich der leeren Menge, die sich aus der Vereinigung der leeren Menge aller Regionen und X als Vereinigung aller 2^ⁿ Regionen ergibt) bezüglich Vereinigung, Schnitt und Komplement bezüglich X abgeschlossen und bildet daher eine konkrete Boolesche Algebra. Auch hier gibt es nur endlich viele Teilmengen einer unendlichen Menge, die eine konkrete Boolesche Algebra bilden. Beispiel 2 ergibt sich aus dem Fall n = 0 (keine Kurven).

Eine Teilmenge Y von X kann durch eine indizierte Bitfamilie mit Indexmenge X identifiziert werden , wobei das Bit, das durch x ∈ X indiziert wird , den Wert 1 oder 0 annimmt, je nachdem, ob x ∈ Y gilt oder nicht . (Dies ist die sogenannte charakteristische Funktion einer Teilmenge.) Beispielsweise besteht ein 32-Bit-Computerwort aus 32 Bits, die durch die Menge {0, 1, 2, ..., 31} indiziert werden, wobei 0 und 31 das niederwertigste bzw. höchstwertigste Bit indizieren. Betrachten wir als kleineres Beispiel a , ${\displaystyle X=\{a,b,c\}}$b, c als Bitpositionen in dieser Reihenfolge von links nach rechts, so lassen sich die acht Teilmengen {}, { c } , { b }, { b , c }, { a }, { a , c } , { a , b } und { a , b , c } von X mit den entsprechenden Bitvektoren 000, 001, 010, 011, 100, 101, 110 und 111 identifizieren. Bitvektoren, die durch die Menge der natürlichen Zahlen indiziert sind, bilden unendliche Bitfolgen , während solche, die durch die reellen Zahlen im Einheitsintervall [0,1] indiziert sind, zu dicht gepackt sind, um konventionell geschrieben werden zu können, aber dennoch wohldefinierte indizierte Familien bilden (man stelle sich vor, man färbe jeden Punkt des Intervalls [0,1] unabhängig voneinander entweder schwarz oder weiß; die schwarzen Punkte bilden dann eine beliebige Teilmenge von [0,1]).

Aus dieser Bitvektor-Perspektive lässt sich eine konkrete Boolesche Algebra äquivalent als eine nichtleere Menge von Bitvektoren definieren, die alle die gleiche Länge haben (allgemeiner: durch dieselbe Menge indiziert werden) und unter den Bitvektoroperationen ∧, ∨ und ¬ abgeschlossen sind , wie in 1010∧0110 = 0010 , 1010∨0110 = 1110 , und ¬1010 = 0101 , den Bitvektorrealisierungen von Schnittmenge, Vereinigung bzw. Komplement.

Die Menge {0,1} und ihre oben behandelten Booleschen Operationen lassen sich als Spezialfall von Bitvektoren der Länge eins verstehen, die durch die Identifizierung von Bitvektoren mit Teilmengen auch als die beiden Teilmengen einer einelementigen Menge interpretiert werden können. Dies wird als prototypische Boolesche Algebra bezeichnet, was sich durch folgende Beobachtung begründen lässt.

Die Gesetze, denen alle nicht-ausgearteten konkreten Booleschen Algebren genügen, stimmen mit denen der prototypischen Booleschen Algebra überein.

Diese Beobachtung wird wie folgt bewiesen. Jede Regel, die von allen konkreten Booleschen Algebren erfüllt wird, wird selbstverständlich auch von der prototypischen erfüllt, da diese konkret ist. Umgekehrt muss jede Regel, die für eine konkrete Boolesche Algebra nicht gilt, an einer bestimmten Bitposition nicht gelten; in diesem Fall liefert genau diese Position ein Ein-Bit-Gegenbeispiel zu der betreffenden Regel. Die Nichtentartung gewährleistet die Existenz mindestens einer solchen Bitposition, da es nur einen leeren Bitvektor gibt.

Das Endziel des nächsten Abschnitts besteht darin, den Begriff „konkret“ aus der obigen Beobachtung zu eliminieren. Dieses Ziel wird durch die stärkere Aussage erreicht, dass bis auf Isomorphie alle Booleschen Algebren konkret sind.

Bisher waren alle Booleschen Algebren konkret und bestanden aus Bitvektoren oder, äquivalent dazu, aus Teilmengen einer Menge. Eine solche Boolesche Algebra besteht aus einer Menge und Operationen auf dieser Menge, die nachweislich die Gesetze der Booleschen Algebra erfüllen.

Anstatt zu zeigen, dass die Booleschen Gesetze erfüllt sind, können wir stattdessen eine Menge X , zwei binäre Operationen auf X und eine unäre Operation postulieren und fordern , dass diese Operationen die Gesetze der Booleschen Algebra erfüllen. Die Elemente von X müssen keine Bitvektoren oder Teilmengen sein, sondern können beliebige Datentypen sein. Dies führt zu der allgemeineren abstrakten Definition.

Eine Boolesche Algebra ist jede Menge mit binären Operationen ∧ und ∨ und einer unären Operation ¬, die die Booleschen Gesetze erfüllt. ^{[ 31 ]}

Für diese Definition ist es unerheblich, wie die Operationen die Gesetze erfüllen, ob durch Dekret oder Beweis. Alle konkreten Booleschen Algebren erfüllen die Gesetze (durch Beweis, nicht durch Dekret), daher ist jede konkrete Boolesche Algebra gemäß unserer Definition eine Boolesche Algebra. Diese axiomatische Definition einer Booleschen Algebra als Menge und bestimmte Operationen, die bestimmte Gesetze oder Axiome per Dekret erfüllen , ist völlig analog zu den abstrakten Definitionen von Gruppe , Ring , Körper usw., die für die moderne oder abstrakte Algebra charakteristisch sind .

Bei jeder vollständigen Axiomatisierung der Booleschen Algebra, wie etwa den Axiomen eines komplementierten distributiven Verbandes , ist eine hinreichende Bedingung dafür, dass eine algebraische Struktur dieser Art alle Booleschen Gesetze erfüllt, dass sie genau diese Axiome erfüllt. Die folgende Definition ist daher äquivalent.

Eine Boolesche Algebra ist ein komplementierter distributiver Verband.

Im Abschnitt über Axiomatisierung werden weitere Axiomatisierungen aufgeführt, von denen jede als Grundlage für eine äquivalente Definition dienen kann.

Obwohl jede konkrete Boolesche Algebra eine Boolesche Algebra ist, muss nicht jede Boolesche Algebra konkret sein. Sei n eine quadratfreie positive ganze Zahl, die nicht durch das Quadrat einer ganzen Zahl teilbar ist, beispielsweise 30, aber nicht 12. Es lässt sich zeigen, dass die Operationen des größten gemeinsamen Teilers (ggT) , des kleinsten gemeinsamen Vielfachen ( kgV ) und der Division durch n (d. h. ¬x = n / x ) alle Booleschen Gesetze erfüllen, wenn ihre Argumente die positiven Teiler von n durchlaufen . Daher bilden diese Teiler eine Boolesche Algebra. Da diese Teiler keine Teilmengen einer Menge sind, ist die Menge der Teiler von n eine Boolesche Algebra, die gemäß unseren Definitionen nicht konkret ist.

Wenn jedoch jeder Teiler von n durch die Menge seiner Primfaktoren dargestellt wird , ist diese nicht-konkrete Boolesche Algebra isomorph zur konkreten Booleschen Algebra, die aus allen Mengen von Primfaktoren von n besteht . Die Vereinigung entspricht dabei dem kleinsten gemeinsamen Vielfachen, der Schnitt dem größten gemeinsamen Teiler und das Komplement der Division durch n . Obwohl dieses Beispiel also technisch gesehen nicht konkret ist, ist es durch diese Darstellung, die als Isomorphismus bezeichnet wird, zumindest gewissermaßen konkret . Dieses Beispiel ist ein Anwendungsfall des folgenden Konzepts.

Eine Boolesche Algebra heißt darstellbar , wenn sie isomorph zu einer konkreten Booleschen Algebra ist.

Die nächste Frage wird wie folgt positiv beantwortet.

Jede Boolesche Algebra ist darstellbar.

Das heißt, bis auf Isomorphie sind abstrakte und konkrete Boolesche Algebren identisch. Dieses Ergebnis beruht auf dem Booleschen Primidealsatz , einem Auswahlprinzip, das etwas schwächer ist als das Auswahlaxiom . Diese starke Beziehung impliziert ein schwächeres Ergebnis, das die Beobachtung aus dem vorherigen Unterabschnitt zu folgender einfacher Konsequenz der Darstellbarkeit verschärft.

Die Gesetze, die von allen Booleschen Algebren erfüllt werden, stimmen mit denen der prototypischen Booleschen Algebra überein.

Sie ist insofern schwächer, als sie nicht per se Repräsentierbarkeit impliziert. Boolesche Algebren bilden hier eine Sonderstellung; beispielsweise ist eine Relationsalgebra eine Boolesche Algebra mit zusätzlicher Struktur, aber nicht jede Relationsalgebra ist im für Relationsalgebren typischen Sinne repräsentierbar.

Die obige Definition einer abstrakten Booleschen Algebra als Menge von Operationen, die „die“ Booleschen Gesetze erfüllen, wirft die Frage auf, was diese Gesetze sind. Eine einfache Antwort wäre „alle Booleschen Gesetze“, definiert als alle Gleichungen, die für die Boolesche Algebra von 0 und 1 gelten. Da es jedoch unendlich viele solcher Gesetze gibt, ist dies in der Praxis keine zufriedenstellende Antwort, was zu der Frage führt, ob es ausreicht, nur endlich viele Gesetze zu fordern.

Im Fall von Booleschen Algebren lautet die Antwort „ja“: Die oben aufgeführten endlich vielen Gleichungen genügen. Daher sagt man, dass Boolesche Algebren endlich axiomatisierbar oder endlich fundiert sind .

Darüber hinaus lässt sich die Anzahl der benötigten Gleichungen weiter reduzieren. Zunächst einmal ergeben sich einige der obigen Gesetze aus anderen. Eine hinreichende Teilmenge der obigen Gesetze besteht aus den Paaren von Assoziativ-, Kommutativ- und Absorptionsgesetzen, der Distributivität von ∧ über ∨ (oder dem anderen Distributivgesetz – eines genügt) und den beiden Komplementgesetzen. Tatsächlich handelt es sich hierbei um die traditionelle Axiomatisierung der Booleschen Algebra als komplementierter distributiver Verband .

Durch die Einführung weiterer, oben nicht aufgeführter Gesetze lässt sich die Liste der benötigten Gleichungen noch weiter verkürzen; beispielsweise genügt mit dem senkrechten Strich als Symbol für die Sheffer- Operation ein einzelnes Axiom, um die Boolesche Algebra vollständig zu axiomatisieren. Es ist auch möglich, längere einzelne Axiome mithilfe konventionellerer Operationen zu finden; siehe Minimale Axiome für die Boolesche Algebra . ^{[ 32 ]}${\displaystyle ((a\mid b)\mid c)\mid (a\mid ((a\mid c)\mid a))=c}$

Die Aussagenlogik ist ein logisches System , das eng mit der Booleschen Algebra verbunden ist. ^{[ 5 ]} Viele syntaktische Konzepte der Booleschen Algebra lassen sich mit nur geringfügigen Änderungen in Notation und Terminologie auf die Aussagenlogik übertragen, während die Semantik der Aussagenlogik über Boolesche Algebren so definiert wird, dass die Tautologien (Sätze) der Aussagenlogik den Gleichungssätzen der Booleschen Algebra entsprechen.

Syntaktisch entspricht jeder Boolesche Term einer Aussagenformel der Aussagenlogik. In dieser Übersetzung zwischen Boolescher Algebra und Aussagenlogik werden Boolesche Variablen x, y, ... zu Aussagenvariablen (oder Atomen ) P, Q , ... Boolesche Terme wie x ∨ y werden zu Aussagenformeln P ∨ Q ; 0 wird zu falsch oder ⊥ und 1 zu wahr oder ⊤ . Bei der Bezeichnung allgemeiner Aussagen ist es zweckmäßig, die griechischen Buchstaben Φ, Ψ, ... als Metavariablen (Variablen außerhalb der Sprache der Aussagenlogik, die im Kontext der Aussagenlogik verwendet werden) zu verwenden.

Die Semantik der Aussagenlogik basiert auf Wahrheitszuweisungen . Die Grundidee einer Wahrheitszuweisung besteht darin, dass die Aussagenvariablen auf Elemente einer festen Booleschen Algebra abgebildet werden. Der Wahrheitswert einer Aussagenformel, die diese Variablen verwendet, ist dann das Element der Booleschen Algebra, das sich durch Berechnung des Wertes des der Formel entsprechenden Booleschen Terms ergibt. In der klassischen Semantik wird nur die zweielementige Boolesche Algebra verwendet, während in der Boolesch-wertigen Semantik beliebige Boolesche Algebren berücksichtigt werden. Eine Tautologie ist eine Aussagenformel, der durch jede Wahrheitszuweisung ihrer Aussagenvariablen an eine beliebige Boolesche Algebra (oder äquivalent dazu durch jede Wahrheitszuweisung an die zweielementige Boolesche Algebra) der Wahrheitswert 1 zugewiesen wird .

Diese Semantik ermöglicht eine Übersetzung zwischen Tautologien der Aussagenlogik und Gleichungssätzen der Booleschen Algebra. Jede Tautologie Φ der Aussagenlogik lässt sich als Boolesche Gleichung Φ = 1 ausdrücken, welche einen Satz der Booleschen Algebra darstellt. Umgekehrt entspricht jeder Satz Φ = Ψ der Booleschen Algebra den Tautologien (Φ ∨ ¬Ψ) ∧ (¬Φ ∨ Ψ) und (Φ ∧ Ψ) ∨ (¬Φ ∧ ¬Ψ). Existiert der Operator → in der Sprache, lassen sich diese letztgenannten Tautologien auch als (Φ → Ψ) ∧ (Ψ → Φ) oder als zwei separate Sätze Φ → Ψ und Ψ → Φ schreiben. Wenn ≡ verfügbar ist, dann kann die einfache Tautologie Φ ≡ Ψ verwendet werden.

Eine motivierende Anwendung der Aussagenlogik ist die Analyse von Aussagen und deduktiven Argumenten in der natürlichen Sprache. ^{[ 33 ]} Während die Aussage „Wenn x = 3, dann x + 1 = 4“ von der Bedeutung von Symbolen wie + und 1 abhängt, ist dies bei der Aussage „Wenn x = 3, dann x = 3“ nicht der Fall; sie ist allein aufgrund ihrer Struktur wahr und bleibt wahr, egal ob „ x = 3“ durch „ x = 4“ oder „Der Mond besteht aus grünem Käse“ ersetzt wird . Die allgemeine oder abstrakte Form dieser Tautologie lautet „Wenn P , dann P “ oder , in der Sprache der Booleschen Algebra, P → P.

Ersetzt man P durch x = 3 oder eine andere Aussage, nennt man das Instanziieren von P durch diese Aussage. Das Ergebnis der Instanziierung von P in einer abstrakten Aussage heißt Instanz der Aussage. So ist x = 3 → x = 3 eine Tautologie, da sie eine Instanz der abstrakten Tautologie P → P ist . Alle Vorkommen der instanziierten Variable müssen mit derselben Aussage instanziiert werden, um Unsinn wie P → x = 3 oder x = 3 → x = 4 zu vermeiden.

Der Aussagenkalkül beschränkt die Betrachtung auf abstrakte Aussagen, also solche, die aus Aussagenvariablen mithilfe boolescher Operationen gebildet werden. Instanziierung ist im Aussagenkalkül weiterhin möglich, jedoch nur durch Instanziierung von Aussagenvariablen durch abstrakte Aussagen, wie beispielsweise die Instanziierung von Q durch Q → P in P → ( Q → P ), um die Instanz P → (( Q → P ) → P ) zu erhalten.

(Die Verfügbarkeit von Instanziierungen als Teil des Apparats der Aussagenlogik vermeidet die Notwendigkeit von Metavariablen innerhalb der Sprache der Aussagenlogik, da gewöhnliche Aussagenvariablen innerhalb der Sprache betrachtet werden können, um beliebige Aussagen zu bezeichnen. Die Metavariablen selbst liegen außerhalb der Reichweite der Instanziierung, da sie nicht Teil der Sprache der Aussagenlogik sind, sondern vielmehr Teil derselben Sprache, in der über sie gesprochen wird und in der dieser Satz geschrieben ist, wo es notwendig ist, Aussagenvariablen und ihre Instanziierungen als unterschiedliche syntaktische Einheiten unterscheiden zu können.)

Eine Axiomatisierung der Aussagenlogik ist eine Menge von Tautologien, den sogenannten Axiomen, und einer oder mehreren Schlussregeln, mit denen sich aus bestehenden Tautologien neue ableiten lassen. Ein Beweis in einem Axiomensystem A ist eine endliche, nichtleere Folge von Aussagen, von denen jede entweder ein Beispiel für ein Axiom von A ist oder sich aus zuvor im Beweis vorkommenden Aussagen durch eine Regel von A ableiten lässt (wodurch Zirkelschlüsse ausgeschlossen werden). Die letzte Aussage ist der durch den Beweis bewiesene Satz . Jedes nichtleere Anfangssegment eines Beweises ist selbst ein Beweis, und somit ist jede Aussage in einem Beweis selbst ein Satz. Eine Axiomatisierung ist korrekt , wenn jeder Satz eine Tautologie ist, und vollständig, wenn jede Tautologie ein Satz ist. ^{[ 34 ]}

Die Aussagenlogik ist üblicherweise als Hilbert-System organisiert , dessen Operationen denen der Booleschen Algebra entsprechen und dessen Theoreme Boolesche Tautologien sind, also jene Booleschen Terme, die gleich der Booleschen Konstante 1 sind. Eine andere Form ist die Sequenzenlogik , die zwei Arten kennt: Aussagen wie in der gewöhnlichen Aussagenlogik und Paare von Aussagenlisten, sogenannte Sequenzen , wie z. B. A ∨ B , A ∧ C , ... ⊢ A , B → C , .... Die beiden Hälften einer Sequenz werden Antezedens bzw. Succedens genannt. Die übliche Metavariable für ein Antezedens oder einen Teil davon ist Γ, für ein Succedens Δ; so bezeichnet Γ, A ⊢ Δ eine Sequenz, deren Succedens eine Liste Δ und deren Antezedens eine Liste Γ mit einer angehängten zusätzlichen Aussage A ist . Das Antezedens wird als Konjunktion seiner Aussagen interpretiert, das Sukzedens als Disjunktion seiner Aussagen und das Sequent selbst als Folgerung des Sukzedens aus dem Antezedens.

Die Folgerung unterscheidet sich von der Implikation dadurch, dass letztere eine binäre Operation ist , die einen Wert in einer Booleschen Algebra zurückgibt, während erstere eine binäre Relation darstellt , die entweder gilt oder nicht gilt. In diesem Sinne ist die Folgerung eine externe Form der Implikation, d. h. sie ist außerhalb der Booleschen Algebra, da der Leser der Sequenz ebenfalls als extern betrachtet wird und Antezedenten und Succedenten in einer Booleschen Algebra interpretiert und vergleicht. Die natürliche Interpretation von ⊢ ist die eines ≤ in der partiellen Ordnung der Booleschen Algebra, definiert durch x ≤ y genau dann, wenn x ∨ y = y . Diese Möglichkeit, externe Implikation ⊢ und interne Implikation → in ein und derselben Logik zu kombinieren, gehört zu den wesentlichen Unterschieden zwischen Sequenzenkalkül und Aussagenkalkül. ^{[ 35 ]}

Die Boolesche Algebra als Zwei-Werte-Rechnung ist grundlegend für Computerschaltungen, Computerprogrammierung und mathematische Logik und findet auch in anderen Bereichen der Mathematik wie der Mengenlehre und Statistik Anwendung. ^{[ 5 ]}

Zu Beginn des 20. Jahrhunderts erkannten mehrere Elektrotechniker intuitiv, dass die Boolesche Algebra analog zum Verhalten bestimmter elektrischer Schaltungen ist. Claude Shannon bewies in seiner Masterarbeit von 1937 mit dem Titel „ A Symbolic Analysis of Relay and Switching Circuits“ formal, dass dieses Verhalten logisch äquivalent zur Booleschen Algebra ist .

Heutzutage funktionieren alle modernen Allzweckrechner mithilfe der zweiwertigen Booleschen Logik; das heißt, ihre elektrischen Schaltkreise sind eine physikalische Manifestation dieser Logik. Dies geschieht auf verschiedene Weise: durch Spannungen an Leitungen in Hochgeschwindigkeitsschaltungen und kapazitiven Speichermedien, durch die Ausrichtung magnetischer Domänen in ferromagnetischen Speichermedien, durch Löcher in Lochkarten oder Lochstreifen usw. (Einige frühe Computer verwendeten Dezimalschaltungen oder -mechanismen anstelle von zweiwertigen Logikschaltungen.)

Natürlich lassen sich in einem Medium mehr als zwei Symbole kodieren. Beispielsweise könnte man 0, 1, 2 und 3 Volt verwenden, um ein vierstelliges Alphabet auf einem Draht oder unterschiedlich große Löcher in einer Lochkarte zu kodieren. In der Praxis führen die strengen Anforderungen an hohe Geschwindigkeit, geringe Größe und niedrigen Stromverbrauch dazu, dass Rauschen eine entscheidende Rolle spielt. Dies erschwert die Unterscheidung von Symbolen, wenn an einer Stelle mehrere Symbole auftreten können. Anstatt zu versuchen, vier Spannungen auf einem Draht zu unterscheiden, haben sich Entwickler digitaler Schaltungen auf zwei Spannungen pro Draht geeinigt: eine hohe und eine niedrige.

Computer verwenden aus den oben genannten Gründen binäre Boolesche Schaltkreise. Die gängigsten Computerarchitekturen nutzen geordnete Folgen von Booleschen Werten, sogenannte Bits, mit 32 oder 64 Werten, z. B. 0110100011010110010101010101001011. Bei der Programmierung in Maschinencode , Assemblersprache und bestimmten anderen Programmiersprachen arbeiten Programmierer mit der digitalen Struktur der Datenregister . Diese Register arbeiten mit Spannungen, wobei null Volt dem Booleschen Wert 0 und eine Referenzspannung (oft +5 V, +3,3 V oder +1,8 V) dem Booleschen Wert 1 entspricht. Solche Sprachen unterstützen sowohl numerische als auch logische Operationen. In diesem Zusammenhang bedeutet „numerisch“, dass der Computer Bitfolgen als Binärzahlen (Zahlen zur Basis 2) behandelt und arithmetische Operationen wie Addition, Subtraktion, Multiplikation oder Division ausführt. „Logisch“ bezieht sich auf die Booleschen Operationen Disjunktion, Konjunktion und Negation zwischen zwei Bitfolgen, wobei jedes Bit der einen Folge mit seinem Gegenstück in der anderen Folge verglichen wird. Programmierer können daher je nach Bedarf entweder mit den Regeln der numerischen oder der Booleschen Algebra arbeiten und diese anwenden. Ein wesentliches Unterscheidungsmerkmal dieser Operationsfamilien ist das Vorhandensein der Übertragsoperation in der ersten, nicht aber in der zweiten.

Weitere Anwendungsgebiete der Zweiwertlogik sind Recht und Mathematik. Im alltäglichen, lockeren Gespräch sind differenzierte oder komplexe Antworten wie „vielleicht“ oder „nur am Wochenende“ akzeptabel. In fokussierteren Situationen wie vor Gericht oder in der theorembasierten Mathematik ist es jedoch vorteilhaft, Fragen so zu formulieren, dass eine einfache Ja/Nein-Antwort möglich ist – ist der Angeklagte schuldig oder nicht schuldig? Ist die Aussage wahr oder falsch? – und jede andere Antwort ausgeschlossen wird. Auch wenn dies in der Praxis für den Befragten einschränkend wirken mag, ist das Prinzip der einfachen Ja/Nein-Frage zu einem zentralen Bestandteil sowohl der juristischen als auch der mathematischen Logik geworden, sodass die Zweiwertlogik eine eigene Systematisierung und Erforschung verdient.

Ein zentrales Konzept der Mengenlehre ist die Zugehörigkeit. Eine Organisation kann mehrere Zugehörigkeitsgrade zulassen, wie beispielsweise Anfänger, assoziiertes Mitglied und Vollmitglied. Bei Mengen hingegen ist ein Element entweder Mitglied oder nicht. Die Kandidaten für die Zugehörigkeit zu einer Menge funktionieren wie die Leitungen in einem Digitalrechner: Jeder Kandidat ist entweder Mitglied oder Nichtmitglied, genau wie jede Leitung entweder auf hohem oder niedrigem Pegel liegt.

Da die Algebra ein grundlegendes Werkzeug in jedem Bereich ist, der sich einer mathematischen Behandlung unterziehen lässt, führen diese Überlegungen dazu, dass die Algebra zweier Werte von grundlegender Bedeutung für Computerhardware, mathematische Logik und Mengenlehre ist.

Die zweiwertige Logik lässt sich zur mehrwertigen Logik erweitern , insbesondere durch Ersetzen des booleschen Wertebereichs {0, 1} durch das Einheitsintervall [0,1]. In diesem Fall können Werte nicht nur 0 oder 1 annehmen, sondern jeder Wert zwischen 0 und 1 (einschließlich). Algebraisch wird die Negation (NICHT) durch 1 −  x , die Konjunktion (UND) durch die Multiplikation ( xy ) und die Disjunktion (ODER) durch die De Morganschen Gesetze definiert . Die Interpretation dieser Werte als logische Wahrheitswerte führt zu einer mehrwertigen Logik, die die Grundlage für Fuzzy-Logik und probabilistische Logik bildet . In diesen Interpretationen wird ein Wert als der „Grad“ der Wahrheit interpretiert – inwieweit eine Aussage wahr ist oder mit welcher Wahrscheinlichkeit sie wahr ist.

Die ursprüngliche Anwendung für Boolesche Operationen war die mathematische Logik , wo sie die Wahrheitswerte, wahr oder falsch, einzelner Formeln kombinieren.

Natürliche Sprachen wie Englisch verfügen über Wörter für verschiedene Boolesche Operationen, insbesondere Konjunktion ( und ), Disjunktion ( oder ), Negation ( nicht ) und Implikation ( impliziert ). „Nicht“ ist jedoch synonym mit „ und nicht“ . Werden diese logischen Konjunktionen verwendet, um Situationsaussagen wie „Der Block liegt auf dem Tisch“ und „Katzen trinken Milch“ zu verbinden, die naiv betrachtet entweder wahr oder falsch sind, entspricht ihre Bedeutung oft der ihrer logischen Entsprechungen . Bei Verhaltensbeschreibungen wie „Jim ging durch die Tür“ fallen jedoch Unterschiede auf, beispielsweise die fehlende Kommutativität. Die Konjunktion von „Jim öffnete die Tür“ mit „Jim ging durch die Tür“ ist in dieser Reihenfolge nicht äquivalent zur Konjunktion in der anderen Reihenfolge, da „ und “ in solchen Fällen üblicherweise „und dann“ bedeutet . Ähnliches gilt für Fragen: Die Reihenfolge „Ist der Himmel blau, und warum ist der Himmel blau?“ ist sinnvoller als die umgekehrte. Konjunktionale Befehle über Verhalten ähneln Verhaltensaussagen wie „ Zieh dich an“ und „Geh zur Schule“ . Disjunktive Befehle wie „ Lieb mich oder lass mich in Ruhe“ oder „Fisch oder lass die Finger davon“ sind oft asymmetrisch, da sie implizieren, dass eine Alternative weniger wünschenswert ist. Zusammengesetzte Substantive wie „ Tee“ und „Milch“ beschreiben im Allgemeinen eine Vereinigung, während „ Tee“ oder „Milch “ eine Wahlmöglichkeit darstellt. Der Kontext kann diese Bedeutungen jedoch umkehren, wie in „ Deine Wahlmöglichkeiten sind Kaffee und Tee“ , was üblicherweise dasselbe bedeutet wie „ Deine Wahlmöglichkeiten sind Kaffee oder Tee“ (Alternativen). Doppelte Negation, wie in „Ich mag Milch nicht“, bedeutet selten wörtlich „Ich mag Milch“, sondern vermittelt eher eine Art Abschwächung, als ob eine dritte Möglichkeit angedeutet würde. „Nicht nicht P“ kann lose als „sicherlich P“ interpretiert werden, und obwohl P notwendigerweise „nicht nicht P “ impliziert , ist die Umkehrung im Englischen fragwürdig, ähnlich wie intuitionistischer Logik . Angesichts des höchst individuellen Gebrauchs von Konjunktionen in natürlichen Sprachen kann die Boolesche Algebra nicht als zuverlässiger Rahmen für deren Interpretation gelten.

Boolesche Operationen werden in der digitalen Logik verwendet , um die auf einzelnen Leitungen übertragenen Bits zu kombinieren und sie so über {0,1} zu interpretieren. Werden zwei Bitvektoren mit jeweils n Bits mithilfe eines Vektors aus n identischen Binärgattern kombiniert , lassen sich die einzelnen Bitoperationen gemeinsam als eine einzige Operation auf Werten einer Booleschen Algebra mit 2^ⁿ Elementen verstehen.

Die naive Mengenlehre interpretiert Boolesche Operationen als Operationen auf Teilmengen einer gegebenen Menge X. Wie wir bereits gesehen haben, entspricht dieses Verhalten genau den koordinatenweisen Kombinationen von Bitvektoren, wobei die Vereinigung zweier Mengen der Disjunktion zweier Bitvektoren entspricht und so weiter.

Die freie Boolesche Algebra mit 256 Elementen und drei Generatoren wird in Computerbildschirmen mit Rastergrafik eingesetzt . Diese verwenden Bit-Blitting , um ganze Pixelbereiche zu manipulieren und legen mithilfe von Booleschen Operationen fest, wie der Quellbereich mit dem Zielbereich kombiniert werden soll, typischerweise mithilfe eines dritten Bereichs, der Maske . Moderne Grafikkarten bieten hierfür alle 256 ternären Operationen ( ^{2³ × 2²} × 3³ ), wobei die Auswahl der Operation ein 8-Bit-Parameter ist. Die Konstanten SRC = 0xaa oder 0b10101010 , DST = 0xcc oder 0b11001100 und MSK = 0xf0 oder 0b11110000 ermöglichen es, boolesche Operationen wie die XOR-Verknüpfung von Quelle und Ziel und die anschließende UND-Verknüpfung des Ergebnisses mit der Maske direkt als Konstante zu schreiben. Diese Konstante bezeichnet ein Byte, das zur Kompilierzeit berechnet wird ( 0x80 im Beispiel, 0x88 bei einfacher Berechnung usw.). Zur Laufzeit interpretiert die Grafikkarte das Byte als die durch den ursprünglichen Ausdruck angegebene Rasteroperation. Dies geschieht einheitlich, erfordert bemerkenswert wenig Hardware und ist zeitlich völlig unabhängig von der Komplexität des Ausdrucks. (SRC^DST)&MSK(SRC^DST)&MSKSRC^DST

CAD- Systeme ( Computer-Aided Design) bieten vielfältige Methoden, um Objekte aus anderen Objekten zu erstellen, darunter die Kombination mittels Boolescher Operationen. Dabei wird der Raum, in dem Objekte existieren, als Menge S von Voxeln (dem dreidimensionalen Analogon zu Pixeln in der zweidimensionalen Grafik) verstanden. Formen werden als Teilmengen von S definiert , wodurch Objekte durch Vereinigung, Schnittmenge usw. zu Mengen kombiniert werden können. Eine naheliegende Anwendung ist die Erstellung komplexer Formen aus einfachen Formen durch deren Vereinigung. Eine weitere Anwendung ist das Modellieren, verstanden als Materialabtrag: Jede Bearbeitungsoperation, wie Schleifen, Fräsen, Ausfräsen oder Bohren, die mit Maschinen an realen Materialien durchgeführt werden kann, lässt sich am Computer mit der Booleschen Operation x ∧ ¬y oder x −y simulieren . In der Mengenlehre entspricht dies der Differenz: Die Elemente von y werden von denen von x subtrahiert . Gegeben seien also zwei Formen – eine zu bearbeitende und die andere das zu entfernende Material. Das Ergebnis der Bearbeitung der Form zur Entfernung des Materials wird einfach als deren Differenzmenge beschrieben.

Suchmaschinenanfragen verwenden ebenfalls Boolesche Logik. In diesem Zusammenhang kann jede Webseite im Internet als „Element“ einer „Menge“ betrachtet werden. Die folgenden Beispiele verwenden eine von Google unterstützte Syntax . ^{[ NB 1 ]}

• Doppelte Anführungszeichen werden verwendet, um durch Leerzeichen getrennte Wörter zu einem einzigen Suchbegriff zu kombinieren. ^{[ NB 2 ]}
• Leerzeichen werden verwendet, um ein logisches UND anzugeben, da dies der Standardoperator für die Verknüpfung von Suchbegriffen ist:

"Suchbegriff 1" "Suchbegriff 2" 

• Das Schlüsselwort OR wird für logisches ODER verwendet:

"Suchbegriff 1" ODER "Suchbegriff 2" 

• Ein vorangestelltes Minuszeichen wird für die logische NICHT-Logik verwendet:

"Suchbegriff 1" − "Suchbegriff 2" 

• Klammern können die Suche erweitern: wenn die Begriffe 2 und 3 ähnliche Begriffe/Synonyme sind:

"Suchbegriff 1" und ("Suchbegriff 2" oder "Suchbegriff 3") 

• Mano, Morris; Ciletti, Michael D. (2013). Digital Design . Pearson. ISBN 978-0-13-277420-8Die
• Whitesitt, J. Eldon (1995). Boolesche Algebra und ihre Anwendungen . Courier Dover Publications . ISBN 978-0-486-68483-3Die
• Dwinger, Philip (1971). Einführung in Boolesche Algebren . Würzburg, Deutschland: Physica Verlag.
• Sikorski, Roman (1969). Boolesche Algebren (3. Aufl.). Berlin, Deutschland: Springer-Verlag . ISBN 978-0-387-04469-9Die
• Bocheński, Józef Maria (1959). Eine Zusammenfassung der mathematischen Logik . Aus dem Französischen und Deutschen übersetzt von Otto Bird. Dordrecht, Südholland: D. Reidel.

• Boole, George (1848). „The Calculus of Logic“ . Cambridge and Dublin Mathematical Journal . III : 183–198 .
• Hailperin, Theodore (1986). Booles Logik und Wahrscheinlichkeit: Eine kritische Darstellung aus der Perspektive der zeitgenössischen Algebra, Logik und Wahrscheinlichkeitstheorie (2. Aufl.). Elsevier . ISBN 978-0-444-87952-3Die
• Gabbay, Dov M.; Woods, John (Hrsg.). (2004). Die Entstehung der modernen Logik: von Leibniz bis Frege . Handbuch der Geschichte der Logik. Band 3. Elsevier . ISBN 978-0-444-51611-4Diemehrere einschlägige Kapitel von Hailperin, Valencia und Grattan-Guinness
• Badesa, Calixto (2004). „Kapitel 1. Klassenalgebra und Aussagenlogik“. Die Geburtsstunde der Modelltheorie: Der Satz von Löwenheim im Rahmen der Relativitätstheorie . Princeton University Press . ISBN 978-0-691-05853-5Die
• Stanković, Radomir S. [auf Deutsch] ; Astola, Jaakko Tapio [auf Finnisch] (2011). Verfasst in Niš, Serbien & Tampere, Finnland. Von der Booleschen Logik zu Schaltkreisen und Automaten: Auf dem Weg zu moderner Informationstechnologie . Studies in Computational Intelligence. Band 335 (1. Aufl.). Berlin & Heidelberg, Deutschland: Springer-Verlag . S. xviii + 212. doi : 10.1007/978-3-642-11682-7 . ISBN 978-3-642-11681-0. ISSN  1860-949X . LCCN  2011921126 . Abgerufen am 25.10.2022 .
• Eintrag „Die Algebra der Logiktradition“ von Stanley Burris in der Stanford Encyclopedia of Philosophy , 21. Februar 2012