From facts to consequences
A rule-based system may know individual facts and rules that connect them. Forward chaining starts with the facts and repeatedly adds a rule's conclusion once all its premises are known. Before using it, we must specify the language.
Definition 20.1.1
(Finite Horn rule base)
The atoms are a finite set of propositional symbols, and a rule has the form
where each premise and the conclusion is an atom. We treat the premises as a set, so repeating an atom does not create a second requirement. A rule with no premises () is a fact. There are no variables, function symbols, negative conclusions or rules expressing contradiction in this section.
Definition 20.1.2
(Valuation, model and entailment)
A valuation identifies the atoms that are true. It satisfies a rule when either at least one premise is false or the conclusion is true; hence a rule can be satisfied without firing. It is a model of the knowledge base when it satisfies every fact and every rule. The knowledge base entails an atom if every such model makes true. This is a statement about all models, not just the sequence in which an implementation happened to process rules.
Definition 20.1.3
(Forward-chaining closure)
A set of atoms is closed when the conclusion of every rule whose premises all lie in also lies in . The closure is obtained by starting from the empty set and repeatedly adding the conclusion of some rule whose premises all lie in the current set and whose conclusion is not yet in it, until no such rule remains. Facts have no premises, so they are added first. The set at which the process stops is called the fixed point.
Trace a small system
Worked example 20.1.4
(Forward chaining on the rain system)
Let stand for rain, wet ground, slippery ground and sprinkler running. These labels are illustrative: the implications are explicitly supplied rules, not claims that rain always makes real ground wet.
| Kind | Rule or fact |
|---|---|
| Fact | |
| Rule | |
| Rule | |
| Rule | |
| Rule |
Start with . The first rule adds , giving . Now both premises of are present, so add : . The rule is applicable, but is already present. No rule adds , and cannot fire on the basis of alone. We have reached the fixed point .
Counterexample mode
A conclusion does not prove its premise
From and it is invalid to infer : wet ground may be supported by . In this formal system, the valuation in which exactly are true satisfies every listed rule but makes false. It is a concrete countermodel to the claim that the knowledge base entails .
It does not follow that the knowledge base entails . The valuation making all four atoms true is also a model. Thus neither nor is entailed: absence from the derived set is not a general assertion that an atom is false.
Why the fixed point answers positive-atom queries
Theorem 20.1.5
(The closure is the least model)
Let be a finite Horn rule base over a finite set of atoms. Forward chaining terminates, whatever order of applicable rules is used, and its closure satisfies:
- every atom of is true in every model of ;
- the valuation making exactly the atoms of true is itself a model of .
Consequently is the least model of under inclusion, every terminating order gives the same , and for an atom the knowledge base entails if and only if .
Proof
(Soundness, then the closure as a model)
Because the atom set is finite and each productive step adds an atom not already present, the process terminates. Its order may vary, provided we continue until no rule can add anything.
First, every atom added to is true in every model. This holds for the initial facts. If it holds for all premises of a rule, any model satisfies those premises and therefore must satisfy the rule's conclusion. Induction establishes soundness for every added atom.
Second, interpret exactly the atoms in as true. All facts are in . If every premise of a rule is in , its conclusion is also in , because otherwise another productive step would be possible. If a premise is absent, the implication is true under this valuation. Therefore itself is a model.
Soundness says is contained in every model, while the second part shows it is a model. Thus it is the least model under inclusion. If a positive atom is in , every model satisfies . If is absent, the model makes it false and witnesses that is not entailed. In particular, every terminating order of rule applications gives the same closure.
Proof X-ray
Where finiteness, the Horn form and the two inclusions enter
Finiteness is used once, for termination: each productive step enlarges inside a finite atom set. Without it the process need not stop.
The Horn form, a single positive atom as conclusion, is what makes the second part work. When every premise is in , the conclusion can be added, so is closed under all rules. A rule with a disjunctive conclusion and no premises has the models and but their intersection is not a model, so there is no least model and no single set to chase.
The key move is a squeeze between two inclusions. Soundness gives for every model . Closure under the rules gives that is one of those models. A set that lies inside every model and is a model itself must be the least one. The argument closes by turning absence into evidence: if , the valuation is a model in which is false, a concrete countermodel. Nothing here asserts that is false in every model, and this is why is not obtained.
The countermodel answers a precise question: “must this positive atom be true in all models?” It does not make a closed-world assumption that every unstated atom is false in reality. The result above also does not claim completeness for arbitrary negated formulas or unrestricted predicate logic.
Concept lensStructural
The closure as the intersection of all models
The set of models of a Horn rule base is closed under intersection: if and satisfy a rule and all its premises lie in , then its conclusion lies in both, hence in the intersection. So the intersection of all models is itself a model, and it is the smallest one, namely . For the rain system the only models are and , and their intersection is , the closure found by chaining. Entailed atoms are those lying in this intersection.
The explorer below replays forward chaining on these rules and checks every valuation independently, so a missing conclusion is confirmed by an actual countermodel rather than assumed false.
A base with an underivable premise
Worked example 20.1.6
(A premise that no rule concludes)
Take the fact together with the rules , and . Forward chaining adds , then . The atom is neither a fact nor the conclusion of any rule, so it is never added, and neither nor is ever derived. The closure is .
The valuation with exactly true satisfies the fact and all three rules, because the premise is false in both of the last two. So are not entailed. The valuation making all five atoms true is also a model, so none of is entailed either. The fact is a rule with no premises, so its premise count is already zero before any step is taken.
A worklist implementation
For efficient processing, index every rule under each distinct premise it mentions. For each rule keep a counter equal to the number of its distinct premises not yet processed. Put each known fact into a queue once. When an atom is removed from the queue, visit the rules indexed by that atom and decrement their counters. When a counter reaches zero, add the head if it is not already known, and enqueue it once. Rules with zero premises contribute their heads initially.
Worked example 20.1.7
(Counters on the rain system)
The counters start at for , for , for and for , and the queue holds .
Remove : the rule drops to , so is added and enqueued; the rule drops from two to one. Remove : the rule drops to , so is added and enqueued. Remove : the rule drops to , but is already known, so nothing is enqueued and the cycle terminates. The queue is empty. The counter of never changed because was never processed, so was derived only through .
With suitable adjacency lists and one queue entry per atom, initialization and processing take time and space, where is the finite set of atoms, the rules, and the total number of distinct premise occurrences across rules. The bound includes initializing counters and rule heads; it is not a claim about an unrestricted first-order inference engine.
Common mistakes
Common mistake
(Stopping after a single pass over the rules)
Suppose the rules are listed as first and second, with the fact . A single pass in listed order finds the first rule inapplicable because is not yet known; the second rule then adds , and the pass ends without . Yet is entailed. Continue until a whole pass adds nothing, or use the worklist, which revisits a rule exactly when one of its premises becomes known.
Common mistake
(Counting premise occurrences instead of distinct premises)
Premises form a set, so has one distinct premise. If a counter is initialized to two because is written twice, but the rule is indexed under only once, then processing decrements it to one and the rule never fires, so is lost although it is entailed by the fact . Initialize each counter to the number of distinct premises.
Practice with solutions
Quick check
(If the fact is removed and there are no other facts, what is the closure of the rain system?)
Ask which rule can fire first.
Solution · Answer
It is empty. Neither a cycle nor a rule with unsatisfied premises starts itself.
Quick check
(Keep the original facts and add the rule . Is now entailed?)
Follow the derivation of and first.
Solution · Answer
Yes. First derive , then , then use the new rule to derive ; soundness makes it true in every model.
Quick check
(Does the single rule entail ?)
Look for a valuation that satisfies the rule and makes false.
Solution · Answer
No. The valuation with both and false satisfies the implication and is a countermodel to .
Quick check
(Why must a worklist avoid enqueuing again when processing ?)
Recall that is already in the closure at that point.
Solution · Answer
is already known. Enqueuing only newly known atoms prevents the cycle from creating endless duplicate work, while preserving every possible conclusion.
Forward chaining makes the proof and the implementation meet: derived atoms have a proof from facts, and the completed closure supplies a countermodel for every positive atom left out.