2.2 Normalformen

Für eine Reihe von Anwendungen ist es sinnvoll und notwendig, an Stelle einer aussagenlogischen Formel eine äquivalente aussagenlogische Formel zu verwenden, die eine standardisierte, vereinfachte Form aufweist.

Ein Literal ist eine aussagenlogische Variable $A\in AB$ oder das Negat einer solchen. Sind $L_{i,j}$ Literale für $i=1,\ldots,m$, $j=1,\ldots,n$, so ist eine Formel in disjunktiver Normalform (DNF), wenn sie die Form

$$\left(L_{1,1}\wedge\cdots\wedge L_{1,n_{1}}\right)\vee\cdots\vee\left(L_{m,1}\wedge\cdots\wedge L_{m,n_{m}}\right)$$

besitzt, oder in konjunktiver Normalform (KNF), wenn sie die Form

$$\left(L_{1,1}\vee\cdots\vee L_{1,n_{1}}\right)\wedge\cdots\wedge\left(L_{m,1}\vee\cdots\vee L_{m,n_{m}}\right)$$

besitzt. Eine Formel in disjunktiver Normalform ist also eine Disjunktion von Konjunktionen von Literalen, eine Formel in konjunktiver Normalform eine Konjunktion von Disjunktionen von Literalen. Die Disjunktionen einer KNF werden auch Klauseln genannt, die KNF entsprechend Klauselnormalform. Spezialfälle für konjunktive beziehungsweise disjunktive Normalformen sind $\mbox{\boldmath$\mathrm{t}$}$ beziehungsweise $\mbox{\boldmath$\mathrm{f}$}$.

Konjunktion und Disjunktion sind

• assoziativ: $\left(A\wedge B\right)\wedge C=A\wedge \left(B\wedge C\right)$ beziehungsweise $\left(A\vee B\right)\vee C=A\vee \left(B\vee C\right)$ für alle $A,B,C\in AF$,
• kommutativ: $A\wedge B=B\wedge A$ sowie $A\vee B=B\vee A$ für alle $A,B\in AF$ und
• idempotent: $A\wedge A=A$ beziehungsweise $A\vee A=A$ für alle $A\in AF$.

Daher ist es möglich, für Formeln in KNF beziehungsweise DNF die folgende Mengenschreibweise zu verwenden:

$$\left\{\left\{L_{1,1}\ldots L_{1,n_{1}}\right\},\ldots,\left\{L_{m,1}\ldots L_{m,n_{m}}\right\}\right\}$$

Eine solche Literalmenge kann jedoch sowohl als DNF als auch als KNF interpretiert werden. Um Unklarheiten zu vermeiden, wollen wir diese Schreibweise ausschließlich für KNFs verwenden.

Im Folgenden wird nun die syntaktische (algebraische) Methode beschrieben, um zu einer beliebigen aussagenlogischen Formel die äquivalente KNF beziehungsweise DNF zu ermitteln. Eine andere Möglichkeit stellt die semantische Methode dar, die eine KNF beziehungsweise DNF an Hand der Wahrheitstafel einer Formel konstruiert. Die semantische Methode ist an dieser Stelle jedoch irrelevant, da der KNF-DNF-Konverter ausschließlich die syntaktische Methode verwendet.

Im Folgenden stehen $A$, $B$ und $C$ für beliebige Formeln $A,B,C\in AF$.

 

Schritt 1: Ersetze alle Operatoren durch $\wedge$, $\vee$ sowie $\neg$:

A ⊃ B	=	¬A ∨ B		A ⊅ B	=	A ∧ ¬B
A ⊂ B	=	A ∨ ¬B		A ⊄ B	=	¬A ∧ ¬B
A ↑ B	=	¬A ∨ ¬B		A ↓ B	=	¬A ∧ ¬B
(A ≡ B)	=	(A ∧ B) (¬A ∧ ¬B)		(A ≢ B)	=	(A ∧ B) (¬A ∧ ¬B)

 

Schritt 2: Schiebe alle Negationen direkt vor die Variablen und Konstanten (die ersten beiden Umformungen sind die De Morgan'schen Gesetze):

$\neg\left(A\wedge B\right)=\neg A\vee\neg B$

$\neg\left(A\vee B\right)=\neg A\wedge\neg B$

$\neg\neg A=A$

 

Schritt 3: Eliminiere die Konstanten $\mbox{\boldmath$\mathrm{t}$}$ und $\mbox{\boldmath$\mathrm{f}$}$; dabei darf auf die Kommutativität von Konjunktion und Disjunktion (siehe oben) nicht vergessen werden:

$A\wedge \mbox{\boldmath$\mathrm{t}$}=A$

$A\wedge \mbox{\boldmath$\mathrm{f}$}=\mbox{\boldmath$\mathrm{f}$}$

$A\vee \mbox{\boldmath$\mathrm{t}$}=\mbox{\boldmath$\mathrm{t}$}$

$A\vee \mbox{\boldmath$\mathrm{f}$}=A$

$\neg \mbox{\boldmath$\mathrm{t}$}=\mbox{\boldmath$\mathrm{f}$}$

$\neg \mbox{\boldmath$\mathrm{f}$}=\mbox{\boldmath$\mathrm{t}$}$

 

Schritt 4: Wende die Distributivgesetze an. Dabei führt die linke Äquivalenz zu einer DNF, die rechte zu einer KNF; wieder ist die Kommutativität von Konjunktion und Disjunktion zu beachten.

$A\wedge\left(B\vee C\right)=\left(A\wedge B\right)\vee\left(A\wedge C\right)$

$A\vee\left(B\wedge C\right)=\left(A\vee B\right)\wedge\left(A\vee C\right)$

Dieses Verfahren basiert auf drei Tatsachen:

• Alle angegebenen Gleichungen sind gültige Äquivalenzen. Das bedeutet, dass jede Formel, auf welche das Verfahren angewandt wird, äquivalent zur ursprünglichen Formel ist.
• Auf jede Formel, die noch nicht in KNF beziehungsweise DNF vorliegt, kann eine der Äquivalenzen angewandt werden.
• Es entstehen keine unendlich langen Umformungsketten, wenn die Äquivalenzen von links nach rechts angewandt werden (im Programm werden die Umformungen von außen nach innen angewandt, siehe unten).

Dadurch terminiert das Verfahren, und das Ergebnis ist eine Formel in DNF beziehungsweise KNF, die zur ursprünglichen Formel äquivalent ist.