¿Es posible traducir una fórmula booleana B en una conjunción equivalente de cláusulas Horn? El artículo de Wikipedia sobre HornSAT parece implicar que lo es, pero no he podido perseguir ninguna referencia.
Tenga en cuenta que no me refiero a "en tiempo polinómico", sino más bien "en absoluto".
reference-request
lo.logic
sat
Evgenij Thorstensen
fuente
fuente
Respuestas:
No. Las cláusulas de las conjunciones de Horn admiten menos modelos de Herbrand, que las disyunciones de los literales positivos no. Cf. Lloyd, 1987, Fundamentos de la programación lógica .
Los modelos de Herbrand menos tienen la propiedad de estar en las intersecciones de todos los satisfactores. Los modelos de Herbrand para son { { a } , { b } , { a , b } } , que no contiene su intersección, por lo que, como dice arnab, ( a ∨ b ) es un ejemplo de fórmula que no se puede expresar como una conjunción de las cláusulas de Horn.(a∨b) {{a},{b},{a,b}} (a∨b)
Respuesta incorrecta sobrescrita
fuente
La capacidad de satisfacción se puede lograr de la siguiente manera (reducción de 2SAT a HornSAT). Entonces también se puede reducir a una fórmula Horn de esta manera. Gracias a Joshua Gorchow por señalar esta reducción.(p∨q)
Entrada: una fórmula 2-SAT , con cláusulas C 1 , ..., C k en las variables x 1 , ..., x n .ϕ C1 Ck x1 xn
Construya una fórmula de bocina siguiente manera:Q
Habrá 4 ( n elegir 2 ) + 2 n + 1 nuevas variables, una para cada posible× n 2 +2n+1
cláusula 2-cnf posible en las variables con como máximo 2 literales ( no solo las cláusulas C i en ϕ ) - esto es incluyendo cláusulas de la unidad y la cláusula de vacío .. la nueva variable correspondiente a una cláusula de D se denota por z D .x Ci ϕ D zD
El 4 ( n elige 2 ) proviene del hecho de que cada par de ( x i , x j ) da lugar a cuatro cláusulas 2-cnf. El 2 n proviene del hecho de que cada x i× n 2 (xi, xj) 2n xi puede crear cláusulas de 2 unidades. Y finalmente el "uno" proviene de la cláusula vacía. Entonces, el número total de posibles cláusulas 2-cnf es
4 × ( n elige 2 ) + 2 n + 1 .= × n 2 +2n+1
Si una cláusula 2-cnf sigue de otras dos cláusulas 2-cnf D y E en un solo paso de resolución, entonces agregamos la cláusula Horn ( z D ∧ z E → z F ) a Q ... Nuevamente, hacemos esto para todos los posibles cláusulas 2-CNF - los 4 × ( n elegir 2 ) + 2 n + 1 de ellos - no sólo la C i .F D E (zD∧zE→zF) Q × n 2 +2n+1 Ci
Luego agregamos las cláusulas unitarias a Q , para cada cláusula C izCi Q Ci
aparece en la entrada de ... Por último, se añade la cláusula unidad ( ¬ z e m p t y ) a Q .ϕ (¬zempty) Q
La fórmula Cuerno ahora está completa. Observe que las variables utilizadas en Q son completamente diferentes de las utilizadas en ϕ .Q Q ϕ
fuente
No creo que sea posible. No hay forma, por ejemplo, de escribir como una conjunción de cláusulas de claxon ya que ϕ solo prohíbe una sola asignación de verdad, concretamente 0011. Cualquier cláusula de claxon con menos de 4 literales prohibirían más de 1 asignación de verdad, y las cláusulas de claxon con 4 literales solo pueden prohibir las asignaciones de verdad con un máximo de 0.ϕ=(X1∨X2∨¬X3∨¬X4) ϕ
Editar: ¡Uy! No notaron que esto ya fue respondido
fuente