Verwenden Sie 2sat, um anzuzeigen, dass ein Implikationsdiagramme einen Zyklus haben müssen, wenn er nicht erfüllt ist

Question

Mit 2sat- und Implikationsdiagrammen, wie könnte ich die folgenden Eigenschaften von Implikationsdiagrammen nachweisen:

Angenommen, es gibt einen gerichteten Weg zwischen den L1 und L2 in G_φ. Dann gibt es auch einen gerichteten Weg zwischen ihren Ergänzungen. Dann gibt es τ, ein Wahrheitsauftrag, bei dem φ, wobei τ (l1) wahr ist, dann muss τ (l2) auch wahr sein.

Verwenden Sie diese, zeigen Sie, dass φ nichtatisabilisiert ist <=> Es gibt einen gerichteten Zyklus in G_φ, der eine Variable x und seine Ergänzung enthält.

wobei g_φ das gerichtete Implikationsgraph von 2sat enthält, der die Formel φ mit N Variablen enthält. Daher 2n-Scheitelpunkte mit einem für jedes mögliche Literal in φ und Kanten (nicht L1, L2) und (nicht L2, L1) für jede Klausel (L1 ∨ L2) in φ.

Meine erste Intuition war ein Beweis nach Widerspruch, jedoch konnte ich nicht eine allgemeine Annahme konstruieren. Ich habe dann versucht, zu zeigen, dass, wenn die Wahrheitsprüfung, dass L1 und L2 erfüllt sind, und dann durch den Aufbau eines Zyklus, der alle Variablen verbindet, die Zuordnung nur dann gültig, wenn diese Kanten vorhanden sind. Dies scheint jedoch nicht streng genug zu sein, da ich nicht richtig verstanden, warum der Zyklus die Ergänzung von X erfordert.

Derzeit baue ich g, indem ich einen Scheitelpunkt für jede Variable x und es ist auch ergänzend ergänzt. Dann füge ich für jede Klausel (a v b) eine Kante zwischen nicht A und B und NOB B und a hinzu.

Ich kann jedoch nicht sehen, wie dies speziell einen Zyklus bilden würde.

Arbeiten des SIPSER-Lehrbuchs.

Answer 1

Hier ist eine Proofskizze. Wir zeigen, dass die angegebene Formel unbefriedigbar ist, wenn es einen Zyklus gibt, der sowohl $ x $ und $ \ lnot x $ , für ein paar variable $ x $ .

Angenommen, zunächst, dass ein Zyklus vorhanden ist, der sowohl $ X $ und $ \ lnot x $ enthält. Das Vorhandensein eines Pfads $ x \ bis ^ * y $ in der Implikationsgrafik bedeutet, dass in einer erfüllenden Zuordnung, wenn $ x $ hält dann dann $ y $ (Sie können es durch Induktion über die Länge des Pfads beweisen). Da es einen Zyklus gibt, der sowohl $ X $ und $ \ lnot x $ enthält, gibt es Pfade $ x \ to ^ * \ lnot x $ und $ \ lnot x \ to ^ * x $ . In jeder erfüllenden Zuordnung, entweder $ x $ oder $ \ lnot x $ HOLDS, und beide Fälle führen dazu Widerspruch.

Nehmen Sie an, als nächstes, dass es keine Zyklen gibt, die sowohl $ X $ und $ \ lnot x $ enthalten. Wir erstellen eine zufriedenstellende Aufgabe wie folgt. Wählen Sie einige Variable $ x $ . Wenn es einen Pfad gibt $ x \ to ^ * \ lnot x $ , wenden Sie sich an $ x= f $ , und für jeden wörtlichen $ \ ell $ so, dass $ \ lnot x \ to ^ * \ \ \ \ \ lnot x \ to ^ * \ ell $ , weisen Sie den Wert der zugrunde liegenden Variablen zu, wodurch $ \ ell $ true erstellt wird. Sie können nicht dieselbe Variable zwei verschiedene Wahrheitswerte zuweisen, da $ \ lnot x \ to ^ * y $ und $ \ lnot x \ to ^ * \ lnot y $ dann auch $ y \ to ^ * x $ und so auch $ \ lnot x \ to ^ * x $ , Abschluss eines Zyklus mit $ x $ und $ \ lnot x $ .

Wenn es einen Pfad gibt $ \ lnot x \ to ^ * x $ , wenden Sie sich auf $ x= t $ < / span> und weiter analog.

Wenn keine dieser Pfade vorhanden ist, weisen Sie $ x $ willkürlich zu, und fahren Sie wie zuvor fort. Dies kann aus folgendem Grund nicht zu einem Widerspruch führen. Angenommen, wir weisen $ x= F $ , und dass es Pfade gibt $ x \ bis ^ * y $ und $ x \ bis ^ * \ lnot y $ . Dann gibt es auch einen Pfad $ y \ to ^ * \ lnot x $ und so ein Pfad $ x \ to ^ * \ lnot x $ und widersprüchst der Annahme, dass keiner der beiden Pfade vorhanden ist.

Wenn nach diesem Prozess eine andere variable Variable vorhanden ist, wählen Sie einen von ihnen aus, und wiederholen Sie, bis die Zuordnung alle Variablen deckt.