Boolesche Algebra und Normalformen

Zu jeder Wahrheitstafel gehört eine Aussageform, und zu jeder Aussageform gibt es viele gleichwertige Schreibweisen. Mit den Normalformen bekommst du eine, die sich immer systematisch aufstellen lässt. Sie ist die Grundlage für den Entwurf digitaler Schaltungen und für das Erfüllbarkeitsproblem der theoretischen Informatik.

Beweis. Ein Minterm ist genau in der einen Zeile wahr, aus der er gebildet wurde, und in allen anderen falsch. Die Disjunktion der Minterme ist deshalb genau in den Zeilen mit dem Wert $1$ wahr. Für die KNF wendet man das auf $\neg f$ an und verneint nach De Morgan. Ist $f$ nie wahr, ist $A\wedge \neg A$ eine DNF. $\square$

Die Rechenregeln der Booleschen Algebra

Das Vereinfachen beruht auf Regeln, die für $\wedge$ und $\vee$ jeweils gelten, wobei sich beim Vertauschen von $\wedge$ und $\vee$ (und von $0$ und $1$) wieder eine gültige Regel ergibt. Das ist das Dualitätsprinzip.

Der Unterschied zum Rechnen mit Zahlen liegt im zweiten Distributivgesetz: Auch das Oder verteilt sich über das Und. Mit einem Karnaugh-Diagramm, das die Wahrheitstafel so anordnet, dass benachbarte Felder sich in genau einer Variablen unterscheiden, findet man die zusammenfassbaren Minterme als Rechtecke.

Wie viele Bausteine braucht man?

Der Normalformsatz zeigt, dass $\neg$, $\wedge$ und $\vee$ ausreichen, um jede Aussageform zu bilden. Wegen De Morgan genügen sogar $\neg$ und $\wedge$. Es geht mit einem einzigen Baustein: Der Sheffer-Strich $A\uparrow B=\neg (A\wedge B)$ (NAND) reicht, denn $\neg A=A\uparrow A$, $A\wedge B=(A\uparrow B)\uparrow (A\uparrow B)$ und $A\vee B=(A\uparrow A)\uparrow (B\uparrow B)$. Henry Sheffer zeigte das 1913. In der Technik baut man deshalb ganze Prozessoren aus NAND-Gattern. Ein Halbaddierer addiert zwei Bits: Die Summe ist $A\oplus B$ (das ausschließende Oder), der Übertrag ist $A\wedge B$.

Für eine KNF ist die Frage, ob es eine Belegung der Variablen gibt, die sie wahr macht, das Erfüllbarkeitsproblem (SAT). Für eine DNF ist sie leicht: Es genügt ein Glied, das nicht zugleich eine Variable und ihre Verneinung enthält. Bei der KNF ist bis heute kein schnelles Verfahren bekannt; das steht auf der Seite Komplexität und Berechenbarkeit.

Weitere Aufgaben mit Normalformen gibt es auf dem Blatt Wahrheitstafeln (Aufgabenart „Normalformen“). Mit Quantoren und Strukturen erweitert die Prädikatenlogik die Aussagenlogik.