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

5.5 Complete Knowledge Assumption

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

Example 5.24: 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 okay. Thus, down is the default value of switches, and okay 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 okay. 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 be known to the agent.

When there are rules for an atom, the assumption is that the rules for each atom cover all of the cases where the atom is true. In particular, suppose the rules for atom a are

a←b1.
     ...
a←bn.

where an atomic clause a is the rule a ←true. The complete knowledge assumption says that if a is true in some interpretation then one of the bi must be true in that interpretation; that is,

a→b1∨ ...∨ bn.

Because the clauses defining a are equivalent to

a←b1∨ ...∨ bn,

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

a↔b1∨ ...∨ bn,

where 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↔false, which means that a is false.

Example 5.25: Consider the following clauses from Example 5.5:
down_s1.
up_s2.
live_l1 ←live_w0.
live_w0 ←live_w1 ∧up_s2.
live_w0 ←live_w2 ∧down_s2.
live_w1 ←live_w3 ∧up_s1.

Suppose that these are the only clauses for the atoms in the heads of these clauses, and there are no clauses for up_s1 or down_s2. The completion of these atoms is

down_s1 ↔true.
up_s1 ↔false.
up_s2 ↔true.
down_s2 ↔false.
live_l1 ↔live_w0.
live_w0 ↔(live_w1 ∧up_s2) ∨(live_w2 ∧down_s2).
live_w1 ↔live_w3 ∧up_s1.

This implies that up_s1 is false, and live_w1 is false.

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 ∼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 KB'  |= g, where KB' is Clark's completion of KB. A negation ∼a in the body of a clause or the query becomes ¬a in the completion. That is, a query following 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.26: Consider the axiomatization of Example 5.5. 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:
down_s1 ←∼up_s1.
down_s2 ←∼up_s2.
down_s3 ←∼up_s3.

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

ok_cb1 ←∼broken_cb1.
ok_cb2 ←∼broken_cb2.

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 okay is normal for circuit breakers.

To represent the state of Figure 5.2, the user specifies

up_s2.
up_s3.

The system can infer that s1 must be down and both circuit breakers are okay.

The completion of the knowledge base is

down_s1 ↔¬up_s1.
down_s2 ↔¬up_s2.
down_s3 ↔¬up_s3.
ok_cb1 ↔¬broken_cb1.
ok_cb2 ↔¬broken_cb2.
up_s1↔false.
up_s2 ↔true.
up_s3 ↔true.
broken_cb1↔false.
broken_cb2↔false.

Notice that atoms in bodies of clauses but 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:

a ←∼b.
b ←∼a.

Clark's completion of this knowledge base is equivalent to a ↔¬b, which just specifies that a and b have different truth values but not which one is true.

The following knowledge base is not acyclic:

a ←∼a.

Clark's completion of this knowledge base is a ↔¬a, which is logically inconsistent.

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