Belief as Defeasible Knowledge

1 Introduction

Epistemic notions such as knowledge, ignorance, belief and awareness play an important role in AI. The ac­ tions available to an intelligent agent depend partly on his knowledge - for example, opening a safe depends on knowing the combination. Conversely, the effects of some actions are to change the state of knowledge - for example, informing another agent of a new fact. The no­ tion of belief is similarly involved in intelligent action - to use the same speech-act example above, agent A will only inform agent B of the new fact if agent A believes that agent B does not already know that fact , and as a result of the speech act agent B will believe that agent A indeed knows that fact.

In recent years there has been much interest in formal reasoning about knowledge and belief, in both the AI community and the distributed computation community. ~oti~ated by the need to represent the knowledge of mtelligent agents, and drawing on Hintikka's work in philosophy [6), Moore was the first to introduce the logic of knowledge to AI [10). Further work in AI on formal modeling of agents' epistemic states . includes [7, 9, 1) (the latter two concerned with distinguishing between

·The author was supported by NSF grant IRI-8721701, IBM grant 1220042, and a gift from DEC Corporation.

Yoram Moses

Department of Applied Mathematics The Weizmann Institute of Science Rehovot 76100, Israel

explicit and implicit belief). An introduction to modal epistemic logic in AI can be found in [3) . (Motivated by the need to represent the local knowledge of individual processors, the distributed computation community too has taken great interest in the topic. There has been a tremendous amount of work there, best represented by the proceedings of the two conferences devoted to the subject [5, 13) .) This is by no means an exhaustive list of references, either in AI or in distributed computation.

Our aim in this paper is to clarify the relation be­ tween knowledge and belief, probably the two most cen­ tral epistemic notions in AI. The old slogan is that ':knowledge is justified, true belief," suggesting that be­ lief should be taken as basic, and knowledge defined in terms of it. In fact, we know of few attempts to capture the two notions in the same formal system, and none which take this particular tack.

. One could imagine a second way of combining the no­ twns of knowledge and belief, which starts by defining them each separately. It has become standard to define epistemic notions through Kripke models, (although see [2) for an alternative to Kripke semantics). In the case of knowledge, one usually uses the simple S5 system (but see, e.g., [12) for arguments against the S5 system and for the S4 system) . This yields intuitive properties for knowledge: if I know cp then cp is true, if I know cp then I know that I know it, and (in the case of S5) if I don't know cp then I know that I don't know it. As is well known, these three properties are achieved by the axioms K cp ::::> cp, K cp ::::> K K cp, and -.K cp ::::> K -.K cp respectively (or, equivalently, by the requirement that the accessibility relation on possible worlds be reflexive transitive and Euclidean) . In addition one has the 'nor~ mality' condition, K(p ::::> q) I\ Kp ::::> Kq: An agent knows the tautological consequences of his knowledge.

Of these properties, the first one is clearly inappro­ priate for belief: I may believe something false. Indeed since this seems to be the property distinguishing knowl~ edge from belief, the common logic for belief is so-called K45, in which the K cp ::::> cp axiom (equivalently, the re­ flexivity requirement) is omitted. Sometimes another axiom is then added, -.K false (which corresponds to the requirement that the accessibility relation be serial: from every state there is at least one accessible state) re­ sulting in the system called KD45. Both K45 and KD45 have been called also weak S5.

One could thus imagine combining knowledge and be­ lief as follows: create two modalities, one (say) regular S5, the other (say) weak S5, and write enough axioms relating them to one another. Indeed, we know of at least one such attempt [8]. Although reasonable, this approach suffers a serious disadvantage: there is no the­ oretical basis for those added axioms, and therefore we have no guarantee that we have indeed captured the full connection between the two notions.

In this paper we offer a simple alternative: start with only a definition of knowledge, any definition that you find acceptable, and define belief as a defeasible version of it. Roughly speaking, we will translate each occur­ rence of "the agent believes that cp" into "the agent knows that either cp, or else something specific unusual is the case." For example, if the robot's vision system reports an obstacle then the robot believes that an obsta­ cle exists, since it knows that either the obstacle indeed exists , or else its vision system is malfunctioning (the latter considered unusual). The full definition we will adopt is only slightly more complex.

This definition of belief has several advantages. First, it is short. Second, we do not need to add anything to the logic of knowledge: the right properties of belief fall out of the definition and the properties of knowledge. Third, not only do we get a connection between knowl­ edge and belief, but we get it from one fundamental prin­ ciple, in a way that is more enlightening than a collection of arbitrary-seeming axioms relating the two notions. Fi­ nally, and most surprisingly, we note an added benefit of our definition: it suggests a close connection between the notion of belief and, of all things, nonmonotonic rea­ sonmg.

The paper is organized as follows. In Section 2 we give our definition of belief. In fact, we will give two such def­ initions, of which we will adopt one. Both are a general reduction of the notion of belief to that of knowledge, and do not assume any particular definition of knowl­ edge. In Section 3 we explore a particular instance of our definition, the one in which knowledge is taken to be defined by the S5 system. In Section 4 we tie the discussion to the notion of nonmonotonicity. We end in Section 5 with some concluding remarks and discussion of related work.

2 Defining belief

As was said in the introduction, we will reduce the no­ tion of belief to that of knowledge. We will not assume anything about the definition of knowledge, only that we have a language for describing the world, and that if cp is a wff in that language then so is K cp, meaning "the agent knows that cp" (we restrict the discussion in this article to a single agent, but the extension to multiple agents is straightforward).

Each formula that is believed will be believed only with respect to some other "assumption" formula. We start with a definition that is close to the one we will actually adopt. This initial definition is a direct trans­ lation of the sentence given in the introduction: we say that cp is believed just in case it is known that either cp holds or else that the assumption is violated.

We will see later that this simple definition actually has some attractive properties. However, it also has some properties that, under certain circumstances, we might not find acceptable. In particular, most logics of knowl­ edgeallowustoderiveK---.cpau :J B'(cp,cpa .. ): whenever we know that our assumption is violated, we must be­ lieve cp.

This motivates our final definition of belief. In the fol­ lowing definition, we add the condition that beliefs can­ not be grounded in assumptions that are actually known to be violated. Specifically, we require that a formula be believed relative to an assumption that is known not to hold, only if that formulamisexplicitly known.

We first note the following easily-seen connection be­ tween the two definitions of belief:

Proposition 1 ---.K ---.cpa .. :J (B'(cp, cpa .. ):= B(cp, cpa .. )) Indeed, as we explore the ramifications of our definition of B in the next section, we will also see that the dif­ ference between B and B' hinges on the possibility of knowing the negation of one's assumptions.

3 Properties of belief

Our definition of belief in the previous section was jus­ tified on intuitive grounds, if at all. Indeed, it was this intuition alone that originally led us to the definition. We now put it to a test by verifying that it has formal consequences that make sense. We have not discovered any undesirable consequences of our definition (but see discussion in the summary section). On the other hand, many desirable properties do follow from them. These include all the properties of belief that we have seen in previous formalisms, and some new ones.

In order to present crisp results, we will explore the ramification of our definitions in the context of a par­ ticular logic of knowledge, the S5 system described in the introduction. As was said, S5 is the most popu­ lar system for defining knowledge. Although it is very well known, for completeness we repeat the definition of (single-agent, propositional) S5 here. (Throughout this article we will restrict the discussion to the single-agent, propositional case, but it will be apparent that the dis­ cussion extends easily to the multiple-agent, first-order case.)

Definition 3

Syntax. Given a set of primitive propositions P, the for­ mulas of the logic consist of the members of P, their boolean closure (closure under 1\ and ---.), and their clo­ sure under the modal operator K.

Axiom system. Beside the axiom schemas of prop­ sotional calculus, the S5 axiom schemas consist of (K(cp1 :J cp2) 1\ Kepi) :J Kcp2 , Kcp :J cp, Kcp :J KKcp, and ---.K cp :J K ---.K cp. The rules of inference are modus ponens and generalization: from cp infer Kcp.

Semantics. S5 Kripke Structures are pairs (M, w), where M is a set of (total) valuations of P, and w is a member of M . The notion of a formula being satisfied in a K ripke structure is defined as follows . For primitive propositions p, (M, w) f= p iff w f= p, where the latter f= denotes standard propositional satisfaction. (M, w) f= cp1 1\ cpz iff (M, w) f= cp1 and (M, w) f= cp z. (M, w) f= ·cp iff it is not the case that (M, w) f= cp. Finally, (M, w) f= K cp (or simply M f= K cp) iff (M , w') f= cp for all w' E M.

As has been discussed extensively in the literature, K can be viewed as the knowledge operator, and thus K cp is read "cp is known" (or, in the general case, Kicp is read "agent i knows cp") .

Notational convention. When cpa .. can be inferred by context , or when it is not important what the particular assumption is , we will replace B(cp, cpa .. ) by B(cp) , or simply Bcp . We will do the same for B'. When several belief operators occur in the same sentence with omitted assumption arguments, we assume that all the assump­ tion formulas are the same. For example, Bpi\ Bq stands for B(p, r) 1\ B(q, r), where r is either understood from context , or else is any arbitrary formula.

We will concentrate on the properties of B, although at some points, when some properties of B' are illumi­ nating, we will make reference to B' too. We start by noting an equivalent definition of B. The definition reads "cp is believed iff it is known that either cp is indeed true, or else the assumption is violated without this violation being known":

Proposition 2 B(cp,cpa .. ) := K(cpV(·cpa,. I\·K·cpa .. ))

Proof.

B( cp , cpa,.) :=

K (cpa.. ::::> cp) 1\ ( K ·cp au ::::> K cp) :=

K(cp v ·cpa .. ) 1\ (Kcp v ·K·cpa.,) :=

K(cp V ·cpa.,) 1\ K(cp V ·K·cpa.,) :=

K( ( cp V ·cpa.,) 1\ ( cp V ·K ·cpa .. )) :=

K(cp V (·cpau A ·K·cpa .. ))

·

It is also easy to see that one cannot believe in contra­ dictory statements (and recall the notational convention of suppressing the assumption argument) :

Proposition 3 ·(Bcp 1\ B·cp)

Proof. Bcp 1\ B·cp := K(cp V (·cpa,. 1\ ·K·cpa.,)) l\ K(·cp V (·cpa., 1\ ·K ·cpa.,)) := K((cp 1\ ·cp) V (·cpa., 1\ ·K·cpa.,)) := K(· cpa,. 1\ ·K·cpa,.) := K ·cpa., 1\ ·K ·cpa.,) := ~" . Interestingly, for B' we get the following:

Proposition 4 B' ( cp , cpa··) 1\ B' ( ·cp, cpa .. ) := K ·cpa.,

Proof.

B'( cp, cpa.,) 1\ B' ( ·cp, cpa.,) :=

K(cp V ·cpa,.) 1\ K(·cp V ·cpa66 ) :=

K((cp V ·cp) 1\ ·cpa,.) :=

K·cpa.,

·

We now begin to explore the connection between knowledge and belief. The first connection is obvious:

Proposition 5 Kcp ::::> Bcp

The converse implication of course does not hold. Note that this proposition is true of B' too. Note also that the validity of the generalization inference rule, from cp infer Bcp, follows from the last proposition.

Proposition 6 BKcp = Kcp

·

The transitivity property of belief, or the property of "positive introspection," follows immediately:

Corollary 7 BEep= Bcp

Proposition 8 B·Kcp = ·Kcp

Proof.

B·Kcp :=

K·(Kcp V(·cpa·· 1\ ·K·cpa,. )) :=

·Kcp v K(·cpa·· 1\ ·K·cpa,.)) :=

·K cp V false =

·Kcp

·

As a corollary we get the "negative introspection" property:

Corollary 9 B·Bcp = ·Bcp

Recall that knowledge was defined essentially by the four axioms of S5. The last two corollaries show that two of the axioms hold for belief too. Another axiom, that of distributivity, also holds:

Proposition 10 B(cp1 ::::> cpz) 1\ Bcp1 ::::> Bcpz

Thus, through our one definition of B, we have ob­ tained a weak-S51ogic of belief!

The one remaining axiom S5, K cp ::::> cp, we would not want belief to have, and indeed it does not . We do, however, have that if our assumptions hold, then indeed our beliefs are correct:

Proposition 11 B(cp, cpa .. ) 1\ cpa .. ::::> cp

This is true of B' too, and in both cases the proof is immediate.

We now continue to explore the connection between B and K . We have seen that B K and B·K collapse to K and ·K, respectively. We now show that K B and K ·B collapse to B and ·B, respectively.

Proposition 12 K Bcp = Bcp

Proof.

KEep:=

KK(cp V(·cpa .. 1\ ·K·cpa .. )) :=

K(cp V(·cpa., 1\ ·K·cpa .. )) :=

Bcp

Proposition 13 K ·Bcp = ·Bcp

·

·

4 Knowledge, belief and nonmonotonic reasontng

So far we have paid little attention to the second argu­ ment to the belief operator. It turns out to be instructive to look at the assumptions more closely.

We first note the "belief weakening" property (some of the easy proofs below are omitted):

This property holds also for B'. One might have ex­ pected an analogous "assumption strengthening" prop­ erty. For B' this expectation is met:

The same fact, however, does not hold for B. Indeed, the way to understand the role of the assumption in B is as an assumption in nonmonotonic logics. On the basis of certain assumptions we are willing to adopt certain beliefs, but given more evidence we may discard some of them.

This point is further made when we examine the con­ ditions under which one can believe in, or even know, the very assumption in which the belief is grounded. In the following we assume a specific implicit assumption formula cpa ... Thus, Bcp stands for B( cp, cpa .. ). In par­ ticular, Bcpa .. stands for B(cpa · ., cpa.,)·

The B' operator holds few surprises in this regard. We have the following two easy facts:

Proposition 16 B' cpa ..

Thus, according to B', we always believe in the truth of our assumption, and the only time we believe in the negation of our assumption is also the only time beliefs can become inconsistent - when we actually know the assumption to be violated.

As far as believing the negation of the assumption, the B operator behaves identically:

Proposition 18 B·cpa .. := K ·cpa ..

K·cpa..

·

When it comes to believing that the assumption does hold, however, B behaves quite differently from B'. Ob­ viously, if we know that our assumption holds then we also believe that it does (knowledge entails belief), but in fact we believe in the assumption even under weaker conditions:

Proposition 19 Bcpa11 = ·K ·cpa ..

Proof. Bcpa., := K( cpa·· V ( ·cpa .. A ·K ·cpa .. )) :=

·

Now, this is an eminently nonmonotonic inference: as long as you don't know your assumption to be false , be­ lieve it to be true. Notice, however, that our logic is entirely monotonic. 1

As a corollary of the last two propositions, we get that we always take a stance towards our assumption; we ei­ ther know that it does not hold, or we believe that it does:

Of course, this last property does not hold for arbitrary cp's. Nor can we replace the B by a K : we do not nec­ essarily have complete knowledge about the truth of our assumptions. Intuitively speaking, if we know whether our assumption is true or false, it is no longer an assump­ tion. Indeed, we have the following property:

5 Summary and Discussion

We have offered a definition of belief as a defeasible form of knowledge, or as knowledge-relative-to-assumptions. The definition is short , and, we find, intuitive, deriving the connection between knowledge and belief from one basic principle. The definition, which was based on in­ tuitive understanding of knowledge and belief, turns out to be very robust. We have shown it to have formal consequences that one would expect from the concept of belief. We have also shown that the notion of belief strongly exhibits properties of nonmonotonic reasoning.

Our notion of belief originates from a definition given by the second author in [11] for belief in the context of distributed computation. There the definition for pro­ cessor i believing in cp was Ki ( ( i E .N) ~ cp), where N is the set of nonfaulty processors. This is clearly a special case of our B'. Otherwise, we know of little previous work on incorporating knowledge and belief within the same framework, and none which takes our approach. The most closely related work of which we are aware is by Kraus and Lehmann [8], who indeed introduce two modalities and relate them through axioms. Their ax­ ioms turn out to be a proper subset of the propositions proved in this paper. In addition, Halpern has recently proposed a probabilistic account of both knowledge and belief, in which knowledge is equated with certainty and belief with "almost certainty" [4]. Although on the one hand Halpern's account does not explicate the assump­ tion underlying belief, and on the other hand we do not explain the connection between statistical information and belief, there appears to be full compatibility between the two accounts.

1 Who was it that once said: "nonmonotonicity - !i, non­ monotonic logics - no!"

Finally, we note that our definition of belief does not rely on assuming a particular logic of knowledge. In this article we adopted the S5 system for two reasons : it is by far the most widely adopted system, and we needed some system in order to present crisp results. There are those who object to an S5 definition of knowledge. Some objections are mild, for example to the axiom of negative introspection ( -,K <p ::::> K -,K <p). Other objec­ tions are more extreme, for example to the assumption of deductive closure (the axiom (K(<p1 ::::> <pz) 1\ K<p1) ::::> K<p2). However , our definition of B(<p,<pa,.) =de f K( <pa .. ::::> <p) 1\ ( K -,<pa,. ::::> K <p) holds regardless of the meaning assigned to the K operator. For example, one could drop the axiom of negative introspection (and thus adopt the S4 system) , and remain with our definition of belief. Or, one might adopt the notion of resource­ bounded knowledge in [11). Of course, the specific prop­ erties of belief will change as we assume different logics of knowledge.

Indeed, several fascinating issues remain to be inves­ tigated:

• It will be interesting to explore the properties of belief that result from other notions of knowledge.
• We are interested in repercussions of our definition on notions such as common belief It can be shown to be be both intuitive and useful to base the no­ tion of common belief on the definition of belief as defeasible knowledge.
• -We have not given completeness results for the dervied notion of belief. For example, we have not shown that if we start with an 55 logic of knowledge, then the resulting notion of belief is complete for, e.g, weak 55. We believe that such a result will be rel­ atively easy to attain.
• All formal theories of commonsense leave open prag­ matic questions. For example, the theory of circum­ scription does not tell us which predicates to min­ imize and vary. Similarly, we have not presented guidelines for choosing which assumptions to make. Although these are not questions about logic itself, answers are crucial if we hope to integrate our re­ sults with other work in AI.

Acknowledgements

We thank Joe Halpern, Vladimir Lifschitz, Fangzhen Lin, John McCarthy and Amir Pnueli for their com­ ments, as we do quite a number of others who have dis­ cussed the paper with us.

References

• [1) R. Fagin and J . Y. Halpern. A logic of awareness. In Proc. 9th IJCAI, Los Angeles, CA, 1985.
• [2) R. Fagin and M. Y. Vardi. Internal semantics for modal logic. In Proc. 17th A CM Symp. on Theory of Computing, pages 305-315, 1985.
• [3) J. Y. Halpern andY. Moses. A guide to the modal logics of knowledge and belief: Preliminary draft. In Proc. IJCAI-85, pages 480-490, 1985.
• [4) J .Y. Halpern. Knowledge, belief and uncertainty. IBM technical report (to appear), 1988.
• [5) J .Y. Halpern, editor. Proceedings of the First Con­ ference on Theoretical issues in Reasoning about Knowledge. Morgan-Kaufmann, Monterey, CA, 1986.
• [6) J . Hintikka. Knowledge and Belief Cornell Univer­ sity Press, 1962.
• [7) K. Konolige. A Deduction Model of Belief Morgan­ Kaufmann/ Pitman, 1986.
• [8) S. Kraus and D. Lehmann. Knowledge, belief and time. Theoretical Computer Science, 58:155- 174, 1988.
• [9) H. Levesque. A logic of implicit and explicit be­ lief. In Proceedings of AAAI, pages 198-202, Austin, TX, August 1984.
• [10) R.C. Moore. Reasoning about Knowledge and Ac­ tion. PhD thesis, M.I.T. Artificial Intelligence Lab­ oratory, 1975.
• [11) Y. Moses. Resource-bounded knowledge. In M.Y. Vardi, editor, Proc. of the Second Conference on Theoretical Apsects of Reasoning about Knowledge, pages 261-275. Morgan-Kaufmann, May 1988.
• [12) M.Y. Vardi. A model-theoretic analysis of mono­ tonic knowledge. In Proc. 9th IJCAI, pages 509512, Los Angeles, CA, 1985.
• [13) M.Y. Vardi, editor. Proceedings of the Second Con­ ference on Theoretical issues in Reasoning about Knowledge. Morgan-Kaufmann, Monterey, CA, 1988.

(See next page for continuation of the article "Time for Action".)

Continuation of the article "Time for Action" in these proceedings.

Based on that I outlined a technical framework for combining time and action. Starting with a branch­ ing structure, I generalized the picture to set of par­ allel time lines, which can be thought of as represent­ ing knowledge at a particular point the real course of events.! defined the notion of evolving time-line struc­ tures (ETS's), which describe the increase of knowledge with time, and showed that they were closed under in­ tersection and union. I also showed that a certain view of agents' action itself induces an ETS. I concluded by showing that the closure of ETS's provides a natural mechanism for representing and combining knowledge of observers with different detail of knowledge.

I am not familiar with previous work that ties time, action and knowledge so tightly. Partial ties do exist . The view of action as choice making, and the use of par­ allel time lines to capture this, is most closely related to Pelavin and Allen's development in [Pelavin and Allen, 1987, Pelavin, 1988]. They choose to view action as a function mapping a time line and an interval to set of other time lines, in a way based loosely on a "closest world" construction. I have explained why there is no need to view action as changing the actual world, and how as a result we can account in the same framework for the knowledge of different observers. Combining knowl­ edge and time has not been done extensively in AI, prob­ ably the main example being [Shoham, 1987]. There has been some work on combining knowledge and action, most notably by Moore in [Moore, 1975].

The analysis here is incomplete in many ways. Here are two glaring examples.

• Actions were defined to depend only on what is true and false, not on knowledge. This should clearly be generalized to allow for actions such as dialing a phone number or opening a safe, which are dealt with by Moore in [Mooi:e, 1975].
• I have said that an advantage of actions is that they allow us to employ other intensional notions such as goals and beliefs, but I have not dealt with these no­ tions at all. I believe that they can be given intuitive meaning in the framework of time-line systems, in a way that extends the work in [Cohen and Levesque, 1987].