In der Boolean Logik ist eine Formel in der verbindenden normalen Form (CNF), wenn es eine Verbindung von Klauseln ist, wo eine Klausel eine Trennung von Druckfehlern ist.

Als eine normale Form ist es im automatisierten Lehrsatz-Beweis nützlich. Es ist dem Produkt der in der Stromkreis-Theorie verwendeten Summe-Form ähnlich.

Alle Verbindungen von Druckfehlern und alle Trennungen von Druckfehlern sind in CNF, weil sie als Verbindungen von einwörtlichen Klauseln und Verbindungen einer einzelnen Klausel beziehungsweise gesehen werden können. Als in der abtrennenden normalen Form (DNF) sind die einzigen Satzbindewörter, die eine Formel in CNF enthalten kann, und, oder, und nicht. Der nicht Maschinenbediener kann nur als ein Teil eines Druckfehlers verwendet werden, was bedeutet, dass er nur einer Satzvariable vorangehen kann.

Beispiele und Gegenbeispiele

Alle folgenden Formeln sind in CNF:

Die letzte Formel ist in CNF, weil es als die Verbindung der zwei einzeln-wörtlichen Klauseln gesehen werden kann und. Beiläufig ist diese Formel auch in der abtrennenden normalen Form. Die folgenden Formeln sind nicht in CNF:

Die obengenannten drei Formeln sind beziehungsweise zu den folgenden drei Formeln gleichwertig, die in CNF sind:

Konvertierung in CNF

Jede Satzformel kann in eine gleichwertige Formel umgewandelt werden, die in CNF ist. Diese Transformation basiert auf Regeln über logische Gleichwertigkeiten: das doppelte negative Gesetz, die Gesetze von De Morgan und das verteilende Gesetz.

Da alle logischen Formeln in eine gleichwertige Formel in der verbindenden normalen Form umgewandelt werden können, basieren Beweise häufig in der Annahme, dass alle Formeln CNF sind. Jedoch in einigen Fällen kann diese Konvertierung zu CNF zu einer Exponentialexplosion der Formel führen. Zum Beispiel erzeugt das Übersetzen der folgenden non-CNF Formel in CNF eine Formel mit Klauseln:

Insbesondere die erzeugte Formel ist:

(X_1 \vee \cdots \vee X_ {n-1} \vee Y_n) \wedge

\cdots \wedge

(Y_1 \vee \cdots \vee Y_ {n-1} \vee Y_n). </Mathematik>

Diese Formel enthält Klauseln; jede Klausel enthält entweder oder für jeden.

Dort bestehen Sie Transformationen in CNF, die eine Exponentialzunahme in der Größe durch die Bewahrung satisfiability aber nicht Gleichwertigkeit vermeiden. Diese Transformationen werden zu nur geradlinig Zunahme die Größe der Formel versichert, aber führen neue Variablen ein. Zum Beispiel kann die obengenannte Formel in CNF durch das Hinzufügen von Variablen wie folgt umgestaltet werden:

(\neg Z_1 \vee X_1) \wedge (\neg Z_1 \vee Y_1) \wedge

\cdots \wedge

(\neg Z_n \vee X_n) \wedge (\neg Z_n \vee Y_n). </Mathematik>

Eine Interpretation befriedigt diese Formel nur, wenn mindestens eine der neuen Variablen wahr sind. Wenn diese Variable ist, dann sind beide und ebenso wahr. Das bedeutet, dass jedes Modell, das diese Formel auch befriedigt, den ursprünglichen befriedigt. Andererseits befriedigen nur einige der Modelle der ursprünglichen Formel diesen: Seitdem sie nicht erwähnt in der ursprünglichen Formel gewesen sind, sind ihre Werte für die Befriedigung davon irrelevant, die nicht der Fall in der letzten Formel ist. Das bedeutet, dass die ursprüngliche Formel und das Ergebnis der Übersetzung equisatisfiable, aber nicht gleichwertig sind.

Eine alternative Übersetzung schließt auch die Klauseln ein. Mit diesen Klauseln bezieht die Formel ein; diese Formel wird häufig betrachtet, um "zu definieren", um ein Name dafür zu sein.

Logik der ersten Ordnung

In der ersten Ordnungslogik kann verbindende normale Form weiter angenommen werden, um die clausal normale Form einer logischen Formel nachzugeben, die dann verwendet werden kann, um Entschlossenheit der ersten Ordnung durchzuführen.

Rechenbetonte Kompliziertheit

Ein wichtiger Satz von Problemen in der rechenbetonten Kompliziertheit schließt Entdeckung von Anweisungen zu den Variablen einer boolean Formel ein, die in der Verbindenden Normalen Form ausgedrückt ist, solch, dass die Formel wahr ist. Das k-SAT Problem ist das Problem, eine befriedigende Anweisung zu einer boolean Formel ausgedrückt in solchem CNF zu finden, dass jede Trennung an den meisten k Variablen enthält. 3 GESESSEN ist NP-complete (wie jedes andere k-SAT Problem mit k>, 2) während 2 GESESSEN, ist bekannt, Lösungen in der polynomischen Zeit zu haben.

Typische Probleme schließen in diesem Fall Formeln in "3CNF" Form ein: verbindende normale Form ohne mehr als drei Variablen pro verbundenen. Beispiele solcher Formeln gestoßen können in der Praxis, zum Beispiel mit 100,000 Variablen und 1,000,000 conjuncts sehr groß sein.

Das Umwandeln von der Logik der ersten Ordnung

Logik der ersten Ordnung zu CNF umzuwandeln:

1. Wandeln Sie zur Ablehnung normale Form um.
2. Beseitigen Sie Implikationen: Wandeln Sie sich zu um
3. Bewegen Sie NOTs nach innen, indem Sie das Gesetz von DeMorgan wiederholt anwenden. Ersetzen Sie spezifisch dadurch; ersetzen Sie dadurch; und ersetzen Sie dadurch.
4. Standardisieren Sie Variablen
5. Für Sätze wie (x P (x))  (x Q (x)), die denselben Variablennamen zweimal verwenden, ändern Sie den Namen von einer der Variablen. Das vermeidet Verwirrung später, wenn wir den quantifiers fallen lassen.
6. Von x [y Tier (y)  Liebt ¬ (x, y)]  [Liebt y (y, x)]. wir herrschen vor: x [y Tier (y)  ¬ Liebt (x, y)]  [Liebt z (z, x)].
7. Skolemize die Behauptung
8. x P (x) in P (A), wo A eine neue Konstante ist (befragen verbundenen Artikel für mehr Details)
9. Lassen Sie universalen quantifiers fallen
10. Verteilen Sie ORs über ANDs.

Referenzen

Siehe auch

• Algebraische normale Form
• Abtrennende normale Form
• Hornklausel
• Quine-McCluskey Algorithmus
• Paul Jackson, Daniel Sheridan: Klausel-Form-Konvertierungen für Boolean Stromkreise. In: Holger H. Hoos, David G. Mitchell (Hrsg.).: Theorie und Anwendungen der Satisfiability-Prüfung, 7. Internationaler Konferenz, haben 2004, Vancouver, v. Chr., Kanada, am 10-13 Mai 2004, Revidierte Ausgewählte Papiere GESESSEN. Vortrag-Zeichen in der Informatik 3542, Springer 2005, Seiten 183-198
• G.S. Tseitin: Auf der Kompliziertheit der Abstammung in der Satzrechnung. In: Slisenko, A.O. (Hrsg.). Strukturen in Konstruktiver Mathematik und Mathematischer Logik, zweitem Teil, Seminaren in der Mathematik (übersetzt aus dem Russisch), Seiten 115-125. Steklov Mathematisches Institut (1968)

Links

• Java applet, um sich zu CNF und DNF umzuwandeln, Gesetze zeigend, hat verwendet
• 3D-Anwendung, den Unterschied zwischen CNF und DNF für verschiedenen De Morgan Triples zeigend