Forward chaining with definite clauses

Derive new facts from if-then rules until the query is proved or nothing new follows.

Python

def forward_chain(rules, facts, query):
    known = set(facts)
    derived = []
    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)
                derived.append(conclusion)
                changed = True
    return query in known, derived


rules = [(["P"], "Q"), (["L", "M"], "P"), (["B", "L"], "M"), (["A", "P"], "L"), (["A", "B"], "L")]
print(forward_chain(rules, ["A", "B"], "Q"))
print(forward_chain(rules, ["A"], "Q"))

Output

(True, ['L', 'M', 'P', 'Q'])
(False, [])

Explanation

General propositional reasoning is expensive, but many knowledge bases fit a restricted form that is much cheaper to use. A definite clause is a rule of the form p1 and p2 and ... and pk implies q, with one positive conclusion; a fact is a clause with no premises. Knowledge bases of definite clauses, also called Horn knowledge bases, are used in rule-based expert systems and in logic programming languages such as Prolog.

Forward chaining is data-driven. It starts with the known facts, finds any rule whose premises are all known, adds that rule's conclusion to the known facts, and repeats until nothing new can be added. The query is entailed if it ends up in the set of known facts. For propositional definite clauses this is sound and complete, and a careful implementation runs in time linear in the size of the knowledge base. Backward chaining is the goal-driven alternative: it starts from the query and works back to see which facts would prove it.

The example is the standard textbook knowledge base. From the facts A and B, the rule A ∧ B ⇒ L fires first, then B ∧ L ⇒ M, then L ∧ M ⇒ P, and finally P ⇒ Q. The program prints the facts in the order they were derived. When only A is known, none of the rules can fire, so Q is not derived. That shows the difference between not entailed and false: failing to derive Q only means the knowledge base does not prove it.

Explore the dry run

Guided walkthroughReady

1def forward_chain(rules, facts, query):

2 known = set(facts)

3 derived = []

4 changed = True

5 while changed:

6 changed = False

7 for premises, conclusion in rules:

8 if conclusion not in known and all(p in known for p in premises):

9 known.add(conclusion)

10 derived.append(conclusion)

11 changed = True

12 return query in known, derived

15rules = [(["P"], "Q"), (["L", "M"], "P"), (["B", "L"], "M"), (["A", "P"], "L"), (["A", "B"], "L")]

16print(forward_chain(rules, ["A", "B"], "Q"))

17print(forward_chain(rules, ["A"], "Q"))

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A rule fires when its conclusion is new and every premise is already known.	`—`	—
Add the derived fact. With A and B known, A ∧ B ⇒ L derives L first.	`known = {A, B, L}`	—
New facts may enable more rules, so scan again until a full pass adds nothing.	`known = {A, B, L}`	—
Chain of derivations: L, then M, then P, then Q. The query is proved.	`known = {A, B, L}`	(True, ['L', 'M', 'P', 'Q'])
With only A known, no rule's premises are satisfied, so nothing is derived and Q is not proved.	`known = {A, B, L}`	(True, ['L', 'M', 'P', 'Q']) (False, [])

Cost and common mistakes

This version is O(r²) for r rules in the worst case. With premise counters and an agenda it is O(size of the knowledge base).

Failing to derive a query does not make it false. It only means the knowledge base does not entail it.
This simple loop rescans every rule on each pass. A counter of unsatisfied premises per rule gives the linear-time version.
Forward chaining derives everything reachable, including facts irrelevant to the query. Backward chaining focuses on the goal.

Try it yourself

Which fact would you add so that Q can be derived when only A is known?

Reveal answer and reasoning

B. With A and B known, the chain L, M, P, Q is derived. Adding L alone would not be enough, because deriving M needs both B and L.

Forward chaining with definite clauses

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading