Everything about Equisatisfiability
In mathematical 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 is true if either the two subformulae are both satisfiable or if they both are not: Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: EquisatisfiabilityA 5-minute orientation
- Go sideways: Independence-friendly logicA closely related topic
- Go sideways: Prenex normal formA closely related topic
📖 Definitions
Noun The condition of being equisatisfiable.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
- No matching papers found.
📚 Books worth reading
Open Library didn't respond; try again in a moment.
🔗 Related topics
- Independence-friendly logic Independence-friendly logic (IF logic; proposed by Jaakko Hintikka and Gabriel Sandu [fr] in 1989) is an extension of classical first-order logic (FOL)…
- Prenex normal form A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix,…
- Intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical…
- Conjunction/disjunction duality In propositional logic and Boolean algebra, there is a duality between conjunction and disjunction, also called the duality principle. It is the most widely…
- Modal μ-calculus In theoretical computer science, the modal μ-calculus (Lμ, Lμ, or propositional mu-calculus, sometimes just μ-calculus, although this can have a more general…
- Craig interpolation In mathematical logic, Craig's interpolation theorem is a result about the relationship between different logical theories. Roughly stated, the theorem…
- List of rules of inference This is a list of rules of inference, logical laws that relate to mathematical formulae. Rules of inference are syntactical transform rules which one can…
- Tseytin transformation The Tseytin transformation, alternatively written Tseitin transformation, takes as input an arbitrary combinatorial logic circuit and produces an equisatisfiabl…