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)
- Convert every premise to clause form (CNF; see 10 Beyond the Slides).
- Add the negated conclusion as a clause.
- 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
- Resolve on exactly ONE complementary pair at a time. From and you may get (useless) — you may not cancel both pairs to get □.
- 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.
| # | Clause | From |
|---|---|---|
| C1 | premise | |
| C2 | premise | |
| C3 | ¬conclusion: | |
| C4 | ¬conclusion | |
| C5 | C1, C2 on b | |
| C6 | C5, 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:
| # | Clause | From |
|---|---|---|
| C1 | ||
| C2 | ||
| C3 | ||
| C4 | premise | |
| C5 | ||
| C6 | same | |
| C7 | ¬conclusion | |
| C8 | C1, C4 on r | |
| C9 | C8, C2 on p | |
| C10 | C9, C3 on q | |
| C11 | C10, C5 on s | |
| C12 | C11, C6 on t | |
| C13 | □ | C12, C7 on u |
Valid ✅ — Superman does not exist.
🏠 Slide homework — solved
"It is not raining or Yvette has her umbrella", "Yvette does not have her umbrella or she does not get wet", "It is raining or Yvette does not get wet" ⇒ "Yvette does not get wet".
r: raining, u: umbrella, w: gets wet.
# Clause From C1 premise C2 premise C3 premise C4 ¬conclusion C5 C1, C2 on u C6 C5, C3 on r () C7 □ C6, C4 on w Valid ✅
Prev ← FOL 07 Nested Translation and Negation · Next → FOL 09 Inference for Quantified Statements