Logic

2025年11月7日

An interpretation M is a mapping from propositional variables to truth values {true, false}. Only with an interpretation can people talk about the truth of a propositional logic formula which consists of propositional variable.

A propositional logic formula has three status: valid, satisfiable, and unsatisfiable. A formula is satisfiable if it has an interpretation that makes it true. In this case, we say the interpretation is a model for the formula. A formula is unsatisfiable if it does not have any model. A formula is valid if it is true in any interpretation.

Formula F and G are equisatisfiable if and only if F and G both are unsatisfiable or both satisfiable. Equisatisfiability does not involve the internal structure of the formulas, or the models/interpretations that make the formula true.

In this sense, it’s quite clear that equisatisfiability is not logic equivalency, which looks into the internal structure and compares truth values.