FOL 08 · The Resolution Principle

Scope

The slides present resolution on propositional clauses (it’s the inference rule #8 from 09 Rules of Inference, turned into a full proof method). FOL resolution additionally needs unification — not covered in the slides and rarely asked in GATE CS.

Vocabulary

  • Literal — a variable or its negation: ,
  • Clause — a disjunction (OR) of literals:
  • Empty clause □ — a clause with no literals; it is FALSE (a contradiction)
  • Resolvent — from containing and containing : delete and , OR the rest.

Example

, → resolvent

Theorem

The resolvent of and is a logical consequence of them. Proof: , , both true.

  • L true ⇒ false ⇒ true ⇒ true.
  • L false ⇒ true ⇒ true. ∎

Modus ponens and modus tollens are special cases:

  • MP: , ⟶
  • MT: , ⟶

Proving an argument valid (refutation)

  1. Convert every premise to clause form (CNF; see 10 Beyond the Slides).
  2. Add the negated conclusion as a clause.
  3. Resolve repeatedly. Derive □ ⇒ argument is valid.

Why it works: the premises plus ¬C can’t all be true, so the premises force C.

Two rules people break

  1. Resolve on exactly ONE complementary pair at a time. From and you may get (useless) — you may not cancel both pairs to get □.
  2. A conjunction is several clauses. is two clauses, and — not one clause.

Solved problem 1 (slides)

“Allen is a bad boy or Hillary is a good girl” and “Allen is a good boy or David is happy” ⇒ “Hillary is a good girl or David is happy”. b: Allen good boy, g: Hillary good girl, h: David happy.

#ClauseFrom
C1premise
C2premise
C3¬conclusion:
C4¬conclusion
C5C1, C2 on b
C6C5, C3 on g
C7□C6, C4 on h

Valid ✅

Solved problem 2 — Superman (✏️ corrected)

If Superman were able and willing to prevent evil, he would do so. If he were unable, he would be impotent; if unwilling, malevolent. Superman does not prevent evil. If Superman exists, he is neither impotent nor malevolent. ∴ Superman does not exist.

p: able, q: willing, r: prevents evil, s: impotent, t: malevolent, u: exists.

What the slides got wrong

The slides write the 5th premise as . That says “not both impotent and malevolent”. “Neither … nor” means , so the premise is = two clauses and . The slides then resolve with to get — cancelling two pairs at once, which is illegal. (With the slides’ weaker premise the argument is actually invalid: u = T, s = T, t = F, q = T, p = F, r = F satisfies every premise.)

Correct refutation:

#ClauseFrom
C1
C2
C3
C4premise
C5
C6same
C7¬conclusion
C8C1, C4 on r
C9C8, C2 on p
C10C9, C3 on q
C11C10, C5 on s
C12C11, C6 on t
C13□C12, C7 on u

Valid ✅ — Superman does not exist.


🏠 Slide homework — solved


Prev ← FOL 07 Nested Translation and Negation · Next → FOL 09 Inference for Quantified Statements