Konjunktive Normalform

Als konjunktive Normalform (kurz KNF) einer aussagenlogischen Formel liegt vor, wenn diese 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

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 sogenannte 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 tun.

Die Frage, ob die Variablen einer aussagenlogischen Formel so belegt werden können, dass die Aussage wahr wird, wird Erfüllbarkeitsproblem genannt. Es 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).

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