Equisatisfiability¶

The logical relation in which two formulas share the same existence-of-a-model status—both satisfiable or both unsatisfiable—without requiring the same models, enabling compact satisfiability-preserving transformations such as Tseitin encoding and Skolemization.

Version: v2 · 2026-09-19 · History
Domain-specific #: 1781
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Mathematical Logic, Satisfiability Preserving Transformations → Mathematics
Aliases: Equisatisfiable formulas, Satisfiability equivalence

Core Idea¶

Two logical formulas are equisatisfiable when either both have at least one model or neither has any model. Writing Sat(φ) for “there exists an interpretation or assignment satisfying φ,” the relation is φ ~sat ψ exactly when Sat(φ) <-> Sat(ψ). It preserves the answer to an existence question while allowing almost everything else about the formulas to change: syntax, vocabulary, number of variables, truth value under a particular assignment, and even the sets of models can differ.

How would you explain it like I'm…

Both-or-Neither Puzzles

Think of two puzzles. They can look totally different and have different answers. We call them a matching pair if either both puzzles can be solved or neither one can. So if you only want to know 'is there any answer?', you can work on whichever puzzle is easier.

Same 'Can It Be Solved?' Answer

In logic, a formula is a statement with blanks that can be filled in with true or false. A formula is 'satisfiable' if there is at least one way to fill in the blanks that makes it true. Two formulas are equisatisfiable if they are either both satisfiable or both not. They can use different blanks and have different solutions; all that has to match is the yes-or-no answer to 'is there a solution?'. Computers use this to swap a hard formula for an easier one that gives the same yes-or-no answer.

Matching Solvability

Two formulas are equisatisfiable when either both have at least one satisfying assignment (a model) or neither does. This is much weaker than logical equivalence, which requires the formulas to be true under exactly the same assignments. Equisatisfiable formulas can have different variables, different sizes, and different sets of solutions. That freedom is useful: the Tseitin encoding adds new helper variables to turn any formula into conjunctive normal form with only linear growth, instead of the exponential blow-up an equivalent conversion might cause. The result isn't equivalent to the original, but it's satisfiable exactly when the original is, which is all a SAT solver needs.

Equisatisfiability is the relation φ ~sat ψ iff Sat(φ) ↔ Sat(ψ), where Sat(φ) means some interpretation or assignment satisfies φ under a declared semantics. It preserves only Boolean model-existence status; syntax, vocabulary, number of variables, truth value under a given assignment, and even the model sets may differ. Structurally, it is the kernel of the map Sat from formulas to {satisfiable, unsatisfiable}, hence an equivalence relation—but a specialized one with its own semantics, proof obligations, and uses. Its payoff is computational: it licenses replacing a formula with another for a satisfiability decision. Tseitin encoding is the standard example, introducing fresh variables to produce a linear-size CNF formula that is satisfiable iff the original is, whereas an equivalent CNF could blow up exponentially. Proofs typically show that models extend from the original to the encoding and restrict back. It must be kept distinct from logical equivalence (truth in every shared interpretation) and from mere one-directional satisfiability preservation.

Scope of Application¶

Equisatisfiability is used in SAT preprocessing, conversion to conjunctive normal form, reductions between decision problems, automated theorem proving, SMT encodings, bounded model checking, knowledge representation, and first-order transformations. It licenses replacement wherever the downstream question is only whether a model exists.

In Tseitin encoding, a fresh propositional variable names each relevant subformula and clauses constrain the name to agree with that subformula. Asserting the variable for the root produces a CNF formula of size linear in the syntax graph. Any satisfying assignment of the original extends by assigning each fresh variable its subformula’s value; any satisfying assignment of the encoding restricts to an assignment satisfying the original.

Clarity¶

Because satisfiability is a single Boolean property, the relation is extremely coarse. Every satisfiable formula is equisatisfiable with True; every unsatisfiable formula is equisatisfiable with False, under a shared logical setting. This does not make arbitrary replacement useful: the transformation must be effective, size-controlled, and capable of supporting whatever witness or certificate the application needs.

Manages Complexity¶

Exact semantic preservation can be unnecessarily expensive when a procedure consumes only feasibility. Equisatisfiability deliberately discards model-by-model identity and preserves one bit: whether the model set is empty. This controlled loss enables compact encodings, solver-friendly syntax, and modular reductions.

The danger is contract mismatch. A SAT solver needs the bit and often one witness, while a model counter, optimizer, interpolant generator, or equivalence checker needs more.

Abstract Reasoning¶

Logical equivalence implies equisatisfiability, but equisatisfiability does not imply logical equivalence.
Equisatisfiability is reflexive, symmetric, and transitive on a fixed carrier because it is equality after applying the Boolean Sat function.
If φ is satisfiable and φ ~sat ψ, at least one model of ψ exists, but no particular model of φ need satisfy ψ.
If ψ is an equisatisfiable encoding of φ and the solver returns UNSAT, φ is also unsatisfiable.

Knowledge Transfer¶

The exact relation transfers among propositional SAT, first-order theorem proving, description logics, SMT, and verification whenever formulas are compared solely by model existence under declared semantics. The proof machinery changes: assignments may extend with Boolean auxiliaries, structures with Skolem functions, or theory models with introduced terms.

Outside logic, “both feasible or both infeasible” is a related kernel equivalence on constraint problems, but importing the logical name should be explicit. The cross-domain prime is Equivalence Relation; the domain accent is model-theoretic satisfiability and satisfiability-preserving transformation.

Relationships to Other Abstractions¶

Current abstraction Equisatisfiability Domain-specific

Parents (1) — outgoing typed relations

Equisatisfiability is a kind of Equivalence Relation Prime

equisatisfiability is the kernel of the satisfiability-status function and partitions formulas into satisfiable and unsatisfiable classes.

Hierarchy path (1) — routes to 1 parentless root

Equisatisfiability → is a kind of Equivalence Relation

Neighborhood in Abstraction Space¶

Equisatisfiability sits in a sparse region of the domain-specific corpus (87^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Logical Semantics & Many-Valued Systems (12 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25