##  [Satisfiability Solving](/satisfiability-solving-0) 

 Definition

The algorithmic procedure that decides whether a given propositional or Boolean formula admits at least one assignment of truth values that makes the formula true; commonly applied to formulas in conjunctive normal form (CNF) and implemented by SAT solvers.

 

 

 

 

 

 





## Principle

Principle

Reduce logical satisfiability to a guided search over assignments plus inference and learning: systematically explore partial assignments, propagate implied values, detect conflicts, backtrack with learned clauses or heuristics, and terminate when a full satisfying assignment is found or unsatisfiability is proved.

 

 

 

 

 





## Demonstration

Demonstration

Given CNF clauses (x ∨ y), (¬x ∨ z), (¬y ∨ ¬z), a SAT solver using CDCL may assign x=true, propagate y=true, derive conflict with (¬y ∨ ¬z), analyze conflict to learn a clause (¬x ∨ ¬z), backtrack, then find a full assignment such as x=false, y=true, z=false that satisfies every clause.

 

 

 

 

## Misapplication

Misapplication

Treating satisfiability solving as an optimization routine that necessarily returns the 'best' model or assuming that a SAT solver will enumerate all satisfying assignments by default; or applying propositional SAT methods directly to first-order formulas without grounding or theory handling.

 

 

 

 

 





## Consequence

Consequence

Correct application yields a certificate: either a concrete satisfying assignment (model) demonstrating satisfiability or a proof of unsatisfiability (e.g., a derived empty clause) enabling automated verification, counterexample generation, and reductions from many NP problems to SAT.

 

 

 

 

## Reversal

Reversal

Instead of searching for a satisfying assignment, the inverted task is unsat core extraction or model enumeration; conceptually, one can invert the procedure to enumerate minimal unsatisfiable subsets rather than models.

 

 

 

 

 





## Boundary

Boundary

Scope is propositional/Boolean formulas (finite Boolean combinations). It excludes, unless explicitly extended, first-order logic with function symbols and infinite domains, as well as satisfiability modulo theories (SMT) which integrates background theories like arithmetic.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension exists between pure SAT solving and SMT: both decide satisfiability but SMT combines theory reasoning and SAT techniques, so methods and guarantees differ; likewise between decision (is there a model?) and search/optimization (find best model under cost).

 

 

 

 

 





## Synthesis

Synthesis

Satisfiability solving unites search, propagation, conflict analysis, and heuristic choice to answer the decision problem for Boolean formulas: it either produces a concrete assignment that makes the formula true or derives unsatisfiability, enabling many downstream verification and synthesis tasks.