Backward Chaining — Beginner-Friendly Notes

1. What It Is

Backward chaining = goal-driven reasoning: start from the query and work backwards — find rules that conclude the query, then try to prove their premises, recursively.

Query → Which rules could give me this? → Prove those premises.

2. How It Works (depth-first, with unification)

To prove $Q$:

1. If $Q$ is known fact → success.
2. Find rule $P_1 \land ... \land P_n \Rightarrow Q$ (consequent unifies with $Q$).
3. Try to prove each $P_i$ (recursively, as sub-goals) — all must succeed.

Example:

• Query $Flies(Tweety)$?
• Rule $Bird(x) \Rightarrow Flies(x)$ with $\{x/Tweety\}$ → need to prove $Bird(Tweety)$ → fact exists → success.

Flies(Tweety)?
  └─ Bird(Tweety)?  (via rule)
      └─ fact Bird(Tweety) — yes

3. Algorithm Sketch

Backward(Q):
  if Q in KB: return true
  for rule (P ⇒ Q) where Q unifies:
    if all Backward(P_i) succeed: return true
  return false

Uses stack (depth-first search) — like DFS.

4. Forward vs Backward (exam contrast)

	Forward	Backward
Direction	Facts → Conclusions (data-driven)	Query → Facts (goal-driven)
Search style	Derives all consequences (broad)	Only explores relevant rules (focused)
When better	Many queries, want all facts (e.g., monitoring)	Single query, few relevant rules (e.g., diagnosis question)
Analogy	BFS	DFS

Example to remember: If KB has 1000 facts and query is "does Tweety fly?", forward would derive everything about all birds; backward directly checks Tweety.

5. Properties

Property	Value
Sound	Yes
Complete	Yes for definite clauses
Space	Linear (DFS-like)
Pitfall	Can loop if rules recursive — needs visited check

6. Where You See It

• Prolog language uses backward chaining.
• Expert systems that answer questions ("does patient have X?") use backward.

7. One-Line Summary

Backward chaining proves a query by recursively backward-searching for rules that conclude it and proving their premises, yielding goal-driven, depth-first inference that is sound and complete for Horn KBs.

8. Quick Self-Check

1. When is backward better than forward?
2. Trace backward for query $Mammal(Tweety)$ with rule $Bird(x) \Rightarrow Mammal(x)$? No, that's wrong — why would that happen?