Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 37 · Propositional Logic

SAT and Resolution: Automated Propositional Reasoning

Learn the Boolean satisfiability problem, the resolution rule, and the DPLL algorithm, then write a working SAT solver in Python and test it on puzzles.

The Boolean satisfiability problem (SAT) asks: given a propositional formula, is there an assignment that makes it true? It sounds modest, yet it is the most famous problem in computer science: SAT was the first problem proved NP-complete (Cook, 1971), and modern SAT solvers routinely handle formulas with millions of variables. Because "is φ valid?" reduces to "is ¬φ unsatisfiable?", a SAT solver is also an automatic prover for propositional logic.

Problem format: CNF clauses

Solvers read CNF (see normal forms). By convention variables are positive integers and a negative integer means a negated variable, so the formula (p ∨ ¬q) ∧ (q ∨ r) with p=1, q=2, r=3 is the list [[1, -2], [2, 3]]. This is the idea behind the DIMACS file format used by real solvers.

Validity through unsatisfiability

To prove φ is a tautology, convert ¬φ to CNF and show it is unsatisfiable. To prove p → q, q → r ⊢ p → r, check that (p → q) ∧ (q → r) ∧ ¬(p → r) has no satisfying assignment. This "refutation" approach is how almost all automated provers work.

The resolution rule

Resolution takes two clauses that clash on one variable and produces a new clause without it:

(A ∨ x) and (B ∨ ¬x) give (A ∨ B).

It is the clause-level version of "either x or A; not x or B; so A or B". Special cases include modus ponens (x and x → B, i.e. ¬x ∨ B, give B) and the empty clause (from x and ¬x), which stands for a contradiction. Resolution refutation is sound and complete: a CNF set is unsatisfiable exactly when repeated resolution derives the empty clause.

Python Resolution refutation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

So p → q, q → r and p really do entail r: adding ¬r produces a contradiction.

DPLL: search with propagation

Resolution can generate huge numbers of clauses. The DPLL algorithm (Davis, Putnam, Logemann, Loveland) is a smarter search:

  1. Unit propagation: if a clause has one literal left, that literal must be true; set it and simplify.
  2. Pure literal elimination: if a variable appears with only one sign, set it to satisfy those clauses.
  3. Branch: pick an unassigned variable, try true, and if that fails try false (backtracking).

Modern CDCL solvers add clause learning (recording why a branch failed), non-chronological backtracking, restarts and clever heuristics; that is what makes industrial SAT feasible.

How DPLL works

Unit propagation One literal left is forced
Pure literals Only one sign: set it
Branch Guess, then backtrack
CDCL adds learning Remember failures

Propagate first, guess last

1 / 2
Python A DPLL SAT solver

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Variables not mentioned in the returned assignment may take any value.

A real puzzle: scheduling as SAT

Suppose three tasks A, B, C must each be assigned to a morning (variable true) or afternoon (false) slot with these rules: A and B cannot share a slot; B and C cannot share a slot; at least one of A or C must be in the morning. Encode each rule as clauses: "not both in the morning" is (¬A ∨ ¬B); "not both in the afternoon" is (A ∨ B); together they say A and B differ. The solver then finds a schedule.

Python Encoding a scheduling puzzle

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity in perspective

  • SAT is NP-complete, so no known algorithm is fast on all inputs.
  • Yet industrial instances (hardware verification, planning, package dependency resolution) are solved daily because real problems have structure.
  • 2-SAT (clauses of at most two literals) is solvable in linear time; Horn-SAT too. 3-SAT is already NP-complete.
  • Real tools: MiniSat, CaDiCaL, Kissat and Z3 (an SMT solver extending SAT with arithmetic and data types).

Common mistakes

  • Forgetting to negate the goal when using SAT for validity.
  • Encoding "exactly one" as only "at least one"; you need pairwise "not both" clauses too.
  • Treating a solver's "SAT" answer as a proof of validity. Satisfiable means a counterexample may exist; validity needs UNSAT of the negation.
  • Expecting the Python solvers above to scale; they are teaching tools.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. To show φ is a tautology with a SAT solver you check that...

    If no assignment makes ¬φ true, then every assignment makes φ true.
  2. 2. Resolving (a ∨ x) and (b ∨ ¬x) yields...

    The clashing literals cancel and the remaining literals are joined by OR.
  3. 3. What does unit propagation do?

    A one-literal clause can only be satisfied by making that literal true.
  4. 4. Which statement about SAT complexity is correct?

    SAT is NP-complete in general (Cook-Levin), though practical solvers handle huge structured instances.

Summary

  • SAT asks whether a formula has a satisfying assignment; validity reduces to unsatisfiability of the negation.
  • Resolution derives new clauses; deriving the empty clause proves unsatisfiability (sound and complete).
  • DPLL combines unit propagation, pure literals and backtracking; CDCL adds clause learning.
  • SAT is NP-complete yet practical on structured instances; 2-SAT and Horn-SAT are easy.
  • Encoding real problems as clauses is a core applied-logic skill.

Next: Predicates and Quantifiers