foundations of computational agents
The top-down proof procedure can be extended to handle variables by allowing instances of rules to be used in the derivation.
A generalized answer clause is of the form
$yes({t}_{1},\mathrm{\dots},{t}_{k})\leftarrow {a}_{1}\wedge {a}_{2}\wedge \mathrm{\dots}\wedge {a}_{m}$ |
where ${t}_{1},\mathrm{\dots},{t}_{k}$ are terms and ${a}_{1},\mathrm{\dots},{a}_{m}$ are atoms. The use of $yes$ enables answer extraction: determining which instances of the query variables are a logical consequence of the knowledge base.
Initially, the generalized answer clause for query $q$ is
$$yes({V}_{1},\mathrm{\dots},{V}_{k})\leftarrow q$$ |
where ${V}_{1},\mathrm{\dots},{V}_{k}$ are the variables that appear in $q$. Intuitively this means that an instance of $yes({V}_{1},\mathrm{\dots},{V}_{k})$ is true if the corresponding instance of the query is true.
The proof procedure maintains a current generalized answer clause.
At each stage, the algorithm selects an atom in the body of the generalized answer clause. It then chooses a clause in the knowledge base whose head unifies with the atom.
The SLD resolution of the generalized answer clause
$$yes({t}_{1},\mathrm{\dots},{t}_{k})\leftarrow {a}_{1}\wedge {a}_{2}\wedge \mathrm{\dots}\wedge {a}_{m}$$ |
on ${a}_{1}$ with the chosen clause
$a\leftarrow {b}_{1}\wedge \mathrm{\dots}\wedge {b}_{p}$ |
where ${a}_{1}$ and $a$ have most general unifier $\sigma $, is the answer clause
$(yes({t}_{1},\mathrm{\dots},{t}_{k})\leftarrow {b}_{1}\wedge \mathrm{\dots}\wedge {b}_{p}\wedge {a}_{2}\wedge \mathrm{\dots}\wedge {a}_{m})\sigma $ |
where the body of the chosen clause has replaced ${a}_{1}$ in the answer clause, and the MGU $\sigma $ is applied to the whole answer clause.
An SLD derivation is a sequence of generalized answer clauses ${\gamma}_{0}$, ${\gamma}_{1}$, $\mathrm{\dots}$, ${\gamma}_{n}$ such that
${\gamma}_{0}$ is the answer clause corresponding to the original query. If the query is $q$, with free variables ${V}_{1},\mathrm{\dots},{V}_{k}$, the initial generalized answer clause ${\gamma}_{0}$ is
$yes({V}_{1},\mathrm{\dots},{V}_{k})\leftarrow q.$ |
${\gamma}_{i}$ is obtained by selecting an atom ${a}_{1}$ in the body of ${\gamma}_{i-1}$; choosing a copy of a clause $a\leftarrow {b}_{1}\wedge \mathrm{\dots}\wedge {b}_{p}$ in the knowledge base whose head, $a$, unifies with ${a}_{i}$; replacing ${a}_{1}$ with the body, ${b}_{1}\wedge \mathrm{\dots}\wedge {b}_{p}$; and applying the unifier to the whole resulting answer clause.
The main difference between this and the propositional top-down proof procedure is that, for clauses with variables, the proof procedure must take copies of clauses from the knowledge base. The copying renames the variables in the clause with new names. This is both to remove name clashes between variables and because a single proof may use different instances of a clause.
${\gamma}_{n}$ is an answer. That is, it is of the form
$yes({t}_{1},\mathrm{\dots},{t}_{k})\leftarrow .$ |
When this occurs, the algorithm returns the answer
$${V}_{1}={t}_{1},\mathrm{\dots},{V}_{k}={t}_{k}.$$ |
Notice how the answer is extracted; the arguments to $yes$ keep track of the instances of the variables in the initial query that lead to a successful proof.
Figure 13.4 gives a non-deterministic algorithm that answer queries by searching for SLD derivations. This is non-deterministic in the sense that all derivations can be found by making appropriate choices that do not fail. If all choices fail, the algorithm fails, and there are no derivations. The “choose” on line 13 is implemented using search. Recall that $Unify({a}_{i},a)$ returns an MGU of ${a}_{i}$ and $a$, if there is one, and $\perp $ if they do not unify. The algorithm for $Unify$ is given in Figure 13.3.
Consider the database of Figure 13.2 and the query
$${\text{\U0001d622\U0001d634\U0001d62c}}{\mathit{\text{}}}{}{t}{}{w}{}{o}{}{\mathrm{\_}}{}{d}{}{o}{}{o}{}{r}{}{s}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{R}{,}{r}{}{107}{)}{.}$$ |
Figure 13.5 shows a successful derivation with answer ${R}{\mathrm{=}}{r}{\mathit{}}{\mathrm{111}}$.
${y}{}{e}{}{s}{}{(}{R}{)}{\leftarrow}{}{t}{}{w}{}{o}{}{\mathrm{\_}}{}{d}{}{o}{}{o}{}{r}{}{s}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{R}{,}{r}{}{107}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{resolve with}}}{}{t}{}{w}{}{o}{}{\mathrm{\_}}{}{d}{}{o}{}{o}{}{r}{}{s}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{{E}}_{{1}}{,}{{W}}_{{1}}{)}{\leftarrow}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}}}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{{E}}_{{1}}{,}{{M}}_{{1}}{)}{\wedge}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{{M}}_{{1}}{,}{{W}}_{{1}}{)}{.}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{substitution:}}}{}{\{}{{E}}_{{1}}{/}{R}{,}{{W}}_{{1}}{/}{r}{}{107}{\}}$ | ||
${y}{}{e}{}{s}{}{(}{R}{)}{\leftarrow}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{R}{,}{{M}}_{{1}}{)}{\wedge}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{{M}}_{{1}}{,}{r}{}{107}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{select leftmost conjunct}}}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{resolve with}}}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{{E}}_{{2}}{,}{{W}}_{{2}}{)}{\leftarrow}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{w}{}{e}{}{s}{}{t}{}{(}{{W}}_{{2}}{,}{{E}}_{{2}}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{substitution:}}}{}{\{}{{E}}_{{2}}{/}{R}{,}{{W}}_{{2}}{/}{{M}}_{{1}}{\}}$ | ||
${y}{}{e}{}{s}{}{(}{R}{)}{\leftarrow}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{w}{}{e}{}{s}{}{t}{}{(}{{M}}_{{1}}{,}{R}{)}{\wedge}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{{M}}_{{1}}{,}{r}{}{107}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{select leftmost conjunct}}}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{resolve with}}}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{w}{}{e}{}{s}{}{t}{}{(}{r}{}{109}{,}{r}{}{111}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{substitution:}}}{}{\{}{{M}}_{{1}}{/}{r}{}{109}{,}{R}{/}{r}{}{111}{\}}$ | ||
${y}{}{e}{}{s}{}{(}{r}{}{111}{)}{\leftarrow}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{r}{}{109}{,}{r}{}{107}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{resolve with}}}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{{E}}_{{3}}{,}{{W}}_{{3}}{)}{\leftarrow}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{w}{}{e}{}{s}{}{t}{}{(}{{W}}_{{3}}{,}{{E}}_{{3}}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{substitution:}}}{}{\{}{{E}}_{{3}}{/}{r}{}{109}{,}{{W}}_{{3}}{/}{r}{}{107}{\}}$ | ||
${y}{}{e}{}{s}{}{(}{r}{}{111}{)}{\leftarrow}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{w}{}{e}{}{s}{}{t}{}{(}{r}{}{107}{,}{r}{}{109}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{resolve with}}}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{w}{}{e}{}{s}{}{t}{}{(}{r}{}{107}{,}{r}{}{109}{)}$ | ||
${\mathrm{}}{\mathit{\hspace{1em}\hspace{1em}\u2006}}{\mathit{\text{substitution:}}}{}{\{}{\}}$ | ||
${y}{}{e}{}{s}{}{(}{r}{}{111}{)}{\leftarrow}$ |
Note that this derivation used two instances of the rule
$${i}{}{m}{}{m}{}{\mathrm{\_}}{}{e}{}{a}{}{s}{}{t}{}{(}{E}{,}{W}{)}{\leftarrow}{}{i}{}{m}{}{m}{}{\mathrm{\_}}{}{w}{}{e}{}{s}{}{t}{}{(}{W}{,}{E}{)}{.}$$ |
One instance eventually substituted ${r}{\mathit{}}{\mathrm{111}}$ for ${E}$, and one instance substituted ${r}{\mathit{}}{\mathrm{109}}$ for ${E}$.
When the atom ${i}{\mathit{}}{m}{\mathit{}}{m}{\mathit{}}{\mathrm{\_}}{\mathit{}}{w}{\mathit{}}{e}{\mathit{}}{s}{\mathit{}}{t}{\mathit{}}{\mathrm{(}}{{M}}_{{\mathrm{1}}}{\mathrm{,}}{R}{\mathrm{)}}$ was selected, other choices of the clause to resolve with would have resulted in a partial derivation that could not be completed.