13 Individuals and Relations

13.8 Complete Knowledge Assumption

The complete knowledge assumption, as discussed in Section 5.6, 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.

To extend the complete knowledge assumption to logic programs with variables and functions symbols, we require axioms for equality, and the domain closure, and a more sophisticated notion of the completion. Again, this defines a form of negation as failure.

Example 13.47.

Suppose a student relation is defined by

student(mary).
student(john).
student(ying).

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

student(X)X=maryX=johnX=ying.

That is, if X is mary, john, or ying, 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 prove kimmarykimjohnkimying. To derive the inequalities, the unique names assumption is required.

The complete knowledge assumption includes the unique names assumption. As a result, we assume the axioms for equality and inequality for the rest of this section.

The Clark normal form of the clause

p(t1,,tk)B.

is the clause

p(V1,,Vk)W1WmV1=t1Vk=tkB.

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

p(V1,,Vk)B1.
    
p(V1,,Vk)Bn.

which is equivalent to

p(V1,,Vk)B1Bn.

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

Clark’s completion of predicate p is the equivalence

V1Vkp(V1,,Vk)B1Bn

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 along with the axioms for equality and inequality.

Example 13.48.

For the clauses

student(mary).
student(john).
student(ying).

the Clark normal form is

student(V)V=mary.
student(V)V=john.
student(V)V=ying.

which is equivalent to

student(V)V=maryV=johnV=ying.

The completion of the student predicate is

Vstudent(V)V=maryV=johnV=ying.
Example 13.49.

Consider the following recursive definition:

passed_each([],St,MinPass).
passed_each([CR],St,MinPass)
    passed(St,C,MinPass)
    passed_each(R,St,MinPass).

In Clark normal form, this can be written as

passed_each(L,S,M)L=[].
passed_each(L,S,M)
    CRL=[CR]
    passed(S,C,M)
    passed_each(R,S,M).

Here, we have removed the equalities that specify renaming of variables and have renamed the variables as appropriate. Thus, Clark’s completion of passed_each is

LSMpassed_each(L,S,M)L=[]
    CR(L=[CR]
    passed(S,C,M)
    passed_each(R,S,M)).

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

Example 13.50.

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

empty_course(C)course(C)has_enrollment(C).
has_enrollment(C)enrolled(S,C).

The completion of this is

Cempty_course(C)course(C)¬has_enrollment(C).
Chas_enrollment(C)Senrolled(S,C).

Here we offer 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. We introduced the predicate has_enrollment in the previous example to avoid having a free variable within a negation as failure. Consider what would have happened if you had not done this:

Example 13.51.

One may be tempted to define empty_course in the following manner:

empty_course(C)course(C)enrolled(S,C).

which has the completion

Cempty_course(C)Scourse(C)¬enrolled(S,C).

This is not correct. Given the clauses

course(cs422).
course(cs486).
enrolled(mary,cs422).
enrolled(sally,cs486).

the clause

empty_course(cs422)course(cs422)enrolled(sally,cs422)

is an instance of the preceding clause for which the body is true, and the head is false, because cs422 is not an empty course. This is a contradiction to the truth of the preceding clause.

Note that the completion of the definition in Example 13.50 is equivalent to

Cempty_course(C)course(C)¬Senrolled(S,C).

The existence is in the scope of the negation, so this is equivalent to

Cempty_course(C)course(C)S¬enrolled(S,C).