5.6 Complete Knowledge Assumption

A database is often complete in the sense that anything not implied is false.

Example 5.27.

You may want the user to specify which switches are up and which circuit breakers are broken so that the system can conclude that any switch not mentioned as up is down and any circuit breaker not specified as broken is ok. Thus, down is the default value of switches, and ok is the default value for circuit breakers. It is easier for users to communicate using defaults than it is to specify the seemingly redundant information about which switches are down and which circuit breakers are ok. To reason with such defaults, an agent must assume it has complete knowledge; a switch’s position is not mentioned because it is down, not because the agent does not know whether it is up or down.

The given definite-clause logic does not allow the derivation of a conclusion from a lack of knowledge or a failure to prove. It does not assume that the knowledge is complete. In particular, the negation of an atom can never be a logical consequence of a definite-clause knowledge base.

The complete knowledge assumption assumes that, for every atom, the clauses with the atom as the head cover all the cases when the atom is true. Under this assumption, an agent can conclude that an atom is false if it cannot derive that the atom is true. This is also called the closed-world assumption. It can be contrasted with the open-world assumption, which is that the agent does not know everything and so cannot make any conclusions from a lack of knowledge. The closed-world assumption requires that everything relevant about the world is known to the agent.

Suppose the clauses for atom $a$ are

	$\displaystyle{a\leftarrow\mbox{}b_{1}.}$
	$\displaystyle\ \ \ \ {\vdots}$
	$\displaystyle{a\leftarrow\mbox{}b_{n}.}$

where an atomic clause $a$ is treated as the rule $a\leftarrow\mbox{}true$ . The complete knowledge assumption specifies that if $a$ is true in some interpretation then one of the $b_{i}$ must be true in that interpretation; that is,

\displaystyle{a\rightarrow b_{1}\vee\ldots\vee b_{n}.}

Because the clauses defining $a$ are equivalent to

\displaystyle{a\leftarrow\mbox{}b_{1}\vee\ldots\vee b_{n}}

the meaning of the clauses can be seen as the conjunction of these two propositions, namely, the equivalence:

\displaystyle{a\iff b_{1}\vee\ldots\vee b_{n}}

where $\iff$ is read as “if and only if” (see Figure 5.1). This equivalence is called Clark’s completion of the clauses for $a$ . Clark’s completion of a knowledge base is the completion for each atom in the knowledge base.

Clark’s completion means that if there are no rules for an atom $a$ , the completion of this atom is $a\iff\mbox{false}$ , which means that $a$ is false.

Example 5.28.

Consider the clauses from Example 5.7:

	$\displaystyle{\mbox{down\_s}_{1}.}$
	$\displaystyle{\mbox{up\_s}_{2}.}$
	$\displaystyle{\mbox{ok\_cb}_{1}.}$
	$\displaystyle{\mbox{live\_l}_{1}\leftarrow\mbox{}\mbox{live\_w}_{0}.}$
	$\displaystyle{\mbox{live\_w}_{0}\leftarrow\mbox{}\mbox{live\_w}_{1}\wedge\mbox% {}\mbox{up\_s}_{2}.}$
	$\displaystyle{\mbox{live\_w}_{0}\leftarrow\mbox{}\mbox{live\_w}_{2}\wedge\mbox% {}\mbox{down\_s}_{2}.}$
	$\displaystyle{\mbox{live\_w}_{1}\leftarrow\mbox{}\mbox{live\_w}_{3}\wedge\mbox% {}\mbox{up\_s}_{1}.}$
	$\displaystyle{\mbox{live\_w}_{2}\leftarrow\mbox{}\mbox{live\_w}_{3}\wedge\mbox% {}\mbox{down\_s}_{1}.}$
	$\displaystyle{\mbox{live\_w}_{3}\leftarrow\mbox{}\mbox{live\_outside}\wedge% \mbox{}\mbox{ok\_cb}_{1}.}$
	$\displaystyle{\mbox{live\_outside}.}$

Suppose that these are the only clauses for the atoms in the heads of these clauses, and there are no clauses for $\mbox{up\_s}_{1}$ or $\mbox{down\_s}_{2}$ . The completion of these atoms is

	$\displaystyle{\mbox{down\_s}_{1}\iff\mbox{true}.}$
	$\displaystyle{\mbox{up\_s}_{1}\iff\mbox{false}.}$
	$\displaystyle{\mbox{up\_s}_{2}\iff\mbox{true}.}$
	$\displaystyle{\mbox{down\_s}_{2}\iff\mbox{false}.}$
	$\displaystyle{\mbox{ok\_cb}_{1}\iff\mbox{true}.}$
	$\displaystyle{\mbox{live\_l}_{1}\iff\mbox{live\_w}_{0}.}$
	$\displaystyle{\mbox{live\_w}_{0}\iff(\mbox{live\_w}_{1}\wedge\mbox{}\mbox{up\_% s}_{2})\vee\mbox{}(\mbox{live\_w}_{2}\wedge\mbox{}\mbox{down\_s}_{2}).}$
	$\displaystyle{\mbox{live\_w}_{1}\iff\mbox{live\_w}_{3}\wedge\mbox{}\mbox{up\_s% }_{1}.}$
	$\displaystyle{\mbox{live\_w}_{2}\iff\mbox{live\_w}_{3}\wedge\mbox{}\mbox{down% \_s}_{1}.}$
	$\displaystyle{\mbox{live\_w}_{3}\iff\mbox{live\_outside}\wedge\mbox{}\mbox{ok% \_cb}_{1}.}$
	$\displaystyle{\mbox{live\_outside}\iff\mbox{true}.}$

This implies that $\mbox{up\_s}_{1}$ is false, $\mbox{live\_w}_{1}$ is false and $\mbox{live\_w}_{2}$ is true.

With the completion, the system can derive negations, and so it is useful to extend the language to allow negations in the body of clauses. A literal is either an atom or the negation of an atom. The definition of a definite clause can be extended to allow literals in the body rather than just atoms. We write the negation of atom $a$ under the complete knowledge assumption as $\mbox{$\sim$}a$ to distinguish it from classical negation that does not assume the completion. This negation is often called negation as failure.

Under negation as failure, body $g$ is a consequence of the knowledge base KB if $\mbox{KB}^{\prime}\models g$ , where $\mbox{KB}^{\prime}$ is Clark’s completion of KB. A negation $\mbox{$\sim$}a$ in the body of a clause or the query becomes $\neg a$ in the completion. That is, a query follows from a knowledge base under the complete knowledge assumption means that the query is a logical consequence of the completion of the knowledge base.

Example 5.29.

Consider the axiomatization of Example 5.7. Representing a domain can be made simpler by expecting the user to tell the system only what switches are up and by the system concluding that a switch is down if it has not been told the switch is up. This can be done by adding the following rules:

	$\displaystyle{\mbox{down\_s}_{1}\leftarrow\mbox{}\mbox{$\sim$}\mbox{up\_s}_{1}.}$
	$\displaystyle{\mbox{down\_s}_{2}\leftarrow\mbox{}\mbox{$\sim$}\mbox{up\_s}_{2}.}$
	$\displaystyle{\mbox{down\_s}_{3}\leftarrow\mbox{}\mbox{$\sim$}\mbox{up\_s}_{3}.}$

Similarly, the system may conclude that the circuit breakers are ok unless it has been told they are broken:

	$\displaystyle{\mbox{ok\_cb}_{1}\leftarrow\mbox{}\mbox{$\sim$}\mbox{broken\_cb}% _{1}.}$
	$\displaystyle{\mbox{ok\_cb}_{2}\leftarrow\mbox{}\mbox{$\sim$}\mbox{broken\_cb}% _{2}.}$

Although this may look more complicated than the previous representation, it means that is it easier for the user to specify what is occurring in a particular situation. The user has to specify only what is up and what is broken. This may save time if being down is normal for switches and being ok is normal for circuit breakers.

To represent the state of Figure 5.2, the user specifies

	$\displaystyle{\mbox{up\_s}_{2}.}$
	$\displaystyle{\mbox{up\_s}_{3}.}$

The system can infer that $s_{1}$ must be down and both circuit breakers are ok.

The completion of the knowledge base consisting of the clauses above is

	$\displaystyle{\mbox{down\_s}_{1}\iff\neg\mbox{up\_s}_{1}.}$
	$\displaystyle{\mbox{down\_s}_{2}\iff\neg\mbox{up\_s}_{2}.}$
	$\displaystyle{\mbox{down\_s}_{3}\iff\neg\mbox{up\_s}_{3}.}$
	$\displaystyle{\mbox{ok\_cb}_{1}\iff\neg\mbox{broken\_cb}_{1}.}$
	$\displaystyle{\mbox{ok\_cb}_{2}\iff\neg\mbox{broken\_cb}_{2}.}$
	$\displaystyle{\mbox{up\_s}_{1}\iff\mbox{false}.}$
	$\displaystyle{\mbox{up\_s}_{2}\iff\mbox{true}.}$
	$\displaystyle{\mbox{up\_s}_{3}\iff\mbox{true}.}$
	$\displaystyle{\mbox{broken\_cb}_{1}\iff\mbox{false}.}$
	$\displaystyle{\mbox{broken\_cb}_{2}\iff\mbox{false}.}$

Notice that atoms that are in the bodies of clauses but are not in the head of any clauses are false in the completion.

Recall that a knowledge base is acyclic if there is an assignment of natural numbers (non-negative integers) to the atoms so that the atoms in the body of a clause are assigned a lower number than the atom in the head. With negation as failure, non-acyclic knowledge bases become semantically problematic.

The following knowledge base is not acyclic:

	$\displaystyle{a\leftarrow\mbox{}\mbox{$\sim$}b.}$
	$\displaystyle{b\leftarrow\mbox{}\mbox{$\sim$}a.}$

Clark’s completion of this knowledge base is equivalent to $a\iff\neg b$ , which just specifies that $a$ and $b$ have different truth values but not which one is true.

The following knowledge base is also not acyclic:

\displaystyle{a\leftarrow\mbox{}\mbox{$\sim$}a.}

Clark’s completion of this knowledge base is $a\iff\neg a$ , which is logically inconsistent.

Clark’s completion of an acyclic knowledge base is always consistent and always gives a unique truth value to each atom. For the rest of this chapter, we assume that the knowledge bases are acyclic.

5.6.1 Non-monotonic Reasoning

5.6.2 Proof Procedures for Negation as Failure

Artificial Intelligence 2E

5.6 Complete Knowledge Assumption

Example 5.27.

Example 5.28.

Example 5.29.

Artificial
Intelligence 2E