Lernen › Thema 2

Boolesche Algebra: Gesetze, De Morgan und Vereinfachung

7 Min. Lesezeit · bitGateLab-Team

Die boolesche Algebra ist die Sprache, in der digitale Schaltungen beschrieben und umgeformt werden. Jeder Ausdruck entspricht einer Anordnung von Gattern, und jedes Gesetz, das du beim Vereinfachen anwendest, spart dir Gatter. Hier wiederholst du die Postulate, die nützlichsten Gesetze und die De-Morgan-Regeln und lernst, einen Ausdruck Schritt für Schritt zu vereinfachen und dabei jeden Schritt zu begründen.

Variablen und Operationen

Eine boolesche Variable nimmt nur die Werte 0 und 1 an. Es gibt drei Grundoperationen: das Komplement (A, NOT-Gatter), das logische Produkt (A·B oder AB, AND-Gatter) und die logische Summe (A + B, OR-Gatter). Ohne Klammern gilt folgende Rangfolge: zuerst das Komplement, dann das Produkt und zuletzt die Summe. A + BC bedeutet also A + (B·C), genau wie in der gewöhnlichen Algebra.

Postulate

Die gesamte Algebra stützt sich auf wenige Postulate. Beachte, dass sie paarweise auftreten: eines für die Summe und eines für das Produkt.

Postulat	Form mit Summe	Form mit Produkt
Neutrales Element	A + 0 = A	A · 1 = A
Kommutativgesetz	A + B = B + A	AB = BA
Distributivgesetz	A + BC = (A + B)(A + C)	A(B + C) = AB + AC
Komplement	A + A = 1	A · A = 0

Dualitätsprinzip: Gilt eine Gleichung, dann gilt auch die Gleichung, die du erhältst, wenn du + mit · und 0 mit 1 vertauschst (ohne die Variablen oder ihre Negationsstriche anzutasten). Deshalb hat jedes Gesetz eine „Zwillingsform“. Sieh dir das Distributivgesetz der Summe an, A + BC = (A + B)(A + C): In der Algebra der reellen Zahlen gibt es das nicht, hier ist es aber vollkommen gültig.

Nützliche Gesetze und Theoreme

Aus den Postulaten folgen diese Regeln, die du beim Vereinfachen am häufigsten brauchst:

Gesetz	Form mit Summe	Form mit Produkt
Idempotenz	A + A = A	AA = A
Extremalgesetz	A + 1 = 1	A · 0 = 0
Doppelte Negation	A = A
Assoziativgesetz	A + (B + C) = (A + B) + C	A(BC) = (AB)C
Absorption	A + AB = A	A(A + B) = A
Absorption des Komplements	A + AB = A + B	A(A + B) = AB
Nachbarschaftsgesetz	AB + AB = A	(A + B)(A + B) = A
Konsensus	AB + AC + BC = AB + AC	(A + B)(A + C)(B + C) = (A + B)(A + C)

Jedes dieser Gesetze lässt sich mit einer Wahrheitstabelle überprüfen: Stimmen die beiden Spalten in allen Zeilen überein, gilt die Gleichung. Zum Beispiel für A + AB = A: Mit A = 0 sind beide Seiten 0, unabhängig von B; mit A = 1 sind beide 1. Die Absorption des Komplements beweist man so: A + AB = (A + A)(A + B) = 1·(A + B) = A + B, mit dem Distributivgesetz der Summe.

Die De-Morgan-Regeln

Diese beiden Theoreme sagen dir, wie man einen langen Negationsstrich „aufbricht“:

A · B = A + B (das Komplement eines Produkts ist die Summe der Komplemente).
A + B = A · B (das Komplement einer Summe ist das Produkt der Komplemente).

Die Faustregel: Wenn du den Strich auftrennst, wechsle die Operation darunter (· gegen + oder + gegen ·) und negiere jeden Term. Das funktioniert mit beliebig vielen Variablen: ABC = A + B + C.

A	B	AB	A + B	A + B	AB
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

Für Schaltungen bedeutet De Morgan: Ein NAND entspricht einem OR mit Negationskreisen an den Eingängen, und ein NOR entspricht einem AND mit Negationskreisen an den Eingängen. Das ist die Grundlage dafür, jeden Entwurf in reine NAND- oder reine NOR-Logik umzuwandeln, wie im Thema Logikgatter erklärt wird.

Beispiel 1: De Morgan anwenden. Vereinfache F = AB + C.

Der lange Strich überdeckt eine Summe: AB + C = AB · C.
Brich den Strich über dem Produkt auf: AB = A + B.
Ergebnis: F = (A + B)C = AC + BC.

Probe mit A = 1, B = 1, C = 0: Der ursprüngliche Ausdruck ergibt 1 + 0 = 0; das Ergebnis liefert (0 + 0)·1 = 0. Mit A = 0, B = 1, C = 0: ursprünglich 0 + 0 = 1; Ergebnis (1 + 0)·1 = 1.

Algebraische Vereinfachung Schritt für Schritt

Vereinfachen heißt, die Anzahl der Terme und der Literale zu verringern (ein Literal ist jedes Auftreten einer Variablen, negiert oder nicht). Weniger Literale bedeuten weniger Gattereingänge. Mit reiner Algebra gibt es keinen eindeutigen Algorithmus; diese Taktiken funktionieren aber fast immer:

Suche Paare von Termen, die sich in nur einer Variablen unterscheiden, und wende das Nachbarschaftsgesetz an.
Klammere gemeinsame Faktoren aus und suche nach einem versteckten A + A = 1.
Ist ein Term in einem anderen enthalten, entferne ihn durch Absorption.
Du darfst einen Term verdoppeln (Idempotenz), um ihn mit zwei verschiedenen Nachbarn zusammenzufassen.

Beispiel 2. Vereinfache F = AB + AB + AB.

Klammere bei den ersten beiden Termen aus: AB + AB = A(B + B) = A·1 = A.
Es bleibt F = A + AB.
Absorption des Komplements: A + AB = A + B.

F = A + B. Aus drei AND-Gattern, einem OR mit drei Eingängen und zwei Invertern ist ein einziges OR geworden.

Beispiel 3: Mehrheitsfunktion. Vereinfache F = ABC + ABC + ABC + ABC.

Wegen der Idempotenz gilt ABC = ABC + ABC + ABC. Schreibe drei Kopien hin, um jede mit einem Nachbarn zusammenzufassen.
ABC + ABC = BC(A + A) = BC.
ABC + ABC = AC(B + B) = AC.
ABC + ABC = AB(C + C) = AB.

F = AB + AC + BC. Die Funktion ist 1, wenn mindestens zwei der drei Eingänge 1 sind: eine Abstimmschaltung. Du wirst sehen, dass sie zugleich der Übertragsausgang des Volladdierers ist.

Beispiel 4: Distributivgesetz der Summe. Vereinfache F = (A + B)(A + C).

Multipliziere aus: AA + AC + AB + BC = A + AC + AB + BC.
Klammere A aus: A(1 + C + B) + BC.
Extremalgesetz: 1 + C + B = 1, es bleibt also A + BC.

Das ist genau das Distributivpostulat der Summe, rückwärts gelesen.

Häufige Fehler

De Morgan anzuwenden, ohne die Operation zu wechseln: AB ist nicht AB, sondern A + B.
Terme zu „kürzen“ wie in der gewöhnlichen Algebra. In der booleschen Algebra gibt es weder Subtraktion noch Division: Aus A + B = A + C folgt nicht B = C.
Die Rangfolge zu vergessen: A + BC ist nicht (A + B)C.
Nur einen Teil eines langen Strichs aufzubrechen. Der Strich in AB + C wirkt auf die gesamte Summe; arbeite dich vom äußersten Strich nach innen vor.
Zu früh aufzuhören. Prüfe nach jedem Schritt, ob sich noch etwas absorbieren lässt oder ein redundanter Konsensterm übrig ist.

Probiere es im Simulator aus

Eine korrekte Vereinfachung ergibt eine Schaltung mit genau derselben Wahrheitstabelle wie das Original. Im Simulator kannst du das überprüfen, ohne die Tabelle von Hand aufzustellen.

Baue im Editor die ursprüngliche Schaltung eines Beispiels auf, etwa AB + AB + AB, mit ihren Eingängen und ihrem Ausgang.
Erzeuge ihre Wahrheitstabelle und notiere sie.
Baue an einem weiteren Ausgang auf derselben Schaltungsfläche die vereinfachte Version (A + B) mit denselben Eingängen auf.
Schalte die Eingänge durch alle Kombinationen und beobachte, dass beide Ausgänge immer übereinstimmen.
Lass dir aus der Tabelle den vereinfachten Ausdruck ausgeben und vergleiche ihn mit deinem von Hand ermittelten Ergebnis.

Übungen

Vereinfache F = AB + AB + AB.
Lösung
AB + AB = A. Dann A + AB = A + B (Absorption des Komplements). F = A + B = AB: ein NAND.
Vereinfache F = A + B.
Lösung
De Morgan: A · B = AB.
Vereinfache F = A(A + B) + B(B + C).
Lösung
Durch Absorption gilt A(A + B) = A und B(B + C) = B. F = A + B.
Beweise das Konsensus-Theorem: AB + AC + BC = AB + AC.
Lösung
Schreibe BC = BC(A + A) = ABC + ABC. Dann gilt AB + ABC = AB (Absorption) und AC + ABC = AC (Absorption). Es bleibt AB + AC.