Equisatisfiability

In logic, two formulae are equisatisfiable if the first formula is satisfiable whenever the second is and vice versa; in other words, either both formulae are satisfiable or both are not.[1] Equisatisfiable formulae may disagree, however, for a particular choice of variables. As a result, equisatisfiability is different from logical equivalence, as two equivalent formulae always have the same models.

Equisatisfiability is generally used in the context of translating formulae, so that one can define a translation to be correct if the original and resulting formulae are equisatisfiable. Examples of translations involving this concept are Skolemization and some translations into conjunctive normal form.

Examples

A translation from propositional logic into propositional logic in which every binary disjunction ${\displaystyle a\vee b}$ is replaced by ${\displaystyle ((a\vee n)\wedge (\neg n\vee b))}$, where ${\displaystyle n}$ is a new variable (one for each replaced disjunction) is a transformation in which satisfiability is preserved: the original and resulting formulae are equisatisfiable. Note that these two formulae are not equivalent: the first formula has the model in which ${\displaystyle b}$ is true while ${\displaystyle a}$ and ${\displaystyle n}$ are false (the model's truth value for ${\displaystyle n}$ being irrelevant to the truth value of the formula), but this is not a model of the second formula, in which ${\displaystyle n}$ has to be true in this case.

References

1. M. Krötzsch (11 October 2010). Description Logic Rules. IOS Press. ISBN 978-1-61499-342-1.