Equissatisfatibilidade

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.

Exemplos

Uma conversão da lógica proposicional para a própria lógica proposicional em que toda disjunção binária $a\vee b$ é substituída por $((a\vee n)\wedge (\neg n\vee b))$, onde $n$ é 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 $b$ é verdadeiro enquanto $a$ e $n$ são falsos. Entretanto, alterando-se apenas a valoração de $n$ 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.