Skip to main content

Satisfiable and unsatisfiable formulas

Short answer

A satisfiable formula has at least one interpretation (truth assignment) that makes it true. An unsatisfiable formula (contradiction) is false for every possible interpretation.

Define satisfiable and unsatisfiable formulas.

  • Satisfiable formula. A propositional formula is satisfiable if there is at least one interpretation (assignment of truth values to its variables) that makes it true. Such an interpretation is called a model. Example: p ∨ q is satisfiable (p = T makes it true).
  • Unsatisfiable formula. A formula is unsatisfiable (a contradiction) if it is false under every interpretation. Example: p ∧ ¬p.

Relations: a valid formula (tautology) is true under all interpretations, so it is satisfiable. A formula A is valid exactly when ¬A is unsatisfiable.

✓ Answer checked by Claude Opus 5.5 (high effort)

All Discrete Structure chapter 1 questions →