unsatisfiability

Unsatisfiability is a property of a logical formula or theory indicating that no assignment of values satisfies all its constraints. In propositional logic it means the conjunction of the given clauses is false for every truth assignment; in first-order logic it means there is no structure and interpretation making all sentences true.

In practice, unsatisfiability is often discussed for conjunctive normal form (CNF) formulas. A CNF formula is unsatisfiable if no truth assignment to the variables makes every clause true. For example, the CNF (a ∨ b) ∧ (¬a) ∧ (¬b) has no satisfying assignment, hence is unsatisfiable.

Algorithmic and complexity aspects: The problem of determining unsatisfiability (UNSAT) for propositional formulas is co-NP-complete; SAT is NP-complete. In practice, SAT/SMT solvers search for a satisfying assignment or derive a refutation. A common refutation method is resolution, which can produce an empty clause to certify unsatisfiability.

Related concepts: unsatisfiable cores identify a subset of clauses already unsatisfiable; minimal unsatisfiable formulas are a class with properties that any proper subset is satisfiable.

In mathematics and logic, unsatisfiability corresponds to inconsistency: a set of sentences has no model. If a theory is unsatisfiable, by the completeness theorem it has no interpretation in any structure.

Applications: formal verification, model checking, automatic theorem proving, optimization, and constraint solving rely on identifying unsatisfiable sets to prune search spaces or prove impossibility. See also SAT, SAT solver, resolution, unsatisfiable core.