Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
12.8 Complete Knowledge Assumption
To extend the complete knowledge assumption of Section 5.5 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.
student(john).
student(ying).
The complete knowledge assumption would say that these three are the only students; that is,
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 kim≠mary ∧kim ≠john ∧kim≠ying. 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
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. "exist " 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)←Bn.
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 negations as failure (∼) in the bodies are 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.
student(john).
student(ying).
the Clark normal form is
student(V)←V=john.
student(V)←V=ying.
which is equivalent to
The completion of the student predicate is
passed_each([C|R],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)←
exist C exist R L=[C|R]∧
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
exist C exist R (L=[C|R]∧
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.
Using negation as failure, empty_course(C) can be defined by
has_Enrollment(C)←enrolled(S,C).
The completion of this is
∀C has_Enrollment(C)↔exist S enrolled(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:
which has the completion
This is not correct. Given the clauses
course(cs486).
enrolled(mary,cs422).
enrolled(sally,cs486).
the clause
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 12.48 is equivalent to
The existence is in the scope of the negation, so this is equivalent to
