Backward chaining with example

Backward chaining is a goal-driven reasoning method used in rule-based systems. It starts with the goal (hypothesis) and works backwards: it finds rules whose THEN part (conclusion) matches the goal, and then tries to prove the IF parts (conditions) of those rules as new sub-goals. A sub-goal is proved if it is a known fact, or if it can in turn be proved by another rule. If a sub-goal cannot be proved and cannot be asked from the user, the rule fails and another rule is tried (backtracking). Prolog and MYCIN use backward chaining.

Algorithm

prove(goal):
  if goal is in the fact base -> return TRUE
  for each rule whose conclusion matches goal:
      if prove(every condition of the rule) -> return TRUE
  return FALSE

Example

Rules:

• R1: IF X croaks AND X eats flies THEN X is a frog
• R2: IF X chirps AND X sings THEN X is a canary
• R3: IF X is a frog THEN X is green
• R4: IF X is a canary THEN X is yellow

Facts: Fritz croaks. Fritz eats flies.

Goal: Is Fritz green?

green(Fritz)
   |  R3
frog(Fritz)
   |  R1
   +-- croaks(Fritz)     [fact]
   +-- eats_flies(Fritz) [fact]

Result: The goal is proved: Fritz is green. Rules R2 and R4 are never examined, which shows why backward chaining is efficient when there is a specific goal.