✦ScienexySCIENCE KNOWLEDGE LIBRARY
reference · SCI-MAT-012-013

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

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.

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