## Definition **Forward** and **backward chaining** are two complementary inference strategies for knowledge bases of *definite clauses* (rules of the form $P_1 \land P_2 \land \dots \to Q$). They underlie expert systems, production rule engines, and the Prolog execution model. ## Forward Chaining (Data-Driven) Start with known facts; apply rules that match those facts to derive new facts; repeat until no new facts are derivable or the goal is reached. ``` known ← initial facts loop: new ← {q : (p_1 ∧ ... ∧ p_n → q) is a rule, all p_i ∈ known, q ∉ known} if new is empty: stop if goal ∈ new: return success known ← known ∪ new ``` **Properties:** - Sound and complete for definite clauses (Horn). - Polynomial time on finite knowledge bases. - Derives *everything* entailed — including irrelevant facts. Efficient when the question is "what can I conclude?" rather than "is X true?" ## Backward Chaining (Goal-Driven) Start with the goal; find rules whose conclusion matches; recursively try to prove the premises. ``` prove(goal): if goal ∈ known facts: return success for each rule (p_1 ∧ ... ∧ p_n → goal): if prove(p_1) and ... and prove(p_n): return success return failure ``` **Properties:** - Sound and complete for definite clauses. - Focused: only explores derivations relevant to the goal. - Efficient when the question is specific ("is X true?"). - The execution model of Prolog. Depth-first by default, with backtracking on failure. ## When to Use Which | Use forward chaining when… | Use backward chaining when… | | ------------------------------------------- | ------------------------------------------ | | Facts arrive continuously (sensor streams) | A specific query needs answering | | The system needs to react to every new fact | The space of possible goals is small | | Many goals share many premises | Most facts are irrelevant to the goal | | Examples: production-rule expert systems | Examples: Prolog, query-answering systems | ## Limitations Both algorithms are restricted to **Horn clauses** (at most one positive literal). For full FOL inference, [[Resolution Inference]] is needed. ## Related - [[Propositional Logic]] - [[First-Order Logic]] - [[Inference Rules]] - [[Resolution Inference]]