An incorrect answer is an answer that has been proved yet is false in the intended interpretation. It is also called a false-positive error. An incorrect answer is only produced by a sound proof procedure if an incorrect definite clause was used in the proof.

Assume that whoever is debugging the knowledge base, such as a domain expert or a user, knows the intended interpretation of the symbols of the language and is able to determine whether a particular proposition is true or false in the intended interpretation. The person does not have to know how the answer was computed. To debug an incorrect answer, a domain expert needs only to answer yes-or-no questions.

Suppose there is an atom $g$ that was proved yet is false in the intended interpretation. Then there must be a rule $g\leftarrow a_1\wedge \mathrm{\dots }\wedge a_k$ in the knowledge base that was used to prove $g$. Either

• •

  one of the $a_i$ is false in the intended interpretation, in which case it can be debugged in the same way, or

• •

  all of the $a_i$ are true in the intended interpretation; in this case, the definite clause $g\leftarrow a_1\wedge \mathrm{\dots }\wedge a_k$ must be incorrect.

This leads to an algorithm, presented in Figure 5.6, to debug false positives, namely to find a false clause in a knowledge base when an atom that is false in the intended interpretation is derived.

This only requires the person debugging the knowledge base to be able to answer yes-or-no questions.

This procedure can also be carried out by the use of the how command. Given a proof for an atom $g$ that is false in the intended interpretation, a user can ask how $g$ was proved. This will return the definite clause that was used in the proof. If the clause was a rule, the user could use how to ask about an atom in the body that was false in the intended interpretation. This will return the rule that was used to prove that atom. The user repeats this until a definite clause is found where all of the elements of the body are true (or there are no elements in the body). This is the incorrect definite clause.

The user or domain expert can find the buggy definite clause without having to know the internal workings of the system or how the proof was computed. They only require knowledge about the intended interpretation and the disciplined use of how.

The second type of error occurs when an expected answer is not produced. This manifests itself by a failure when an answer is expected. An atom $g$ that is true in the domain, but is not a consequence of the knowledge base, is called a false-negative error. The preceding algorithm does not work in this case; there is no proof. We must look for why there is no proof for $g$.

An appropriate answer is not produced only if a definite clause or clauses are missing from the knowledge base. By knowing the intended interpretation of the symbols and by knowing what queries should succeed (i.e, what is true in the intended interpretation), a domain expert can debug a missing answer. Given a false negative, an atom that failed when it should have succeeded, Figure 5.7 shows how to debug the knowledge base to find an atom for which there is a missing definite clause.

Suppose $g$ is an atom that should have a proof, but which fails. Because the proof for $g$ fails, the bodies of all of the definite clauses with $g$ in the head fail.

• •

  Suppose one of these definite clauses for $g$ should have resulted in a proof; this means all of the atoms in the body must be true in the intended interpretation. Because the body failed, there must be an atom in the body that fails. This atom is then true in the intended interpretation, but fails. So we can recursively debug it.

• •

  Otherwise, there is no definite clause applicable to proving $g$, so the user must add a definite clause for $g$.

A whynot question can be used by the user to ask why some $g$ was not proved. The system can ask the relevant questions to implement Debug_missing.

Example 5.12 shows an example where the top-down derivation can loop. There can be an infinite loop only if the knowledge base is cyclic, where a knowledge base is cyclic if there is an atom $a$ such that there is a sequence of definite clauses of the form

(where if $n=0$ there is a single definite clause with $a$ in the head and body).

A knowledge base is acyclic if there is an assignment of natural numbers (non-negative integers) to the atoms so that the atoms in the body of a definite clause are assigned a lower number than the atom in the head. There cannot be an infinite loop in an acyclic knowledge base.

To detect a cyclic knowledge base, the top-down proof procedure can be modified to maintain the set of all ancestors for each atom in the proof.

Initially, the set of ancestors of each atom is empty. When the rule

is used to prove $a$, the ancestors of $a_i$ will be the ancestors of $a$ together with $a$. That is,

The proof can fail if an atom is in its set of ancestors. This failure only occurs if the knowledge base is cyclic. This is a refined version of cycle pruning used in search, with each atom having its own set of ancestors.

A cyclic knowledge base is often a sign of a bug. When writing a knowledge base, it is often useful to ensure an acyclic knowledge base by identifying a value that is being reduced at each iteration. For example, in the electrical domain, the number of steps away from the outside of the house is meant to be reduced by one each time through the loop.

Note that the bottom-up proof procedure does not get into an infinite loop, because it selects a rule only when the head has not been derived.