# Satisfiability

[https://en.wikipedia.org/wiki/Satisfiability](https://en.wikipedia.org/wiki/Satisfiability)

In mathematical logic, satisfiability and validity are elementary concepts of _semantics_.

A formula is **satisfiable** if it is possible to find an interpretation (model) that makes the formula true.

A formula is valid if all interpretations make the formula true.

The opposites of these concepts are _unsatisfiability_ and _invalidity_, that is, a formula is unsatisfiable if none of the interpretations make the formula true, and invalid if some such interpretation makes the formula false. These 4 concepts are related to each other in a manner exactly analogous to Aristotle's _square of opposition_.

The 4 concepts can be raised to apply to whole theories: a theory is satisfiable (valid) if one (all) of the interpretations make each of the axioms of the theory true, and a theory is unsatisfiable (invalid) if all (one) of the interpretations make each of the axioms of the theory false.

It is also possible to consider only interpretations that make all of the axioms of a second theory true. This generalization is commonly called _satisfiability modulo theories_.

The question whether a sentence in propositional logic is satisfiable is _decidable_.

The question whether a sentence in first-order logic is satisfiable is _not decidable_.

In universal algebra and equational theory, the methods of term rewriting, congruence closure and unification are used to attempt to decide satisfiability. Whether a particular theory is decidable depends on many factors (such as whether the theory is variable-free).
