Grundlagen der Booleschen Algebra -- AND / OR / NOT / XOR
Die Boolesche Algebra ist die mathematische Grundlage aller digitalen Schaltungen; Kombinationen der vier grundlegenden logischen Operationen können verwendet werden, um beliebig komplexe Schaltungen zu konstruieren.
Alltagsanalogie: Automatische Türen und Zutrittskontrollsysteme
Wenn Sie ein hochsicheres Gebäude betreten, begegnen Ihnen verschiedene Zutrittskontrollregeln. Diese Regeln entsprechen zufällig genau den Grundoperationen der Booleschen Algebra; verstehen wir sie anhand alltäglicher Szenarien.
AND-Gatter — zwei Türen müssen gleichzeitig geöffnet sein, um einzutreten: Ein bestimmter Tresor erfordert, dass zwei Schlüssel gleichzeitig gedreht werden, um geöffnet zu werden. Nur wenn beide Schlüssel eingesteckt und gedreht sind (beide Eingaben sind 1), öffnet sich die Tür (Ausgabe ist 1). Fehlt einer der Schlüssel, bleibt die Tür bewegungslos.
OR-Gatter——wenn irgendeine Tür geöffnet ist, können Sie eintreten: Ein Bürogebäude hat zwei Eingänge; solange entweder die Vordertür oder die Hintertür geöffnet ist, können Sie eintreten. Wenn ein beliebiger Eingang geöffnet ist (mindestens eine Eingabe ist 1), können Sie passieren (Ausgabe ist 1).
NOT-Gatter — Taste kehrt das Vorzeichen um: Am Toiletteneingang befindet sich ein Umschalt-Schild „Frei/Belegt“; ein Tastendruck kehrt den aktuellen Zustand um. Bei Eingabe 0 (frei) ist die Ausgabe 1 (belegt), und umgekehrt.
XOR-Gatter — die beiden Lampen in einem Raum müssen eine eingeschaltet und die andere ausgeschaltet sein: Ein Raum hat zwei Lampen, und die Regel ist, dass sich die beiden Lampen in entgegengesetzten Zuständen befinden müssen (eine eingeschaltet, eine ausgeschaltet); andernfalls wird das Alarmsystem ausgelöst. Wenn sich die beiden Eingaben unterscheiden, ist die Ausgabe daher 1; wenn sie gleich sind, ist die Ausgabe 0.
Kurze Geschichte der Booleschen Algebra
Die Boolesche Algebra wurde vom britischen MathematikerGeorge BooleIm Jahr 1854 wurde die Boolesche Algebra erstmals systematisch in dem Werk An Investigation of the Laws of Thought vorgestellt. Booles Ziel war es, das menschliche logische Denken zu mathematisieren; er entwickelte eine Methode, mit algebraischen Symbolen „wahr“ und „falsch“ auszudrücken.
Im Jahr 1938,Claude ShannonIn seiner Masterarbeit am MIT bewies er, dass die Boolesche Algebra zur Beschreibung und Vereinfachung von Relais-Schaltkreisen verwendet werden kann. Diese Arbeit, bekannt als „die wichtigste Masterarbeit der Geschichte“, legte die theoretische Grundlage für das gesamte Design digitaler Schaltungen.
Man kann sagen, dass es ohne boolesche Algebra keine digitalen Schaltungen gäbe und ohne digitale Schaltungen keine modernen Computer. In dem Gerät, auf dem Sie diesen Abschnitt lesen, werden jede Sekunde Hunderte Millionen boolescher Operationen ausgeführt.
Detaillierte Erklärung der vier grundlegenden logischen Operationen
UND-Operation
Die Regel für die UND-Operation besteht nur aus einem Satz:Die Ausgabe ist nur dann 1, wenn alle Eingaben 1 sind.; andernfalls ist die Ausgabe 0. Man kann sie sich als in Reihe geschaltete Schalter vorstellen – beide Schalter müssen geschlossen sein, damit die Glühbirne leuchtet.
| A | B | A UND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Logischer Ausdruck:Y = A · B(Manchmal wird der Punkt weggelassen und direkt als Y = AB geschrieben). Merkregel: Die Ausgabe ist nur dann 1, wenn alle Eingaben 1 sind.
ODER-Operation
Regeln der ODER-Operation:Wenn mindestens eine Eingabe 1 ist, ist die Ausgabe 1; die Ausgabe ist nur dann 0, wenn alle Eingaben 0 sind. Analog zu parallel geschalteten Schaltern – wenn irgendein Schalter geschlossen ist, leuchtet die Glühbirne.
| A | B | A ODER B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Logischer Ausdruck:Y = A + B(Beachten Sie, dass dies keine arithmetische Addition ist; in der booleschen Algebra ergibt 1+1 immer noch 1). Merkregel: Jede 1 ergibt 1.
NICHT-Operation
NICHT ist die einzige grundlegende Operation, die genau eine Eingabe akzeptiert, und ihre Regel ist die einfachste:Die Ausgabe ist das Inverse der EingabeWenn die Eingabe 1 ist, ist die Ausgabe 0; wenn die Eingabe 0 ist, ist die Ausgabe 1.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Logischer Ausdruck:Y = A'oderY = NOT AIn Schaltplänen wird ein kleiner Kreis auf der Eingangsleitung üblicherweise verwendet, um eine Inversion darzustellen. Merksatz: 0 wird zu 1, 1 wird zu 0.
XOR-Operation (exklusives ODER)
Regeln für XOR:Wenn die beiden Eingänge unterschiedlich sind, Ausgabe 1; wenn sie gleich sind, Ausgabe 0. XOR wird durch eine Kombination von AND, OR und NOT implementiert: A XOR B = (A' · B) + (A · B').
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Logischer Ausdruck:Y = A XOR BXOR wird in vielen Bereichen eingesetzt, z. B. beim Entwurf von Addierern, bei der Paritätsprüfung und bei der Datenverschlüsselung. Merksatz: unterschiedliche Eingänge ergeben 1.
Logikgatter-Symbole
In digitalen Schaltplänen hat jede grundlegende logische Operation ein entsprechendes Standard-Logikgatter-Symbol:
AND-Gatter: Das Symbol ist D-förmig – eine gerade Kante plus ein halbkreisförmiger Bogen, mit zwei Eingangsleitungen auf der linken und einer Ausgangsleitung auf der rechten Seite.
OR-Gatter: Das Symbol ist schildförmig – ein nach innen gewölbter Bogen, der an der Rückseite in einer Spitze zusammenläuft und die logische Bedeutung von „oder“ darstellt.
NOT-Gatter (Inverter): ein Dreieck gefolgt von einem kleinen Kreis – das Dreieck steht für Pufferung/Treiber, und der Kreis steht für Signalumkehr.
XOR-Gatter: in der Form ähnlich dem OR-Gatter, jedoch mit einem zusätzlichen Bogen vor dem eingangsseitigen Bogen, um „exklusives ODER“ zu kennzeichnen.
Jede komplexe digitale Schaltung — einschließlich des Rechenwerks und des Steuerwerks innerhalb einer CPU — lässt sich letztlich in Kombinationen dieser vier grundlegenden Logikgatter zerlegen. Dies ist der grundlegende Grund dafür, dass die Boolesche Algebra die theoretische Grundlage digitaler Schaltungen bildet.
Anhang: SVG-Symbole für Logikgatter und interaktive Wahrheitstabellen (Beispiel-Demo)
Unten sehen Sie die Standardsymbole der vier grundlegenden Logikgatter zusammen mit einer interaktiven Wahrheitstabelle — klicken Sie auf die Schaltflächen A und B, um die Eingänge umzuschalten und die Änderungen der Ausgänge in den entsprechenden Zeilen zu beobachten.
Standardsymbole der vier Logikgatter
Interaktive Wahrheitstabelle — Klicken Sie auf die Schaltflächen, um Eingaben umzuschalten
Klicken Sie unten auf die Schaltflächen A und B, um zwischen 0/1 umzuschalten, und beobachten Sie, wie die entsprechenden Eingabezeilen in der Tabelle hervorgehoben werden
| A | B | AND | OR | NOT A | NOT B | XOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Interaktive Demo
Klicken Sie auf die Schaltflächen unten, um die Werte der Eingänge A und B umzuschalten (0 oder 1), und beobachten Sie, wie sich die Ausgänge jedes Logikgatters in Echtzeit ändern:
Interaktive Demonstration eines Logikgatters (Beispiel-Demo)
Klicken Sie auf die Schaltflächen unten, um die Werte der Eingänge A und B umzuschalten
| Logikgatter | Logische Ausdrücke | Aktueller Ausgang | Mnemonic |
|---|---|---|---|
| AND-Gatter | A UND B | - | Nur 1, wenn alle 1 |
| OR-Gatter | A ODER B | - | 1, wenn mindestens eine 1 |
| NOT-Gatter | NOT A | - | 0 wird 1, 1 wird 0 |
| NOT-Gatter | NOT B | - | 0 wird 1, 1 wird 0 |
| XOR-Gatter | A XOR B | - | Ungleich ist 1 |
Python-Code-Demonstration
Im Folgenden wird Python verwendet, um Funktionen für die vier grundlegenden logischen Operationen zu implementieren, wobei automatisch vollständige Wahrheitstabellen erzeugt und gleichzeitig die De Morgan’schen Gesetze überprüft werden:
Beispiel
def AND(a, b):
"""UND-Operation: alle 1en, dann 1"""
return 1 if a == 1 and b == 1 else 0
def OR(a, b):
"""ODER-Operation: wenn irgendeine 1, ist das Ergebnis 1"""
return 1 if a == 1 or b == 1 else 0
def NOT(a):
"""NOT-Operation: invertieren"""
return 1 if a == 0 else 0
def XOR(a, b):
"""XOR-Operation: verschieden ist 1"""
return 1 if a != b else 0
def print_truth_table(title, func, inputs):
"""Generische Funktion zum Drucken einer Wahrheitstabelle"""
print(f"\n{'='*40}")
print(f" {title}")
print(f"{'='*40}")
if func.__code__.co_argcount == 1:
print(f" {'A':>4} | {'Ausgabe':>4}")
print(f" {'-'*13}")
for a in inputs:
print(f" {a:>4} | {func(a):>4}")
else:
print(f{'A':>4} | {'B':>4} | {'Ausgabe':>4})
print(f" {'-'*20}")
for a in inputs:
for b in inputs:
print(f" {a:>4} | {b:>4} | {func(a, b):>4}")
# Hauptprogramm: Alle Wahrheitstabellen ausgeben
inputs = [0, 1]
print("Beispielhafte vollständige Demonstration einer Wahrheitstabelle der Booleschen Algebra")
print_truth_table("AND-Operation", AND, inputs)
print_truth_table("OR (ODER-Operation)", OR, inputs)
print_truth_table("NOT-Operation", NOT, inputs)
print_truth_table("XOR-Operation", XOR, inputs)
# Verifikation der De-Morgan-Gesetze
print(f"\n{'='*40}")
print(" Verifikation der De-Morgan-Gesetze")
print(f"{'='*40}")
print(Gesetz 1: NOT(A AND B) = NOT A OR NOT B)
print(Gesetz 2: NOT(A OR B) = NOT A AND NOT B)
for a in inputs:
for b in inputs:
left1 = NOT(AND(a, b))
right1 = OR(NOT(a), NOT(b))
left2 = NOT(OR(a, b))
right2 = AND(NOT(a), NOT(b))
print(f" A={a}, B={b}:")
print(f" entscheide Gesetz1: {left1} = {right1} -> {'OK' if left1 == right1 else 'FAIL'}")
print(f" entscheide Gesetz2: {left2} = {right2} -> {'OK' if left2 == right2 else 'FAIL'}")