A Unified View of Consequence Relation, Belief Revision and Conditional Logic

1 Introduction

The notion of minimality is proving to be a key unify­ ing idea in three different areas of Artificial Intelligence: nonmonotonic reasoning, belief revision, and conditional reasoning. However, it is difficult for the readers of the literature in these areas to perceive the similarities clearly. The models used differ, sometimes superficially, sometimes in depth, and the notation is different, mak­ ing it hard to apply results on, say, conditional logic to, say, belief revision. Even within the same area there is confusion, as, for example, different authors use differ­ ent formalisms for conditional logic, sometimes without relating their proposals to the literature. We present a uniform view of how minimality is used in these three ar­ eas, shedding light on deep connections among the areas. We clarify differences and similarities between different approaches by classifying them according to the notion of minimality that they are based on.

The first field in which minimality plays a crucial role is nonmonotonic reasoning. Shoham [1987] proposes a uniform approach to subsuming various formalisms of nonmonotonic reasoning in terms of preferential relations among interpretations. Kraus, Lehmann and Magidor [1990] propose several consequence relations that capture Ken Satoh ICOT Research Center 1-4-28 Mita, Minato-ku, Tokyo 108 Japan ksatoh~icot.or.jp general patterns of nonmonotonic reasoning. A conse­ quence relation, denoted by JJ f-v ¢, means that JJ is a good enough reason to believe ¢, or that ¢ is a plausible consequence of JJ. We can regard their work as an exten­ sion of Shoham's work since some consequence relations can be characterized in terms of preferential relations among possible worlds.

The second field in which minimality is discussed is knowledge base revision and update . Alchourron, Giirdenfors and Makinson [1985] propose, on philosoph­ ical grounds, a set of rationality postulates that belief revision operators must satisfy. Katsuno and Mendelzon [1989; 1991a] show that the AGM postulates precisely characterize revision operators that accomplish a modifi­ cation with minimal change among models of knowledge bases expressed in a finitary propositional logic.

Katsuno and Mendelzon [1991b] clarify a fundamen­ tal distinction between knowledge base revision and up­ date. They propose update postulates in the spirit of the AGM revision postulates, and show that the update pos­ tulates precisely characterize minimal change update op­ erators just as the revision postulates characterize min­ imal change revision .

The third field is conditional logic, which is concerned with the logical and semantical properties of counterfac­ tuals, statements such as "if I were a bird then I could fly." Many applications of counterfactuals in Artificial Intelligence are pointed out by Ginsberg [1986] . Del­ grande [1988] uses a conditional logic to formalize default reasoning.

There are several different conditional logics, and some of them can be formulated in terms of minimal change [Nute, 1984]. According to this minimality view, a coun­ terfactual, p. > ¢, is true if we add its antecedent p. to our set of beliefs, modify the set as little as possible to pre­ serve consistency, and then its consequent¢ is true under the modified set of beliefs. Giirdenfors [1988] shows the difficulties associated with using revision to model this view of counterfactuals; Katsuno and Mendelzon [1991b] suggest using update instead of revision. This suggestion is carried out by Grahne [1991] in a logic of updates and counterfactuals.

Lewis [1973] proposes conditional logics called VC and VW. In the semantics of VC and VW, total pre-orders (in Lewis' terminology, "systems of spheres") play a key role. Pollock [Pollock, 1981; Nute, 1984] proposes another conditional logic, called SS, the semantics of which is determined by changing total pre-orders in VC to par­ tial orders.

In this paper, we discuss fundamental similarities and d~fferences among the above works, and give a unified vtew of all the above in terms of notions of minimality.

. A good deal of previous work has been done, espe­ cta!ly recently, on comparisons among consequence re­ latiOns, knowledge base revision and conditional logics. Kraus, Lehmann and Magidor [1990] point out a rela­ tionship between one of their consequence relations and conditional logics. We extend their result and show more accurate semantic and syntactic correspondences.

Makinson and Gardenfors [Makinson and Gii.rdenfors 1991; Gii.rdenfors, 1990] show the relationship betwee~ the AGM postulates for revision and postulates for non­ monotonic consequence relations. Gii.rdenfors [1988] also i~v;stigates the ~e!ationship between knowledge base re­ VISion and conditiOnal logic based on Ramsey test in terms of syntax. He shows that although there are close resemblances between his postulates for revision and axioms of conditional logic, it is impossible to for­ mulate conditional logic by knowledge base revision and Ramsey test. We show the distinctions between condi­ tional logic an~ knowledge base revision in light of their semantics; and show that there is a close relationship between knowledge base update and conditional logic. Grahne [1991] proposes a new logic in which counterfac­ tual and update are treated in a unified way.

Bell [1989] proposes using a conditional logic, called C, to extend Shoham's work. The C logic is no more than SS, although the semantics of C seems to be slightly different from the semantics of SS.

Boutilier [1990a; 1990b] establishes a mapping be­ tween two conditional logics, called CT4 and CT4D, and consequence relations. We show the differences between his conditional logics and other conditional logics in light of notions of minimality. We also extend these results to other conditional logics.

The outline of the paper is as follows. We define in Section 3, ordered structures and families of ordered structures as the common ingredient of the semantics of all the works above, based on the observation that an order among possible worlds is a key concept in all of them. We defin~ logics for ordered structures and fam­ ilies, and give sqund and complete axiomatizations for them. In Section 4, we consider in detail each of the three areas - nonmonotonic logic, belief revision, and conditional logic- and show how the works in each area fit into our framework. Finally, in Section 5 we use our framework to derive new cross-connections among the areas.

2 Preliminaries

Let L be a language of propositional logic that may have an infinite number of propositional letters. Let Ln be a finitary propositional language that has exactly n propo­ sitional letters. We denote the set consisting of all the interpretations of Ln by In· Throughout this paper, we use t/J, p and <P to denote a well-formed formula of L.

A pre-order ;::; over a set W is a reflexive and transitive relation. We denote the strict order of ;::; by <. An element w is a minimum with respect to < if w < w' for any w' E. W- {w}. Let W' be a subscl of W. An element w is minimal in W' with respect to < if w is a member of W' and for any w' E W', w' ;::; ;;; implies w ;::; w'. We denote by Min(W', ;::;) the set of minimal elements in W' with respect to;::;. We can define a total pre-order and a partial order in a usual way.

3 Common Language

We define a common language L... to discuss conse­ quence relations, knowledge base revision, update and conditional logics in a unified way. The language L~ is a language augmented L with a binary connective ......... The connective ...._.. is directly related to the connective r- in the context of consequence relations and the con­ ditional connective > of conditional logics.

We define Wff~ as the set consisting of all the well formed formulas of L~. We also define S- Wff~ as the set of formulas that have no nesting of...._... For example, <P ...__. ( t/J ...__. 1-') is not a formula of S- Wff~. We define W.ffn ~ as the set consisting of all the formulas in Wff~ su'ch that every propositional letter occurred in the formula is a propositional letter of Ln .

3.1 Ordered Structure

An ordered structure is one of the central notions in the semantics of the works that involve minimality. We can give semantics of the formulas in S- Wff~ by using ordered structures. An ordered structure is a special case of Kripke structure used in modal logics.

We define an ordered structure 0 as a triple (W,;::;, V), where W is a nonempty set of worlds, ;::; is a pre-order over W satisfying the smoothness property defined later, and V is a function that maps a pair of each propositional letter of Land an element of W toT or F.

For an ordered structure 0 = (W, ;::;, V), we define truth of each formula in S- Wff~ as follows. First, we recursively define the truth of formulas at a world w by using 0, w f=.

O,wf=p iff V(p,w)=T

0, w F= ...,0' iff 0, w ~ 0',

0, w F= a A {3 iff 0, w f= a and 0, w f= {3,

0, w F= <P ...__. cp iff Min(II<PII, ;::;) ~ llcpll,

where II<PII = {w I V(<fJ,w) = T}.

We say that a formula a in S- Wff~ is true under an ordered structure 0, denoted by 0 f= a, if 0, w f= a for any w in Min(W, ;::;), that is, a is true at every minimal world of W.

Note the following facts.

1. If w1 ;::; w2 means Wt is a more natural world than w2, then the semantics defined above shows that <P ...__. cp is true under 0 if and only if all most natural worlds that satisfy <P also satisfy cp.
2. If W is an infinite set, there might exist infinite descending chains of elements of W. Then, al­ though some II<PII is not empty, Min(li<Pii, ;::;) might be empty.

The smoothness condition, mentioned in the defini­ tion of ordered structure, precludes the possibility of the above emptiness problem. A pre-order ~ satisfies the smoothness condition if, for any formula <P of L and any w E II<PII, there is some world w' such that w' ~ w and w' is minimal in II<PII with respect to ~ -

We consider various restrictions on an ordered struc­ ture 0 = {W, ~. V). If the pre-order ~ is a total pre­ order (or a partial order), then we say that 0 is a totally ordered structure (or partially ordered structure). If W is finite, we say that 0 is a finite ordered structure . If, for any two different worlds, w1 and w2 , there is some formula <P of L such that V(</J, wt) ::j; V(</J, w2 ), then we say that 0 is a distinguishable ordered structure . If 0 is a distinguishable ordered structure then no two worlds represent the same interpretation of L . If the pre-order ~ has a minimum in W, we say that 0 is an ordered structure with a minimum. The ordered structures with a minimum are used to give semantics to formulas of WJJ .... .

The readers who are familiar with ranked models and preferential models of consequence relations may easily notice that totally (resp. partially) ordered structures are very similar to ranked (resp. preferential) models.

Another restriction is the case where a finitary propo­ sitional logic Ln is used instead of L. An ordered Ln­ structure is an ordered structure {W, ~. V) such that if a propositional letter pis not in Ln then V(p, w) is un­ defined. We can also define various restrictions (total, partial, finite, distinguishable, with a minimum) on or­ dered Ln-structures.

Next, we consider a collection of ordered structures in order to give semantics to any formula of WJJ.._. . A fam­ ily of ordered structures 8 = (Ow )we w is a collection of ordered structures such that W is a nonempty set of worlds, each Ow = {W w, ~w, V) is an ordered structure, Ww is a nonempty subset of W, w is minimal in Ww with respect to ~w, and a stronger smoothness condi­ tion defined later is satisfied. For · a family of ordered structures 8 = ( {Ww, ~w, V) )wew, if each w is the min­ imum of Ww with respect to ~w then we say that 8 is a family of ordered structures with minimum. We can also define various restrictions on a family of ordered struc­ tures (with minimum) in a similar way to the case of ordered structures.

For a family of ordered structures 8 = (Ow )we w, we recursively define the truth of formulas at each world w in W as follows.

where IIAII 0 = {w I 8, w f: A}. Intuitively, the set IIAII0 denotes all the worlds under which A is true. We say that A is true under a family of ordered structures 8 if IIAII 0 = w.

The stronger smoothness condition for a family of or­ dered structures 8 is: for any formula A in Wff .... and any w E W, if w' E IIAII 0 n Ww then there is some world w" E Ww such that w" < w' and w" is minimal ~ - in IIAII 0 n Ww with respect to ~w ·

3.2 Validity

We investigate the relationship between ordered struc­ tures and families of ordered structures (with minimum) in light of the validity of formulas. We also show how various restrictions on those structures are related to the interpretation of formulas.

First, we can show that there is no difference between ordered structures and families of ordered structure in light of the validity of formulas of S- Wff.._..

Theorem 3.1 For any formula a inS- WJJ.._., a is valid under totally {resp. partially) ordered structures if and only if a is valid under families of totally {resp. partially) ordered structures.

The validity under families of ordered structures and the validity under families of ordered structures with minimum are different. We show, at the end of this sub­ section, that the two validities are equivalent for some restricted formulas .

Next, we can show that all the restrictions on totally ordered structures introduce no distinction as long as we consider formulas of S- WJJ.._. in the context of Ln. This result implies that none of the restrictions influence the validity of each formula a.

Theorem 3.2 For any totally ordered structure 0, there exists a finite, distinguishable, totally ordered Ln­ structure O' such that for any formula a in S- Wffn, ..... , a is true under 0 if and only if a is true under 0'.

The case of partially ordered structures is different from the case of totally ordered structures. The valid­ ity under finite, distinguishable, partially ordered Ln­ structures is exceptional.

Theorem 3.3 For any partially ordered structure 0, there exists a finite, partially ordered Ln -structure 0' such that for any formula a in S- Wffn,--.., a is true un­ der 0 if and only if a is true under 0'.

We can show similar theorems about families of or­ dered structures (with minimum) in the context of Wff.._. .

Third, we can define a conditional Horn formula by regarding p """ <P as an atom. For example, a formula (J.Il """ <Pd 1\ 0 0 ° 1\ (J.Ik """ <P~c) J (p""" <P) is a conditional Horn formula. Then, we can prove that the validity of a conditional Horn formula is independent of whether total pre-order or partial order is used in ordered struc­ tures . This fact is interesting in light of axiomatizations, because in the axiomatic systems proposed in various works, non-Horn axioms are used to discriminate total pre-order cases from partial order cases.

Furthermore, we can show that the validity of a con­ ditional Horn formula under families of ordered struc­ tures is the same as the validity under families of ordered structures with minimum.

3.3 Axiomatization

We show axiomatic systems for ordered structures and families of ordered structures (with minimum) . As we see later, the axiomatic system for ordered structures is the same as the axiomatic system for families of ordered structures except for the fact that a variable of the for­ mer system ranges over a formula in either S- Wff .... or L, but a variable of the latter system ranges over a formula in Wff .....

First, let (, 1J and e be formula variables that range over formulas of L. Let 1 and 6 be formula variables that range over formulas of S- Wff..... Let X, Y and Z be formula variables that range over formulas of Wff.... . An axiomatic system TO is a set of the following axiomatic schemas and inference rules. 1

Axiom Schemas

(PC) Truth-functional tautologies.

(ID) (--...(.

(MP) (( --...TJ) :J (( :J TJ).

(AND) ((--... TJ) A ((--...e) :J ((--... (TJ A e)) .

(oR) (( ...... e)" (TJ ...... e):) ((( v TJ) ...... e).

(cE) (( ...... TJ)" (TJ ...... ()" (( ...... e) :) (TJ ...... e).

(RM) (( ...... e)"-.(( ...... -.TJ):) (((" TJ) ...... e).

Inference Rules

(Mp) From 6 and 6 :J 1 infer I ·

(RCM) From 1J :J e infer ((--... TJ) :J ((--...e).

Another axiomatic system PO is the axiomatic system obtained from TO by removing the axiomatic schema (RM).

We can show a kind of the completeness theorem.

Theorem 3.4 A formula 0' in S- Wff .... is a theorem of TO {resp. PO) if and only if 0' is valid under totally {resp. partially) ordered structures.

Next, let us give an axiomatization for families of ordered structures. An axiomatic system FTO (resp. FPO) is the axiomatic system obtained from TO (resp. PO) by replacing the formula variables(, fJ, e, 6 and 1 with X, Y, Z, X and Y, respectively.

Theorem 3.5 A formula A in Wff.... is a theorem of FTO {resp . FPO) if and only if A is valid under families of totally (resp. partially) ordered structures.

Third, we consider an axiomatization of families of ordered structures with minimum. An axiomatic system FTOM (resp. FPOM) is the axiomatic system obtained from FTO (resp. FPO) by adding an axiomatic schema: (CS) (X A Y) :J (X--... Y) .

Theorem 3.6 A formula A in Wff.... is a theorem of FTOM (resp. FPOM) if and only if A is valid under fam­ ilies of totally (resp. partially) ordered structures with mmzmum.

For each axiomatic system above, we can construct a kind of canonical model such that a set consists of all the true formulas at a world of the model if and only if the set is a maximally consistent set under the axiomatic system. A later version of this paper will provide the details.

Finally, we note that we can prove nonexistence of ax­ iomatic systems, such as PO, for finite, distinguishable, partially ordered Ln-structures. Despite this, Katsuno and Mendelzon (1991a] give a kind of axiomatization of finite, distinguishable, partially ordered Ln-structures in the context of knowledge base revisions. They achieve this by introducing a revision operator that corresponds to a kind of function mapping a formula to another for­ mula.

1 TO and the other axiomatic systems given are based on the axiomatization of Bell's C logic [Bell, 1989].

4 Comparison

4.1 Consequence Relation

A consequence relation represents a well-behaved set of conditional assertions, where a conditional assertion I' ~ <P intuitively shows that I' is a good enough reason to believe <fl. Kraus, Lehmann and Magidor [Kraus eta/., 1990; Lehmann, 1989] define preferential (resp. rational) consequence relations as a set of conditional assertions that is closed under a set of inference rules, P (resp. R) . They also define preferential models and ranked mod­ els to discuss the semantics of the consequence rela­ tions. They show that preferential (resp. rational) con­ sequence relations can be characterized by preferential (resp. ranked) models. It is easy to define a bijection between preferential (resp. ranked) models and partially (resp. totally) ordered structures.

By associating the connective--... to the connective ~~ we can transform the results on TO or PO to the re­ sults on consequence relations, and vice versa. A super­ ficial difference between consequence relations and TO or PO is the way of representations of rules and ax­ ioms. Gentzen-style rules are used in consequence re­ lations, while a Hilbert-style axiomatization is used for ordered structures. Since a transformation between the two styles is straightforward, we can easily find a coun­ terpart of each rule of R or P in the axioms, the inference rules, or the theorems ofTO or PO. However, note that : when we consider the converse transformation, there is no counterpart to (MP) in the rules of consequence re­ lations.

Another difference is that some logical combinations of conditional assertions are not allowed in rules of con­ sequence relations, while all combinations are allowed in S- Wff .... . For example, ((1-'1 ~ <Pt) V (1-'2 ~ <P2)) :J I' is not allowed, but ((p1--... </l1)V(IJ2--... <P2)) :J I' is allowed. Boutilier [1990a; 1990b] also extends the syntax of conse­ quence relation so that we may use logical combinations of conditional assertion. However, his semantics of an extended formula is different from ours.

Although the above differences exist, Theorem 4.1 shows that there is no essential distinction between R (resp. P) and TO (resp. PO). For any subset r of S­ Wff .... , we define C on(f) as a set of conditional assertions such that Con(f) = {p ~ <P II'--... <PEr}.

Theorem 4.1 A set of conditional assertions C is a ranked (resp. preferential) consequence relation if and only if there is some deductively closed set r of S- Wtf .... under TO (resp. PO} such that C = Con(r) .

4.2 Knowledge Base Revision

A major problem for knowledge base management is how to revise a knowledge base (KB) when new information that is inconsistent with the current KB is obtained. Al­ chourr6n, Gardenfors and Makinson [1985] propose ra­ tionality postulates for the revision operation. Katsuno and Mendelzon [1989; 1991a] characterize the AGM pos­ tulates in terms of minimal change with respect to an ordering among interpretations. We discuss the rela­ tionship between those works and the results on ordered structures.

Gardenfors and his colleagues [Alchourr6n et al., 1985; Gardenfors, 1988; Gardenfors and Makinson, 1988] rep­ resent a KB as a knowledge set. A knowledge set is, in our context, a deductively closed set of formulas in L . Given knowledge set K and sentence p, K*p is the revi­ sion of K by I'· J<+ I' is the smallest deductively closed set containing K and I'· KJ. is the set consisting of all the propositional formulas. The AGM postulates consist of the following eight rules. See [Gardenfors, 1988] for a discussion of the intuitive meaning and formal properties of these postulates.

(K*l) K*p is a knowledge set .

(K*2) I' E K*p

• (K*3) K*p ~ J<+ I'
• (K*4) If ...,I' fl. K, then J<+ I'~ K*p
• (K*5) K*p = KJ. only if I' is unsatisfiable.
• (K*6) If I'=: <P then K*p = K*</J.
• (K*7) K*(pi\</J) ~ (I<*p)+<!J

(K*S) If ....,</J fl. K*p then ( K*p )+ </J ~ K*(p 1\ </J)

We note that (K*3) and (K*4) imply the condition: if new knowledge I' is consistent with a knowledge set K then the revised knowledge set K*p is J<+ I'· We call this condition an expansion condition.

Makinson and Gardenfors [1991] discuss similarities between these postulates and rules of consequence re­ lations by fixing a knowledge set K and by using the transformation rule: <P E K*p iff I' f- </J. Since the rules of consequence relations can be translated into formulas in S- WJJ ..... , we can apply their discussion to the relation­ ship between the postulates and formulas in S-WjJ ......

We give a semantic characterization of the postulates (K*1),......(K*8) by using the ordered structures. We can capture a revision operator * by a collection of totally ordered structures, where a totally ordered structure is assigned to each knowledge set. The total ordered struc­ ture 0 K = (W K, ~K, VK) assigned to a knowledge set K must satisfy a covering condition 2 : for any satisfi­ able formula I' there is some world w E WK such that VK(J', w) = T. The expansion condition of the postu­ lates implies a remarkable property (the third condition of Theorem 4.2): each consistent knowledge set K con­ sists of all the propositional formulas that are true un­ der every minimal world of OK. The second condition of Theorem 4.2 corresponds to the transformation rule proposed by Makinson and Gardenfors .

Theorem 4.2 A revision operator * satisfies (K*1}"' (K*B) if and only if for each knowledge set K, there is a total ordered structure OK such that

2 This property is related to (K*5 ).

1. OK satisfies the covering condition,
2. K*p = { <P I 0 K F I'..__. <P}'
3. K={<PIOK f=<P} ifK"fKJ..

Katsuno and Mendelzon [1989; 1991a] consider knowl­ edge base revision in the framework of a finitary propo­ sitional logic Ln. They represent a KB as a formula of Ln, since a computer-based KB must be finitely rep­ resentable. We note that every knowledge set K (i.e., deductively closed set) can be represented in the context of Ln by a formula t/J of Ln such that K = { <P I t/J 1- <P}. We denote by t/J o I' the revision of a KB t/J by p, where o is a revision operator.

Katsuno and Mendelzon show the six · postulates (R1),......(R6) for a revision operator o that are equiva­ lent to (K*l),......(K*8). By introducing total pre-orders among interpretations of Ln, they characterize all the re­ vision operators satisfying (R1),......(R6) in light of minimal change with respect to the introduced total pre-orders. It is possible to rephrase the characterization in terms of finite, distinguishable, totally ordered Ln-structures, and show a theorem similar to Theorem 4.2.

Katsuno and Mendelzon [1991a] show postulates for a revision operator that is defined by minimal change with respect to partial orders among interpretations. The postulates consist of (R1),......(R5) and other two postu­ lates (R7) and (R8). Due to space limitation let us only state the (R8) postulate.

(RS) (t/J o p!) 1\ (t/J o 1'2) implies t/J o (1'1 V 1'2)·

The postulate (R8) is noteworthy in light of the ax­ iomatization of finite, distinguishable, partially ordered Ln-structures, because it is difficult to find a counterpart to (R8) in formulas of S- WJJ ......

We can show the relationship between revision opera­ tors satisfying (Rl),......(R5), (R7), (R8) and finite, distin­ guishable, partially ordered Ln-structures. To. do so, we need a restriction on partially ordered Ln-structures . We say that a partially ordered Ln-structure 0 = (W, ~, V) has a minimum set if it satisfies the condition: for any w E Min(W, ~) and any w' E W, if w' fl. Min(W, ~) then w < w' holds. The reason why we must impose this condition is related to the expansion condition which requires that every model of t/J be less than any non­ model with respect to the order that characterizes min­ imal change.

Theorem 4.3 A revision operator o satisfies (R1}"' (R5), (R7) and {RB} if and only if for each formula t/J of Ln, there is a finite, distinguishable, partially ordered Ln -structure, 01/J, such that

1. t/J o ~-' = A{<P I o"' F= I'--.. <P},
2. 01/J satisfies the covering condition and has a mini­ mum set,
3. t/J =A { <P I 01/J F= <P} if t/J is consistent,
4. if t/J and t/J1 are logically equivalent then 01/J is equal to 01/J,·

The fourth condition of Theorem 4.3 says that revision is independent of the syntactic representation of a KB t/J .

4.3 Knowledge Base Update

We discuss the relationship between knowledge base up­ date and families of ordered structures with minimum. The revision discussed in Section 4.2 is used to mod­ ify a KB when we obtain new information about a static world, while we need another operation, update, to bring the KB up to date when the world described by it changes. The distinctions between update and revision are discussed in [Katsuno and Mendelzon, 1991b].

Katsuno and Mendelzon propose postulates (Ul)­ (U8) for an update operator under Ln, and character­ ize all the update operators that satisfy the postulates in terms of partial orders among interpretations. The postulates (Ul)-(U8) are defined along the same lines as (Rl)-(R8). However, two important differences ex­ ist; one is that (Ul)-(U8) do not require the expansion condition, that is, even if a KB t/J and new information J.l are consistent, the new KB t/J o J.l is not necessarily equivalent to t/J /1. fl.· The other difference is that an up­ date operator should satisfy a "disjunction rule" (U8) guaranteeing that each possible world of the KB is given independent consideration.

(US} (t/J1 Vt/J2)oJ.l.=(tfloJ.l.)V(t/J2oJ.l.).

We can show that an update operator satisfying (Ul)-(U8) can be identified with a family of finite, dis­ tinguishable, partially ordered Ln-structures with min­ imum, where an ordered structure is assigned to each interpretation of Ln.

Theorem 4.4 An update operator o satisfies {UJ)­ {UB) if and only if there is a family of finite, distin­ guishable, partially ordered Ln -structures with minimum 8 = (OI)Iei,. such that

1. (}[ satisfies the covering condition,
2. the minimum of 01 is I,
3. t/J o fl.= t\{4> 18 F= t/J =>(fl.~¢)}.

4.4 Conditional Logic

The conditional logics consist of the propositional logic augmented with a conditional connective denoted by >. If we replace ~ with >, we can regard £ ..... as a language of conditional logics.

The various conditional logics are surveyed in [Nute, 1984]. Table 1 shows a correspondence between the pro­ posed conditional logics and the axiomatization in Sec­ tion 3.3. 3 For instance, the table states that FTO is an axiomatization of VW.

3 We have not found any conditional logic proposed in the literature that corresponds to FPO.

Conditional logics that are not appeared in [Nute, 1984] are CT4 and CT4D proposed by Boutilier [1990a; 199Gb]. The logics are formalized to represent and rea­ son with "normality". The semantics of J.l > 4> under CT4 (or CT4D) is that 4> is true under the most normal situation where J.l is true. Roughly speaking, he consid­ ers an order such that the more distant a world is from w, the more normal the world is. A later version of this paper will provide a formal analysis on the relationship between Boutilier's semantics and the notion of ordering.

5 Reciprocal Relation

5.1 Consequence Relation versus Revision

If we fix a knowledge set [{, we can identify a revision operator* satisfying (K*l )-(K*8) with a rational conse­ quence relation determined by a ranked model satisfying the covering condition. The identification is established by Condition 2 of Theorem 4.2. In general, a revision operator * satisfying (K*l)-(K*8) corresponds to some collection of rational consequence relations.

The discussion in Section 4, in light of P or PO, sug­ gests a way of determining the rationality postulates for revision to knowledge sets that correspond to preferen­ tial consequence relations.

5.2 Consequence Relation versus Conditional Logic

Consequence relations are, in some sense, equivalent to "nesting-free" conditional logics. We can show the following theorem 4 by extending the discussion of Sec­ tion 4.1 and by using Theorems 3.1 and 3.5.

Theorem 5.1 For any rule a that holds in all ratio­ nal {resp. preferential) consequence relations, the corre­ sponding formula a' of conditional logic is a theorem of VW {resp. FPO). Conversely, for any theorem a' of VW (resp. F PO) that is a restricted formula of S- Wff 5 , the corresponding rule a holds in all rational {resp. prefer­ ential) consequence relations.

5.3 Revision versus Conditional Logic

Giirdenfors [1988] investigates the relationship between the postulates for revision and the conditional logic VC in light of the Ramsey test: {3 E /{*a iff a > {3 E [{. He shows that the Ramsey test is incompatible with the postulate (K*4) (intuitively, the expansion condition) in his framework. Since he considers a knowledge set con­ structed from formulas of L> whereas we use a knowl­ edge set as a set of propositional formulas, we can not translate his results into our context.

A revision operator satisfying (K*l)-(K*8) is equiv­ alent to some collection of totally ordered structures. However, the semantics of VC is determined by a family of totally ordered structures with minimum. The two dif­ ferences, i.e., having minimum or not and different types of collection, suggest an incompatibility result similar to the incompatibility obtained by Giirdenfors.

4 Boutilier [1990a; 1990b] shows a similar theorem in terms of CT4 and CT4D.

5 Note that the syntax of rules of consequence relations is restricted as discussed in Section 4.1; for example, neither p rv (q rv r) nor r 1\ (p rv q) is allowed.

5.4 Update versus Conditional Logic

The update operators satisfying (U1),..,(U8) are charac­ terized by families of finite, distinguishable, partially or­ dered Ln-structures with minimum. The semantics of the conditional logic SS (or equivalently C) is deter­ mined by families of partially ordered structures with minimum. We can expect more similarities of update to conditional logic than those of revision from the above two facts. To develop the correspondence, we must de­ fine an update operator in the context of knowledge sets, and find postulates for the update that correspond to (U1),..,(U8) .

Grahne [1991] proposes a conditional logic VCU 2 hav­ ing an update operator, and shows the Gardenfors' in­ compatibility result does not hold in VCU 2 .

6 Concluding Remarks

We define ordered structures and families of ordered structures (with minimum) as tools to develop a unified view of existing work on consequence relations, knowl­ edge base revision, update and conditional logics. By using ordered structures and families of ordered struc­ tures, we can show reciprocal relations among the differ­ ent approaches.

Acknowledgements

The authors are grateful to Alberto 0. Mendelzon for discussions on this work and many insightful comments on drafts of this paper. The authors are also grateful to Yves Lesperance and anonymous referees for their help­ ful comments.