¿Equivalencia de las fórmulas Krom, transabierto?

Question

Supongamos que tengo dos krom fórmulas $ \ psi_1, \psi_2 $ .Las fórmulas KROM son fórmulas proposicionales en CNF que tienen 2 literales en cada cláusula.Cada literal puede ser negado o sin negarse.En otras palabras, $ \ psi_1, \ psi_2 $ son fórmulas de 2-CNF.Por ejemplo:

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

Quiero decidir si $ \ psi_1, \ psi_2 $ son lógicamente equivalentes, es decir, $ \ psi_1 \ leftrightarrow\ psi_2 $ .Equivalente, quiero probar si $ f= (\ psi_1 \ vee \ neg \ psi_2) \ wedge (\ neg \ psi_1 \ vee \ psi_2) $ es cierto paraTodas las asignaciones de $ x_1, \ dots, x_n $ .

¿Este problema es tratable?

Answer 1

Sí, la equivalencia se puede verificar en el tiempo polinomial (de hecho, en el tiempo cuadrático).

Describiré cómo probar si $ \ psi_1 \ lor \ neg \ psi_2 $ es cierto para todas las tareas. Puede hacer lo mismo para $ \ net \ psi_1 \ lor \ psi_2 $ y use esto para probar si $ f $ es una tautología, es decir, si $ \ psi_1, \ psi_2 $ son lógicamente equivalentes.

Voy a hacer esto comprobando si $ \ psi_1 \ lor \ neg \ psi_2 $ es falso para cualquier asignación, o en otras palabras, ya sea $ \ NEG (\ PSI_1 \ lor \ NET \ PSI_2) $ es satisfactorio. Observe que

$$ \ NEG (\ PSI_1 \ LOR \ NEG \ PSI_2)=NET \ PSI_1 \ Land \ PSI_2, $$

Por lo tanto, se basa en probar la satisfacción de $ \ net \ psi_1 \ land \ psi_2 $ donde $ \ psi_1, \ PSI_2 $ son fórmulas KROM (2-CNF).

Supongamos que $ \ psi_1= c_1 \ land \ cdots \ land c_k $ donde $ c_i $ es el $ i $ th cláusula en $ \ psi_1 $ . Entonces

$$ \ NEG \ PSI_1= (\ NET C_1) \ LOR \ CDSTS \ LOR (\ NET C_K). $$

por lo tanto

$$ \ comienzan {align *} \ NEG \ PSI_1 \ Land \ PSI_2 &= ((\ NEG C_1) \ LOR \ CDSS \ LOR (\ NEG C_K)) \ Land \ PSI_2 \\ &= (\ neg c_1 \ land \ psi_2) \ lor \ cdots \ lor (\ neg c_k \ land \ psi_2). \ End {align *} $$

ahora, $ \ neg \ psi_1 \ land \ psi_2 $ es satisfecho IFF $ \ net c_i \ land \ psi_2 $ es satisfactorio para algunos $ i $ . Entonces, podemos iterar a través de $ i $ y pruebe la satisfacción de cada $ \ net c_i \ land \ psi_2 $ ; Si alguno de ellos es satisfecho, entonces $ \ net \ psi_1 \ lor \ psi_2 $ es satisfactorio y $ f $ no es una tautología y $ \ psi_1, \ psi_2 $ no son lógicamente equivalentes.

Cómo probar la satisfacción de $ \ net c_i \ land \ psi_2 $ ? Bueno, $ c_i $ tiene el formulario $ (\ ell_1 \ lor \ ell_2) $ donde $ \ ELL_1, \ ELL_2 $ son dos literales, por lo que $ \ neg c_i \ land \ psi_2 $ tiene el formulario < span class="Math-contenedor"> $ \ NET \ ELL_1 \ Land \ NET \ ELL_2 \ Land \ PSI_2 $ . Esta es también una fórmula KROM (2-CNF), por lo que puede probar su satisfacción utilizando el algoritmo de tiempo polinomial estándar. Usted hace un número lineal de tales pruebas, por lo que el tiempo total de funcionamiento es polinomial. De hecho, es cuadrático, ya que la satisfacción de las pruebas se puede realizar en tiempo lineal.

Answer 2

RECUPTRACIÓN SOLUCIÓN DE 2 SAT que utiliza componentes fuertemente conectados: construimos un gráfico con vértices $ x_1, \ ldots, x_n, \ lnot x_1, \ ldots, \ lnot x_n $ < / span>, y reemplazamos cada cláusula $ x_i \ lor x_j $ con bordes $ \ lnot x_i \ a x_j $ < / span> y $ \ lnot x_j \ to x_i $ . Un ejemplo de aquí :

Para satisfacer la fórmula, es necesario y suficiente para asignar vértices para que no haya contradicciones en el gráfico (sin editar $ true \ a falso $ ). Usaremos estos gráficos para la verificación de equivalencia.

1. Construimos estos gráficos $ g_1 $ y $ g_2 $ para ambas fórmulas $ F_1 $ y $ f_2 $ .
2. Si hay un ciclo $ x_i \ lidesto \ lnot x_i \ lidestso x_i $ en un gráfico, entonces su fórmula no tiene soluciones. Verificamos que ambas fórmulas son solucionables / no solucibles.
3. Si existe un camino de la forma $ x_i \ lidestso \ lnot x_i $ (de manera similar para el caso $ \ lnot x_i \ lidesto x_i $ ), sabemos que para satisfacer la fórmula, debemos seleccionar $ x_i $ para ser falso (de lo contrario tenemos una contradicción). Recordamos esta elección. Usando el gráfico, podemos asignar valores a todos los vértices accesibles desde $ \ lnot x_i $ (deben ser verdaderos). Una vez más, verifique que ambas fórmulas hicieron exactamente las mismas decisiones al final.
4. Retire todos los bordes a / desde todos los vértices conocidos de los gráficos.
5. ahora, $ f_1 $ y $ f_2 $ son equivalentes $ \ iff $ Los gráficos restantes son equivalentes en el siguiente sentido: para cualquier $ v_1, v_2 $ ruta $ v_1 \ lidesto v_2 $ existe en $ g_1 $ IFF, existe en $ g_2 $ . Esto se puede registrar en la mayoría de $ o (| v | \ cdot | e |) $ tiempo (simplemente ejecute DFS de cada vértice y verifique que haya visitado el mismo vértices para ambos gráficos). Tal vez se pueda hacer más rápido.

prueba :

$ \ itcharrow $ : evidente, ya que después del cierre transitivo de los gráficos tendremos las mismas implicaciones en ambas fórmulas.

$ \ rudowarrow $ : por contradicción. Wlog asumimos que existe un camino $ v_1 \ lidesto v_2 $ en $ g_1 $ que no existen en $ g_2 $ . Significa que la asignación $ v_1:= true $ , $ v_2:= falso $ es factible en $ F_2 $ (ya que no hay ruta $ v_1 \ lidesto v_2 $ ) pero es inviable en $ F_1 $ .

a saber, la siguiente asignación satisface $ f_2 $ :

• $ true $ para todos los vértices accesibles desde $ v_1 $ .
• $ falso $ de todos los vértices que pueden llegar a $ v_2 $ .
• eliminar todos los vértices conocidos (mencionados anteriormente y sus complementos) de la gráfica. Todos los vértices restantes crean componentes conectados. Coloreamos los componentes conectados en $ true $ y componentes conectados correspondientes a sus complementos, en $ falso $ ( Ver nota a continuación).

Esta tarea no tiene ninguna contradicción, ya que no puede haber borde $ u \ a v $ de formulario $ true \ a FALSO $ :

• si $ u $ pertenece a un componente que fue completamente coloreado $ true $ , entonces tal < Span Class="Math-Container"> $ v $ también debe ser verdad.
• de lo contrario, significa que $ u $ se puede llegar desde $ v_1 $ y, por lo tanto, $ v $ también se puede llegar desde $ v_1 $ y debe ser verdadero. $ \ blacksquare $

Nota técnica : para cada variable $ x_i $ Hay dos vértices:

una clase="Matemáticas-contenedor"> $ V_I $ y $ \ lnot v_i $ - y uno puede preguntarse si conduce a algunos problemas con algunos problemas conasignaciones.La respuesta es que después del paso 4), $ v_i $ y $ \ lnot v_i $ estará en dos(además, son componentes (además, son simétricos: $ u \ a v $ en un componente significa $ \ lnot u \ alnot v $ en otro).Por lo tanto, sea la decisión que hagamos para $ u $ en un componente, podemos tomar la decisión opuesta para $ \ lnot u $ en otro.