Propositional Logic · step 12 of 13

Resolution & proof by refutation

Resolution is a single inference rule operating on CNF clauses: from (A ∨ x) and (B ∨ ¬x) you may infer the resolvent (A ∨ B). It is refutation-complete — if a clause set is unsatisfiable, repeated resolution will eventually derive the empty clause □ — which makes it the engine behind automated theorem provers and Prolog.

Practise resolution & proof by refutation free → All Propositional Logic subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Convert everything to CNF and negate the goalTo prove Γ ⊨ A, put Γ and ¬A into CNF and collect all clauses into one set.
Find a complementary pairLook for a variable appearing positively in one clause and negatively in another. Those two clauses can be resolved.
Resolve on exactly one variable at a timeDelete x from the first clause and ¬x from the second, then union the remainders. Resolving on two variables at once is unsound.
Continue until you derive □Resolving a unit clause x with the unit clause ¬x gives the empty clause, which is unsatisfiable. That completes the refutation and proves the entailment.

Worked example

Use resolution to show that {p ∨ q, ¬p ∨ r, ¬q ∨ r, ¬r} is unsatisfiable.

Resolve (p ∨ q) with (¬p ∨ r) on p, giving (q ∨ r).
Resolve (q ∨ r) with (¬q ∨ r) on q, giving (r ∨ r) = (r).
Resolve the unit clause (r) with (¬r) on r, giving the empty clause □.

Answer. The empty clause is derived, so the set is unsatisfiable. Equivalently, {p ∨ q, ¬p ∨ r, ¬q ∨ r} entails r.

Where marks get dropped

These are the specific errors that cost credit on resolution & proof by refutation questions — QED's rubric penalises each of them separately.

Resolving two clauses on more than one variable simultaneously. From (x ∨ y) and (¬x ∨ ¬y) you may derive (y ∨ ¬y), not □ — the double step is invalid.
Forgetting to collapse duplicate literals. (r ∨ r) is just (r), and failing to simplify stalls the derivation.
Trying to prove the goal directly. Resolution is a refutation method — you must negate the conclusion first, and a proof that never adds ¬A proves nothing.

Practise this until it is automatic

Unlimited fresh questions

QED generates new resolution & proof by refutation problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Propositional Logic mastery is tracked so you know when this is exam-ready.

Resolution & proof by refutation — frequently asked questions

What does the empty clause mean?

It is the disjunction of no literals, which is false under every valuation. Deriving it shows the clause set has no model, so the original entailment holds.

Is resolution complete for proving theorems?

It is refutation-complete, which is the useful sense: it will always detect unsatisfiability. It cannot derive every entailed clause directly, which is why you always negate the goal.

How does this relate to Prolog?

Prolog uses SLD resolution, a restricted strategy over Horn clauses (at most one positive literal). The restriction makes the search tractable while keeping refutation-completeness for that fragment.

The rest of Propositional Logic

Connectives, truth tables, equivalences and normal forms. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make resolution & proof by refutation exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →