Konjunktive Normalform

Als konjunktive Normalform (kurz KNF, engl. CNF für conjunctive normal form) wird in der Aussagenlogik eine bestimmte Form von Formeln bezeichnet.

Definition

Eine Formel der Aussagenlogik ist in konjunktiver Normalform, wenn sie eine Konjunktion von Disjunktionstermen ist. Disjunktionsterme sind dabei Disjunktionen von Literalen. Literale sind nichtnegierte oder negierte Variablen. Eine Formel in KNF hat also die Form

$\bigwedge_i \bigvee_j (\neg)x_{ij}.$

Beispiel:

$(A \vee B \vee C ) \wedge (\bar{A} \vee B \vee C)$

Kanonische konjunktive Normalform

Eine kanonische konjunktive Normalform (KKNF) besteht aus paarweise verschiedenen Maxtermen. In jedem dieser Maxterme kommt jede Variable genau einmal vor.^[1] Jede Boolesche Funktion besitzt genau eine KKNF. Die KKNF wird auch vollständige kanonische Normalform genannt.

Bildung

Jede Formel der Aussagenlogik lässt sich in konjunktive Normalform umwandeln, da sich auch jede boolesche Funktion mit einer KNF darstellen lässt. Dazu genügt es, die Zeilen ihrer Wahrheitstabelle abzulesen. Für jede Zeile, die als Resultat eine 0 liefert, wird eine Klausel gebildet, die alle Variablen der Funktion disjunktiv mit der invertierten Belegung verknüpft. Die entstehenden Terme sind Maxterme. Deren konjunktive Verknüpfung liefert die kanonische konjunktive Normalform.

Diese ist in der Regel keine minimale Formel, das heißt eine Formel mit möglichst wenig Klauseln. Will man eine minimale Formel bilden, so kann man dies etwa mit Hilfe von Karnaugh-Veitch-Diagrammen (kurz KV-Diagrammen) tun.

Beispiel für die Bildung

Gesucht sei eine Formel in KNF für die boolesche Funktion mit drei Variablen x₂, x₁ und x₀, die genau dann den Wahrheitswert 1 (wahr) annimmt, wenn die Dualzahl [x₂x₁x₀]₂ eine Primzahl ist.

Die Wahrheitstafel für diese Funktion hat folgende Gestalt:

Anmerkung: Die einzelnen Klauseln sind als Maxterme notiert. Außerdem kann man gut sehen, dass jede KNF eine äquivalente DNF besitzt.

Entscheidbarkeit

Die Frage, ob die Variablen einer aussagenlogischen Formel so belegt werden können, dass die Aussage wahr wird, wird Erfüllbarkeitsproblem (kurz SAT) genannt. SAT gehört zur Klasse der NP-vollständigen Probleme und gilt damit im Allgemeinen als schwierig lösbar. Dies gilt auch für Formeln, die in KNF vorliegen; eine Ausnahme bilden allerdings Horn-Formeln, die einen Spezialfall der KNF-Formeln darstellen und in Polynomialzeit auf Erfüllbarkeit getestet werden können. Es gibt im Grunde zwei Ansätze, wie ein aussagenlogischer Ausdruck auf seine Erfüllbarkeit überprüft werden kann: durch Testen aller möglichen Belegungen seiner Variablen (semantische Herangehensweise) oder durch den Resolutionskalkül (rein syntaktisch).

Weitere Normalformen

Neben der konjunktiven Normalform gibt es in der Aussagenlogik weitere Normalformen, etwa die disjunktive Normalform oder die Negationsnormalform.

Einzelnachweise

1. ↑ In manchen Quellen (z.B. Klaus Beuth: Digitaltechnik, ISBN 9783802319587, auf S. 78) versteht man unter KNF genau diese kanonische KNF.

Weblinks

• Webformular zur Umwandlung in die "Konjunktive Normalform"