Konjunktive Normalform

Als konjunktive Normalform (kurz KNF, englisch 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

Beispiel:

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 konjunktive 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.

Das Verfahren nach Quine und McCluskey kann genutzt werden, um die konjunktive Normalform einer beliebigen Formel berechnen zu können. Dazu wird die Formel negiert, dann mit dem Verfahren nach Quine und McCluskey in die disjunktive Normalform transformiert und wieder negiert.

Beispiel für die Bildung der KNF

Gesucht ist eine Formel in konjunktiver Normalform für die Boolesche Funktion mit drei Variablen ${\displaystyle A}$, ${\displaystyle B}$ und ${\displaystyle C}$, die genau dann den Wahrheitswert 1 annimmt, wenn die Dualzahl ${\displaystyle [ABC]_{2}}$ eine Primzahl ist.

Die Wahrheitstafel für diese Funktion hat folgende Gestalt:

Für jede Kombination der Variablen ${\displaystyle A}$, ${\displaystyle B}$ und ${\displaystyle C}$, für die sich der Funktionswert 0 ergibt, wird eine Disjunktion gebildet. Die Variablen, die den Wert 1 haben, werden negiert. Im Beispiel oben sind das die Disjunktionen ${\displaystyle A\lor B\lor C}$ und ${\displaystyle A\lor B\lor \lnot C}$ und ${\displaystyle \lnot A\lor B\lor C}$ und ${\displaystyle \lnot A\lor \lnot B\lor C}$. Schließlich werden diese Maxterme mit Konjunktionen verknüpft. Daraus ergibt sich die konjunktive Normalform:

${\displaystyle (A\lor B\lor C)\land (A\lor B\lor \lnot C)\land (\lnot A\lor B\lor C)\land (\lnot A\lor \lnot B\lor C)}$

Anmerkung: Die einzelnen Klauseln sind als Maxterme notiert. Außerdem ist in der Abbildung zu 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, die Negationsnormalform oder die kanonische Normalform.

Einzelnachweise

1. ↑ In manchen Quellen (z. B. Klaus Beuth: Digitaltechnik, ISBN 978-3-8023-1958-7, auf S. 78) versteht man unter KNF genau diese kanonische KNF.

Weblinks

• Tool zur Umwandlung von Wahrheitstafeln in die "Konjunktive Normalform"
• Webformular zur Umwandlung in die "Konjunktive Normalform"