Erfüllbar

Erfüllbar is a term used in logic and computer science to describe whether a given formula or set of constraints can be made true by some assignment of values. In German, the corresponding noun is Erfüllbarkeit and the related adjective is erfüllbar. The concept is central in propositional and first-order logic, as well as in constraint satisfaction problems, verification, and automated reasoning.

In propositional logic, a formula is erfüllbar if there exists a truth assignment to its propositional variables that makes the formula evaluate to true. A set of clauses in conjunctive normal form is satisfiable if there is an assignment that makes every clause true. If no assignment exists, the formula is unerfüllbar (unsatisfiable). A formula that is true under every possible assignment is called a tautology and is automatically erfüllbar, though satisfiable formulas are not necessarily tautologies.

Determining satisfiability is the core problem of the SAT problem. For propositional logic, the satisfiability problem is NP-complete, and practical solvers use algorithms such as DPLL and CDCL, along with heuristics and learning. SAT solving has wide applications in software verification, hardware design, planning, and constraint solving.

Beyond propositional logic, satisfiability can be studied in first-order logic (existence of a model), and in theories such as arithmetic or arrays (theories of satisfiability). The negation of an unsatisfiable formula is a tautology, and proofs of unsatisfiability can be obtained via resolution and model checking through refutation.