Information Technology Reference
In-Depth Information
Figure 11.1.
A recap of back-chaining
There is a
knowledge base
of
clauses
, where each clause has a
head
, which is an atom,
and a
body
, which is a sequence of atoms. There is also a
query
, which is a sequence
of atoms. The task is to
establish
the query given the knowledge base.
The query
A
1
, ...,
A
n
returns
success
or
failure
by back-chaining as follows:
1.
If
n
=
0, the query returns
success
.
2.
Otherwise, the query returns
success
only if there is a clause in the knowledge
base whose head is
A
1
(the first atom of the query) and whose body is
B
1
, ...,
B
m
,
such that the query
B
1
,
...
,
B
m
,
A
2
,
...
,
A
n
returns
success
(recursively) .
11.1 Back-chaining as subject matter
The back-chaining procedure that Prolog uses is summarized in figure 11.1. (This sim-
plified version omits negation, equality, and any mention of variables or unification
in the atoms.) In talking about back-chaining, it is assumed that any knowledge to be
applied in thinking is represented symbolically in the knowledge base (KB). The KB
can be about a world of family relationships, or a visual scene, or a game; the clauses
in the KB will talk about these items and the relationships among them. An example
is the clause in the family program in figure 3.1 that relates the
father
predicate to
the
child
and
male
predicates.
But suppose one wants to think about
back-chaining
itself rather than about fathers
and families. The clauses in the KB would have to talk not about people but about
knowledge bases, clauses and queries. Instead of a predicate like
father
(
x
,
y
)
that
holds if person
x
is a father of person
y
, there might be a predicate like
est
(
)
(short for establish) that holds when the query
q
can be established by back-chaining
from the knowledge base
k
. The arguments to the predicate
est
would be Prolog
terms standing for a knowledge base and a query. In sum, clauses, knowledge bases,
and queries would be represented
as Prolog terms
so that they can then be used as
arguments to predicates like
est
.
How is this done? To simplify matters, assume for now that predicates have no
arguments. Then a clause can be represented as a Prolog term using a list of constants:
the head of the list will represent the head of the clause, and the tail will represent
the body of the clause.
k
,
q
