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

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

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

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

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

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

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

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

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.