Epistemic Extension of Propositional Preference Logics

1 Introduction

Reasoning about other agents, and in par­ ticular reasoning about the beliefs of other agents, is of fundamental importance if an intelligent system is to deal with social sit­ uations. But the logics that have been created to deal with knowledge of more than one agent (for example [Halpern and Moses, 1985]) have the limitation that the agents they model are monotonic. Since it is widely assumed that interesting forms of intelligence cannot be captured by mono­ tonic forms of reasoning, these logics are very limited on their capacity of modeling interesting social behavior.

On the other hand, most of the ex­ isting nonmonotonic logics are limited to a first-order or a propositional language. That is, although these logics capture the nonmonotonicity of the agent's reasoning, they can only model the agent when it is reasoning about "things in the world," which can be expressed in either first-order or propositional languages. In particu­ lar, the existing nonmonotonic logics can­ not model an agent reasoning about the knowledge of another agent.

Summarizing, the existing formal de­ vices either model many "uninteresting" agents, or they can model only a single interesting agent . This paper addresses this problem: it describe a nonmonotonic logic that can model an agent reasoning about the knowledge of other nonmono­ tonic agents.

The approach taken in this paper is to extend some of the existing non­ monotonic logics to include formulas that refer to another agent's knowledge. We call these logics epistemically ex­ tended. This involves extending the se­ mantics of a nonmonotonic logics since most formalism (with the exception of de­ fault logic) are semantically limited to ei­ ther propositional or first-order languages. This paper will also discuss the require­ ments that an epistemically extended logic should exhibit if it is to model the knowl­ edge of other non-monotonic agents.

The paper is divided into two parts. The first part discusses the requirements that an epistemic extended logic should meet in the context of a model of com­ munication (or at least a model of utter­ ance understanding). Section 2 describes a model of utterance understanding that solves some of the problems a naive the­ ory would face, but this paper will not deal with the consequences of this model. In­ stead, we use the model to motivate the need of an epistemically extended logic, and to find out what are the require­ ments that the logic should meet. The sec­ ond part discusses a method of extending propositional preference logics into epis­ temic domains, and proves that the result­ ing logic meets the requirements put forth in the first part.

2 A Model of Communication

McCarthy [1986] suggested that one of the many uses of nonmonotonic logics is to model conventions in communication. For example, the default rule "birds usually fly" can be seen as stating that if in a con­ versation a bird is mentioned and nothing is said about its flying condition, then one can assume that it flies. More specifically, if S (for speaker) tells H (for hearer) about a bird, and S says nothing about the bird's ability to flight, then H should conclude that the bird flies .

McCarthy suggests that H's reasoning can be done entirely within a first-order framework. This is done by representing the content of S's assertion as a first-order formula in H's belief space, and combining it with H's beliefs about birds in general, and Tweety in particular . H would then perform the following nonmonotonic infer­ ence:

Tweety is a bird Usually, birds fly

Tweety flies .

which McCarthy implements usmg Cir­ cumscription.

We will call this method of modeling H's ·reasoning the import-default method, because the content of the utterance is first imported into H's belief space, and only after that are the defaults inferred. The import-default method has many short­ comings. First, it does not allow for the modeling of S's beliefs and the mutual be­ liefs between S and H . A second short­ coming comes from the import process it­ self. If S's statement contradicts with H's beliefs, then H would not like to import it, and thus resulting in a contradictory knowledge base. Also, H would not like to import the content of the utterance if H has reason to believe that S is lying (and that can only be concluded if we compare the content of the utterance with S's own knowledge and not H's).

Although the previous two problems could be addressed by some extra-logic mechanism (for example by first check­ ing the utterance against S's beliefs and only if it is not contradictory perform the import process), there is a third prob­ lem that undermines the assumption that the reasoning can be done in a first-order framework. For a class of utterances that we named epistemic cancellations, the speaker uses the epistemic possibility op­ erator to cancel (or block) the defaults. For example, by uttering

Tweety is a bird, perhaps a penguin.

(1)

the speaker blocks the default that Tweety flies. The semantic content of the utter­ ance, even after it is imported into H's be­ lief space, still carries the modal operator.

These shortcomings suggest that a more elaborate method to model understand­ ing of utterances should be pursued. This method is based on explicitly reasoning about the S's beliefs, followed by a trans­ ferring step, where H accepts S's beliefs (or what he thinks areS's beliefs) as his own . This method is called belief transfer and was first discussed in [Perrault, 1990] .

2.1 The belief transfer method

Like the import-default, the belief-transfer is a model of the hearer's reasoning pro­ cess. But instead of importing the con­ tent of the utterance directly into the his own belief space and deriving the defaults in that space, H derives the defaults in S's belief space (or in his view of the S 's belief space) and then transfer consistent beliefs from that space into his own. The belief transfer method is based on the following defaults:

• the speaker usually believes in what she says. This is Grice's maxim of quality
• if the speaker believes that a default

rule holds, and that the antecedent of this default rule also holds, and that the conse­ quence of the default does not contradicts with what else the speaker believes, then the speaker believes in the consequent of the default .

• if the hearer believes that the speaker believes in p and p does not contradicts with the hearer's beliefs, then the hearer should also believe p. This is the belief­ transfer process.

The first default above deals with the concept of "saying" which is outside the scope of this paper and we will not at­ tempt to formalize it . The formalization of the two other defaults will shed some light on what should be the properties of an epistemically extended logic.

We will model the defaults above from the hearer's point of view. This approach is what McArthur [1988] calls an inter­ nal logic, that is, a logic that assumes a particular agent 's point of view instead of describing the reality. All formulas will implicitly refer to the hearer's knowledge, and thus asserting a formula a states that the hearer knows a .

We will use the modal operator B to refer to the hearer 's belief about the speaker's knowledge. Thus, the formula p 1\ Bq states that the hearer believes p and he believes the speaker believes q. We will also use the symbol "--..." as a generic representation of a default rule. Thus "p --... q" represents the rule "p's are usu­ ally q's." The symbol "--..." is a meta­ level symbol that abbreviates the way a default rule is represented in a particu­ lar logic. For example, in circumscrip­ tion , the default p --... q is implemented asp 1\ -.abnt -+ q where abnt is one of the predicates being minimized . The symbol "1-" is the consequence relation of the non­ monotonic logic.

Given this representation scheme one can describe the basic defaults of the belief-transfer model in a formal way. They are:

Expression (2) capture the hearer 's belief that the speaker can perform nonmono­ tonic reasoning. And expression (3) is the belief transfer rule.

Expressions (2) and (3) make it clear some of the requirement for the consequence relation "1- ." To be able to perform the reasoning described in (2) and (3), one must extend the existing formalisms in at least two directions. The first one is to al­ low defaults inside a knowledge operator, which is exemplified by expression (2) . We call this extension internal default . . Be­ side the fact that the syntax of the logic should allow for a default rule inside the scope of the knowledge operator , which is a problem for default logic the application of a default rule should work normally in­ side the knowledge operator. That is, if from p --... q and p, one concludes q, then from B(p --... q] and Bp one should con­ clude Bq.

The second direction in which the ex­ isting formalism must be extended is to allow for default rules whose arguments are modal formulas. We call this exten­ sion external default , and it is best il­ lustrated when (3) is expressed as the ap­ plication of a default rule:

The logic should allow ·for default rules to have one or more arguments that are modal formulas , and these default rules should derive the "expected" conclusions when they are applied.

2.2 Assumptions

In this paper we will follow simplifications below:

1. We will assume that the knowledge operator is a modal operator that follows the KD45 (or weak S5) axioms .
2. We will restrict the language to a propositional modal language.
3. We will not deal with multiple agents (besides the speaker and the hearer) and we will not deal with nested knowledge , that is, the speaker's belief about the hearer's beliefs, and so on.

We introduced this last simplification, which severely limits the applicability of the logics developed here in modeling communication, in order to avoid multi­ modalities. For example, having to repre­ sent nested beliefs would bring the need of a modal operator to represent the hearer's beliefs (which is done implicitly now) when it occurs within the scope of the speaker's beliefs (the speaker think­ ing about the hearer) . We believe that this last simplification can be incrementally weakened, resulting in more interest­ ing logics.

2.3 Notation

We will use the following notations. The greek letters t/J, ¢, ( denote formulas that may or may not contain a modal opera­ tor (the operator B or it's dual P) . The greek letters a, {3, r, and 8 denote propo­ sitional formulas, that is formulas without modal operators. The letters p, q and so on denote propositional symbols.

3 Requirements for epistemically extended logics

In this section we define the require­ ments that the epistemically extended 'log­ ics should exhibit. Among other things, we formalize the intuitions of the internal and external defaults discussed above.

If .Cx is a propositional nonmonotonic logic and f- x is the entailment or con­ sequence relation of that logic, then we would like to define an epistemically ex­ tended logic .Cx, which extends the lan­ guage of .Cx to a modal propositional lan­ guage, and also extends the entailment relation appropriately. f-~ is the conse­ quence or entailment relation of the logic ex.

The first requirement is that the logic .Cx should have the same power as the logic .Cx when dealing only with proposi­ tional formulas. This means that the logic .Cx should yield the same results as .Cx for propositional formulas . We call this re­ quirement extension, abbreviated as E , and it can be captured formally as:

The second requirement is that the logic .Cx should include the logic chosen to rep­ resent knowledge, in this case KD45. We call this requirement KD45-inclusion, or KD45i, and it can be formalized as:

The logic .Cx should also capture the mode of reasoning that we named internal default in (2). We call this property of .Cx internal default (ID). The formulation below extends the idea of defaults working inside the knowledge operator.

If a above, contains both a default rule .and its antecedent (for example p ...__. q and p) then it will correspond to the in­ ternal default as expressed in (2) . The for­ mulation above also captures the interest­ ing intuition that the hearer believes that speaker has the same propositional reason­ ing power as himself. If the hearer can de­ duce f3 from a, then he believes that if the the speaker believes a then she would also believe {3 .

The forth requirement is related to the external defaults . The logic .Cx to be able to have default rules with modal sub­ formulas as arguments, and these default rules should generate "expected" conclu­ siOns. For example if

is an entailment of the logic .Cx , then both

should also be correct entailments in the logic .Cx . It is somewhat difficult to capture this intuition formally. We will propose a weaker characterization since a complete formalization still elude us. The weak characterization of the external de­ fault requirement, abbreviated as WED, is an extension of (6), when p and q are general propositional formulas . That is:

Expression (7) above does not capture the full intuition behind external default be­ cause, for example, it does not deal with conflicting defaults . If:

Finally, the last requirement is related to epistemic cancellation and the intu­ itions behind it require some further elab­ oration.

3.0.1 Epistemic Cancellation

As mentioned above, epistemic cancel­ lation are a class of utterances in which the speaker uses the epistemic possibil­ ity operator to cancel or block a default that would otherwise be attributed to her. For example, if the speaker had uttered: "Tweety is a bird." and given the de­ fault that birds usually fly, the hearer should conclude that the speaker knows that Tweety flies. Epistemic cancella­ tion is a way of canceling this knowledge attribution by explicitly saying that the speaker believes it to be possible that the default would not hold in this case. Thus by uttering ( 1) the speaker is explicitly saying that she considers it possible that Tweety is a penguin and therefore that Tweety cannot fly. This blocks the conclu­ sion that the speaker believes that Tweety could fly.

But , although it is clear what should not be inferred about the speaker beliefs from (1), it is less clear what should be inferred about the speaker's beliefs about Tweety flying abilities. Here there is a clash of intuitions. One position is that nothing can be concluded from (1) since the speaker expressed her doubts about whether Tweety is a penguin or not. We will follow a second position which states that the corresponding defaults do apply to each of the possibilities raised by the speaker. In the example above, the possi­ bilities are that Tweety is a penguin, and that Tweety is a non-penguin bird. For each of these possibilities the relevant de­ faults should apply. If Tweety is a pen­ guin, then it does not fly, and if Tweety is a non-penguin bird then it should fly. Thus, this second view would claim that the conclusion one should derive from the utterance of ( 1) is that either Tweety is a non-flying penguin, or Tweety is a flying , non-penguin bird.

This motivates the last requirement on the logic .C:X, the strong epistemic can­ cellation(SEC) . It states:

4 Epistemic Extension of Preference Logics

In this section we will describe the epis­ temic extensions of propositional prefer­ ence logics. Or more precisely, we will describe a method of defining the epis­ temic extension of any particular prefer­ ence logic. The work described here is based on [Wainer, 1992b], with some differences regarding definition of elementary improvement.

The definition of entailment in model preference logics is based on a partial order among the models of the theory [Shoham, 1987] . Given a partial order "~" among models, one defines entailment as the propositions that are satisfiable by the ~-minimal models of the theory. For­ mally:

The epistemic extension of a preference logic will also be a preference logic char­ acterized by the partial-order relation ~ among modal-models (that is, models for formulas of a modal language). And the partial order ~ will be based on the origi­ nal partial order ~ .

4.1 The definition ofF!;

A propositional-model, -that is, a model for a formula restricted to a propositional language, is a valuation function w that assigns a truth value to all propositional symbols in the language. The truth value of a compound formula is defined by the usual recursive rules.

A KD45-model is a tuple (w0 , W} where w0 a propositional-model, named the real world, and W is a set of propositional-models. Each of the ele­ ments of W and w0 are called worlds. The satisfiability relation for KD45-models is defined as usual ([Halpern and Moses , 1985]) .

We will now define a auxiliary rela­ tion ~e among KD45-models based on the ~ relation among propositional models. Given two KD45-models M1 = (wo,, W1} and M2 = (wo 2 , W2}, we will say that M1 is an elementary improvement of M2 , or M1 ~e M2, if:

(9)

Intuitively, M1 is an elementary im­ provement of M2 if the real world in M 1

is "smaller" (in the ~ sense) than the real world in M2 , or if W2 has one world more than wl and there is a world in wl that is smaller than the missing world, or if W1 and W2 disagree in only one world and the extra world in wl is smaller than the extra world in w2·

The partial order !;;;; is defined as the transitive closure of !;;;;. . Finally, the en­ tailment relation F~; is defined similarly as (8) with the exception that !;;;; is used instead of ~.

4.2 The properties of the logic F!;;

This section states that the entailment re­ lation f=c satisfy all properties discussed in section 3. Due to space limitations this paper will not present the proofs, which can be found in [Wainer, 1992a].

Theorem 1 (E) For a and {J proposi­ tional: a Fs {J if and only if a F!;; {J .

The proof is based on the fact that for propositional formulas the !;;;; relation is ex­ actly the ~ relation (from definition 9)

Theorem 2 (KD45-i) If 1/; FKD<> ¢i then 1j; F!;; ¢.

Theorem 3 (ID) a F< {J if and only if Ba F!; B{J. -

To prove that WED holds for any par­ ticular logic one has to be specific about how that logic implements a default rule. We will prove that WED holds for propo­ sitional circumscription. In propositional circumscription one represents the default a "-+ {J as a 1\ ab1 -+ {J where ab, should be one of the propositional symbols to be minimized (that is, the preference relation ~~all other things being equal, should pre­ fer a model where ab1 is false) .

Theorem 4 (WED) If a 1\ (a 1\ ·ab1 -+ {J) Fs {J when ~ (also) minimizes ab1, then both Ba 1\ (Ba 1\ ·ab1 -+ {J) Fe {J and a 1\ (a 1\ ·ab1 -+ B{J) F!; B{J -

Theorem 5 (SEC) If a F< {J and a 1\ 8 Fs / , then Ba 1\ P8 F!; B[({J 1\ ·8) V (! 1\ 8)].

5 Conclusions

The author hopes this paper makes two important contributions. The first one is that it discusses some of the require­ ments that an epistemic nonmonotonic logic should meet . Although we developed these requirements based on a theory of utterance understanding, we believe that they are general requirements and should be used to compare different proposals of epistemic nonmonotonic logics .

The second contribution is the epistemic extension of preference logics. We dis­ cussed a method of extending any propo­ sitional preference logic, and proved that the resulting logics satisfy all require­ ments .

The research reported here is being ex­ panded in two directions. The first one is the development of the epistemic exten­ sion of other nonmonotonic logics, for ex­ ample conditional logics . The second area of future research is the study of the re­ quirements for multi-modal epistemic log­ ICS.