Backward Chaining Algorithm
A backward chaining algorithm is a deductive inference algorithm that works from the rule consequent to the rule antecedent.
- AKA: Backward Reasoning, Backward Chaining.
- Context:
- It can make use of Modus Ponens.
- …
- Example(s):
- an SLD Resolution Algorithm.
- …
- Counter-Example(s):
- See: Inference Rule, Inference Engine, Horn Clause, Logic Sentence, Prolog Language, Dynamic Programming, Knowledge Machine Language, ECLiPSe Language.
References
2011
- (Wikipedia, 2011) http://en.wikipedia.org/wiki/Backward_chaining
- QUOTE:Backward chaining (or backward reasoning) is an inference method used in automated theorem provers, proof assistants and other artificial intelligence applications. It is one of the two most commonly used methods of reasoning with inference rules and logical implications – the other is forward chaining. Backward chaining is implemented in logic programming by SLD resolution. Both rules are based on the modus ponens inference rule.
Backward chaining starts with a list of goals (or a hypothesis) and works backwards from the consequent to the antecedent to see if there is data available that will support any of these consequents. An inference engine using backward chaining would search the inference rules until it finds one which has a consequent (Then clause) that matches a desired goal. If the antecedent (If clause) of that rule is not known to be true, then it is added to the list of goals (in order for one's goal to be confirmed one must also provide data that confirms this new rule).
For example, suppose that the goal is to conclude the color of my pet Fritz, given that he croaks and eats flies, and that the rule base contains the following four rules:
- If X croaks and eats flies – Then X is a frog
- If X chirps and sings – Then X is a canary
- If X is a frog – Then X is green
- If X is a canary – Then X is yellow
- This rule base would be searched and the third and fourth rules would be selected, because their consequents (Then Fritz is green, Then Fritz is yellow) match the goal (to determine Fritz's color). It is not yet known that Fritz is a frog, so both the antecedents (If Fritz is a frog, If Fritz is a canary) are added to the goal list. The rule base is again searched and this time the first two rules are selected, because their consequents (Then X is a frog, Then X is a canary) match the new goals that were just added to the list. The antecedent (If Fritz croaks and eats flies) is known to be true and therefore it can be concluded that Fritz is a frog, and not a canary. The goal of determining Fritz's color is now achieved (Fritz is green if he is a frog, and yellow if he is a canary, but he is a frog since he croaks and eats flies; therefore, Fritz is green).
- QUOTE:Backward chaining (or backward reasoning) is an inference method used in automated theorem provers, proof assistants and other artificial intelligence applications. It is one of the two most commonly used methods of reasoning with inference rules and logical implications – the other is forward chaining. Backward chaining is implemented in logic programming by SLD resolution. Both rules are based on the modus ponens inference rule.
2004
2003
- (Friedman-Hill, 2003) ⇒ Ernest Friedman-Hill. (2003). “Jess in Action: Java Rule-based Systems.
- 7.4 Backward-chaining rules p.116
- Backward chaining and queries p.131
- Implementing backward chaining p.143