Normalformen

Logische Ausdrücke können in Standardformen umgeschrieben werden. Diese werden Normalformen genannt. Die zwei wichtigsten Typen: konjunktive Normalform (KNF) und disjunktive Normalform (DNF).

Disjunktive Normalform (DNF)

Die DNF ist eine Form, in der der Ausdruck eine Disjunktion von Konjunktionen ist. Anders gesagt: Konjunktionen in jedem Teil, und die Teile sind durch Disjunktion verbunden.

Das ist DNF: erster Teil (p ∧ q), zweiter Teil (¬p ∧ r), verbunden durch ∨.

Konjunktive Normalform (KNF)

Die KNF ist eine Form, in der der Ausdruck eine Konjunktion von Disjunktionen ist. Anders gesagt: Disjunktionen in jedem Teil, und die Teile sind durch Konjunktion verbunden.

Das ist KNF: erster Teil (p ∨ q), zweiter Teil (¬p ∨ r), verbunden durch ∧.

Warum sind sie nützlich?

• Sie helfen, logische Ausdrücke zu vereinfachen.
• Grundformen in automatisierten Beweissystemen.
• Computer-Algorithmen können leichter mit ihnen arbeiten.

Beispiel einer Transformation

Nehmen wir den Ausdruck: (p → q). Dieser kann umgeschrieben werden zu: (¬p ∨ q). Das ist bereits sowohl KNF als auch DNF, da es nur eine Disjunktion gibt.

Zusammenfassung

DNF: Disjunktion von Konjunktionen. KNF: Konjunktion von Disjunktionen. Jeder logische Ausdruck kann in eine dieser Normalformen umgeschrieben werden.

Übungsaufgabe