Satisfiability is a fundamental concept in propositional and predicate logic. A formula is satisfiable when there exists at least one assignment or model under which it evaluates to true. It does not need to be true under every interpretation. A formula that is true under every interpretation is logically valid and therefore satisfiable in a nonempty class of interpretations. An unsatisfiable formula is false under every interpretation. For example, p ∧ ¬p is unsatisfiable because p and its negation cannot both be true under the same classical truth assignment. A formula such as p ∨ q is satisfiable because at least one assignment makes it true. Collections of formulas can also be studied for joint satisfiability.
Satisfiability and Unsatisfiability
A logical formula is satisfiable if at least one interpretation makes it true, and unsatisfiable if no interpretation can make it true.
∃I such that I ⊨ φ — φ is satisfiable
For every I, I ⊭ φ — φ is unsatisfiable
p ∧ ¬p — unsatisfiable formula
p ∨ ¬p — valid formula in classical logic
Explanation
Variables
I: an interpretation
φ: a logical formula
p: a proposition
⊨: satisfies
⊭: does not satisfy
∃: there exists
∀: for every
Example or application
The formula p ∧ q is satisfiable because assigning p = T and q = T makes it true. The formula p ∧ ¬p is unsatisfiable because no truth assignment can make both p and ¬p true.
Definition
Satisfiability is the property of a logical formula or set of formulas having at least one model, while unsatisfiability means that no model satisfies them.
Purpose
To determine whether a logical formula or a collection of logical conditions can be true under at least one consistent interpretation.
Importance
Satisfiability is essential in automated reasoning, constraint solving, software testing, hardware verification, and the analysis of logical consistency.
Learning Objectives
Define satisfiability and unsatisfiability.
Determine satisfiability using truth tables.
Distinguish satisfiable formulas from valid formulas.
Recognize contradictions in logical expressions.
Explain the importance of satisfiability in computing.
Key Concepts
Satisfiability
Unsatisfiability
Model
Interpretation
Contradiction
Tautology
Constraint satisfaction
Working Principle
A formula is tested against possible interpretations. If at least one interpretation makes it true, it is satisfiable. If every interpretation makes it false, it is unsatisfiable.
Process
Identify the logical variables and connectives.
List possible truth assignments or interpretations.
Evaluate the formula under each assignment.
Check whether at least one assignment makes it true.
Classify the formula as satisfiable or unsatisfiable.
Applications
SAT solving
Automated theorem proving
Scheduling and resource constraints
Hardware verification
Software configuration
Artificial intelligence planning
Worked Example
Consider φ = (p ∨ q) ∧ ¬p. If p = F and q = T, then p ∨ q = T and ¬p = T. Therefore, φ = T. At least one satisfying assignment exists, so φ is satisfiable. It is not logically valid because other assignments can make it false.
Common Misconceptions
A satisfiable formula does not need to be true under every interpretation.
An unsatisfiable formula is not merely a formula that happens to be false under one assignment.
A logically valid formula is also satisfiable under the usual nonempty interpretation assumptions.
Satisfiability of individual formulas does not automatically establish joint satisfiability of a collection.
Practice Questions
Define satisfiability.
Why is p ∧ ¬p unsatisfiable?
Determine whether p ∨ q is satisfiable.
Explain the difference between satisfiability and logical validity.
Give one application of SAT solving.
Key Takeaway
Satisfiability asks whether at least one interpretation makes a formula true; unsatisfiability means no such interpretation exists.
Prerequisites
Truth Values and Logical Interpretation
Logical Expressions and Formulas
Logical Validity and Logical Truth
Reference
Handbook of Satisfiability — Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh
A Mathematical Introduction to Logic — Herbert B. Enderton
Discrete Mathematics and Its Applications — Kenneth H. Rosen
Related Topics
Logical Validity and Logical Truth
Logical Consequence
Logical Consistency and Inconsistency
Logic in Computer Science
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Mathematical Logic & Set Theory