Definition von 2-CNF-Formel (a.k.a krom)
-
29-09-2020 - |
Frage
In den Notizen meines Dozenten wird folgende Definition für eine 2-CNF-WFF gegeben:
Eine 2-CNF-Formel oder Krom-Formel ist eine CNF-Formel-F-CNF-Formel F, so dass jede Klausel höchstens zwei Literatur aufweist.
Es gibt jedoch keine Erwähnung in den Anmerkungen, wie man Klauseln darstellen kann, die ein einzelnes wörtliches Liter-L in der entsprechenden Implikationsgrafik des WFFs enthalten (obwohl ich angenommen habe, man könnte eine Kante von jedem anderen Literal nach Literal hinzufügen.Blick auf Kroms Originalpapier, die Definition, die er zu verwenden scheint, ist:
Eine 2-CNF-Formel oder Krom-Formel ist eine CNF-Formel F, so dass jede Klausel genau zwei Literale aufweist.
Diese Definition scheint viel sinnvoller zu machen.Welche Definition ist richtig?Vermisse ich etwas?
Lösung
Eine Einheit-Klausel des Formulars $ P $ ist derselbe wie die Klausel $ p \ lor p $ , und so entspricht der Pfeil $ \ lnot p \ bis p $ .
Betrachten Sie als Beispiel die unbefriedigbare CNF