satisfierbar

Satisfierbar, or satisfiable, is a property of a logical formula meaning that there exists an assignment of truth values to its variables that makes the formula true. In propositional logic, a valuation assigns each propositional variable either true or false. If at least one valuation yields true for the formula, the formula is satisfierbar, and the assignment that makes it true is called a model.

Examples help illustrate the concept. The formula p ∨ q is satisfierbar because it becomes true whenever p is true (or q is true). The formula p ∧ ¬p is not satisfierbar; it is unsatisfierbar because no truth assignment can make both p and not p true at the same time. The formula p ∨ ¬p is satisfierbar as well as a tautology, since it is true under every valuation.

The notion is central to the SAT problem. Given a finite propositional formula, the question asks whether it is satisfierbar. This problem is NP-complete in general, with many practical instances solved by specialized algorithms and tools known as SAT solvers. In practice, formulas are often converted into conjunctive normal form (CNF) to apply efficient solving techniques, including backtracking, conflict-driven learning, and heuristics.

Beyond propositional logic, the concept generalizes to first-order logic, where a formula is satisfierbar if there exists a structure and an interpretation under which the formula holds. Satisfiability also plays a key role in areas such as automated reasoning, constraint solving, and formal verification.