15.9 Complete Knowledge Assumption

The complete knowledge assumption, as discussed in Section 5.7, is the assumption that any statement that does not follow from a knowledge base is false. It also allows for proof by negation as failure.

The complete knowledge assumption for logic programs with variables and functions symbols requires axioms for equality, and the domain closure, and a more sophisticated notion of the completion.

Example 15.41.

Suppose a student relation is defined by


The complete knowledge assumption would say that these three are the only students:


That is, if X is huan, manpreet, or karan, then X is a student, and if X is a student, X must be one of these three. In particular, kim is not a student.

Concluding ¬student(kim) requires proving kimhuankimmanpreetkimkaran. To derive the inequalities, the unique names assumption is required.

The complete knowledge assumption includes the unique names assumption.

The Clark normal form of the clause


is the clause


where V1,,Vk are k variables that did not appear in the original clause, and W1,,Wm are the original variables in the clause. “” means “there exists”. When the clause is an atomic clause, B is true.

Suppose all of the clauses for p are put into Clark normal form, with the same set of introduced variables, giving


which is equivalent to


This implication is logically equivalent to the set of original clauses.

Clark’s completion of predicate p is the equivalence


where negation as failure () in bodies is replaced by standard logical negation (¬). The completion means that p(V1,,Vk) is true if and only if at least one body Bi is true.

Clark’s completion of a knowledge base consists of the completion of every predicate symbol.

Example 15.42.

For the clauses


the Clark normal form is


which is equivalent to


The completion of the student predicate is

Example 15.43.

Consider the following recursive definition:


In Clark normal form, with variable renaming, this can be written as


Clark’s completion of passed_each is


Under the complete knowledge assumption, relations that cannot be defined using only definite clauses can now be defined.

Example 15.44.

Suppose you are given a database of course(C) that is true  if C is a course, and enrolled(S,C), which means that student S is enrolled in course C. Without the complete knowledge assumption, you cannot define empty_course(C), which is true  if there are no students enrolled in course C. This is because there is always a model of the knowledge base where every course has someone enrolled.

Using negation as failure, empty_course(C) can be defined by


The completion of this is


As a word of caution, you should be very careful when you include free variables within negation as failure. They usually do not mean what you think they might. The predicate has_enrollment was introduced in the previous example to avoid having a free variable within a negation as failure. See Exercise 15.15.

15.9.1 Complete Knowledge Assumption Proof Procedures

The top-down proof procedure for negation as failure with the variables and functions is much like the top-down procedure for propositional negation as failure. As with the unique names assumption, a problem arises when there are free variables in negated goals.

Example 15.45.

Consider the clauses


According to the semantics, there is only one answer to the query ask p(X), which is X=d. As r(d) follows, so does q(d) and so p(d) logically follows from the knowledge base.

When the top-down proof procedure encounters q(X), it should not try to prove q(X), which succeeds (with substitution {X/a}). This would make the goal p(X) fail, when it should succeed with X=d. Thus, the proof procedure would be incomplete. Note that, if the knowledge base contained s(X)q(X), the failure of q(X) would mean s(X) succeeding. Thus, with negation as failure, incompleteness leads to unsoundness.

As with the unique names assumption (Section 15.8.2), a sound proof procedure should delay the negated subgoal until the free variable is bound.

A more complicated top-down procedure is required when there are calls to negation as failure with free variables:

  • Negation-as-failure goals that contain free variables must not be selected in the negation-as-failure procedure of Figure 5.12 until the variables become bound.

  • If the variables never become bound, the goal flounders. In this case, you cannot conclude anything about the goal. The following example shows that you should do something more sophisticated for the case of floundering goals.

Example 15.46.

Consider the clauses


and the query

       ask p(X).

The completion of the knowledge base is


Substituting X=a for r gives q(X)¬X=a, and so p(X)X=a. Thus, there is one answer, namely X=a, but delaying the goal will not help find it. A proof procedure should analyze the cases for which the goal failed to derive this answer. However, such a procedure is beyond the scope of this book.