Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 37 · Projects and Practice

Project: A Resolution Theorem Prover

Build a propositional theorem prover step by step: parse formulas, convert to clause form, apply the resolution rule and print a proof, then test it against truth tables.

In this project you build a small automated theorem prover for propositional logic using resolution, the inference rule introduced by J. A. Robinson in 1965. It is the rule behind Prolog and many first-order provers. You will turn formulas into clauses, saturate the clause set, print a human-readable refutation and check the result against brute-force truth tables.

The plan reuses ideas from this chapter: clauses are the same objects the DPLL solver manipulates, the proof is a derivation in a formal system (proof calculi), and soundness and completeness (that lesson) tell us what to expect.

The resolution rule

Resolution works on clauses. From two clauses that contain complementary literals, C ∨ p and D ∨ ¬p, derive their resolvent C ∨ D. It is sound because in any valuation p or ¬p is false, so the other clause must supply a true literal. To prove φ valid, add ¬φ to the clause set and try to derive the empty clause □ (a contradiction). If you can, ¬φ is unsatisfiable and φ is valid. This is refutation: resolution is refutation-complete, which means every unsatisfiable clause set eventually yields □.

flowchart LR
    A["formula φ"] --> B["negate: not φ"]
    B --> C["convert to CNF clauses"]
    C --> D["resolve pairs until empty clause or fixed point"]
    D -->|"empty clause"| E["φ is valid"]
    D -->|"no new clauses"| F["φ is not valid"]

The refutation workflow.

Step 1: formulas and CNF

Formulas are nested tuples as in earlier lessons, with operators not, and, or, imp and iff. Converting to CNF has three steps: remove → and ↔, push negations inward with De Morgan (negation normal form), then distribute OR over AND. A clause is a frozenset of literals such as "p" and "~p", and a clause set is a frozenset of clauses. Dropping tautological clauses (p ∨ ¬p) keeps the set small.

Python Formula to clause form

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.

Step 2: saturation with resolution

Repeat: pick every pair of clauses, compute all resolvents, add the new ones. Stop when the empty clause appears (unsatisfiable) or nothing new is produced (saturation, so satisfiable). To print a proof, remember for each new clause the two parents that produced it. Because the number of clauses over n variables is finite, the loop always terminates; the number of clauses can explode, which is why real provers add subsumption (drop a clause if a smaller clause covers it) and strategies such as unit preference and set-of-support.

Python Resolution with proof output

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.

The trace lists only the clauses used in the refutation, each with the clauses it came from. The full prover below drops the trace to stay short, so add it back as the first extension exercise.

Step 3: the prover and a test harness

Now combine the parts. prove(f) negates the formula, converts to clauses, saturates and reports. We cross-check it against a truth table on hundreds of random formulas: a prover that disagrees even once has a bug.

Python The complete prover, checked against truth tables

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.

Extensions to try

  1. Print the proof tree. Store parents for every resolvent (as in the previous example) and print only the clauses used in the refutation.
  2. Subsumption. Delete any clause that is a superset of another clause; measure how much faster the prover gets on p1..p6 pigeonhole instances.
  3. Unit preference and set of support. Resolve only pairs where one clause comes from the negated goal.
  4. Horn clauses. Detect when all clauses are Horn and switch to forward chaining.
  5. First-order resolution. Add variables and unification, which finds substitutions that make two literals complementary. This is the heart of Prolog.

Always keep the brute-force checker. A verified slow oracle is the best test a fast clever program can have, and it turns subtle bugs (a missing tautology check, a forgotten negation) into immediate failures.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the resolvent of {p, q} and {¬p, r}?

    Resolve on p: drop p and ¬p and unite the rest, giving q ∨ r.
  2. 2. How does a resolution prover show that φ is valid?

    Refutation: a derivation of the empty clause from the clauses of ¬φ shows ¬φ is unsatisfiable.
  3. 3. What does it mean if saturation ends without the empty clause?

    Resolution is refutation-complete, so if no contradiction is derivable the clause set is satisfiable.
  4. 4. Why remove tautological clauses such as {p, ¬p}?

    A tautological clause is true in every valuation, so it can never contribute to a refutation.

Summary

  • Resolution derives C ∨ D from C ∨ p and D ∨ ¬p; it is sound and refutation-complete.
  • The pipeline is: negate the goal, convert to CNF, saturate, look for the empty clause.
  • Tautology removal and subsumption keep the clause set small; a truth-table oracle tests the prover.
  • First-order resolution adds unification and underlies Prolog.

Next: Project: A Finite Model Checker