Boolesche Algebra verstehen: Rechenregeln und Vereinfachen

Im letzten Beitrag stand am Ende die Mehrheitsentscheidung als Gleichung mit vier langen UND-Termen. Gebaut aus Gattern braucht sie acht Bausteine. Dieselbe Funktion lässt sich mit nur vier Gattern realisieren. Weniger Gatter bedeuten weniger Fläche auf dem Chip, weniger Stromverbrauch und weniger mögliche Fehlerstellen. Aber wie kommst du von der langen auf die kurze Form, ohne alles zu raten?

Dafür gibt es die Boolesche Algebra. Sie liefert Rechenregeln, mit denen du logische Ausdrücke umformst und vereinfachst, ähnlich wie du in der Mathematik Gleichungen umstellst. Die Wertetabelle aus dem Beitrag Wertetabellen erstellen und lesen bleibt dabei dein Kontrollwerkzeug.

Woher kommt der Name?

Die Boolesche Algebra geht auf den englischen Mathematiker George Boole zurück, der sie Mitte des 19. Jahrhunderts als Rechnen mit Wahrheitswerten entwickelte. Praktisch wichtig wurde sie rund achtzig Jahre später: Der Ingenieur Claude Shannon zeigte 1937, dass sich die Regeln auf Schaltungen aus Relais und Schaltern anwenden lassen. Seitdem ist sie das mathematische Fundament der Digitaltechnik.

Schreibweise

In diesem Beitrag verwenden wir die kompakte Schreibweise, wie sie in der Ausbildung üblich ist:

UND als Punkt: A · B, oft ohne Punkt als AB geschrieben
ODER als Plus: A + B
NICHT als ¬A. In Büchern steht dafür meist ein Strich über dem Buchstaben.

Auch hier gilt wie schon beim ODER: Das Pluszeichen ist keine Addition. In der Booleschen Algebra ist 1 + 1 = 1.

Die Rechenregeln im Überblick

Gesetz	UND-Form	ODER-Form
Neutrales Element	A · 1 = A	A + 0 = A
Nullelement	A · 0 = 0	A + 1 = 1
Idempotenz	A · A = A	A + A = A
Komplement	A · ¬A = 0	A + ¬A = 1
Doppelte Negation	¬(¬A) = A
Kommutativgesetz	A · B = B · A	A + B = B + A
Assoziativgesetz	(A · B) · C = A · (B · C)	(A + B) + C = A + (B + C)
Distributivgesetz	A · (B + C) = A·B + A·C	A + (B · C) = (A + B) · (A + C)
Absorptionsgesetz	A · (A + B) = A	A + (A · B) = A
De Morgan	¬(A · B) = ¬A + ¬B	¬(A + B) = ¬A · ¬B

Du siehst eine Symmetrie: Jedes Gesetz hat eine UND-Form und eine ODER-Form. Tauschst du in einem gültigen Gesetz überall UND und ODER sowie 0 und 1 gegeneinander aus, erhältst du ein weiteres gültiges Gesetz. Man nennt das das Dualitätsprinzip. Es spart dir Lernaufwand: Wenn du eine Hälfte kennst, kennst du die andere.

Besonders auffällig ist die ODER-Form des Distributivgesetzes. In der normalen Algebra gilt a + (b · c) = (a + b) · (a + c) nicht, hier schon. Das ist eine häufige Stolperstelle.

Regeln überprüfen: Der Beweis per Wertetabelle

Jede dieser Regeln kannst du mit einer Wertetabelle nachprüfen. Als Beispiel die Absorption A + (A · B) = A:

A	B	A · B	A + (A · B)
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

Die letzte Spalte stimmt in allen Zeilen mit A überein. Das Gesetz ist also bewiesen. Der Name verrät auch den Sinn: Der Term A · B wird vom Term A „aufgesaugt“. Hat A schon alles abgedeckt, trägt A · B nichts mehr bei.

Vereinfachen Schritt für Schritt

Das Vorgehen ist immer gleich: Du suchst in deinem Ausdruck ein Muster aus der Regeltabelle und ersetzt es. Dabei schreibst du bei jedem Schritt dazu, welches Gesetz du benutzt hast. Das hilft dir bei der Kontrolle und gibt in Prüfungen Punkte.

Beispiel 1: Ausklammern

Q = A·B + A·¬B
  = A · (B + ¬B)     Ausklammern (Distributivgesetz)
  = A · 1            Komplement
  = A                Neutrales Element

Die Schaltung braucht am Ende gar kein Gatter mehr. Der Ausgang ist einfach A, und B spielt keine Rolle. Ein deutlicher Hinweis, dass der ursprüngliche Entwurf überflüssige Teile enthielt.

Beispiel 2: Das zweite Distributivgesetz

Q = A + ¬A·B
  = (A + ¬A) · (A + B)   Distributivgesetz (ODER-Form)
  = 1 · (A + B)          Komplement
  = A + B                Neutrales Element

Das Ergebnis lässt sich nachprüfen: Ist A = 1, ist der Ausdruck 1 und A + B ebenfalls 1. Ist A = 0, bleibt im Original nur noch B übrig, und das stimmt mit A + B = B überein. Statt UND-, NICHT- und ODER-Gatter reicht ein einziges ODER-Gatter.

Beispiel 3: Die Mehrheitsentscheidung vereinfachen

Aus dem Beitrag zu den Wertetabellen kennst du die lange Form:

Q = ¬A·B·C + A·¬B·C + A·B·¬C + A·B·C

Der Trick besteht darin, den letzten Term mehrfach zu verwenden. Nach der Idempotenz darf A·B·C beliebig oft hinzugefügt werden, denn X + X = X. Wir schreiben ihn dreimal:

Q = ¬A·B·C + A·¬B·C + A·B·¬C + A·B·C + A·B·C + A·B·C

Gruppieren und ausklammern:

  (¬A·B·C + A·B·C)  =  B·C · (¬A + A)  =  B·C
  (A·¬B·C + A·B·C)  =  A·C · (¬B + B)  =  A·C
  (A·B·¬C + A·B·C)  =  A·B · (¬C + C)  =  A·B

Q = B·C + A·C + A·B

Aus acht Gattern (drei NICHT, vier UND mit drei Eingängen und ein ODER mit vier Eingängen) sind vier geworden: drei UND mit zwei Eingängen und ein ODER mit drei Eingängen. Dieselbe Funktion, die Hälfte des Aufwands.

Dieselbe Funktion vor und nach der Vereinfachung: acht Gatter gegenüber vier.

De Morgan: Negation über Klammern hinweg

Die beiden Regeln von Augustus De Morgan sind die mächtigsten Umformungswerkzeuge der Digitaltechnik:

¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B

Merke dir das Prinzip: Die Negation geht in die Klammer hinein, dabei wird jeder Operator getauscht (UND wird ODER und umgekehrt) und jede Variable negiert. Die Wertetabelle im Beitrag zuvor hat die erste Regel bereits bestätigt.

Ein Anwendungsbeispiel:

Q = ¬(A · ¬B)
  = ¬A + ¬(¬B)    De Morgan
  = ¬A + B        Doppelte Negation

Aus einem NAND-Gatter, dessen zweiter Eingang negiert ist, wird also ein ODER-Gatter, bei dem stattdessen der erste Eingang negiert ist.

De Morgan in der Programmierung

Die Regeln gelten genauso in Bedingungen im Code. Ein Beispiel aus der Praxis einer Zugriffsregel: Eine Verbindung soll verweigert werden, wenn nicht gilt, dass sie aus dem internen Netz kommt und auf Port 443 zielt. Das ist ein NICHT über eine UND-Verknüpfung. Nach De Morgan heißt das: verweigern, wenn sie nicht intern ist oder nicht auf Port 443 zielt.

Mit Python kannst du die Gleichheit für alle Fälle prüfen:

from itertools import product

for a, b in product([False, True], repeat=2):
    links = not (a and b)
    rechts = (not a) or (not b)
    print(a, b, links == rechts)

Der Code testet alle vier Kombinationen von a und b und vergleicht beide Seiten der Regel. Jede Zeile der Ausgabe endet mit True, die Regel stimmt also in allen Fällen.

De Morgan als Schaltbild: Ein NAND entspricht einem ODER mit invertierten Eingängen.

Alles mit NAND bauen

Im Beitrag zu den Logikgattern hieß es, NAND sei ein Universalgatter. Jetzt kannst du es mit den Regeln der Algebra beweisen:

Gewünschte Funktion	Umformung	Nur mit NAND
NICHT A	¬(A · A) = ¬A (Idempotenz)	NAND(A, A)
A UND B	¬(¬(A · B)) = A · B	NAND(NAND(A, B), NAND(A, B))
A ODER B	¬(¬A · ¬B) = A + B (De Morgan)	NAND(NAND(A, A), NAND(B, B))

Beim ODER steckt De Morgan drin: Du negierst beide Eingänge mit zwei NAND-Gattern und verknüpfst sie mit einem dritten NAND. Das ergibt dank der Regel genau A + B. Weil ein einziger Gattertyp genügt, lässt sich ein Chip einheitlicher aufbauen.

Wo hilft dir das in der Praxis?

Schaltungsentwurf: Vereinfachte Ausdrücke brauchen weniger Gatter und sind damit kleiner, sparsamer und weniger fehleranfällig.
Programmierung: Du erkennst, wenn eine verschachtelte if-Bedingung sich zusammenfassen oder lesbarer umformen lässt.
Datenbanken: Auch bei Bedingungen in SQL mit AND, OR und NOT gelten diese Regeln, etwa wenn du eine Abfrage umschreibst.
Fehlersuche: Wenn zwei Bedingungen angeblich dasselbe tun, aber unterschiedliche Ergebnisse liefern, kannst du sie mit den Regeln oder per Wertetabelle vergleichen.

Für größere Funktionen mit vielen Eingängen gibt es zusätzlich grafische Verfahren wie das KV-Diagramm, das in manchen Lehrplänen im Anschluss behandelt wird. Die Regeln aus diesem Beitrag bleiben aber die Grundlage.

Typische Fehler

De Morgan unvollständig angewendet. Wer nur die Variablen negiert, aber UND und ODER nicht tauscht, erhält ein falsches Ergebnis. Beides gehört zusammen.
Die ODER-Form des Distributivgesetzes übersehen. A + (B · C) lässt sich ausmultiplizieren, nicht nur A · (B + C).
Klammern weglassen. Ohne Klammern gilt NICHT vor UND vor ODER. Wer das vergisst, formt einen anderen Ausdruck um.
1 + 1 = 2 rechnen. In der Booleschen Algebra bleibt es bei 1.
Nicht kontrollieren. Prüfe das Ergebnis jeder Vereinfachung kurz mit einer Wertetabelle. Das dauert wenige Minuten und fängt die meisten Fehler ab.

Zum Üben

Vereinfache Q = A·A + A·¬A.
Vereinfache Q = A·B + A·B·C.
Wende De Morgan an auf Q = ¬(A + ¬B).
Vereinfache Q = (A + B) · (A + ¬B).
Vereinfache Q = ¬A·¬B + ¬A·B.
Schreibe A + B ausschließlich mit NAND-Gattern.

Lösungen:

(1) A·A + A·¬A = A + 0 = A
    (Idempotenz, Komplement, Neutrales Element)

(2) A·B + A·B·C = A·B · (1 + C) = A·B · 1 = A·B
    (Ausklammern, Nullelement, Neutrales Element)

(3) ¬(A + ¬B) = ¬A · ¬(¬B) = ¬A · B
    (De Morgan, Doppelte Negation)

(4) (A + B) · (A + ¬B) = A + B·¬B = A + 0 = A
    (Distributivgesetz ODER-Form, Komplement, Neutrales Element)

(5) ¬A·¬B + ¬A·B = ¬A · (¬B + B) = ¬A · 1 = ¬A
    (Ausklammern, Komplement, Neutrales Element)

(6) NAND(NAND(A, A), NAND(B, B))

Das solltest du dir merken

Die Boolesche Algebra ist ein Regelwerk zum Umformen logischer Ausdrücke. UND schreibst du als Punkt, ODER als Plus, NICHT mit Negationszeichen oder Strich.
Jedes Gesetz hat eine UND- und eine ODER-Form. Das Dualitätsprinzip verbindet beide.
Wichtige Regeln: Idempotenz, Komplement, Distributivgesetz (in beiden Formen), Absorption und De Morgan.
De Morgan: Negation in die Klammer ziehen, Operator tauschen, Variablen negieren.
Beim Vereinfachen nennst du bei jedem Schritt das benutzte Gesetz und kontrollierst das Ergebnis mit einer Wertetabelle.
Mit NAND (oder NOR) allein lässt sich jede logische Funktion bauen.

Damit hast du die Grundlagen der Digitaltechnik beisammen: Signale, Gatter, Tabellen und Regeln. Im nächsten Block geht es um Netzwerke, also darum, wie Geräte Daten austauschen. Los geht es mit der Grundfrage: Was ist ein Computernetzwerk?

Boolesche Algebra verstehen: Rechenregeln für logische Schaltungen