Equisatisfiability

In mathematical logic (a subtopic within the field of formal 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 none of them is.{{cite book|author=Markus Krötzsch|title=Description Logic Rules|url=https://books.google.com/books?id=Z8h7AgAAQBAJ&dq=equisatisfiable+OR+equisatisfiability&pg=PA21|date=11 October 2010|publisher=IOS Press|isbn=978-1-61499-342-1}} The truth values of two 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. Whereas within equisatisfiable formulae, {{clarify span|only the primitive proposition the formula imposes is valued|What is this supposed to mean?|date=May 2025}}.

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 that preserve equisatisfiability are Skolemization and some translations into conjunctive normal form such as the Tseytin transformation.

Examples

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

References

Category:Metalogic

Category:Model theory

Category:Concepts in logic