Normalformen dienen der einheitlichen Darstellung von aussagenlogischen Ausdrücken.

Eine negierte oder unnegierte Aussagevariable.

Beispiele:
p, a, ¬b, W

Eine Konjunktion von Literalen.

Beispiele:
a ∧ b, ¬p ∧ q

Eine Disjunktion von Literalen.

Beispiele:
a ∨ b, ¬p ∨ q

Ein Minterm, der alle gegebenen Aussagevariablen genau ein Mal als Literal enthält.

Beispiele:
Variablen a, b, c: a ∧ ¬b ∧ c
Variablen p, q, r, s: ¬p ∧ q ∧ r ∧ ¬s

Ein Maxterm, der alle gegebenen Aussagevariablen genau ein Mal als Literal enthält.

Beispiele:
Variablen a, b, c: a ∨ ¬b ∨ c
Variablen p, q, r, s: ¬p ∨ q ∨ r ∨ ¬s

Ziel ist es einen Ausdruck in eine äquivalente Konjunktion von Maxtermen umzuformen.

Beispiel:
(a ∨ b) ∧ (c ∨ d)

Ziel ist es einen Ausdruck in eine äquivalente Disjunktion von Mintermen umzuformen.

Beispiel:
(a ∧ b) ∨ (c ∧ d)

Eine kanonische konjunktive Normalform KKNF ist eine konjunktive Verknüpfung von Basdisjunktionen, wobei jede Basisdisjunktion höchstens einmal vorkommt.

Beispiele:
Variablen a, b, c: (¬a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c) ∧ (¬a ∨ b ∨ ¬c)
Variablen p, q, r, s: (¬p ∨ ¬q ∨ r ∨ s) ∧ (¬p ∨ q ∨ r ∨ ¬s) ∧ (p ∨ q ∨ r ∨ s) ∧ (p ∨ q ∨ r ∨ ¬s)

Eine kanonische disjunktive Normalform KDNF ist eine disjunktive Verknüpfung von Basiskonjunktionen, wobei jede Basiskonjunktion höchstens einmal vorkommt.

Beispiele:
Variablen a, b, c: (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ ¬c) ∨ (¬a ∧ b ∧ ¬c)
Variablen p, q, r, s: (¬p ∧ ¬q ∧ ¬r ∧ ¬s) ∨ (¬p ∧ q ∧ ¬r ∧ ¬s) ∨ (p ∧ q ∧ r ∧ s) ∨ (p ∧ q ∧ r ∧ ¬s)

1. Auflösung der Bijunktion
   B ↔ C ⇔ (B ∨ ¬C) ∧ (¬B ∨ C)
   B und C können nicht nur einzelne Variablen sondern auch ganze Ausdrücke sein.
2. Auflösung der Implikation
   B → C ⇔ ¬B ∨ C
3. Auflösung negierter Konjungate und Disjungate mit dem DeMorgan-Gesetz
   ¬(B ∨ C) ⇔ (¬B ∧ ¬C)
   ¬(B ∧ C) ⇔ (¬B ∨ ¬C)
4. Anwendung des Distributivgesetzes zur Umformung von B ∨ (C ∧ D) nach (B ∨ C) ∧ (B ∨ D)

1. Auflösung der Bijunktion
   B ↔ C ⇔ (B ∧ C) ∨ (¬B ∧ ¬C)
   B und C können nicht nur einzelne Variablen sondern auch ganze Ausdrücke sein.
2. Auflösung der Implikation
   B → C ⇔ ¬B ∨ C
3. Auflösung negierter Konjungate und Disjungate mit dem DeMorgan-Gesetz
   ¬(B ∨ C) ⇔ (¬B ∧ ¬C)
   ¬(B ∧ C) ⇔ (¬B ∨ ¬C)
4. Anwendung des Distributivgesetzes zur Umformung von B ∧ (C ∨ D) nach (B ∧ C) ∨ (B ∧ D)

Bei der Entwicklung der KKNF stellt man zuerst die KNF auf, vereinfacht diese und erweitert die Terme auf Basisdisjunktionen. Mehrfach auftretende Basisdisjunktionen werden weggelassen.
Um einen disjunktiv Verknüpften Ausdruck in eine Basisdisjunktionen umzuwandeln ohne, dass sich das Ergebnis ändert, muss mit F erweitert werden.
Begründung: Ausdruck ∨ F ⇔ Ausdruck Der Wahrheitswert des Ausdruckes ändert sich nicht.
Für F werden dann die fehlenden Variablen konjunktiv mit ihren Negat verknüpft.

Beispiel:
Variablen a, b, c
a ∨ b
a ∨ b ∨ F
a ∨ b ∨ (c ∧ ¬c)
a ∨ ((b ∨ c) ∧ (b ∨ ¬c))
(a ∨ b ∨ c) ∧ (a ∨ b ∨ ¬c)

Bei der Entwicklung der KDNF stellt man zuerst die DNF auf, vereinfacht diese und erweitert die Terme auf Basiskonjunktionen. Mehrfach auftretende Basiskonjunktionen werden weggelassen.
Um einen konjunktiv Verknüpften Ausdruck in eine Basiskonjunktion umzuwandeln ohne, dass sich das Ergebnis ändert, muss mit W erweitert werden.
Begründung: Ausdruck ∧ F ⇔ Ausdruck Der Wahrheitswert des Ausdruckes ändert sich nicht.
Für W werden dann die fehlenden Variablen disjunktiv mit ihren Negat verknüpft.

Beispiel:
Variablen a, b, c
a ∧ b
a ∧ b ∧ W
a ∧ b ∧ (c ∨ ¬c)
a ∧ ((b ∧ c) ∨ (b ∧ ¬c))
(a ∧ b ∧ c) ∨ (a ∧ b ∧ ¬c)

Angabe: p ∧ (¬(¬r → p) ∨ q)

Da es in diesem Beispiel keine Bijunktion gibt, sind die nächsten beiden Schritte sowohl für KKNF als auch KDNF gültig.

Auflösung der Inplikation
p ∧ (¬(r ∨ p) ∨ q)

DeMorgan
p ∧ ((¬r ∧ ¬p) ∨ q)


Erstellung der DNF
(p ∧ ¬p ∧ ¬r) ∨ (p ∧ q)
F ∨ (p ∧ q)
DNF: p ∧ q

Erstellung der KDNF
(p ∧ q ∧ W)
(p ∧ q ∧ (r ∨ ¬r))
p ∧ ((q ∧ r) ∨ (q ∧ ¬r))
KDNF: (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r)

KNF: (p ∧ (¬r ∨ q) ∧ (¬p ∨ q))

Erstellung der KKNF
(p ∨ F ∨ F) ∧ (F ∨ ¬r ∨ q) ∧ (¬p ∨ q ∨ r)

Die Ausdrücke werden jetzt einzeln berechnet, da es sonst ein ziemlich langer Ausdruck wird.

1.: (p ∨ (¬q ∧ q) ∨ (¬r ∧ r))
((p ∨ ¬q) ∧ (p ∨ q)) ∨ (¬r ∧ r)
((p ∨ ¬q) ∨ (¬r ∧ r)) ∧ ((p ∨ q) ∨ (¬r ∧ r))
(p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r)

2.: ((p ∧ ¬p) ∨ ¬r ∨ q)
((p ∨ ¬r) ∧ (¬p ∧ ¬r) ∨ q)
(p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r)

3.: (¬p ∨ q ∨ (¬r ∧ r))
(¬p ∨ ((q ∨ ¬r) ∧ (q ∨ r)))
(¬p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ r)

Die Ausdrücke (¬p ∨ q ∨ ¬r) und (p ∨ q ∨ ¬r) kommen doppelt vor und werden in der Lösung nur ein Mal angeschrieben.

KKNF: (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r)