5 Propositions and Inference 5.6 Proving by Contradiction 5.8 Abduction

5.7 Complete Knowledge Assumption

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

Example 5.25.

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. In particular, an atom with no clauses is false. 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.

This assumption that there is a definition of each atom in terms of clauses is the basis of logic programming. Here we give the propositional version; richer variants are presented in Section 15.4 and Section 15.6.

Suppose the clauses for atom $a$ are

a\leftarrow\mbox{}b_{1}.

\vdots

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,

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

Because the clauses defining $a$ are equivalent to

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

a\leftrightarrow b_{1}\vee\ldots\vee b_{n}

where $\leftrightarrow$ 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$ , then the completion of this atom is $a\leftrightarrow false$ , which means that $a$ is false.

Example 5.26.

Consider the clauses from Example 5.8:

{down\_s}_{1}.

{up\_s}_{2}.

{ok\_cb}_{1}.

{live\_l}_{1}\leftarrow\mbox{}{live\_w}_{0}.

{live\_w}_{0}\leftarrow\mbox{}{live\_w}_{1}\wedge\mbox{}{up\_s}_{2}.

{live\_w}_{0}\leftarrow\mbox{}{live\_w}_{2}\wedge\mbox{}{down\_s}_{2}.

{live\_w}_{1}\leftarrow\mbox{}{live\_w}_{3}\wedge\mbox{}{up\_s}_{1}.

{live\_w}_{2}\leftarrow\mbox{}{live\_w}_{3}\wedge\mbox{}{down\_s}_{1}.

{live\_w}_{3}\leftarrow\mbox{}{live\_outside}\wedge\mbox{}{ok\_cb}_{1}.

{live\_outside}.

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

{down\_s}_{1}\leftrightarrow true.

{up\_s}_{1}\leftrightarrow false.

{up\_s}_{2}\leftrightarrow true.

{down\_s}_{2}\leftrightarrow false.

{ok\_cb}_{1}\leftrightarrow true.

{live\_l}_{1}\leftrightarrow{live\_w}_{0}.

{live\_w}_{0}\leftrightarrow({live\_w}_{1}\wedge\mbox{}{up\_s}_{2})\vee\mbox{}% ({live\_w}_{2}\wedge\mbox{}{down\_s}_{2}).

{live\_w}_{1}\leftrightarrow{live\_w}_{3}\wedge\mbox{}{up\_s}_{1}.

{live\_w}_{2}\leftrightarrow{live\_w}_{3}\wedge\mbox{}{down\_s}_{1}.

{live\_w}_{3}\leftrightarrow{live\_outside}\wedge\mbox{}{ok\_cb}_{1}.

{live\_outside}\leftrightarrow true.

This implies that ${up\_s}_{1}$ is false, ${live\_w}_{1}$ is false, and ${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 ${KB}^{\prime}\models g$ , where ${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.27.

Consider the axiomatization of Example 5.8. 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\_s}_{1}\leftarrow\mbox{}\mbox{$\sim$}{up\_s}_{1}.

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

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

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

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

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

Although this may look more complicated than the previous representation, it means that it is 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

{up\_s}_{2}.

{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

{down\_s}_{1}\leftrightarrow\neg{up\_s}_{1}.

{down\_s}_{2}\leftrightarrow\neg{up\_s}_{2}.

{down\_s}_{3}\leftrightarrow\neg{up\_s}_{3}.

{ok\_cb}_{1}\leftrightarrow\neg{broken\_cb}_{1}.

{ok\_cb}_{2}\leftrightarrow\neg{broken\_cb}_{2}.

{up\_s}_{1}\leftrightarrow false.

{up\_s}_{2}\leftrightarrow true.

{up\_s}_{3}\leftrightarrow true.

{broken\_cb}_{1}\leftrightarrow false.

{broken\_cb}_{2}\leftrightarrow 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:

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

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

Clark’s completion of this knowledge base is equivalent to $a\leftrightarrow\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:

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

Clark’s completion of this knowledge base is $a\leftrightarrow\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.7.1 Non-Monotonic Reasoning

A logic is monotonic if any proposition that can be derived from a knowledge base can also be derived when extra propositions are added to the knowledge base. That is, adding knowledge does not reduce the set of propositions that can be derived. The definite-clause logic is monotonic.

A logic is non-monotonic if some conclusions can be invalidated by adding more knowledge. The logic of definite clauses with negation as failure is non-monotonic. Non-monotonic reasoning is useful for representing defaults. A default is a rule that can be used unless it is overridden by an exception.

For example, to say that $b$ is normally true if $c$ is true, a knowledge base designer can write a rule of the form

b\leftarrow\mbox{}c\wedge\mbox{}\mbox{$\sim$}{ab\_a}.

where ${ab\_a}$ is an atom that means abnormal with respect to some aspect $a$ . Given $c$ , the agent can infer $b$ unless it is told ${ab\_a}$ . Adding ${ab\_a}$ to the knowledge base can prevent the conclusion of $b$ . Rules that imply ${ab\_a}$ can be used to prevent the default under the conditions of the body of the rule.

Example 5.28.

Suppose the purchasing agent is investigating purchasing holidays. A resort may be adjacent to a beach or away from a beach. This is not symmetric; if the resort were adjacent to a beach, the knowledge provider would specify this. Thus, it is reasonable to have the clause

{away\_from\_beach}\leftarrow\mbox{}\mbox{$\sim$}{on\_beach}.

This clause enables an agent to infer that a resort is away from the beach if the agent is not told it is on a beach.

A cooperative system tries to not mislead. If we are told the resort is on the beach, we would expect that resort users would have access to the beach. If they have access to a beach, we would expect them to be able to swim at the beach. Thus, we would expect the following defaults:

{beach\_access}\leftarrow\mbox{}{on\_beach}\wedge\mbox{}\mbox{$\sim$}{ab\_% beach\_access}.

{swim\_at\_beach}\leftarrow\mbox{}{beach\_access}\wedge\mbox{}\mbox{$\sim$}{ab% \_swim\_at\_beach}.

A cooperative system would tell us if a resort on the beach has no beach access or if there is no swimming. We could also specify that, if there is an enclosed bay and a big city, then there is no swimming, by default:

{ab\_swim\_at\_beach}\leftarrow\mbox{}{enclosed\_bay}\wedge\mbox{}{big\_city}% \wedge\mbox{}\mbox{$\sim$}{ab\_no\_swimming\_near\_city}.

We could say that British Columbia (BC) is abnormal with respect to swimming near cities:

{ab\_no\_swimming\_near\_city}\leftarrow\mbox{}{in\_BC}\wedge\mbox{}\mbox{$% \sim$}{ab\_BC\_beaches}.

Given only the preceding rules, an agent infers ${away\_from\_beach}$ . If it is then told ${on\_beach}$ , it can no longer infer ${away\_from\_beach}$ , but it can now infer ${beach\_access}$ and ${swim\_at\_beach}$ . If it is also told ${enclosed\_bay}$ and ${big\_city}$ , it can no longer infer ${swim\_at\_beach}$ . However, if it is then told ${in\_BC}$ , it can then infer ${swim\_at\_beach}$ .

By having defaults of what is normal, a user can interact with the system by telling it what is abnormal, which allows for economy in communication. The user does not have to state the obvious.

One way to think about non-monotonic reasoning is in terms of arguments. The rules can be used as components of arguments, in which the negated abnormality gives a way to undermine arguments. Note that, in the language presented, only positive arguments exist, so these are the only ones that can be undermined. In more general theories, there can be positive and negative arguments that attack each other.

5.7.2 Proof Procedures for Negation as Failure

Bottom-Up Procedure

The bottom-up proof procedure for negation as failure is a modification of the bottom-up procedure for definite clauses. The difference is that it can add literals of the form $\mbox{$\sim$}p$ to the set $C$ of consequences that have been derived; $\mbox{$\sim$}p$ is added to $C$ when it can determine that $p$ must fail.

Failure can be defined recursively: $p$ fails when every body of a clause with $p$ as the head fails. A body fails if one of the literals in the body fails. An atom $b_{i}$ in a body fails if $\mbox{$\sim$}b_{i}$ can be derived. A negation $\mbox{$\sim$}b_{i}$ in a body fails if $b_{i}$ can be derived.

1: procedure Prove_NAF_BU(

{KB}

)

2: Inputs

{KB}

: a set of clauses that can include negation as failure

4: Output

5: set of literals that follow from the completion of

{KB}

6: Local

C

is a set of literals

C\;{:}{=}\;\mbox{}\{\}

9: repeat

10: either

11: select

r\in{KB}

such that

12:

r

is “

h\leftarrow\mbox{}b_{1}\wedge\mbox{}\ldots\wedge\mbox{}b_{m}

”

13:

b_{i}\in C

for all

i

, and

14:

h\notin C;

15:

C\;{:}{=}\;\mbox{}C\cup\{h\}

16: or

17: select

h

such that

\mbox{$\sim$}h\notin C

and

18: where for every clause “

h\leftarrow\mbox{}b_{1}\wedge\mbox{}\ldots\wedge\mbox{}b_{m}

”

\in{KB}

19: either for some

b_{i},\mbox{$\sim$}b_{i}\in C

20: or some

b_{i}=\mbox{$\sim$}g

and

g\in C

21:

C\;{:}{=}\;\mbox{}C\cup\{\mbox{$\sim$}h\}

22: until no more selections are possible

Figure 5.11: Bottom-up negation as failure proof procedure

Figure 5.11 gives a bottom-up negation-as-failure interpreter for computing consequents of a ground ${KB}$ . Note that this includes the case of a clause with an empty body (in which case $m=0$ and the atom at the head is added to $C$ ) and the case of an atom that does not appear in the head of any clause (in which case its negation is added to $C$ ).

Example 5.29.

Consider the following clauses:

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

p\leftarrow\mbox{}s.

q\leftarrow\mbox{}\mbox{$\sim$}s.

r\leftarrow\mbox{}\mbox{$\sim$}t.

t .

s\leftarrow\mbox{}w.

The following is a possible sequence of literals added to $C$ :

\displaystyle{t},~{}~{}{\mbox{$\sim$}r},~{}~{}{\mbox{$\sim$}w},~{}~{}{\mbox{$% \sim$}s},~{}~{}{q},~{}~{}{p}

where $t$ is derived trivially because it is given as an atomic clause; $\mbox{$\sim$}r$ is derived because $t\in C$ ; $\mbox{$\sim$}w$ is derived as there are no clauses for $w$ , and so the “for every clause” condition of line 18 of Figure 5.11 trivially holds. Literal $\mbox{$\sim$}s$ is derived as $\mbox{$\sim$}w\in C$ ; and $q$ and $p$ are derived as the bodies are all proved.

Top-Down Negation-as-Failure Procedure

The top-down procedure for the complete knowledge assumption proceeds by negation as failure. It is similar to the top-down definite-clause proof procedure of Figure 5.4. This is a non-deterministic procedure (see the box) that can be implemented by searching over choices that succeed. When a negated atom $\mbox{$\sim$}a$ is selected, a new proof for atom $a$ is started. If the proof for $a$ fails, $\mbox{$\sim$}a$ succeeds. If the proof for $a$ succeeds, the algorithm fails and must make other choices. The algorithm is shown in Figure 5.12.

1: non-deterministic procedure Prove_NAF_TD(

{KB},{Query}

)

2: Inputs

{KB}

: a set of clauses that can include negation as failure

{Query}

: a set of literals to prove

5: Output

{yes}

if completion of

{KB}

entails

{Query}

and

f a i l

otherwise

7: Local

G

is a set of literals

G\;{:}{=}\;\mbox{}{Query}

10: repeat

11: select literal

l\in G

12: if

l

is of the form

\mbox{$\sim$}a

then

13: if

{Prove\_NAF\_TD}({KB},a)

fails then

14:

G\;{:}{=}\;\mbox{}G\setminus\{l\}

15: else

16: fail

17: else

18: choose clause “

l\leftarrow\mbox{}B

” in

{KB}

with

l

as head

19:

G\;{:}{=}\;\mbox{}G\setminus\{l\}\cup B

20: until

G=\{\}

21: return

{yes}

Figure 5.12: Top-down negation as failure interpreter

Example 5.30.

Consider the clauses from Example 5.29. Suppose the query is $\mbox{{ask}~{}}~{}p$ .

Initially, $G=\{p\}$ .

Using the first rule for $p$ , $G$ becomes $\{q,\mbox{$\sim$}r\}$ .

Selecting $q$ , and replacing it with the body of the third rule, $G$ becomes $\{\mbox{$\sim$}s,\mbox{$\sim$}r\}$ .

It then selects $\mbox{$\sim$}s$ and starts a proof for $s$ . This proof for $s$ fails, and thus $G$ becomes $\{\mbox{$\sim$}r\}$ .

It then selects $\mbox{$\sim$}r$ and tries to prove $r$ . In the proof for $r$ , there is the subgoal $\mbox{$\sim$}t$ , and so it tries to prove $t$ . This proof for $t$ succeeds. Thus, the proof for $\mbox{$\sim$}t$ fails and, because there are no more rules for $r$ , the proof for $r$ fails. Therefore, the proof for $\mbox{$\sim$}r$ succeeds.

$G$ is empty and so it returns ${yes}$ as the answer to the top-level query.

Note that this implements finite failure, because it makes no conclusion if the proof procedure does not halt. For example, suppose there is just the rule $p\leftarrow\mbox{}p$ . The algorithm does not halt for the query $\mbox{{ask}~{}}~{}p$ . The completion, $p\leftrightarrow p$ , gives no information. Even though there may be a way to conclude that there will never be a proof for $p$ , a sound proof procedure should not conclude $\mbox{$\sim$}p$ , as it does not follow from the completion.

Artificial Intelligence 3E