Saltar para o conteúdo

Equissatisfatibilidade

Origem: Wikipédia, a enciclopédia livre.

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.

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.