A Procedure for Thinking - Thinking as Computation - page 37

Figure 2.5. A dog example knowledge base

fido is a collie.
If X is a poodle then X is a dog.
If X is a collie then X is a dog.
If X is a poodle then X is a poodle.

not miss anything. Back-chaining almost has this property. It does not miss any
logical entailments provided it does not get stuck in a loop (see the next section).

It forms the basis of the Prolog programming language. A computer can be
programmed to do back-chaining in a very simple and direct way using Prolog
(see chapters 3 and 4).

2.5.1 Getting stuck in a loop

Consider the small knowledge base in figure 2.5. It has one atomic sentence and
three conditional sentences. The last sentence is a bit strange perhaps, but it is not
intuitively false or wrong.
Observe that this knowledge base logically entails fido is a dog . (Just ignore the
poodle sentences.) However, consider establishing this sentence using back-chaining.
Here is the first part of the trace:
1. Look for fido is a dog in the KB. Nothing found.

2. Look for If . . . then fido is a dog in the KB.

Found: If X is a poodle then X is a dog.
This matches for X=fido .

3. Work on the single if-part of the matching conditional:

Establish the query fido is a poodle .
1.

Look for fido is a poodle in the KB. Nothing found.

2. Look for If . . . then fido is a poodle in the KB.

Found: If X is a poodle then X is a poodle.
This matches for X=fido .

3. Work on the single if-part of the matching conditional:

Establish the query fido is a poodle .