Definition von 2-CNF-Formel (a.k.a krom)

Question

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?

Answer 1

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 $$ P \ Land (\ lnot p \ lor q) \ land \ lnot q.$$ Das Implikationsgraph enthält die folgenden Kanten: $$ \ lnot p \ to p \\ p \ bis q, \ lnot \ bis \ lnot p \\ q \ bis \ lnot q $$ Diese können in einem Zyklus angeordnet werden: $$ \ lnot p \ bis p \ bis q \ bis \ lnot \ to \ lnot p $$ Dieser Zyklus enthält sowohl $ P $ und $ \ lnot p $ (und auch beide $ q $ und $ \ lnot q $ ), zeigt an, dass die Formel nichtatisabilisiert ist.