É possível traduzir uma fórmula booleana B em uma conjunção equivalente de cláusulas de Horn? O artigo da Wikipedia sobre HornSAT parece sugerir que sim, mas não pude buscar nenhuma referência.
Note que eu não quero dizer "em tempo polinomial", mas sim "em tudo".
reference-request
lo.logic
sat
Evgenij Thorstensen
fonte
fonte
Respostas:
Não. As cláusulas de conjunções de Horn admitem menos modelos de Herbrand, o que não ocorre com disjunções de literais positivos. Cf. Lloyd, 1987, Fundamentos da Programação Lógica .
Os modelos menos Herbrand têm a propriedade de que estão nas interseções de todos os satisfadores. Os modelos de Herbrand para são { { a } , { b } , { a , b } } , que não contêm sua interseção, portanto, como diz arnab, ( a ∨ b ) é um exemplo de fórmula que não pode ser expresso como uma conjunção de cláusulas de Horn.(a∨b) {{a},{b},{a,b}} (a∨b)
Resposta incorreta substituída
fonte
A equivalência pode ser alcançada da seguinte maneira (redução de 2SAT para HornSAT). Portanto também pode ser reduzido a uma fórmula de Horn dessa maneira. Agradecemos a Joshua Gorchow por apontar essa redução.(p∨q)
Entrada: Uma fórmula 2-SAT , com cláusulas C 1 , ..., C k nas variáveis x 1 , ..., x n .ϕ C1 Ck x1 xn
Construa uma fórmula chifre da seguinte maneira:Q
Haverá 4 ( n× n escolha ) + 2 n + 1 novas variáveis, uma para cada possível
cláusula 2-cnf possível nas variáveis x com no máximo 2 literais ( não apenas as cláusulas C i em ϕ ) - isso é incluindo cláusulas unitários e a cláusula vazio .. a nova variável que corresponde a uma cláusula D será denotado por Z D .2 +2n+1 x Ci ϕ D zD
O 4 ( n, escolha 2 ) vem do fato de que cada par de ( x i , x j× n 2
gera quatro cláusulas 2-cnf. O 2 n vem do fato de que cada x i pode criar 2 cláusulas de unidade. E finalmente o "one" vem da cláusula vazia. Portanto, o número total de cláusulas 2-cnf possíveis é =
4 × ( n escolha 2 ) + 2 n + 1 .(xi, xj) 2n xi = × n 2 +2n+1
Se uma cláusula 2-cnf segue de duas outras cláusulas 2-cnf D e E em uma única etapa de resolução, adicionamos a cláusula Horn ( z D ∧ z E →F D E
a Q ... Novamente, fazemos isso para todas as possíveis cláusulas 2-cnf - todas as 4 × ( n
escolha 2 ) + 2 n + 1 delas - não apenasa C i .(zD∧zE→zF) Q × n 2 +2n+1 Ci
Em seguida, adicionamos as cláusulas unitárias aQ, para cada cláusulaCi aparecendo na entradaφ... Por fim, adicionar o cláusula unidade(¬z e m p t y )paraQ.zCi Q Ci ϕ (¬zempty) Q
A fórmula Horn está agora completa. Observe que as variáveis usadas em Q são completamente diferentes das usadas em ϕ .Q Q ϕ
fonte
Eu não acho que é possível. Não há nenhuma maneira, por exemplo, para escrever como um conjunto de cláusulas do corno desde φ somente os criminosos uma única atribuição verdade, a saber, 0011. Qualquer cláusula chifre com menos de 4 literais proibiriam mais de 1 atribuição de verdade, e cláusulas de corneta com 4 literais só podem proibir atribuições de verdade com no máximo um 0.ϕ=(X1∨X2∨¬X3∨¬X4) ϕ
Edit: oops não percebeu isso já foi respondido
fonte