Abrir menu principal

Em Lógica, duas fórmulas são equissatisfatíveis se a primeira fórmula é satisfatível toda vez que a segunda fórmula também for e vice versa. Em outras palavras: ou as duas fórmulas são satisfatíveis ou nenhuma é. Duas fórmulas equissatisfatíveis podem ter diferentes modelos, desde que nenhuma delas ou ambos tenham algum modelo. Como resultado, temos que a equissatisfatibilidade é diferente da equivalência lógica, pois duas fórmulas logicamente equivalentes sempre possuem os mesmos modelos.

Geralmente, o conceito de equissatisfatibilidade é utilizado na conversão de fórmulas, ou seja, pode se afirmar que uma conversão está correta se a fórmula original e a resultante são equissatisfatíveis. Exemplos de conversões envolvendo esse conceito são a Skolemização e algumas transformações para a forma normal conjuntiva.

ExemplosEditar

Uma conversão da lógica proposicional para a própria lógica proposicional em que toda disjunção binária   é substituída por  , onde   é uma nova variável (uma para cada disjunção substituída), é uma transformação em que a satisfatibilidade é preservada, ou seja, a fórmula original e a resultante são equissatisfatíveis. Note que essas duas fórmulas não são equivalentes, pois existe um modelo que torna a primeira fórmula verdadeira e a segunda falsa: quando   é verdadeiro enquanto   e   são falsos. Entretanto, alterando-se apenas a valoração de   para verdadeiro no modelo do caso anterior, temos que ambas as fórmulas são satisfatíveis, e isso demonstra a equissatisfatibilidade entre as duas.