Lesson plan

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 neither is. The truth values of two equisatisfiable formulae may nevertheless disagree for a particular assignment of variables. As a result, equisatisfiability differs from logical equivalence, since two equivalent formulae always have the same models, whereas equisatisfiable ones need only share satisfiability status. More formally, the equisatisfiability meta formula f is true if either the two subformulae are both satisfiable or if they both are not: : f \;\equiv\; (\operatorname{Sat}(\phi) \land \operatorname{Sat}(\psi)) \lor (\lnot \operatorname{Sat}(\phi) \land \lnot \operatorname{Sat}(\psi)) \;\equiv\; \operatorname{Sat}(\phi) \leftrightarrow \operatorname{Sat}(\psi) 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.

Back to article

Article summary

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 neither is. The truth values of two equisatisfiable formulae may nevertheless disagree for a particular assignment of variables. As a result, equisatisfiability differs from logical equivalence, since two equivalent formulae always have the same models, whereas equisatisfiable ones need only share satisfiability status. More formally, the equisatisfiability meta formula f is true if either the two subformulae are both satisfiable or if they both are not: : f \;\equiv\; (\operatorname{Sat}(\phi) \land \operatorname{Sat}(\psi)) \lor (\lnot \operatorname{Sat}(\phi) \land \lnot \operatorname{Sat}(\psi)) \;\equiv\; \operatorname{Sat}(\phi) \leftrightarrow \operatorname{Sat}(\psi) 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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.