Introduction
Truth tables double in size with every symbol, so they are useless for large knowledge bases. Inference rules derive new sentences directly from old ones, doing work only where it matters. Rule-based expert systems, Prolog, database query engines and the type checkers of some programming languages all work this way.
How it works
Modus ponens is the basic rule: from A and A → B, infer B. Knowledge bases of Horn clauses, rules such as fever ∧ cough → flu_suspected plus plain facts, can be handled entirely with it.
Forward chaining starts from the facts. It repeatedly scans the rules and fires any rule whose premises are all known, adding its conclusion, until nothing new can be added. It is data-driven: it finds every consequence, including ones nobody asked about.
Backward chaining starts from a goal. To prove a goal, it checks whether the goal is a fact; otherwise it looks for a rule that concludes the goal and tries to prove each premise in turn, recursively. It is goal-driven and does only the work the question needs. It must avoid loops, such as P → Q and Q → P, by refusing to prove a goal that is already on the current path.
Resolution handles any sentence in conjunctive normal form (an "and" of clauses, each an "or" of literals). From clauses (A ∨ B) and (¬A ∨ C), it infers (B ∨ C). To prove KB ⊨ α, add ¬α to the KB and resolve until the empty clause appears, which is a contradiction. This refutation method is complete for propositional logic.
First-order logic adds objects, predicates and variables: Knows(john, X) means "John knows X" for some X. To use a rule such as Knows(Y, Mother(Y)), the reasoner must find values for the variables that make two expressions identical: unification. Unifying Knows(john, X) with Knows(Y, Mother(Y)) gives Y = john and X = Mother(john). The occurs check refuses X = f(X), which would need an infinite term.
Syntax
def unify(a, b, s):
a, b = walk(a, s), walk(b, s) # follow existing bindings
if a == b: return s
if is_variable(a): return bind(a, b, s) # unless a occurs in b
if is_variable(b): return bind(b, a, s)
if same_functor_and_arity(a, b):
for x, y in zip(args(a), args(b)):
s = unify(x, y, s)
if s is None: return None
return s
return None
Example
rules = [
(["fever", "cough"], "flu_suspected"),
(["flu_suspected", "positive_test"], "flu"),
(["flu"], "rest"),
(["rash"], "allergy_check"),
]
facts = {"fever", "cough", "positive_test"}
print("forward chaining:")
known = set(facts)
changed = True
while changed:
changed = False
for premises, conclusion in rules:
if conclusion not in known and all(p in known for p in premises):
known.add(conclusion)
changed = True
print(f" {' and '.join(premises)} => {conclusion}")
def prove(goal, depth=0, path=()):
pad = " " * (depth + 1)
if goal in facts:
print(f"{pad}{goal}: a known fact")
return True
for premises, conclusion in rules:
if conclusion == goal and goal not in path:
print(f"{pad}{goal}: try the rule {' and '.join(premises)} => {goal}")
if all(prove(p, depth + 1, path + (goal,)) for p in premises):
return True
print(f"{pad}{goal}: cannot be proved")
return False
for goal in ["rest", "allergy_check"]:
print(f"backward chaining, goal {goal}:")
print(" proved" if prove(goal) else " not proved")Line by line
- The rules are Horn clauses: a list of premises and one conclusion. Three facts are known.
- Forward chaining fires every rule whose premises are known, in passes, and finds flu_suspected, then flu, then rest.
- Backward chaining for
restworks from the goal: rest needs flu, flu needs flu_suspected and a positive test, and so on down to facts. - Each step is indented by how deep it is in the proof.
- For
allergy_check, the only rule needs a rash, which is not a fact and has no rule, so the goal cannot be proved.
Expected result
forward chaining:
fever and cough => flu_suspected
flu_suspected and positive_test => flu
flu => rest
backward chaining, goal rest:
rest: try the rule flu => rest
flu: try the rule flu_suspected and positive_test => flu
flu_suspected: try the rule fever and cough => flu_suspected
fever: a known fact
cough: a known fact
positive_test: a known fact
proved
backward chaining, goal allergy_check:
allergy_check: try the rule rash => allergy_check
rash: cannot be proved
allergy_check: cannot be proved
not proved
In the real world
Prolog runs programs by backward chaining with unification. Business rule engines, such as those that check insurance claims, use forward chaining over thousands of rules. Datalog, a forward-chaining logic language, is used for program analysis and in some databases. Unification is also how compilers infer types in languages such as Haskell, OCaml and Rust.
Common mistakes
- Firing a rule again for a conclusion already known, which never ends in a loop of rules.
- Backward chaining without a loop check, which recurses forever on P → Q, Q → P.
- Resolving on two literals at once, which is not a valid step.
- Skipping the occurs check, so X unifies with f(X) and later code loops forever.
Best practices
- Use forward chaining when new facts arrive and all their consequences are needed; backward chaining for specific questions.
- Record which rule produced each fact, so conclusions can be explained.
- Apply a substitution fully before printing it, so every variable shows its final value.
Summary
Forward chaining applies modus ponens from facts until nothing changes; backward chaining proves a goal by proving the premises of a rule that concludes it. Resolution with refutation is complete for propositional logic. Unification finds variable bindings that make two terms equal, which lets rules with variables apply to many objects.
Quick check
Key takeaways
- Forward chaining derives everything that follows; backward chaining only what a goal needs.
- Resolution with proof by contradiction is complete for propositional logic.
- Unification lets one rule apply to many objects, which is the heart of first-order logic and Prolog.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.