Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 46 Β· Logic and Knowledge Representation

Inference: Resolution, Horn Clauses and Forward/Backward Chaining

Prove things with logic instead of enumerating models: convert to CNF, run resolution, and use forward and backward chaining on Horn clauses, with a wumpus-world example in Python.

Model checking decides entailment by looking at every model, which costs 2^n. A smarter approach is theorem proving: apply rules of inference to the sentences in the knowledge base and derive new sentences, step by step, until the query appears or a contradiction does. If the inference rules are sound (they only derive things that really follow) and complete (they can derive everything that follows), the result is the same as model checking, usually much faster.

This lesson covers the two classic families of proof procedures for propositional logic. Resolution is general: it handles any knowledge base, after converting it to a standard shape. Forward and backward chaining are faster but only work on a restricted class of sentences called Horn clauses, which is where many practical rule systems live. Along the way you will work through a small wumpus-world problem, where an agent reasons about pits it cannot see.

Conjunctive normal form

Resolution works on a uniform input format: conjunctive normal form (CNF), a conjunction of clauses, where each clause is a disjunction of literals. For example (A ∨ ¬B) ∧ (B ∨ C ∨ D) is in CNF. We write a clause as a set of literals, {A, ~B}, and a KB as a set of clauses. The empty clause {} is a disjunction with nothing in it, which is false in every model: deriving it means the knowledge base is contradictory.

Every propositional sentence can be converted to CNF with three mechanical steps.

  1. Eliminate ↔ and β†’: A ↔ B becomes (Β¬A ∨ B) ∧ (Β¬B ∨ A), and A β†’ B becomes Β¬A ∨ B.
  2. Move Β¬ inwards with De Morgan's laws and double negation, until negation applies only to symbols.
  3. Distribute ∨ over ∧: A ∨ (B ∧ C) becomes (A ∨ B) ∧ (A ∨ C).

A clause that contains both P and Β¬P is always true and can be dropped. The code below does exactly these steps, and prints the intermediate results for the wumpus-world rule "there is a breeze in square (1,1) if and only if there is a pit in (1,2) or (2,1)".

Python Converting sentences to CNF step by step

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 biconditional turns into three clauses. Read them as rules: {B11, ~P12} says "a pit in (1,2) forces a breeze in (1,1)", the same for (2,1), and {P12, P21, ~B11} says "a breeze means at least one of the neighbors has a pit".

The resolution rule

The resolution rule takes two clauses that contain complementary literals (one has L, the other Β¬L) and produces a new clause with everything except that pair:

TEXT
{A, B, L}   {C, Β¬L, D}
-----------------------
    {A, B, C, D}

It is sound: if both parent clauses are true, then in any model either L is true, which makes the second clause depend on C or D, or L is false, which makes the first depend on A or B. Either way the new clause holds. Special cases you already know: from and {Β¬P, Q} you get (modus ponens), and from and {Β¬P} you get the empty clause, a contradiction.

Resolution proves things by refutation, which is proof by contradiction. To show KB ⊨ α:

  1. Convert the KB and ¬α to CNF and put all clauses together.
  2. Repeatedly resolve pairs of clauses and add the results.
  3. If the empty clause appears, the KB together with ¬α is contradictory, so KB ⊨ α.
  4. If no new clauses can be generated, Ξ± is not entailed.

Resolution is refutation-complete: if the knowledge base entails Ξ±, this procedure is guaranteed to find the empty clause, and it always terminates for propositional logic, because there are only finitely many clauses over a finite set of symbols.

graph TD
    A["{B11, ~P12}"] --> R1["{B11}"]
    B["{P12}<br/>(negated query)"] --> R1
    R1 --> R2["{} empty clause"]
    C["{~B11}<br/>(percept: no breeze)"] --> R2

A two-step refutation: the query Β¬P12 is proved because assuming its opposite, P12, leads to a contradiction.

Worked example: a little wumpus world

In the wumpus world an agent explores a cave where pits are invisible, but a square next to a pit is breezy. The agent has visited the start square (1,1) and felt no breeze there. It then moved to (2,1) and felt a breeze. Is it safe to enter (1,2)? The KB:

  • Β¬P11 (the start square is safe),
  • Β¬B11 (no breeze in (1,1)),
  • B11 ↔ (P12 ∨ P21),
  • B21 (breeze in (2,1)),
  • B21 ↔ (P11 ∨ P22 ∨ P31).

Below is a complete resolution prover. It converts the KB, adds the negated query, resolves all pairs until it finds the empty clause or runs out of new clauses, and prints the proof for the first query.

Python A resolution prover for the wumpus world

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 agent can prove ¬P12 and ¬P21: the missing breeze in (1,1) rules out pits in both neighbors, so (1,2) and (2,1) are safe. It can also prove P22 ∨ P31: the breeze in (2,1) needs a pit somewhere next to it, and (1,1) is known to be safe. It cannot prove P22 and cannot prove ¬P22, because the evidence does not decide between (2,2) and (3,1). The prover says "not entailed" in both cases, and a careful agent treats those squares as risky. This is the kind of reasoning that propositional logic does well: sure conclusions, plus honest uncertainty.

Horn clauses

Resolution is complete, but the number of clauses can explode. A famous restriction makes reasoning much cheaper. A Horn clause is a clause with at most one positive literal. A definite clause has exactly one. Definite clauses are exactly implications whose premise is a conjunction of symbols:

TEXT
{Β¬Fever, Β¬Cough, FluSuspected}   is the same as   Fever ∧ Cough β†’ FluSuspected

A fact is a definite clause with no negative literals. Horn clauses are less expressive (you cannot say P ∨ Q, and you cannot state a disjunction of two possibilities), yet many rule systems fit: configuration rules, diagnostic checklists, business rules and database queries. For Horn knowledge bases, entailment of a symbol can be decided in time linear in the size of the KB.

Forward chaining

Forward chaining is data-driven. Start with the known facts. Whenever all the premises of a rule are known, add its conclusion as a new fact. Repeat until the query is derived or nothing new can be added. The efficient version counts, for each rule, how many premises are still missing, and fires the rule when the counter reaches zero.

graph LR
    fever --> AND1(("and"))
    cough --> AND1
    AND1 --> flu_suspected
    flu_suspected --> AND2(("and"))
    body_ache --> AND2
    AND2 --> flu
    flu --> needs_rest
    flu --> needs_fluids
    needs_rest --> AND3(("and"))
    needs_fluids --> AND3
    AND3 --> stay_home

An AND-graph of the rules. Forward chaining pushes truth from the facts on the left towards the conclusions on the right.

Backward chaining

Backward chaining is goal-driven. To prove a goal, look for a rule that concludes it and set its premises as new subgoals; a goal is proved if it is a known fact or if all the premises of some rule for it are proved. It never touches rules that have nothing to do with the question, so it is efficient when the KB is large and the question is specific. It is the engine of Prolog (more on that in the first-order logic lesson). Plain recursion can loop forever on rules like A β†’ B and B β†’ A, so the code below remembers the goals on the current path.

Python Forward and backward chaining on a diagnosis rule base

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.

Compare the two traces. For allergy, forward chaining first derives everything it can reach (nine symbols in all) before concluding that allergy never appears, because the fact itchy_eyes is missing. Backward chaining tries one rule and fails after two checks, which is much less work. For stay_home, backward chaining proves flu twice, once under each subgoal. Real implementations cache results (memoization) to avoid that repetition.

Choose by the shape of the problem. Forward chaining suits systems that react to incoming data ("when this sensor reading arrives, what else follows?"). Backward chaining suits question answering ("can I prove this specific thing?"). Many production rule engines mix both.

Choosing a method

Method Works on Direction Cost
Model checking Any KB Enumerates models 2^n
Resolution Any KB (in CNF) Refutation Can blow up, complete
Forward chaining Horn clauses From facts to conclusions Linear
Backward chaining Horn clauses From goal to facts Often less than linear

The most practical general method is none of these but a refined search procedure for satisfiability, covered in the next lesson.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. What does deriving the empty clause during resolution mean?

    The empty clause is false in every model. Because it was derived from the KB plus the negated query, the negated query cannot hold together with the KB, so the query is entailed.
  2. 2. Which clause is a Horn clause?

    A Horn clause has at most one positive literal. {~A, ~B, C} is the implication A and B imply C. The others have two or more positive literals.
  3. 3. Which statement about forward chaining is true?

    Forward chaining is data-driven: facts trigger rules, which produce new facts. It is linear time for Horn knowledge bases only.
  4. 4. In the wumpus example, why can the agent not prove that (2,2) has a pit?

    The breeze requires a pit in at least one of (2,2) and (3,1), but nothing decides which. The KB does not entail either pit on its own.
  5. 5. When is backward chaining usually preferable to forward chaining?

    Backward chaining only explores rules relevant to the goal, so it avoids deriving irrelevant facts.

Summary

  • Theorem proving derives conclusions with sound inference rules instead of enumerating all 2^n models.
  • CNF conversion has three steps: eliminate ↔ and β†’, move Β¬ inward, distribute ∨ over ∧.
  • Resolution combines clauses with complementary literals; deriving the empty clause from KB plus the negated query proves entailment.
  • The wumpus-world example shows sure conclusions (safe squares) and honest "not entailed" answers.
  • Horn clauses (at most one positive literal) allow linear-time entailment checks by forward or backward chaining.
  • Forward chaining is data-driven, backward chaining is goal-driven; backward chaining can loop or repeat work unless it tracks its path and caches results.

Next: SAT Solving and DPLL.