Forward chaining with definite clauses
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.
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"))