Äquivalenz von Krom-Formeln ...

Question

Angenommen, ich habe zwei krom formulas $ \ psi_1, \PSI_2 $ .Krom-Formeln sind ausschlaggebende Formeln in CNF, die in jeder Klausel 2 Literatur haben.Jedes Literal kann negiert oder besintert werden.Mit anderen Worten, $ \ psi_1, \ psi_2 $ sind 2-cnf-Formeln.Zum Beispiel:

$ (x_1 \ vee \ neg x_2) \ land (\ neg x_2 \ vee x_3) \ land (x_3 \ vee x_4) $

Ich möchte entscheiden, ob $ \ psi_1, \ psi_2 $ logisch äquivalent ist, dh $ \ psi_1 \ lefTrightarrow\ psi_2 $ .Äquivalent, möchte ich testen, ob $ f= (\ psi_1 \ vee \ neg \ psi_2) \ wedge (\ neg \ psi_1 \ vee \ psi_2) $ trifftAlle Zuordnungen von $ x_1, \ dots, x_n $ .

ist dieses problem traktabel?

Answer 1

Ja, die Äquivalenz kann in der Polynomzeit (in der Tat in der quadratischen Zeit) geprüft werden.

Ich werde beschreiben, wie man testen soll, ob $ \ psi_1 \ lor \ neg \ psi_2 $ für alle Aufgaben trifft. Sie können dasselbe für $ \ NEG \ PSI_1 \ LOR \ PSI_2 $ tun, um zu testen, ob $ F $ ist eine Tautologie, dh, ob $ \ psi_1, \ psi_2 $ logisch äquivalent sind.

Ich werde dies tun, indem Sie prüfen, ob $ \ psi_1 \ lor \ neg \ psi_2 $ FALSE FALSCH für jede Aufgabe ist, oder mit anderen Worten, ob $ \ neg (\ psi_1 \ lor \ neg \ psi_2) $ ist erfüllt. Beachten Sie, dass

$$ \ neg (\ psi_1 \ lor \ neg \ psi_2)=neg \ psi_1 \ land \ psi_2, $$

So reicht es aus, die Erfüllung von $ \ neg \ psi_1 \ land \ psi_2 $ zu testen, wo $ \ psi_1, \ PSI_2 $ sind Krom (2-CNF) -Formeln.

Angenommen, dass $ \ PSI_1= C_1 \ Land \ CDs \ Land C_K $ wo $ c_i $ Ist der $ I $ th-Klausel in $ \ psi_1 $ . Dann

$$ \ neg \ psi_1= (\ neg c_1) \ lor \ cdoten \ lor (\ neg c_k). $$

deshalb

$$ \ beginnen {ALIGN *} \ neg \ psi_1 \ land \ psi_2 &= (\ neg c_1) \ lor \ cdoten \ lor (\ neg c_k)) \ land \ psi_2 \\ &= (\ neg c_1 \ land \ psi_2) \ lor \ cdoten \ lor (\ neg c_k \ land \ psi_2). \ END {ALIGN *} $$ $$

jetzt, $ \ neg \ psi_1 \ land \ psi_2 $ ist erfüllbar, wenn sie $ \ neg c_i \ land \ psi_2 $ ist für einige $ i $ erfüllt. Wir können also über $ I $ und Testerfrequenz von jeder $ \ neg c_i \ land \ psi_2 $ ; Wenn einer von ihnen erfüllt ist, ist $ \ neg \ psi_1 \ lor \ psi_2 $ erfüllt und $ F $ ist keine Tautologie und $ \ psi_1, \ psi_2 $ sind nicht logisch äquivalent.

So testen Sie die Erfüllung von $ \ neg c_i \ lande \ psi_2 $ ? Nun, $ c_i $ hat das Formular $ (\ tig_1 \ lor \ ell_2) $ wo $ \ ell_1, \ ell_2 $ sind zwei Literale, so dass $ \ neg c_i \ land \ psi_2 $ das Formular < Span-Klasse="Math-Container"> $ \ neg \ ell_1 \ landes \ neg \ ell_2 \ land \ psi_2 $ . Dies ist auch eine Krom-Formel (2-CNF), sodass Sie die Erfüllung mit dem Standard-Polynom-Zeitalgorithmus testen können. Sie führen eine lineare Anzahl solcher Tests aus, sodass die Gesamtlaufzeit auf Polynom ist. Tatsächlich ist es quadratisch, da die Erfüllung der Erfüllung in linearer Zeit erfolgen kann.

Answer 2

erinnern Sie sich an 2 SAT-Lösung, die stark angeschlossene Komponenten verwendet: Wir erstellen ein Diagramm mit Scheitelpunkten $ x_1, \ ldots, x_n, \ lnot x_1, \ ldots, \ lnot x_n $ < / span>, und wir ersetzen jede Klausel $ x_i \ lor x_j $ mit Kanten $ \ lnot x_i \ bis x_j $ < / span> und $ \ lnot x_j \ to x_i $ . Ein Beispiel aus hier :

Um die Formel zu erfüllen, ist es notwendig und ausreichend, um Scheitelpunkte zuzuordnen, damit keine Widersprüche in der Grafik vorhanden sind (keine Kante $ true \ to false $ ). Wir verwenden diese Grafiken für die Äquivalenzprüfung.

.
1. Wir erstellen diese Grafiken $ g_1 $ und $ g_2 $ für beide Formeln $ F_1 $ und $ f_2 $ .
2. Wenn es einen Zyklus gibt $ X_I \ Leadstoe \ LNOT X_I \ Leadsto X_I $ in einem Diagramm, dann hat seine Formel keine Lösungen. Wir prüfen, ob beide Formeln lösbar / unlösbar sind.
3. Wenn es einen Pfad des Formulars gibt $ X_I \ Leadsto \ LNOT X_I $ (ähnlich für den Fall $ \ LNOT) X_I \ Leadsto X_I $ ), wissen wir, dass er die Formel erfüllen muss, die wir wählen müssen $ x_i $ , um falsch zu sein (sonst haben wir einen Widerspruch). Wir erinnern uns an diese Wahl. Mit der Grafik können wir alle aus $ \ lnot x_i $ (sie müssen true) zuweisen. Prüfen Sie erneut, ob beide Formeln am Ende genau die gleichen Entscheidungen getroffen haben.
4. Entfernen Sie alle Kanten auf / von allen bekannten Scheitelpunkten aus den Grafiken.
5. jetzt, $ F_1 $ und $ F_2 $ sind gleichwertig $ \ IFF $ Die verbleibenden Grafiken sind in folgendem Sinne gleichwertig: für jeden $ v_1, v_2 $ path $ v_1 \ Leadsto v_2 $ existiert in $ g_1 $ ifef existiert in $ g_2 $ . Dies kann in den meisten $ O (| V | \ CDOT | E |) $ TIME eingecheckt (Führen Sie einfach die DFS aus jedem Scheitelpunkt aus und überprüfen Sie, ob es das gleiche besucht hat Scheitelpunkte für beide Grafiken). Vielleicht kann es schneller gemacht werden.

Beweis :

$ \ Lisplaw $ : offensichtlich, da nach transitiven Schließung von Diagrammen die gleichen Implikationen in beiden Formeln haben.

$ \ rightarrow $ : durch Widerspruch. Wlog wir gehen davon aus, dass es einen Pfad $ V_1 \ Leadsto v_2 $ in $ g_1 $ $ das nicht gibt Es gibt in $ g_2 $ . Es bedeutet, dass Zuweisung $ v_1:= true $ , $ v_2:= false $ ist in $ F_2 $ (da es keinen Pfad gibt $ V_1 \ Leadsto v_2 $ ) ist jedoch in $ f_1 $ .

nämlich erfüllt der folgende Auftrag $ f_2 $ :

.
• $ true $ für alle Scheitelpunkte aus $ v_1 $ .
• $ false $ von allen Scheitelpunkten, die $ v_2 $ erreichen können.
• Entfernen Sie alle bekannten Scheitelpunkte (erwähnt oben und ihrer Ergänzungen) aus der Grafik. Alle verbleibenden Scheitelpunkte erstellen angeschlossene Komponenten. Wir färben angeschlossene Komponenten in $ True $ und verbundene Komponenten, die ihren Ergänzungen entsprechen - in $ false $ ( Siehe Anmerkung unten).

Diese Aufgabe hat keinen Widerspruch, da keine Kante $ u \ bis V $ von Form $ true \ möglich ist zu false $ :

.
• Wenn $ U $ zu einer Komponente gehört, die vollfarbige $ True $ war, dann < Span-Klasse="Math-Container"> $ V $ muss auch wahr sein.
• Andernfalls bedeutet dies, dass $ U $ von $ v_1 $ erreichbar ist, und daher $ V $ ist auch von $ v_1 $ erreichbar und muss wahr sein. $ \ BlackSquare $

technische Note : Für jede Variable $ x_i $ Es gibt zwei Scheitelpunkte:

Ein Class="Math-Container"> $ v_i $ und $ \ lnot v_i $ - und man fragt sich, ob es zu einigen Problemen führen wirdZuordnungen.Die Antwort ist, dass nach Schritt 4), $ v_i $ und $ \ lnot v_i $ in zweiUnterschiedliche Komponenten (außerdem sind sie symmetrisch: $ u \ bis V $ in einer Komponente bedeutet $ \ lnot u \ to \lnot v $ in einem anderen).Daher, welche Entscheidung auch immer wir für $ U $ in einer Komponente erstellen, können wir die entgegengesetzte Entscheidung für $ \ lnot u $ vornehmen in einem anderen.