Equissatisfatibilidade

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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.