imported>Kleinesfilmröllchen: Einleitung: Versuch an WP:OMA

2025-03-16T20:15:33Z

Einleitung: Versuch an WP:OMA

Neue Seite

Als '''konjunktive Normalform''' (kurz '''KNF''', {{enS|'''CNF'''}} für ''conjunctive normal form'') wird in der [[Aussagenlogik]] eine bestimmte Form von [[Logische Formel|Formeln]] bezeichnet. Vereinfacht gesagt handelt es sich um eine Reihe an (geklammerten) [[Logisches Oder|Oder]]-Termen, die nur aus eventuell [[Logisches Nicht|negierten]] [[Variable (Logik)|Variablen]] bestehen, und diese Oder-Terme sind wiederum mit [[Logisches Und|Und]]-Verknüpfungen verbunden.

== Definition ==
Eine Formel der Aussagenlogik ist in '''konjunktiver Normalform''', wenn sie eine [[Konjunktion (Logik)|Konjunktion]] von [[Disjunktionsterm]]en ist. Disjunktionsterme sind dabei [[Disjunktion]]en von [[Literal]]en. Literale sind nichtnegierte oder negierte Variablen. Eine Formel in KNF hat also die Form <div class="center"><math>\bigwedge_i \bigvee_j (\neg)x_{ij}.</math></div>

Beispiel: <div class="center"><math>(A \vee B \vee C ) \wedge (\bar{A} \vee B \vee C)</math></div>

== Kanonische konjunktive Normalform ==
Eine ''kanonische konjunktive Normalform'' (KKNF) besteht aus paarweise verschiedenen [[Maxterm]]en. In jedem dieser Maxterme kommt jede Variable genau einmal vor.<ref>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.</ref> 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 [[Disjunktionsterm|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-Diagramm]]en (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 <math>A</math>, <math>B</math> und <math>C</math>, die genau dann den Wahrheitswert 1 annimmt, wenn die [[Dualzahl]] <math>[ABC]_2</math> eine [[Primzahl]] ist.

Die Wahrheitstafel für diese Funktion hat folgende Gestalt:

[[Datei:Knf+dnf.svg]]

Für jede Kombination der Variablen <math>A</math>, <math>B</math> und <math>C</math>, 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 <math>A \lor B \lor C</math> und <math>A \lor B \lor \lnot C</math> und <math>\lnot A \lor B \lor C</math> und <math>\lnot A \lor \lnot B \lor C</math>. Schließlich werden diese [[Maxterm|Maxterme]] mit Konjunktionen verknüpft. Daraus ergibt sich die konjunktive Normalform:

: <math>(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)</math>

'''Anmerkung:''' Die einzelnen Klauseln sind als [[Maxterm]]e notiert. Außerdem ist in der Abbildung zu sehen, dass jede KNF eine äquivalente [[Disjunktive Normalform|DNF]] besitzt.

== Entscheidbarkeit ==
Die Frage, ob die Variablen einer aussagenlogischen Formel so belegt werden können, dass die Aussage wahr wird, wird [[Erfüllbarkeitsproblem der Aussagenlogik|''Erfüllbarkeitsproblem'']] (kurz ''SAT'') genannt. SAT gehört zur Klasse der [[NP-Vollständigkeit|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-Formel]]n, 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 [[Resolution (Logik)|Resolutionskalkül]] (rein syntaktisch).

== Weitere Normalformen ==
Neben der konjunktiven Normalform gibt es in der Aussagenlogik weitere [[Normalform]]en, etwa die [[disjunktive Normalform]], die [[Negationsnormalform]] oder die [[kanonische Normalform]].

== Einzelnachweise ==
<references />

== Weblinks ==
* [https://www.erpelstolz.at/gateway/formular-zentral.html Webformular zur Umwandlung in die "Konjunktive Normalform"]
* [https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/normalform/index.html Tool zur Umwandlung von Wahrheitstafeln in die "Konjunktive Normalform"]

[[Kategorie:Mathematische Logik]]
[[Kategorie:Normalform]]

Konjunktive Normalform - Versionsgeschichte

imported>Kleinesfilmröllchen: Einleitung: Versuch an WP:OMA