Normalformen: DNF und KNF

Worum es geht

Skript Teil 1, Folien 19 bis 22. Beispiel der Folien 21 und 22:

\neg\big(\neg x_3 \land \neg(x_2 \land x_1)\big)

Abschnitt 6 hat gezeigt: Eine Funktion ist durch ihre Tafel festgelegt. Jetzt geht es rückwärts: Aus einer Tafel soll ein Ausdruck werden. Das klappt immer, mit nur drei Zeichen: $\land$ , $\lor$ , $\neg$ .

So gehen wir vor:

Was DNF und KNF sind.
Beide am Beispiel XOR.
Kanonische DNF und KNF Schritt für Schritt aus einer Tafel bauen.

Drei Zeichen reichen

Satz

Alle $n$ -stelligen booleschen Funktionen können mit Hilfe von $\land$ , $\lor$ und $\neg$ dargestellt werden.
$\land$ , $\lor$ und $\neg$ können nur durch NAND oder nur durch NOR dargestellt werden.

Der erste Satz sagt: Jede boolesche Funktion lässt sich mit UND, ODER und NICHT schreiben. Wie das geht, zeigen die Schritte 6 bis 8: Man liest den Ausdruck aus der Tafel ab.

Den zweiten Teil kennen wir aus Abschnitt 3: UND, ODER und NICHT lassen sich nur aus NAND bauen. Ebenso nur aus NOR.

Was DNF und KNF sind

Definition · DNF, KNF

Ein logischer Ausdruck befindet sich in disjunktiver Normalform (DNF), falls er nur Disjunktionen ( $\lor$ ) von Konjunktionen ( $\land$ ) von Literalen enthält.
Ein logischer Ausdruck befindet sich in konjunktiver Normalform (KNF), falls er nur Konjunktionen ( $\land$ ) von Disjunktionen ( $\lor$ ) von Literalen enthält.

Beispiele

\text{DNF: } (p \land q) \lor (\neg p \land q), \quad p \lor (q \land r), \quad 0 \\ \text{KNF: } (\neg p \lor q) \land (p \lor q), \quad p \land (q \lor r), \quad 1

Die DNF (disjunktive Normalform) ist ein großes ODER. Jeder Teil davon ist ein UND aus Literalen, etwa $\neg p \land q$ . Zur Erinnerung: Literale sind Variablen, ihre Negationen und die Konstanten 0 und 1 (Abschnitt 4).

Die KNF (konjunktive Normalform) ist es umgekehrt: ein großes UND aus ODER-Teilen.

Auch $p \lor (q \land r)$ ist eine DNF: Der erste Teil ist das einzelne Literal $p$ . Und die Konstante 0 ist schon für sich eine DNF.

Zeile	$p$	$q$	$p \veebar q$	$\neg p \land q$	$p \land \neg q$	$D$	$p \lor q$	$\neg p \lor \neg q$	$K$
1	0	0	0	0	0	0	0	1	0
2	0	1	1	1	0	1	1	1	1
3	1	0	1	0	1	1	1	1	1
4	1	1	0	0	0	0	1	0	0

Schritt 0Worum es geht

Schritt 1Drei Zeichen reichen

Schritt 2Was DNF und KNF sind

Beispiel XOR

Abbildung 1Beispiel XOR

Worum es geht

Drei Zeichen reichen

Was DNF und KNF sind