Satisfiability

A (well-formed) formula is satisfiable if there is some interpretation in which it holds true. Else, it is unsatisfiable

More causally, if a formula can be made true with some combination of variables, it is valid. If there is no possible way to make it true, it is unsatisfiable.

Definition §

Satisfiability ^definition

A well-formed formula $P$ in a formal language $L$ is satisfiable if it is true under at least one model, $M$. Similarly, $P$ is unsatisfiable if there is no model in which it holds true.

Unsatisfiability (Propositional Logic) ^definition-unsatisfiable-propositional

Under propositional logic, a proposition $P$ is unsatisfiable iff:

$$\models \neg P$$

$$P\models \perp$$

Model

In Propositional Logic §

In propositional logic, a proposition is unsatisfiable if:

• It is a contradiction, that is, false under every valuation
• Equivalently, its corresponding truth table has a column of only False