Use 2SAT para mostrar que los gráficos de implicación deben tener un ciclo si no es satisfactorio

Question

Uso de gráficos de 2SAT e implicaciones, ¿cómo podría probar las siguientes propiedades de los gráficos de implicación:

Supongamos que hay un camino dirigido entre literales L1 y L2 en G_φ. Luego también hay un camino dirigido entre sus complementos. Luego, hay τ, una asignación de verdad que satisface φ, donde τ (L1) es verdadero, entonces τ (L2) también debe ser cierto.

Usando esto, muestra que φ es insatisfiable <=> Hay algún ciclo dirigido en G_φ que contiene una variable X y su complemento.

donde g_φ es el gráfico de implicación dirigida de 2sat que contiene fórmula φ con n variables. Por lo tanto, los vértices 2N con uno para cada literal posibles en φ, y los bordes (NO L1, L2) y (NO L2, L1) para cada cláusula (L1 ∨ L2) en φ.

Mi primera intuición fue una prueba por contradicción, sin embargo, no pude construir una suposición general general. Luego intenté demostrar que si la asignación de la verdad significa que L1 y L2 son verdaderos, entonces construyendo un ciclo que conecta todas las variables, la asignación solo es válida cuando esos bordes existen. Sin embargo, esto no parece lo suficientemente riguroso, ya que no estoy entendiendo adecuadamente por qué el ciclo requiere que exista el complemento de X.

Actualmente construyo G agregando un vértice para cada variable x y su complemento también. Luego, para cada cláusula (A V b) agrego un borde entre NO A y B y NO B y A.

Sin embargo, no veo cómo esto formaría específicamente un ciclo.

Trabajo del libro de texto Sipser.

Answer 1

Aquí hay un boceto de prueba. Mostraremos que la fórmula dada es insatisfiable, IFF existe un ciclo que contiene tanto $ x $ y $ \ lnot x $ < / SPAN>, para una variable $ x $ .

Supongamos primero que existe un ciclo que contiene tanto $ x $ y $ \ lnot x $ . La existencia de un camino $ x \ a ^ * y $ en el gráfico de implicación significa que en una asignación satisfactoria, si $ x $ sostiene entonces, también lo hace $ y $ (puede probarlo por inducción en la longitud de la ruta). Dado que hay un ciclo que contiene tanto $ x $ y $ \ lnot x $ , hay caminos $ x \ a ^ * \ lnot x $ y $ \ lnot x \ a ^ * x $ . En cualquier asignación satisfactoria, ya sea $ x $ o $ \ lnot x $ sostiene, y ambos casos conducen a contradicción.

Supongamos que no hay ciclos que contienen tanto $ x $ y $ \ lnot x $ . Construiremos una asignación satisfactoria de la siguiente manera. Elija una variable $ x $ . Si hay un camino $ x \ a ^ * \ lnot x $ , asignar $ x= f $ , y para cada literal $ \ ell $ de modo que $ \ lnot x \ a ^ * \ ell $ , asigne el valor a la variable subyacente que hace $ \ ell $ verdadero. No puede asignar la misma variable dos valores de verdad diferentes, ya que si $ \ lnot x \ a ^ * y $ y $ \ lnot x \ a ^ * \ lnot y $ también $ y \ a ^ * x $ y también $ \ lnot x \ a ^ * x $ , completando un ciclo que involucra $ x $ y $ \ lnot x $ .

Si hay un camino $ \ lnot x \ a ^ * x $ , asignar $ x= t $ < / SPAN>, y continuar de forma análoga.

Si no existe ninguna de estas rutas, asigne $ x $ arbitrariamente, y continúe como antes. Esto no puede llevar a una contradicción, por la siguiente razón. Supongamos que asignamos $ x= f $ , y que hay rutas $ x \ a ^ * y $ y $ x \ a ^ * \ lnot y $ . Luego también hay un camino $ y \ a ^ * \ lnot x $ y por lo tanto una ruta $ x \ a ^ * \ lnot x $ , contradiciendo el supuesto de que ninguno de los dos caminos existe.

Si después de este proceso, hay alguna variable no asignada, elija uno de ellos, y repita hasta que la asignación cubra todas las variables.