15 Individuals and Relations 15.8 Equality 15.10 Social Impact

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

student(huan).

student(manpreet).

student(karan).

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

student(X)\leftrightarrow X=huan\vee X=manpreet\vee X=karan.

That is, if $X$ is $h u a n$ , $m a n p r e e t$ , or $k a r a n$ , 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 $kim\neq huan\wedge\mbox{}kim\neq manpreet\wedge\mbox{}kim\neq karan$ . 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

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

is the clause

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

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

\vdots

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

which is equivalent to

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

\forall V_{1}\ldots\forall V_{k}~{}p(V_{1},\ldots,V_{k})\leftrightarrow 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.

Example 15.42.

For the clauses

student(huan).

student(manpreet).

student(karan).

the Clark normal form is

student(V)\leftarrow\mbox{}V=huan.

student(V)\leftarrow\mbox{}V=manpreet.

student(V)\leftarrow\mbox{}V=karan.

which is equivalent to

student(V)\leftarrow\mbox{}V=huan\vee V=manpreet\vee V=karan.

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

\forall V~{}student(V)\leftrightarrow V=huan\vee V=manpreet\vee V=karan.

Example 15.43.

Consider the following recursive definition:

passed\_each([\,],St,MinPass).

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

passed(St,C,MinPass)\wedge\mbox{}

passed\_each(R,St,MinPass).

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

passed\_each(L,S,M)\leftarrow\mbox{}L=[\,].

passed\_each(L,S,M)\leftarrow\mbox{}

\exists C~{}\exists R~{}L=[C\mid R]\wedge\mbox{}

passed(S,C,M)\wedge\mbox{}

passed\_each(R,S,M).

Clark’s completion of $passed\_each$ is

\forall L~{}\forall S~{}\forall M~{}passed\_each(L,S,M)\leftrightarrow L=[\,]% \vee{}

\exists C~{}\exists R~{}(L=[C\mid R]\wedge\mbox{}

passed(S,C,M)\wedge\mbox{}

passed\_each(R,S,M)).

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

empty\_course(C)\leftarrow\mbox{}course(C)\wedge\mbox{}\mbox{$\sim$}has\_% enrollment(C).

has\_enrollment(C)\leftarrow\mbox{}enrolled(S,C).

The completion of this is

\forall C~{}empty\_course(C)\leftrightarrow course(C)\wedge\mbox{}\neg has\_% enrollment(C).

\forall C~{}has\_enrollment(C)\leftrightarrow\exists S~{}enrolled(S,C).

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

p(X)\leftarrow\mbox{}\mbox{$\sim$}q(X)\wedge\mbox{}r(X).

q(a).

q(b).

r(d).

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

When the top-down proof procedure encounters $\mbox{$\sim$}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)\leftarrow\mbox{}\mbox{$\sim$}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

p(X)\leftarrow\mbox{}\mbox{$\sim$}q(X)

q(X)\leftarrow\mbox{}\mbox{$\sim$}r(X)

r(a)

and the query

\mbox{{ask}~{}}~{}p(X).

The completion of the knowledge base is

p(X)\leftrightarrow\neg q(X)

q(X)\leftrightarrow\neg r(X)

r(X)\leftrightarrow X=a.

Substituting $X=a$ for $r$ gives $q(X)\leftrightarrow\neg X=a$ , and so $p(X)\leftrightarrow 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.

Artificial Intelligence 3E