Normalformen

In den vorigen Lektionen dieser Einheit erhielten die Formeln eine Bedeutung: Die Lektion über die Semantik der Aussagenlogik setzte jede Belegung auf alle Formeln fort; die Lektion über semantische Folgerung und Äquivalenz definierte die Äquivalenz $\varphi \eqsem \psi$ und bewies die semantische Ersetzung; die Lektion über die verallgemeinerten De-Morgan- und Distributivgesetze dehnte diese Gesetze auf Konjunktionen und Disjunktionen aus $n$ Formeln aus; und die Lektion über die funktionale Vollständigkeit zeigte, dass jede Wahrheitsfunktion von irgendeiner Formel dargestellt wird. Nun wird eine Wahrheitsfunktion von unendlich vielen Formeln dargestellt, die sich stark voneinander unterscheiden können: $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$ und $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ sind drei Namen für dasselbe. Wenn dem so ist, empfiehlt es sich, in jeder Äquivalenzklasse einen Vertreter fester Form zu wählen, der sich mühelos lesen lässt und mit dem sich gewisse Fragen durch bloßes Hinsehen beantworten lassen. Das sind die Normalformen.

Literale, Klauseln und Normalformen

Man erinnere sich aus der Lektion über die verallgemeinerten Gesetze an die Schreibweise der Konjunktion und der Disjunktion von $n$ Formeln, die rekursiv und mit Assoziation nach links definiert ist; die einer einzigen Formel ist die Formel selbst.

In derselben Lektion wurde bewiesen, dass Reihenfolge und Gruppierung der Glieder die Formel bis auf Äquivalenz nicht verändern (verallgemeinerte Assoziativität und Unabhängigkeit von Reihenfolge und Wiederholungen); deshalb schreiben wir auch $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ ohne Klammern, wobei die Gruppierung nach links zu verstehen ist.

Ein Literal ist eine Variable $v_n$, die positives Literal heißt, oder die Negation $\neg v_n$ einer Variablen, die negatives Literal heißt. Das Komplement eines Literals $\ell$, das wir $\ell^{*}$ schreiben, ist das Literal derselben Variablen mit dem anderen Vorzeichen:

Aus der Definition folgt $(\ell^{*})^{*} = \ell$. Zwei Literale bilden ein komplementäres Paar, wenn das eine das Komplement des anderen ist, wie $v_3$ und $\neg v_3$.

Eine Klausel ist eine Disjunktion von Literalen, $\bigvee_{j=1}^{k} \ell_j$, und eine Elementarkonjunktion ist eine Konjunktion von Literalen, $\bigwedge_{j=1}^{k} \ell_j$, in beiden Fällen mit $k \geq 1$; ein einzelnes Literal ist daher zugleich eine Klausel und eine Elementarkonjunktion. Man sagt, ein Literal steht in einer Klausel oder einer Elementarkonjunktion, wenn es eines ihrer $\ell_j$ ist.

Eine Formel ist in disjunktiver Normalform, wenn sie eine Disjunktion von Elementarkonjunktionen ist, und in konjunktiver Normalform, wenn sie eine Konjunktion von Klauseln ist; das heißt, wenn sie jeweils eine der beiden folgenden Gestalten hat, wobei $m$ und $k_1, \ldots, k_m$ natürliche Zahlen sind und jedes $\ell_{i,j}$ ein Literal ist:

Wir sagen, $\Phi$ ist eine disjunktive Normalform von $\varphi$, wenn sie in disjunktiver Normalform ist und $\varphi \eqsem \Phi$ gilt, und ebenso für die konjunktive. Die Längen $k_i$ können von einer Konjunktion (oder Klausel) zur anderen verschieden sein: In allen dieselbe Anzahl von Literalen zu verlangen, würde zum Auffüllen mit Wiederholungen zwingen und nichts hinzufügen.

Es lohnt sich, bei der Bedeutung von „in Normalform sein“ zu verweilen. Es ist eine Eigenschaft der Zeichenkette aus Kreisen und Scheiben, nicht ihrer Bedeutung: Die Lektion über die Induktion über die natürlichen Zahlen und über Formeln bewies die eindeutige Lesbarkeit, sodass die Frage, ob eine Formel eine Disjunktion ist, und wovon, eine einzige Antwort hat. Nun bewirken die offiziellen Abkürzungen, dass manche Formeln in Normalform sind, ohne so auszusehen. Die Implikation $(v_1 \rightarrow v_2)$ ist als $(\neg v_1 \vee v_2)$ definiert: Sie ist nicht zu dieser Klausel äquivalent, sondern sie ist genau diese Zeichenkette und daher schon in Normalform. Überraschender ist die doppelte Negation. Nach den Definitionen von $\neg$ und von $\vee$ ist die Zeichenkette $(\varphi \vee \varphi)$ gleich $\neg(\varphi \downarrow \varphi)$, das heißt $\neg\neg\varphi$; daher ist $\neg\neg v_1$ kein Literal, aber Zeichen für Zeichen die Klausel $(v_1 \vee v_1)$.

Der Wert von Konjunktionen und Disjunktionen

Aus der Lektion über die Semantik übernimmt man die Werte der abgeleiteten Junktoren: $v(\neg\varphi) = 1 - v(\varphi)$; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$, was genau dann gleich $1$ ist, wenn beide gleich $1$ sind; und $v(\varphi \vee \psi) = 0$ genau dann, wenn beide gleich $0$ sind. Die Lektion über die verallgemeinerten De-Morgan- und Distributivgesetze dehnte sie auf $n$ Formeln aus, durch Induktion über die Anzahl der Glieder, im Wertlemma: Für jede Belegung $v$ hat die Konjunktion $\bigwedge_{i=1}^{n} \varphi_i$ den Wert $1$ unter $v$ genau dann, wenn jedes $\varphi_i$ den Wert $1$ unter $v$ hat, und die Disjunktion $\bigvee_{i=1}^{n} \varphi_i$ hat den Wert $1$ unter $v$ genau dann, wenn irgendein $\varphi_i$ den Wert $1$ unter $v$ hat. Dieses Lemma, das hier ohne Wiederholung seines Beweises angeführt wird, ist das Werkzeug, mit dem man den Wert jeder Normalform berechnet.

Der zweite Fall wird leicht übersehen: Beim Negieren einer Normalform neigt man dazu, $\neg\ell_{i,j}$ anstelle eines Literals zu schreiben, und $\neg\neg v_n$ ist keines. Die doppelte Negation ist es, die das Ergebnis in die Gussform zurückbringt.