13 Individuals and Relations 13.7.2 Unique Names Assumption 13.8.1 Complete Knowledge Assumption Proof Procedures

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

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 $s t u d e n t$ relation is defined by

	$\displaystyle{student(mary).}$
	$\displaystyle{student(john).}$
	$\displaystyle{student(ying).}$

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

\displaystyle{student(X)\iff X=mary\vee X=john\vee X=ying.}

That is, if $X$ is $m a r y$ , $j o h n$ , or $y i n g$ , then $X$ is a student, and if $X$ is a student, $X$ must be one of these three. In particular, $k i m$ is not a student.

Concluding $\neg student(kim)$ requires proving prove $kim\neq mary\wedge\mbox{}kim\neq john\wedge\mbox{}kim\neq 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

\displaystyle{p(t_{1},\ldots,t_{k})\leftarrow\mbox{}B.}

is the clause

\displaystyle{p(V_{1},\ldots,V_{k})\leftarrow\mbox{}\exists W_{1}\ldots\exists W% _{m}\ V_{1}=t_{1}\wedge\mbox{}\ldots\wedge\mbox{}V_{k}=t_{k}\wedge\mbox{}B.}

where $V_{1},\ldots,V_{k}$ are $k$ variables that did not appear in the original clause, and $W_{1},\ldots,W_{m}$ are the original variables in the clause. “ $\exists$ ” means “there exists”. When the clause is an atomic clause, $B$ is $t r u e$ .

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

	$\displaystyle{p(V_{1},\ldots,V_{k})\leftarrow\mbox{}B_{1}.}$
	$\displaystyle\ \ \ \ {\vdots}$
	$\displaystyle{p(V_{1},\ldots,V_{k})\leftarrow\mbox{}B_{n}.}$

which is equivalent to

\displaystyle{p(V_{1},\ldots,V_{k})\leftarrow\mbox{}B_{1}\vee\ldots\vee B_{n}.}

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

Clark’s completion of predicate $p$ is the equivalence

\displaystyle{\forall V_{1}\ldots\forall V_{k}~{}p(V_{1},\ldots,V_{k})\iff B_{% 1}\vee\ldots\vee B_{n}}

where negation as failure ( $\sim$ ) in bodies is replaced by standard logical negation ( $\neg$ ). The completion means that $p(V_{1},\ldots,V_{k})$ is true if and only if at least one body $B_{i}$ 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

	$\displaystyle{student(mary).}$
	$\displaystyle{student(john).}$
	$\displaystyle{student(ying).}$

the Clark normal form is

	$\displaystyle{student(V)\leftarrow\mbox{}V=mary.}$
	$\displaystyle{student(V)\leftarrow\mbox{}V=john.}$
	$\displaystyle{student(V)\leftarrow\mbox{}V=ying.}$

which is equivalent to

\displaystyle{student(V)\leftarrow\mbox{}V=mary\vee V=john\vee V=ying.}

The completion of the $s t u d e n t$ predicate is

\displaystyle{\forall V~{}student(V)\iff V=mary\vee V=john\vee V=ying.}

Example 13.49.

Consider the following recursive definition:

	$\displaystyle{passed\_each([\,],St,MinPass).}$
	$\displaystyle{passed\_each([C\mid R],St,MinPass)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {passed(St,C,MinPass)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {passed\_each(R,St,MinPass).}$

In Clark normal form, this can be written as

	$\displaystyle{passed\_each(L,S,M)\leftarrow\mbox{}L=[\,].}$
	$\displaystyle{passed\_each(L,S,M)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {\exists C~{}\exists R~{}L=[C\mid R]\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {passed(S,C,M)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {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

	$\displaystyle{\forall L~{}\forall S~{}\forall M~{}passed\_each(L,S,M)\iff L=[% \,]\vee{}}$
	$\displaystyle\ \ \ \ {\exists C~{}\exists R~{}(L=[C\mid R]\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {passed(S,C,M)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {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

	$\displaystyle{empty\_course(C)\leftarrow\mbox{}course(C)\wedge\mbox{}\mbox{$% \sim$}has\_enrollment(C).}$
	$\displaystyle{has\_enrollment(C)\leftarrow\mbox{}enrolled(S,C).}$

The completion of this is

	$\displaystyle{\forall C~{}empty\_course(C)\iff course(C)\wedge\mbox{}\neg has% \_enrollment(C).}$
	$\displaystyle{\forall C~{}has\_enrollment(C)\iff\exists 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:

Example 13.51.

One may be tempted to define $empty\_course$ in the following manner:

\displaystyle{empty\_course(C)\leftarrow\mbox{}course(C)\wedge\mbox{}\mbox{$% \sim$}enrolled(S,C).}

which has the completion

\displaystyle{\forall C~{}empty\_course(C)\iff\exists S~{}course(C)\wedge\mbox% {}\neg enrolled(S,C).}

This is not correct. Given the clauses

	$\displaystyle{course(cs422).}$
	$\displaystyle{course(cs486).}$
	$\displaystyle{enrolled(mary,cs422).}$
	$\displaystyle{enrolled(sally,cs486).}$

the clause

\displaystyle{empty\_course(cs422)\leftarrow\mbox{}course(cs422)\wedge\mbox{}% \mbox{$\sim$}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

\displaystyle{\forall C~{}empty\_course(C)\iff course(C)\wedge\mbox{}\neg% \exists S~{}enrolled(S,C).}

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

\displaystyle{\forall C~{}empty\_course(C)\iff course(C)\wedge\mbox{}\forall S% ~{}\neg enrolled(S,C).}

13.8.1 Complete Knowledge Assumption Proof Procedures

Artificial Intelligence 2E