A Procedure for Thinking - Thinking as Computation - page 27

Figure 2.2. The back-chaining procedure

To establish a sentence Q :
1. Try to locate Q itself in the KB. If you can, then return success .

2. Otherwise, try to locate a conditional sentence of the form

If P 1 and ... and P n then Q
in the KB. If you cannot, then return failure .

3. Otherwise, use back-chaining to try to establish P 1 , then P 2 , . . . , then P n .

If these are all successful, then return success .

4. Otherwise, go back to step 2 and look for another conditional.

2.3 Back-chaining

The computational procedure used in this chapter is called back-chaining . As men-
tioned, the procedure is given an atomic sentence Q and attempts to determine if Q
is logically entailed by the knowledge base, that is, back-chaining is asked to establish
the query. So the input will be a query Q (and implicitly, a KB in the background),
and the output will be either success or failure . (Even if a query Q can be successfully
established, it is not added to the KB. Back-chaining always leaves the KB unchanged.
No learning happens here.)
The back-chaining procedure is shown in figure 2.2. It is called back-chaining
because it chains backward from a query to the atomic sentences in the KB. Note
that the back-chaining procedure for Q depends on using the back-chaining proce-
dure for other sentences (the P i ). This makes it a recursive procedure (discussed in
chapters 3 and 4). Before looking at back-chaining in action, we need to deal with one
complication: variables .

2.3.1 Using variables

There are sentences in the knowledge base that include variables, such as the one
relating child and parent . A sentence like

If X is a child of Y then Y is a parent of X.
is intended to work as if the KB included sentences like