Meeting 14: Forward/Backward Chaining

Reading: AIAMA 9.3-9.4 (you might want to review AIAMA 7.5.4 also)

Recall in PL Forward chaining we used Horn Clauses and iterated application of modus ponens. In FOL we can do the lifted version by restricting ourselves to definite clauses and using iterated lifted modus ponens until no more inferences can be made. Definite clauses can be written as conjunctions of positive predicates in the premise and a single predicate in the conclusion. If we restrict ourselves further to no-functions then the resulting formal language is called datalog. Forward Chaining can infer many facts unrelated to a query. A different approach, as in PL, is to use backward chaining from the query using AND-OR search and the lifted modus ponens.

Questions you should be able to answer after reading are:

  1. Describe how Forward Chaining works.
  2. What is the complexity of forward chaining and how is it related to the number of ground facts in the KB?
  3. How does incremental forward chaining help? What are its assumptions?
  4. Describe how Backward Chaining works.
  5. What is a generator? what does yield do? How does one implement these in Python?
  6. How can these algorithms be used to define a logic programming language?