Forward chaining: deriving facts to a fixpoint

The forward-chaining algorithm

Forward chaining is a recognize–act cycle whose only action is *assert a new fact*. The loop is:

1. Put the known facts in the knowledge base.
2. Scan the rules; for any rule whose premises are all in the KB, add its conclusion to the KB (if not already there).
3. Repeat until a full scan adds nothing new — the fixpoint. Terminating at the fixpoint is what makes the procedure halt.

Each firing is one modus ponens step. The set of facts only grows (the procedure is monotonic), so it always terminates.

Worked example — exam Q8

The exam gives these statements (translate to a knowledge base, part a; then forward-chain, part b):

- (1) cat absent → mice present - (2) dog present → cat absent - (3) cat not sleeping → cat absent or cat present - (4) dog absent and cat absent → mice present - Facts: dog absent, cat not sleeping.

Statement (3) is a disjunctive conclusion, so strictly it derives nothing definite on its own — that is a real subtlety. The exam intends you to resolve it to the productive disjunct: a not-sleeping cat that is not present must be absent. Encoding cat_not_sleeping → cat_absent, forward chaining then runs:

- cat_not_sleeping is a fact → fire stmt 3 (resolved) → derive cat_absent. - Now cat_absent holds → fire stmt 1 → derive mice_present. - (Stmt 4 also concludes mice_present, but it is already known — refraction-style, no re-add.) - Next scan adds nothing → fixpoint.

Conclusion: the mice are present. The derivation order cat_absent → mice_present is the answer to Q8 part b.