Boolsche Algebra - Boolean algebra

In der Mathematik und mathematischen Logik ist die Boolesche Algebra der Zweig der Algebra, in dem die Werte der Variablen die Wahrheitswerte true und false sind , die normalerweise mit 1 bzw. 0 bezeichnet werden. Anstelle der elementaren Algebra , wo die Werte der Variablen Zahlen sind und die Primoperationen Addition und Multiplikation sind, sind die Hauptoperationen der Booleschen Algebra die Konjunktion ( und ) bezeichnet als ∧, die Disjunktion ( oder ) bezeichnet als ∨ und die Negation ( nicht ) als ¬ bezeichnet. Sie ist somit ein Formalismus zur Beschreibung logischer Operationen , genauso wie die elementare Algebra numerische Operationen beschreibt.

Die Boolesche Algebra wurde von George Boole in seinem ersten Buch The Mathematical Analysis of Logic (1847) eingeführt und in seiner An Investigation of the Laws of Thought (1854) ausführlicher dargelegt . Laut Huntington wurde der Begriff "Boolean Algebra" erstmals 1913 von Sheffer vorgeschlagen , obwohl Charles Sanders Peirce 1880 dem ersten Kapitel seiner "The Simplest Mathematics" den Titel "A Boolean Algebra with One Constant" gab war grundlegend für die Entwicklung der digitalen Elektronik und wird in allen modernen Programmiersprachen bereitgestellt . Es wird auch in der Mengenlehre und Statistik verwendet .

Geschichte

Ein Vorläufer der Booleschen Algebra war Gottfried Wilhelm Leibniz ‚s Algebra der Begriffe . Die Konzeptalgebra von Leibniz ist deduktiv äquivalent zur Booleschen Mengenalgebra.

Die Algebra von Boole ging den modernen Entwicklungen der abstrakten Algebra und der mathematischen Logik voraus ; es wird jedoch als mit den Ursprüngen beider Felder verbunden angesehen. In einer abstrakten Umgebung wurde die Boolesche Algebra Ende des 19. Jahrhunderts von Jevons , Schröder , Huntington und anderen perfektioniert , bis sie die moderne Vorstellung einer (abstrakten) mathematischen Struktur erreichte . Zum Beispiel wird die empirische Beobachtung, dass man Ausdrücke in der Algebra von Mengen manipulieren kann , indem man sie in Ausdrücke in der Booleschen Algebra übersetzt, in modernen Begriffen erklärt, indem man sagt, dass die Algebra von Mengen eine Boolesche Algebra ist (beachte den unbestimmten Artikel ). Tatsächlich bewies MH Stone 1936, dass jede Boolesche Algebra zu einem Feld von Mengen isomorph ist .

In den 1930er Jahren stellte Claude Shannon beim Studium von Schaltkreisen fest , dass man die Regeln der Booleschen Algebra auch in dieser Umgebung anwenden kann, und führte die Schaltalgebra ein, um Schaltkreise mit algebraischen Mitteln in Bezug auf logische Gatter zu analysieren und zu entwerfen . Shannon verfügte bereits über den abstrakten mathematischen Apparat, so dass er seine Schaltalgebra als zweielementige Boolesche Algebra formulierte . In modernen schaltungstechnischen Umgebungen müssen andere Boolesche Algebren kaum berücksichtigt werden, daher werden "Schaltalgebra" und "Boolesche Algebra" oft synonym verwendet.

Effiziente Umsetzung von Booleschen Funktionen ist ein grundsätzliches Problem bei der Konstruktion von kombinatorischen Logikschaltungen. Moderne elektronische Design-Automatisierungstools für VLSI-Schaltungen beruhen häufig auf einer effizienten Darstellung von Booleschen Funktionen, die als (reduzierte geordnete) Binärentscheidungsdiagramme (BDD) für die Logiksynthese und formale Verifikation bekannt sind .

Logische Sätze, die in der klassischen Aussagenkalküle ausgedrückt werden können, haben einen äquivalenten Ausdruck in der Booleschen Algebra. Daher wird die Boolesche Logik manchmal verwendet, um die auf diese Weise durchgeführte Aussagenkalküle zu bezeichnen. Boolesche Algebra reicht nicht aus, um logische Formeln mit Quantoren zu erfassen , wie sie aus der Logik erster Ordnung stammen .

Obwohl die Entwicklung der mathematischen Logik nicht dem Programm Booles folgte, wurde die Verbindung zwischen seiner Algebra und der Logik später im Rahmen der algebraischen Logik fest verankert , die auch die algebraischen Systeme vieler anderer Logiken untersucht. Das Problem der Bestimmung , ob die Variablen eines gegebenen Boolean (propositionaler) Formel kann in einer solchen Art und Weise zugeordnet werden , um die Formel zu machen , zu bewerten , um wahr wird das genannte Boolesche Erfüllbarkeit Problem (SAT), und ist von Bedeutung für theoretische Informatik , wobei das erste Problem ist NP-vollständig . Das eng verwandte Berechnungsmodell, das als Boolesche Schaltung bekannt ist, setzt die Zeitkomplexität (eines Algorithmus ) mit der Schaltungskomplexität in Beziehung .

Werte

Während Ausdrücke in der elementaren Algebra hauptsächlich Zahlen bezeichnen , bezeichnen sie in der Booleschen Algebra die Wahrheitswerte false und true . Diese Werte werden mit den Bits (oder Binärziffern) dargestellt, nämlich 0 und 1. Sie verhalten sich nicht wie die ganzen Zahlen 0 und 1, für die 1 + 1 = 2 , sondern können mit den Elementen des zweielementigen Feldes identifiziert werden GF(2) , dh ganzzahlige Arithmetik modulo 2 , für die 1 + 1 = 0 ist . Addition und Multiplikation spielen dann die booleschen Rollen von XOR (Exklusiv-Oder) bzw. AND (Konjunktion), wobei die Disjunktion xy (Inklusiv-Oder) als x + yxy definierbar ist .

Die Boolesche Algebra beschäftigt sich auch mit Funktionen , deren Werte in der Menge {0, 1} liegen. Eine Folge von Bits wird üblicherweise für solche Funktionen verwendet. Ein weiteres übliches Beispiel sind die Teilmengen einer Menge E : zu einer Teilmenge F von E kann man die Indikatorfunktion definieren , die den Wert 1 auf F und 0 außerhalb von F annimmt . Das allgemeinste Beispiel sind die Elemente einer Booleschen Algebra , wobei alle Vorhergehenden Beispiele davon sind.

Wie bei der elementaren Algebra kann auch der rein Gleichungsteil der Theorie entwickelt werden, ohne explizite Werte für die Variablen zu berücksichtigen.

Betrieb

Grundoperationen

Die grundlegenden Operationen der Booleschen Algebra sind Konjunktion , Disjunktion und Negation . Diese booleschen Operationen werden mit den entsprechenden binären Operatoren AND und OR und dem unären Operator NOT ausgedrückt , die zusammen als Boolesche Operatoren bezeichnet werden .

Die grundlegenden booleschen Operationen für die Variablen x und y sind wie folgt definiert:

Alternativ können die Werte von xy , xy und ¬ x kann durch Tabelliermaschinen ihre Werte mit ausgedrückt werden Wahrheitstabellen wie folgt:

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

Man könnte annehmen, dass nur die Negation und eine der beiden anderen Operationen grundlegend sind, aufgrund der folgenden Identitäten, die es ermöglichen, Konjunktion in Bezug auf Negation und Disjunktion zu definieren und umgekehrt ( De Morgans Gesetze ):

Sekundäroperationen

Die drei oben beschriebenen Booleschen Operationen werden als Basis bezeichnet, was bedeutet, dass sie als Grundlage für andere Boolesche Operationen verwendet werden können, die aus ihnen durch Komposition, die Art und Weise, wie Operationen kombiniert oder zusammengesetzt werden, aufgebaut werden können. Operationen, die sich aus den Grundoperationen zusammensetzen, umfassen die folgenden Beispiele:

Materialbedingt :
Exklusives ODER ( XOR ):
Logische Äquivalenz :

Diese Definitionen führen zu den folgenden Wahrheitstabellen, die die Werte dieser Operationen für alle vier möglichen Eingaben angeben.

Sekundäre Operationen. Tabelle 1
0 0 1 0 1
1 0 0 1 0
0 1 1 1 0
1 1 1 0 1
Materialbedingt
Die erste Operation x  →  y oder C xy wird als materielle Implikation bezeichnet . Wenn x wahr ist, wird der Wert von x  →  y als der von y angenommen (zB wenn x wahr und y falsch ist, dann ist x  →  y auch falsch). Wenn x jedoch falsch ist, kann der Wert von y ignoriert werden; Die Operation muss jedoch einen booleschen Wert zurückgeben, und es gibt nur zwei Möglichkeiten. So definitions x  →  y ist wahr , wenn x falsch ist. (Die Relevanzlogik legt diese Definition nahe, 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 exklusiv oder (oft abgekürzt als XOR) aus Disjunktion als inclusive Art zu unterscheiden. Es schließt die Möglichkeit aus, dass sowohl x als auch y wahr sind (zB siehe Tabelle): Wenn beide wahr sind, ist das Ergebnis falsch. Arithmetisch definiert ist es Addition, wobei mod 2 1 + 1 = 0 ist.
Logische Äquivalenz
Der dritte Betrieb, das Komplement von exklusiven oder ist die Gleichwertigkeit oder Booleschen Gleichheit: x  ≡  y oder E xy , gilt nur , wenn x und y denselben Wert haben. Daher kann x  ⊕  y als sein Komplement als x  ≠  y verstanden werden , was genau dann gilt, wenn x und y verschieden sind. Somit ist sein Gegenstück in der Arithmetik mod 2 x + y . Das Gegenstück zur Äquivalenz in der Arithmetik mod 2 ist x + y + 1.

Bei zwei Operanden mit jeweils zwei möglichen Werten ergeben sich 2 2 = 4 mögliche Kombinationen von Eingängen. Da jeder Ausgang zwei mögliche Werte haben kann, gibt es insgesamt 2 4 = 16 mögliche binäre Boolesche Operationen . Jede solche Operation oder Funktion (sowie jede Boolesche Funktion mit mehr Eingaben) kann mit den grundlegenden Operationen von oben ausgedrückt werden. Damit sind die Grundoperationen funktionell abgeschlossen .

Gesetze

Ein Gesetz der Booleschen Algebra ist eine Identität , wie beispielsweise x ∨ ( yz ) = ( xy ) ∨ z zwischen zwei Boolesche Begriffe, in denen ein Boolescher Begriff als Ausdruck aufgebaut aus Variablen definiert ist und die Konstanten 0 und 1 unter Verwendung von die Operationen ∧, ∨ und ¬. Das Konzept kann auf Terme erweitert werden, die andere boolesche Operationen wie ⊕, → und ≡ beinhalten, aber solche Erweiterungen sind für die Zwecke, denen die Gesetze zugrunde liegen, unnötig. Solche Zwecke umfassen die Definition einer Booleschen Algebra wie jedes Modell der Booleschen Gesetze, und als Mittel für die wie bei der Ableitung der neue Gesetz aus alten Herleiten x ∨ ( yz ) = x ∨ ( zy ) von yz = zy (wie in § Axiomatizing Boolesche Algebra behandelt ).

Monotone Gesetze

Die Boolesche Algebra erfüllt viele der gleichen Gesetze wie die gewöhnliche Algebra, wenn man ∨ mit Addition und ∧ mit Multiplikation kombiniert. Insbesondere die folgenden Gesetze sind beiden Algebraarten gemeinsam:

Assoziativität von :
Assoziativität von :
Kommutativität von :
Kommutativität von :
Verteilbarkeit von über :
Identität für :
Identität für :
Vernichter für :

Die folgenden Gesetze gelten in der Booleschen Algebra, jedoch nicht in der gewöhnlichen Algebra:

Vernichter für :
Idempotenz von :
Idempotenz von :
Aufnahme 1:
Aufnahme 2:
Verteilbarkeit von über :

Die Annahme von x = 2 im dritten obigen Gesetz zeigt, dass es sich nicht um ein gewöhnliches Algebra-Gesetz handelt, da 2 × 2 = 4 . Die verbleibenden fünf Gesetze können in der gewöhnlichen Algebra falsifiziert werden, indem alle Variablen als 1 angenommen werden. Zum Beispiel wäre im Absorptionsgesetz 1 die linke Seite 1(1 + 1) = 2 , während die rechte Seite 1 ( und so weiter).

Alle bisher behandelten Gesetze standen für Konjunktion und Disjunktion. Diese Operationen haben die Eigenschaft, dass die Änderung eines der Argumente entweder die Ausgabe unverändert lässt oder sich die Ausgabe auf die gleiche Weise wie die Eingabe ändert. Entsprechend führt das Ändern einer Variablen von 0 auf 1 nie dazu, dass sich die Ausgabe von 1 auf 0 ändert. Operationen mit dieser Eigenschaft werden als monoton bezeichnet . Somit waren die Axiome bisher alle für die monotone Boolesche Logik. Nichtmonotonie tritt über Komplement ¬ wie folgt ein.

Nichtmonotone Gesetze

Die Komplementoperation wird durch die folgenden zwei Gesetze definiert.

Alle Eigenschaften der Negation, einschließlich der folgenden Gesetze, ergeben sich allein aus den beiden obigen Gesetzen.

Sowohl in der gewöhnlichen als auch in der Booleschen Algebra funktioniert die Negation durch den Austausch von Elementpaaren, daher erfüllt sie in beiden Algebren das doppelte Negationsgesetz (auch Involutionsgesetz genannt).

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

Boolesche Algebra erfüllt die Gesetze von De Morgan :

Vollständigkeit

Die oben aufgeführten Gesetze definieren die Boolesche Algebra in dem Sinne, dass sie den Rest des Subjekts beinhalten. Die Gesetze Komplement 1 und 2 zusammen mit den monotonen Gesetzen reichen hierfür aus und können daher als eine mögliche vollständige Gesetzmäßigkeit bzw. Axiomatisierung der Booleschen Algebra angesehen werden. Jedes Gesetz der Booleschen Algebra folgt logisch aus diesen Axiomen. Darüber hinaus können dann Boolesche Algebren als Modelle dieser Axiome definiert werden, wie in § Boolesche Algebren behandelt .

Das Aufschreiben weiterer Gesetze der Booleschen Algebra kann zur Verdeutlichung weder neue Konsequenzen dieser Axiome hervorbringen noch ein Modell davon ausschließen. Im Gegensatz dazu hätte es in einer Liste von einigen, aber nicht allen gleichen Gesetzen Boolesche Gesetze geben können, die nicht aus denen auf der Liste folgten, und außerdem hätte es Modelle der aufgelisteten Gesetze gegeben, die keine Booleschen Algebren waren.

Diese Axiomatisierung ist keineswegs die einzige oder sogar notwendigerweise die natürlichste, da wir nicht darauf geachtet haben, ob einige der Axiome auf andere folgten, sondern einfach aufgehört haben, als wir bemerkten, dass wir genügend Gesetze hatten, die in § Axiomatisierung näher behandelt werden Boolesche Algebra . Oder der Zwischenbegriff des Axioms kann vollständig umgangen werden, indem ein Boolesches Gesetz direkt als jede Tautologie definiert wird , verstanden als eine Gleichung, die für alle Werte ihrer Variablen über 0 und 1 gilt. Alle diese Definitionen der Booleschen Algebra können als äquivalent gezeigt werden.

Dualitätsprinzip

Prinzip: Wenn {X, R} ein Poset ist , dann ist auch {X, R(inverse)} ein Poset.

Die Wahl der Symbole für die Werte der Booleschen Algebra hat nichts Magisches. Wir könnten 0 und 1 umbenennen in α und β , und solange wir dies durchgehend tun, wäre es immer noch Boolesche Algebra, wenn auch mit einigen offensichtlichen kosmetischen Unterschieden.

Aber nehmen wir an, wir benennen 0 und 1 in 1 bzw. 0 um. Dann wäre es immer noch Boolesche Algebra und außerdem mit den gleichen Werten arbeitend. Es wäre jedoch nicht identisch mit unserer ursprünglichen Booleschen Algebra, da wir jetzt feststellen, dass sich ∨ wie früher verhält und umgekehrt. Es gibt also noch einige kosmetische Unterschiede, die zeigen, dass wir an der Notation herumgefummelt haben, obwohl wir immer noch 0 und 1 verwenden.

Aber wenn wir nicht nur die Namen der Werte vertauschen, sondern auch die Namen der beiden Binäroperationen vertauschen, gibt es jetzt keine Spur mehr von dem, was wir getan haben. Das Endprodukt ist von dem, womit wir angefangen haben, nicht zu unterscheiden. Wir können feststellen , dass die Spalten für xy und xy in den Wahrheitstabellen Orte hatte sich verändert, aber das Schalter ist unwesentlich.

Wenn Werte und Operationen so gepaart werden können, dass alles Wichtige unverändert bleibt, wenn alle Paare gleichzeitig geschaltet werden, nennen wir die Mitglieder jedes Paares dual zueinander. Somit sind 0 und 1 dual, und ∧ und ∨ sind dual. Das Dualitätsprinzip , auch De Morgan-Dualität genannt , behauptet, dass die Boolesche Algebra unverändert bleibt, wenn alle dualen Paare ausgetauscht werden.

Eine Änderung, die wir im Rahmen dieses Austauschs nicht vornehmen mussten, war die Ergänzung. Wir sagen, dass Komplement eine selbst-duale Operation ist. Die Identitäts- oder Nichtstun-Operation x (Kopieren der Eingabe in die Ausgabe) ist ebenfalls selbstdual. Ein komplizierteres Beispiel eines selbst dualer Betrieb ist ( xy ) ∨ ( yz ) ∨ ( zx ) . Es gibt keine selbstduale binäre Operation, die von ihren beiden Argumenten abhängt. Eine Zusammenstellung von selbstdualen Operationen ist eine selbstduale Operation. Wenn beispielsweise f ( x , y , z ) = ( xy ) ∨ ( yz ) ∨ ( zx ) ist , dann ist f ( f ( x , y , z ), x , t ) ein Selbst -duale Operation von vier Argumenten x , y , z , t .

Das Prinzip der Dualität lässt sich aus gruppentheoretischer Sicht dadurch erklären , dass es genau vier Funktionen gibt, die Eins-zu-Eins-Abbildungen ( Automorphismen ) der Menge der Booleschen Polynome auf sich selbst sind: die Identitätsfunktion, die Komplementfunktion, die duale Funktion und die kontraduale Funktion (ergänzt dual). Diese vier Funktionen bilden eine Gruppe unter der Funktionszusammensetzung , isomorph zur Klein-Viergruppe , die auf die Menge der Booleschen Polynome wirkt . Walter Gottschalk bemerkte , dass folglich ein passenderer Name für das Phänomen das Prinzip ( oder Quadrat ) der Quaternität wäre .

Schematische Darstellungen

Venn-Diagramme

Ein Venn-Diagramm kann als Darstellung einer Booleschen Operation mit schattierten überlappenden Bereichen verwendet werden. Für jede Variable gibt es eine Region, die in den Beispielen hier alle kreisförmig ist. Das Innere und Äußere der Region x entspricht jeweils den Werten 1 (wahr) und 0 (falsch) für die Variable x . Die Schattierung gibt den Wert der Operation für jede Kombination von Regionen an, wobei dunkel 1 und hell 0 bedeutet (einige Autoren verwenden die entgegengesetzte Konvention).

Die drei Venn - Diagramme in der folgenden Abbildung stellen jeweils Verbindung xy , Disjunktion xy und Komplement ¬ x .

Abbildung 2. Venn-Diagramme für Konjunktion, Disjunktion und Komplement

Zur Verbindung wird der Bereich innerhalb beiden Kreise schattiert , um anzuzeigen , dass xy 1 ist , wenn beide Variablen 1. Die übrigen Bereiche sind links unshaded , um anzuzeigen , dass xy ist 0 für die anderen drei Kombinationen.

Das zweite Diagramm stellt die Disjunktion xy dar, indem die Bereiche schattiert werden, die innerhalb eines oder beider Kreise liegen. Das dritte Diagramm stellt Ergänzung ¬ x durch die Region Beschattung nicht innerhalb des Kreises.

Obwohl wir die Venn-Diagramme für die Konstanten 0 und 1 nicht gezeigt haben, sind sie trivial, da sie jeweils eine weiße Box und eine dunkle Box sind, von denen keines einen Kreis enthält. Wir könnten jedoch einen Kreis für x in diese Kästchen einfügen, wobei in diesem Fall jedes eine Funktion eines Arguments x bezeichnen würde , die unabhängig von x denselben Wert zurückgibt , eine sogenannte konstante Funktion. Was ihre Ausgaben betrifft, sind Konstanten und konstante Funktionen nicht zu unterscheiden; Der Unterschied besteht darin, dass eine Konstante keine Argumente akzeptiert , was als nulläre oder nulläre Operation bezeichnet wird, während eine Konstantenfunktion ein Argument akzeptiert , das sie ignoriert, und eine unäre Operation ist.

Venn-Diagramme sind hilfreich bei der Visualisierung von Gesetzen. Die Kommutativitätsgesetze für ∧ und sind aus der Symmetrie der Diagramme ersichtlich: Eine binäre Operation, die nicht kommutativ wäre, hätte kein symmetrisches Diagramm, da eine Vertauschung von x und y das Diagramm horizontal spiegeln würde und ein Versagen der Kommutativität würde erscheinen dann als Symmetriefehler.

Die Idempotenz von ∧ und ∨ kann visualisiert werden, indem man die beiden Kreise zusammenschiebt und feststellt, dass der schattierte Bereich dann sowohl für ∧ als auch für ∨ der ganze Kreis wird.

Um das erste Absorptionsgesetz zu sehen, x ∧( xy ) = x , beginnen Sie mit dem Diagramm in der Mitte für xy und beachten Sie, dass der Teil der schattierten Fläche gemeinsam mit dem x- Kreis den gesamten x- Kreis ist . Für das zweite Absorptionsgesetz, x ∨( xy ) = x , beginnen Sie mit dem linken Diagramm für xy und beachten Sie, dass die Schattierung des gesamten x- Kreises dazu führt, dass nur der x- Kreis schattiert wird, da die vorherige Schattierung innen war der x- Kreis.

Das doppelte Negationsgesetz kann man erkennen, indem man die Schattierung im dritten Diagramm für ¬ x ergänzt , die den x- Kreis schattiert .

Um das erste Gesetz von De Morgan zu visualisieren, (¬ x )∧(¬ y ) = ¬( xy ), beginnen Sie mit dem mittleren Diagramm für xy und ergänzen seine Schattierung so, dass nur der Bereich außerhalb der beiden Kreise schattiert ist, was beschreibt die rechte Seite des Gesetzes. Das Ergebnis ist das gleiche, als ob wir den Bereich schattieren würden, der sowohl außerhalb des x- Kreises als auch außerhalb des y- Kreises liegt, dh die Konjunktion ihrer Äußeren, die die linke Seite des Gesetzes beschreibt.

Das zweite Gesetz von De Morgan, (¬ x )∨(¬ y ) = ¬( xy ), funktioniert genauso, wenn die beiden Diagramme vertauscht sind.

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

Digitale Logikgatter

Digitale Logik ist die Anwendung der Booleschen Algebra von 0 und 1 auf elektronische Hardware, die aus logischen Gattern besteht, die zu einem Schaltplan verbunden sind . Jedes Gatter implementiert eine Boolesche Operation und wird schematisch durch eine Form dargestellt, die die Operation anzeigt. Die den Gattern zugeordneten Gatter für Konjunktion (UND-Gatter), Disjunktion (ODER-Gatter) und Komplement (Inverter) sind wie folgt.

Von links nach rechts: UND- , ODER- und NICHT- Gatter.

Die Linien auf der linken Seite jedes Gates repräsentieren Eingangsdrähte oder Ports . Der Wert des Eingangs wird durch eine Spannung an der Leitung dargestellt. Bei der sogenannten "aktiv-hoch"-Logik wird 0 durch eine Spannung nahe Null oder "Masse" dargestellt, während 1 durch eine Spannung nahe der Versorgungsspannung dargestellt wird; active-low kehrt dies um. Die Linie rechts von jedem Gate stellt den Ausgangsport dar, der normalerweise denselben Spannungskonventionen wie die Eingangsports folgt.

Die Ergänzung wird mit einem Inverter-Gate realisiert. Das Dreieck bezeichnet die Operation, die einfach die Eingabe in die Ausgabe kopiert; der kleine Kreis am Ausgang bezeichnet die tatsächliche Inversion, die den Eingang ergänzt. Die Konvention, einen solchen Kreis auf einen beliebigen Port zu setzen, bedeutet, dass das Signal, das diesen Port passiert, auf dem Weg durch diesen Port ergänzt wird, egal ob es sich um einen Eingangs- oder einen Ausgangsport handelt.

Das Dualitätsprinzip oder die Gesetze von De Morgan können so verstanden werden, dass sie behaupten, dass die Ergänzung aller drei Ports eines UND-Gatters es in ein ODER-Gatter umwandelt und umgekehrt, wie in Abbildung 4 unten gezeigt. Durch die Ergänzung beider Ports eines Wechselrichters bleibt der Betrieb jedoch unverändert.

DeMorganGates.GIF

Allgemeiner kann man jede der acht Teilmengen der drei Ports entweder eines UND- oder ODER-Gatters ergänzen. Die resultierenden sechzehn Möglichkeiten führen zu nur acht Booleschen Operationen, nämlich solchen mit einer ungeraden Zahl von Einsen in ihrer Wahrheitstabelle. Es gibt acht solcher, weil das "Odd-Bit-Out" entweder 0 oder 1 sein kann und an jede von vier Positionen in der Wahrheitstabelle gehen kann. Da es sechzehn binäre boolesche Operationen gibt, muss dies acht Operationen mit einer geraden Zahl von Einsen in ihren Wahrheitstabellen belassen. Zwei davon sind die Konstanten 0 und 1 (als binäre Operationen, die ihre beiden Eingänge ignorieren); vier sind die Operationen, die nichttrivial von genau einer ihrer beiden Eingaben abhängen, nämlich x , y , ¬ x und ¬ y ; und die restlichen zwei sind xy (XOR) und sein Komplement xy .

Boolesche Algebren

Der Begriff "Algebra" bezeichnet sowohl ein Subjekt, nämlich das Subjekt der Algebra , als auch ein Objekt, nämlich eine algebraische Struktur . Während sich das Vorstehende mit der Booleschen Algebra befasst hat, befasst sich dieser Abschnitt mit mathematischen Objekten, die Boolesche Algebren genannt werden und in voller Allgemeinheit als jedes Modell der Booleschen Gesetze definiert werden. Wir beginnen mit einem Spezialfall des ohne Bezug auf die Gesetze definierbaren Begriffs, nämlich konkreten Booleschen Algebren, und geben dann die formale Definition des allgemeinen Begriffs an.

Konkrete Boolesche Algebren

Eine konkrete boolesche Algebra oder ein Feld von Mengen ist jede nichtleere Menge von Teilmengen einer gegebenen Menge X, die unter den Mengenoperationen Vereinigung , Schnitt und Komplement relativ zu X abgeschlossen ist .

(Abgesehen davon, dass X selbst historisch auch nicht leer sein musste, um die entartete oder einelementige Boolesche Algebra auszuschließen, was die einzige Ausnahme von der Regel ist, dass alle Booleschen Algebra die gleichen Gleichungen erfüllen, da die entartete Algebra jede Gleichung erfüllt. Dieser Ausschluss widerspricht jedoch der bevorzugten rein Gleichungsdefinition der "Booleschen Algebra", da es keine Möglichkeit gibt, die Ein-Elemente-Algebra nur mit Gleichungen auszuschließen - 0 ≠ 1 zählt nicht, da es sich um eine negierte Gleichung handelt. Daher erlauben moderne Autoren die entartete Boolesche Algebra und sei X leer.)

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

Beispiel 2. Die leere Menge und X . Diese Zwei-Elemente-Algebra zeigt, dass eine konkrete Boolesche Algebra endlich sein kann, auch wenn sie aus Teilmengen einer unendlichen Menge besteht. Es ist ersichtlich, dass jedes Feld von Teilmengen von X die leere Menge und X enthalten muss . Daher ist kein kleineres Beispiel möglich, außer der entarteten Algebra, die erhalten wird, indem X als leer angenommen wird, um die leere Menge und X zusammenfallen zu lassen.

Beispiel 3. Die Menge der endlichen und kofiniten Mengen von ganzen Zahlen, wobei eine kofinite Menge eine Menge ist, die nur endlich viele ganze Zahlen weglässt. Dies ist eindeutig unter Komplement abgeschlossen und ist unter Vereinigung abgeschlossen, da die Vereinigung einer kofiniten Menge mit einer beliebigen Menge kofinit ist, während die Vereinigung zweier endlicher Mengen endlich ist. Die Schnittmenge verhält sich wie eine Vereinigung, wobei "endlich" und "kofinit" vertauscht sind.

Beispiel 4. Für ein weniger triviales Beispiel für den in Beispiel 2 gemachten Punkt betrachten wir ein Venn-Diagramm, das aus n geschlossenen Kurven besteht , die das Diagramm in 2 n Bereiche unterteilen, und sei X die (unendliche) Menge aller Punkte in der Ebene nicht auf jede Kurve, aber irgendwo innerhalb des Diagramms. Das Innere jeder Region ist somit eine unendliche Teilmenge von X und jeder Punkt in X liegt in genau einer Region. Dann ist die Menge aller 2 2 n möglichen Vereinigungen von Gebieten (einschließlich der leeren Menge, die als Vereinigung der leeren Menge von Gebieten erhalten wird, und X erhalten als Vereinigung aller 2 n Gebiete) abgeschlossen unter Vereinigung, Durchschnitt und Komplement relativ zu X und bildet damit eine konkrete Boolesche Algebra. Wieder haben wir endlich viele Teilmengen einer unendlichen Menge, die eine konkrete Boolesche Algebra bilden, wobei Beispiel 2 im Fall n = 0 ohne Kurven entsteht.

Teilmengen als Bitvektoren

Eine Untergruppe Y von X kann mit einem identifiziert werden indiziert Familie von Bits mit Indexsatz X , wobei das Bit durch indexierte xX 1 oder 0 ist , je nachdem, ob oder nicht , xY . (Dies ist der sogenannte charakteristische Funktionsbegriff einer Untermenge.) Zum Beispiel besteht ein 32-Bit-Computerwort aus 32 Bits, die durch die Menge {0,1,2,...,31} mit 0 und 31 . indiziert sind Indizieren der Bits niedriger bzw. hoher Ordnung. Für ein kleineres Beispiel, wenn X = { a, b, c } wobei a, b, c als Bitpositionen in dieser Reihenfolge von links nach rechts betrachtet werden, die acht Teilmengen {}, { c }, { b }, { b , c }, { a }, { a , c }, { a , b } und { a , b , c } von X können mit den jeweiligen Bitvektoren 000, 001, 010, 011, 100, 101 identifiziert werden, 110 und 111. Bitvektoren, die durch die Menge natürlicher Zahlen indiziert sind, sind unendliche Folgen von Bits, während diejenigen, die durch die reellen Zahlen im Einheitsintervall [0,1] indiziert sind, zu dicht gepackt sind, um konventionell schreiben zu können, aber dennoch gut definierte indizierte Familien (stellen Sie sich vor, jeden Punkt des Intervalls [0,1] unabhängig voneinander entweder schwarz oder weiß einzufärben; die schwarzen Punkte bilden dann eine beliebige Teilmenge von [0,1]).

Von diesem Bitvektor-Standpunkt aus kann eine konkrete Boolesche Algebra äquivalent als eine nichtleere Menge von Bitvektoren definiert werden, die alle dieselbe Länge haben (allgemeiner ausgedrückt durch dieselbe Menge indiziert) und unter den Bitvektoroperationen von bitweisen ∧, ∨ und abgeschlossen sind ¬, wie in 1010∧0110 = 0010, 1010∨0110 = 1110 und ¬1010 = 0101, die Bitvektorrealisierungen von Schnitt, Vereinigung bzw. Komplement.

Die prototypische Boolesche Algebra

Die Menge {0,1} und ihre oben behandelten Booleschen Operationen können als Spezialfall von Bitvektoren der Länge Eins verstanden werden, die durch die Identifizierung von Bitvektoren mit Teilmengen auch als die beiden Teilmengen eines Ein-Elements verstanden werden können einstellen. Wir nennen dies die prototypische Boolesche Algebra, begründet durch die folgende Beobachtung.

Die von allen nicht entarteten konkreten Booleschen Algebren erfüllten Gesetze stimmen mit denen der prototypischen Booleschen Algebra überein.

Diese Beobachtung lässt sich leicht wie folgt beweisen. Gewiss wird jedes Gesetz, das von allen konkreten Booleschen Algebren erfüllt wird, von dem prototypischen erfüllt, da es konkret ist. Umgekehrt muss jedes Gesetz, das für eine konkrete Boolesche Algebra versagt, an einer bestimmten Bitposition versagt haben, in welchem ​​Fall diese Position selbst ein Ein-Bit-Gegenbeispiel zu diesem Gesetz liefert. Die Nichtentartung stellt die Existenz von mindestens einer Bitposition sicher, da es nur einen leeren Bitvektor gibt.

Das Endziel des nächsten Abschnitts kann so verstanden werden, dass „Beton“ aus der obigen Beobachtung eliminiert wird. Wir werden dieses Ziel jedoch durch die überraschend stärkere Beobachtung erreichen, dass bis auf Isomorphie alle Booleschen Algebren konkret sind.

Boolesche Algebren: die Definition

Die Booleschen Algebren, die wir bisher gesehen haben, waren alle konkret und bestanden aus Bitvektoren oder äquivalent aus Teilmengen einer Menge. Eine solche Boolesche Algebra besteht aus einer Menge und Operationen auf dieser Menge, von denen gezeigt werden kann, dass sie 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 verlangen, dass diese Operationen die Gesetze der Booleschen Algebra erfüllen. Die Elemente von X müssen keine Bitvektoren oder Teilmengen sein, sondern können alles Mögliche 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 ¬ darauf, die die Booleschen Gesetze erfüllt.

Für die Zwecke dieser Definition ist es unerheblich, wie die Operationen dazu kamen, den Gesetzen zu genügen, sei es durch Ermächtigung oder Beweis. Alle konkreten Booleschen Algebren erfüllen die Gesetze (durch Beweis statt Fiat), daher ist jede konkrete Boolesche Algebra nach unseren Definitionen eine Boolesche Algebra. Diese axiomatische Definition einer Booleschen Algebra als Menge und bestimmter Operationen, die bestimmten Gesetzen oder Axiomen durch Fiat genügen, 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 einer vollständigen Axiomatisierung der Booleschen Algebra, wie den Axiomen für ein komplementiertes Verteilungsgitter , ist eine hinreichende Bedingung dafür, dass eine solche algebraische Struktur alle Booleschen Gesetze erfüllt, dass sie genau diese Axiome erfüllt. Das Folgende ist daher eine äquivalente Definition.

Eine Boolesche Algebra ist ein komplementiertes Verteilungsgitter.

Der Abschnitt über Axiomatisierung listet weitere Axiomatisierungen auf, von denen jede zur Grundlage einer äquivalenten Definition gemacht werden kann.

Darstellbare Boolesche Algebren

Obwohl jede konkrete Boolesche Algebra eine Boolesche Algebra ist, muss nicht jede Boolesche Algebra konkret sein. Lassen n a sein quadratfreie positive ganze Zahl ist , eine nicht durch das Quadrat einer ganzen Zahl teilbar ist , zum Beispiel 30 , aber nicht 12. Die Vorgänge des größten gemeinsamen Teiler , kleinste gemeinsame Vielfache und Unterteilung in n (dh, ¬ ist x = n / x ) kann gezeigt werden, dass sie alle Booleschen Gesetze erfüllt, wenn ihre Argumente über die positiven Teiler von n reichen . Daher bilden diese Teiler eine Boolesche Algebra. Diese Teiler sind keine Teilmengen einer Menge, was die Teiler von n zu einer Booleschen Algebra macht, die nach unseren Definitionen nicht konkret ist.

Wenn wir jedoch repräsentieren jeden Teiler von n durch die Menge ihrer Primfaktoren, so finden wir , dass dies nicht verknüpfte Boolesche Algebra ist isomorph auf die konkrete Boolesche Algebra , bestehend aus allen Sätzen von Primfaktoren von n , mit Union kleinstes gemeinsames Vielfaches, Kreuzung entspricht zum größten gemeinsamen Teiler und Komplement zur Division in n . Dieses Beispiel, obwohl es technisch nicht konkret ist, ist durch diese Darstellung, die als Isomorphismus bezeichnet wird, zumindest "moralisch" konkret . Dieses Beispiel ist eine Instanz des folgenden Begriffs.

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

Die naheliegende 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 dasselbe. Dieses ziemlich nichttriviale Ergebnis hängt vom Booleschen Primidealsatz ab , einem Auswahlprinzip, das etwas schwächer ist als das Auswahlaxiom , und wird im Artikel Stones Darstellungssatz für Boolesche Algebren ausführlicher behandelt . Diese starke Beziehung impliziert ein schwächeres Ergebnis, das die Beobachtung im vorherigen Unterabschnitt auf die folgende einfache Konsequenz der Darstellbarkeit verstärkt.

Die von allen Booleschen Algebren erfüllten Gesetze stimmen mit denen der prototypischen Booleschen Algebra überein.

Sie ist insofern schwächer, als sie nicht selbst Repräsentierbarkeit impliziert. Boolesche Algebren sind hier speziell, zum Beispiel ist eine Relationsalgebra eine Boolesche Algebra mit zusätzlicher Struktur, aber nicht jede Relationalgebra ist im Sinne von Relationsalgebren darstellbar.

Axiomatisierende Boolesche Algebra

Die obige Definition einer abstrakten Booleschen Algebra als Menge und Operationen, die "die" Booleschen Gesetze erfüllen, wirft die Frage auf, was sind das für Gesetze? Eine einfältige Antwort ist "alle Booleschen Gesetze", die als alle Gleichungen definiert werden können, die für die Boolesche Algebra von 0 und 1 gelten. Da es unendlich viele solcher Gesetze gibt, ist dies in der Praxis keine besonders zufriedenstellende Antwort, was zu der nächste Frage: Genügt es, nur endlich viele Gesetze zu verlangen?

Bei Booleschen Algebren lautet die Antwort ja. Insbesondere die endlich vielen Gleichungen, die wir oben aufgelistet haben, genügen. Wir sagen, dass die Boolesche Algebra endlich axiomatisierbar oder endlich basiert ist.

Kann diese Liste noch verkürzt werden? Auch hier ist die Antwort ja. Zunächst werden einige der oben genannten Gesetze von einigen anderen impliziert. Eine ausreichende Teilmenge der obigen Gesetze besteht aus den Paaren der Assoziativitäts-, Kommutativitäts- und Absorptionsgesetze, der Distributivität von ∧ über ∨ (oder dem anderen Distributivitätsgesetz – eines genügt) und den beiden Komplementärgesetzen. Tatsächlich ist dies die traditionelle Axiomatisierung der Booleschen Algebra als komplementäres Verteilungsgitter .

Durch die Einführung zusätzlicher Gesetze, die oben nicht aufgeführt sind, wird es möglich, die Liste noch weiter zu kürzen; Wenn beispielsweise der vertikale Balken die Sheffer-Stroke- Operation darstellt, reicht das einzelne Axiom aus, um die Boolesche Algebra vollständig zu axiomatisieren. Es ist auch möglich, längere Einzelaxiome mit konventionelleren Operationen zu finden; siehe Minimale Axiome für Boolesche Algebra .

Aussagelogik

Die Aussagenlogik ist ein logisches System , das eng mit der Booleschen Algebra verbunden ist. Viele syntaktische Konzepte der Booleschen Algebra werden 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 (Theoreme) 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 aus Booleschen Variablen x,y ... Aussagenvariablen (oder Atomen ) P,Q ,..., Boolesche Terme wie xy werden zu Aussageformeln PQ , 0 wird falsch oder und 1 wird wahr oder T . Es ist praktisch, wenn man sich auf generische Aussagen bezieht, griechische Buchstaben Φ, Ψ,... als Metavariablen zu verwenden (Variablen außerhalb der Sprache der Aussagenkalküle, die verwendet werden, wenn man von Aussagenkalkül spricht ), um Aussagen zu bezeichnen.

Die Semantik der Aussagenlogik beruht auf Wahrheitszuweisungen . Die wesentliche Idee einer Wahrheitszuweisung besteht darin, dass die Aussagenvariablen auf Elemente einer festen Booleschen Algebra abgebildet werden und dann der Wahrheitswert einer Aussageformel, die diese Buchstaben verwendet, das Element der Booleschen Algebra ist, das durch Berechnen des Wertes von Boolescher Term entsprechend der Formel. In der klassischen Semantik wird nur die zweielementige boolesche Algebra verwendet, während in der booleschen Semantik beliebige boolesche Algebren berücksichtigt werden. Eine Tautologie ist eine aussagenlogische Formel, der jeder Wahrheitszuordnung ihrer aussagenhaften Variablen zu einer beliebigen Booleschen Algebra (oder äquivalent jeder Wahrheitszuordnung zu der zweielementigen Booleschen Algebra) der Wahrheitswert 1 zugewiesen wird .

Diese Semantik erlaubt eine Übersetzung zwischen Tautologien der Aussagenlogik und Gleichungssätzen der Booleschen Algebra. Jede Tautologie Φ der Aussagenlogik kann als Boolesche Gleichung Φ = 1 ausgedrückt werden, die ein Satz der Booleschen Algebra ist. Umgekehrt entspricht jeder Satz Φ = Ψ der Booleschen Algebra den Tautologien (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) und (Φ∧Ψ) ∨ (¬Φ∧¬Ψ). Wenn → in der Sprache steht, können diese letzten Tautologien auch als (Φ→Ψ) ∧ (Ψ→Φ) oder als zwei getrennte Sätze Φ→Ψ und Ψ→Φ geschrieben werden; wenn ≡ vorhanden ist, kann die Einzeltautologie Φ ≡ Ψ verwendet werden.

Anwendungen

Eine motivierende Anwendung der Aussagenkalküle ist die Analyse von Aussagen und deduktiven Argumenten in natürlicher Sprache. Während der Satz "wenn x = 3, dann x +1 = 4" von der Bedeutung solcher Symbole wie + und 1 abhängt, gilt der Satz "wenn x = 3, dann x = 3" nicht; es ist nur aufgrund seiner Struktur wahr und bleibt wahr, ob " x = 3" durch " x = 4" ersetzt wird oder "der Mond aus grünem Käse besteht". Die generische oder abstrakte Form dieser Tautologie ist „if P then P “ oder in der Sprache der Booleschen Algebra „ PP “.

Das Ersetzen von P durch x = 3 oder einen anderen Satz wird Instantiierung von P durch diesen Satz genannt. Das Ergebnis der Instanziierung von P in einer abstrakten Aussage wird eine Instanz der Aussage genannt. Somit ist " x = 3 → x = 3" eine Tautologie, da sie eine Instanz der abstrakten Tautologie " PP " ist. Alle Vorkommen der instanziierten Variablen müssen mit demselben Satz instanziiert werden, um Unsinn wie Px = 3 oder x = 3 → x = 4 zu vermeiden .

Die Aussagenkalküle beschränkt die Aufmerksamkeit auf abstrakte Aussagen, die aus Aussagenvariablen mit booleschen Operationen aufgebaut sind. Instanziierung ist immer noch möglich , innerhalb Aussagenlogik, sondern nur durch Aussagenvariablen durch abstrakte Sätze Instanziieren wie Instanziieren Q durch QP in P → ( QP ) , um die Instanz zu ergeben , P → (( QP ) → P ).

(Die Verfügbarkeit der Instanziierung als Teil der Maschinerie der Aussagenkalküle vermeidet die Notwendigkeit von Metavariablen innerhalb der Sprache der Aussagenkalküle, da innerhalb der Sprache gewöhnliche Aussagenvariablen als Bezeichnung für beliebige Aussagen angesehen werden können. Die Metavariablen selbst liegen außerhalb der Reichweite der Instanziierung, nicht Teil der Sprache der Aussagenkalküle zu sein, sondern Teil derselben Sprache, um darüber zu sprechen, in der dieser Satz geschrieben ist, wo wir in der Lage sein müssen, Aussagenvariablen und ihre Instanziierungen als unterschiedliche syntaktische Einheiten zu unterscheiden.)

Deduktive Systeme für die Aussagenlogik

Eine Axiomatisierung der Aussagenkalküle ist eine Reihe von Tautologien, die als Axiome bezeichnet werden, und eine oder mehrere Inferenzregeln, um aus alten Tautologien neue zu erzeugen. Ein Beweis in einem Axiomensystem A ist eine endliche nichtleere Folge von Sätzen, von denen jede entweder eine Instanz eines Axioms von A ist oder einer Regel von A aus Sätzen folgt, die früher im Beweis auftauchen (wodurch Zirkelschluss nicht zulässig ist). Der letzte Satz ist der durch den Beweis bewiesene Satz . Jedes nichtleere Anfangssegment eines Beweises ist selbst ein Beweis, daher ist jeder Satz in einem Beweis selbst ein Satz. Eine Axiomatisierung ist richtig, wenn jeder Satz eine Tautologie ist, und vollständig, wenn jede Tautologie ein Satz ist.

Sequenzrechnung

Aussagenlogik ist als allgemein organisiert Hilbert - System , dessen Operationen sind nur diejenigen der Booleschen Algebra und deren Sätze sind Boolesche Tautologien, diese Booleschen Bedingungen entsprechen, die Boolesche Konstante 1. Eine andere Form ist sequent Kalkül , die zwei Sorten hat, Sätze wie bei der gewöhnlichen Aussagenlogik, und Paare von Listen von Sätzen genannt Sequenten wie AB , AC , ... A , BC , .... die beiden Hälften einer Sequent sind die Vorder- und die succedent jeweils genannt. Die übliche Metavariable, die einen Vorgänger oder einen Teil davon bezeichnet, ist Γ, und für einen Nachfolger Δ; also , A Δ würde eine Folge bezeichnen, deren Nachfolger eine Liste Δ und deren Vorgänger eine Liste Γ ist, an die ein zusätzlicher Satz A angehängt ist. Der Vorläufer wird als die Verbindung ihrer Sätze zu interpretieren, die succedent als Disjunktion ihrer Sätze und die Sequent sich als entailment des succedent durch den vorgängigen.

Entailment unterscheidet sich von Implikation dadurch, dass letzteres eine binäre Operation ist , die einen Wert in einer Booleschen Algebra zurückgibt, ersteres eine binäre Beziehung ist, die entweder gilt oder nicht gilt. In diesem Sinne ist die Folgerung eine externe Form der Implikation, d. h. außerhalb der Booleschen Algebra, die den Leser der Sequenz auch als extern betrachtet und Vor- und Nachfolge in einer Booleschen Algebra interpretiert und vergleicht. Die natürliche Interpretation von ist als ≤ in der partiellen Ordnung der Booleschen Algebra, die durch xy definiert ist, gerade wenn xy = y ist . Diese Fähigkeit, externe Implikation und interne Implikation → in der einen Logik zu vermischen, gehört zu den wesentlichen Unterschieden zwischen Sequenzkalkül und Aussagenkalkül.

Anwendungen

Die Boolesche Algebra als Berechnung zweier Werte ist grundlegend für Computerschaltungen, Computerprogrammierung und mathematische Logik und wird auch in anderen Bereichen der Mathematik wie Mengenlehre und Statistik verwendet.

Computers

Im frühen 20. Jahrhundert erkannten mehrere Elektroingenieure intuitiv, dass die Boolesche Algebra dem Verhalten bestimmter Arten von elektrischen Schaltkreisen analog war. Claude Shannon hat in seiner Masterarbeit von 1937, A Symbolic Analysis of Relay and Switching Circuits, formal bewiesen, dass ein solches Verhalten logisch der Booleschen Algebra entspricht .

Heute sind alle modernen Allzweckcomputer führen ihre Funktionen Zweiwert Boolesche Logik verwendet; das heißt, ihre elektrischen Schaltkreise sind eine physikalische Manifestation der booleschen Logik mit zwei Werten. Dies erreichen sie auf verschiedene Weise: als Spannungen an Drähten in Hochgeschwindigkeitsschaltungen und kapazitiven Speichergeräten, als Orientierungen einer magnetischen Domäne in ferromagnetischen Speichergeräten, als Löcher in Lochkarten oder Papierstreifen und so weiter. (Einige frühe Computer verwendeten Dezimalschaltkreise oder -mechanismen anstelle von zweiwertigen Logikschaltkreisen.)

Natürlich ist es möglich, mehr als zwei Symbole in jedem gegebenen Medium zu codieren. Beispielsweise könnte man 0, 1, 2 bzw. 3 Volt verwenden, um ein Vier-Symbol-Alphabet auf einem Draht oder Löcher unterschiedlicher Größe in einer Lochkarte zu codieren. In der Praxis machen die engen Beschränkungen von hoher Geschwindigkeit, kleiner Größe und geringer Leistung das Geräusch zu einem Hauptfaktor. Dies macht es schwierig, zwischen Symbolen zu unterscheiden, wenn mehrere mögliche Symbole an einem einzelnen Standort auftreten können. Anstatt zu versuchen, zwischen vier Spannungen auf einem Draht zu unterscheiden, haben sich digitale Designer auf zwei Spannungen pro Draht, hoch und niedrig, festgelegt.

Computer verwenden aus den oben genannten Gründen zweiwertige boolesche Schaltungen. Die am häufigsten verwendeten Rechnerarchitekturen verwenden Sequenzen von Booleschen Werten, die so genannten Bits bestellt, von 32 oder 64 Werten, zB 01101000110101100101010101001011. Wenn bei der Programmierung Maschinencode , Assemblersprache , und einige anderen Programmiersprachen , Programmierer mit der Low-Level - Digitalstruktur der Arbeit Datenregister . Diese Register arbeiten mit Spannungen, wobei null Volt eine boolesche 0 darstellt und eine Referenzspannung (oft +5 V, +3,3 V, +1,8 V) eine boolesche 1 darstellt. Solche Sprachen unterstützen sowohl numerische Operationen als auch logische Operationen. In diesem Zusammenhang bedeutet "numerisch", dass der Computer Bitfolgen als Binärzahlen ( Zahlen zur Basis zwei) behandelt und arithmetische Operationen wie Addieren, Subtrahieren, Multiplizieren oder Dividieren ausführt. "Logisch" bezieht sich auf die booleschen logischen Operationen der Disjunktion, Konjunktion und Negation zwischen zwei Bitfolgen, bei denen jedes Bit in einer Folge einfach mit seinem Gegenstück in der anderen Folge verglichen wird. Programmierer haben daher die Möglichkeit, je nach Bedarf in die Regeln der numerischen Algebra oder der Booleschen Algebra einzuarbeiten und diese anzuwenden. Ein zentrales Unterscheidungsmerkmal zwischen diesen Operationsfamilien ist die Existenz der Übertragsoperation in der ersten, aber nicht in der zweiten.

Zweiwertige Logik

Andere Bereiche, in denen zwei Werte eine gute Wahl sind, sind das Recht und die Mathematik. Im entspannten Alltagsgespräch sind nuancierte oder komplexe Antworten wie „vielleicht“ oder „nur am Wochenende“ akzeptabel. In konzentrierteren Situationen wie einem Gericht oder der auf Theoremen basierenden Mathematik wird es jedoch als vorteilhaft erachtet, Fragen so zu formulieren, dass eine einfache Ja-oder-Nein-Antwort zugelassen wird – ist der Angeklagte schuldig oder nicht schuldig, ist die Aussage wahr oder falsch? – und jede andere Antwort zu verbieten. So sehr dies für den Befragten in der Praxis eine Zwangsjacke sein mag, das Prinzip der einfachen Ja-Nein-Frage ist zu einem zentralen Merkmal sowohl der juristischen als auch der mathematischen Logik geworden, so dass die zweiwertige Logik selbst organisiert und studiert werden muss.

Ein zentrales Konzept der Mengenlehre ist die Mitgliedschaft. Nun kann eine Organisation mehrere Mitgliedschaftsgrade zulassen, z. B. Novize, Associate und Full. Bei Mengen hingegen ist ein Element entweder in oder out. Die Kandidaten für die Mitgliedschaft in einem Set funktionieren wie die Drähte in einem digitalen Computer: Jeder Kandidat ist entweder ein Mitglied oder ein Nichtmitglied, genauso wie jeder Draht entweder hoch oder niedrig ist.

Algebra ist ein grundlegendes Werkzeug in jedem Bereich, der einer mathematischen Behandlung zugänglich ist. Diese Überlegungen machen die Algebra von zwei Werten von grundlegender Bedeutung für Computerhardware, mathematische Logik und Mengenlehre.

Zweiwertige Logik kann zu mehrwertiger Logik erweitert werden , insbesondere durch Ersetzen des Booleschen Bereichs {0, 1} durch das Einheitsintervall [0,1], wobei in diesem Fall nicht nur die Werte 0 oder 1 angenommen werden, sondern jeder Wert zwischen und einschließlich 0 und 1 kann angenommen werden. Algebraisch wird die Negation (NOT) durch 1 −  x ersetzt , die Konjunktion (AND) wird durch die Multiplikation ( ) ersetzt und die Disjunktion (OR) wird über das De Morgansche Gesetz definiert . Die Interpretation dieser Werte als logische Wahrheitswerte ergibt eine mehrwertige Logik, die die Grundlage für Fuzzy-Logik und Wahrscheinlichkeitslogik bildet . In diesen Interpretationen wird ein Wert als „Grad“ der Wahrheit interpretiert – inwieweit eine Aussage wahr ist oder wie wahrscheinlich die Aussage ist.

Boolesche Operationen

Die ursprüngliche Anwendung für Boolesche Operationen war die mathematische Logik , bei der die Wahrheitswerte, wahr oder falsch, einzelner Formeln kombiniert werden.

Natürliche Sprache

Natürliche Sprachen wie Englisch haben Wörter für mehrere boolesche Operationen, insbesondere Konjunktion ( und ), Disjunktion ( oder ), Negation ( nicht ) und Implikation ( impliziert ). Aber nicht ist gleichbedeutend mit und nicht . Wenn sie verwendet werden, um situative Behauptungen wie "Der Block liegt auf dem Tisch" und "Katzen trinken Milch" zu kombinieren, die naiv entweder wahr oder falsch sind, haben die Bedeutungen dieser logischen Verknüpfungen oft die Bedeutung ihrer logischen Gegenstücke. Bei Verhaltensbeschreibungen wie "Jim ging durch die Tür" bemerkt man jedoch Unterschiede wie das Scheitern der Kommutativität, zum Beispiel die Konjunktion von "Jim öffnete die Tür" mit "Jim ging durch die Tür" in dieser Reihenfolge ist nicht gleichbedeutend mit ihrer Konjunktion in der anderen Reihenfolge, da und in solchen Fällen normalerweise und dann bedeutet . Fragen können ähnlich sein: die Reihenfolge "Ist der Himmel blau und warum ist der Himmel blau?" macht mehr Sinn als die umgekehrte Reihenfolge. Konjunktive Verhaltensbefehle sind wie Verhaltensbehauptungen, wie in anziehen und zur Schule gehen . Disjunktive Befehle wie „ liebe mich“ oder „verlasse mich“ oder „ fische“ oder „schneide Köder“ neigen dazu, asymmetrisch zu sein, da eine Alternative weniger vorzuziehen sei. Verbundene Substantive wie Tee und Milch beschreiben im Allgemeinen die Aggregation wie bei der Satzvereinigung, während Tee oder Milch eine Wahl sind. Der Kontext kann diese Sinne jedoch umkehren, da Ihre Auswahl Kaffee und Tee ist, was normalerweise dasselbe bedeutet, wie Ihre Auswahl Kaffee oder Tee (Alternativen). Doppelte Negation wie in "Ich mag keine Milch" bedeutet selten wörtlich "ich mag Milch", sondern vermittelt eher eine Art Absicherung, als ob es eine dritte Möglichkeit gäbe. "Not not P" kann locker als "Sicher P" interpretiert werden, und obwohl P notwendigerweise "not not P " impliziert, ist das Gegenteil im Englischen verdächtig, ähnlich wie bei der intuitionistischen Logik . Angesichts der sehr eigenwilligen Verwendung von Konjunktionen in natürlichen Sprachen kann die Boolesche Algebra nicht als zuverlässiger Rahmen für deren Interpretation angesehen werden.

Digitale Logik

Boolesche Operationen werden in der digitalen Logik verwendet , um die auf einzelnen Drähten getragenen Bits zu kombinieren und sie dadurch über {0,1} zu interpretieren. Wenn ein Vektor von n identischen binären Gattern verwendet wird, um zwei Bitvektoren mit jeweils n Bits zu kombinieren , können die einzelnen Bitoperationen kollektiv als eine einzelne Operation an Werten aus einer Booleschen Algebra mit 2 n Elementen verstanden werden.

Naive Mengenlehre

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

Grafikkarten

Die 256-Elemente freie Boolesche Algebra auf drei Generatoren wird in Computerdisplays basierend auf Rastergrafiken eingesetzt , die Bit-Blit verwenden , um ganze Regionen bestehend aus Pixeln zu manipulieren , wobei sie sich auf Boolesche Operationen verlassen, um anzugeben, wie die Quellregion typischerweise mit dem Ziel kombiniert werden soll mit Hilfe eines dritten Bereichs, der Maske genannt wird . Moderne Grafikkarten bieten  zu diesem Zweck alle 2 2 3 = 256 ternären Operationen an, wobei die Wahl der Operation als Ein-Byte-(8-Bit-)Parameter steht. Die Konstanten SRC = 0xaa oder 10101010, DST = 0xcc oder 11001100 und MSK = 0xf0 oder 11110000 ermöglichen das Schreiben von booleschen Operationen wie (SRC^DST)&MSK (d. h. Quelle und Ziel XOR und dann UND das Ergebnis mit der Maske) direkt als Konstante, die ein zur Kompilierzeit berechnetes Byte bezeichnet, 0x60 im (SRC^DST)&MSK-Beispiel, 0x66, wenn nur SRC^DST usw. Zur Laufzeit interpretiert die Grafikkarte das Byte als die vom ursprünglichen Ausdruck angegebene Rasteroperation auf eine einheitliche Weise, die bemerkenswert wenig Hardware erfordert und die Zeit völlig unabhängig von der Komplexität des Ausdrucks benötigt.

Modellierung und CAD

Volumenmodellierungssysteme für Computer Aided Design bieten eine Vielzahl von Methoden zum Bauen von Objekten aus anderen Objekten, wobei die Kombination durch Boolesche Operationen eine davon ist. Bei dieser Methode wird der Raum, in dem Objekte existieren, als Menge S von Voxeln (das dreidimensionale Analogon von Pixeln in zweidimensionalen Grafiken) verstanden und Formen werden als Teilmengen von S definiert , wodurch Objekte durch Vereinigung zu Mengen kombiniert werden können. Schnittmenge usw. Eine offensichtliche Verwendung besteht darin, eine komplexe Form aus einfachen Formen einfach als Vereinigung der letzteren aufzubauen. Eine weitere Anwendung ist in der Bildhauerei als Materialabtrag zu verstehen: Jede Schleif-, Fräs-, Fräs- oder Bohroperation, die mit physikalischen Maschinen an physikalischen Materialien durchgeführt werden kann, kann am Computer mit der Booleschen Operation x  ¬ y oder x  −  y simuliert werden. was in der Mengenlehre Mengendifferenz ist, entferne die Elemente von y von denen von x . Bei zwei zu bearbeitenden Formen und dem zu entfernenden Material wird das Ergebnis der Bearbeitung der ersteren zur Entfernung der letzteren einfach als ihre Setzdifferenz beschrieben.

Boolesche Suchen

Suchmaschinenabfragen verwenden auch boolesche Logik. Für diese Anwendung kann jede Webseite im Internet als "Element" einer "Menge" betrachtet werden. Die folgenden Beispiele verwenden eine von Google unterstützte Syntax .

  • Doppelte Anführungszeichen werden verwendet, um durch Leerzeichen getrennte Wörter zu einem einzigen Suchbegriff zu kombinieren.
  • Whitespace wird verwendet, um logisches UND anzugeben, da dies der Standardoperator zum Verbinden von Suchbegriffen ist:
"Search term 1" "Search term 2"
  • Das Schlüsselwort OR wird für logisches ODER verwendet:
"Search term 1" OR "Search term 2"
  • Für logisches NOT wird ein vorangestelltes Minuszeichen verwendet:
"Search term 1" −"Search term 2"

Siehe auch

Verweise

Quellen

Weiterlesen

  • J. Eldon Whitesitt (1995). Boolesche Algebra und ihre Anwendungen . Courier Dover Veröffentlichungen. ISBN 978-0-486-68483-3. Geeignete Einführung für Studierende in angewandten Bereichen.
  • Dwinger, Philipp (1971). Einführung in die Boolesche Algebren . Würzburg: Physica Verlag.
  • Sikorski, Roman (1969). Boolesche Algebren (3/e ed.). Berlin: Springer-Verlag. ISBN 978-0-387-04469-9.
  • Bocheński, Józef Maria (1959). Ein Précis der mathematischen Logik . Übersetzt aus der französischen und deutschen Ausgabe von Otto Bird. Dordrecht, Südholland: D. Reidel.

Historische Perspektive

Externe Links