A Unified View of Propositional Knowledge Base Updates

1 Introduction

Consider a knowledge base (KB) represented by a set of sentences in a language L . As our perception of the world described by the knowledge base changes, the knowledge base must be revised. Several kinds of revisions may oc­ cur. If we simply acquire additional knowledge about the world, and the new knowledge does not conflict with the current beliefs 1 of the KB, there seems to be no dif­ ficulty - at least in theory - in incorporating the new knowledge in the form of new sentences. If, however, the new knowledge is inconsistent with the old beliefs, and we want the KB to be always consistent, we must resolve the conflict somehow; this operation will be called revi­ sion. A different kind of change occurs when a sentence previously believed becomes questionable; we call the operation that makes this change a contraction. A third operation erases all knowledge that involves a particular Alberto 0. Mendelzont Department of Computer Science University of Toronto Toronto, Ontario M5S 1A4 Canada fact; we call this elimination. Eliminating p will result not only in uncertainty over whether p is true or false, but we will also have to give up a belief that, say, q ::: p. The fourth kind of change we consider is retraction: it involves undoing the effect of a previous operation.

*This work was done while the first author was visiting the University of Toronto.

'This work was partially supported by the Natural Science and Engineering Research Council of Canada.

1 We use the terms belief and knowledge interchangeably in this paper.

Foundational work on knowledge base revision was done by Giirdenfors and his colleagues [Giirdenfors, 1984, Alchourr6n et al., 1985, Giirdenfors and Makinson, 1988]. They propose, on philosophical grounds, a set of rationality postulates that the operations of contrac­ tion and revision must satisfy and explore the implica­ tions of these postulates. The Giirdenfors postulates do not assume any concrete representation of the KB; in fact, KB's are modeled as deductively closed sets of sen­ tences in some unspecified language. When we consider computer-based KB's, we need to fix a formalism and a finite syntactic representation of a KB. In this pa­ per, we will assume the KB is represented by a finite set of propositional sentences. For this case, the both AI and database literatures contain several proposals on the appropriate definitions for some of the update op­ erators [Dalal, 1988a, Dalal, 1988b, Fagin et al., 1983, Weber, 1986, Winslett, 1987, Winslett, 1988, Borgida, 1985, Satoh, 1988]. The question now arises of whether the result of an update will depend on the particular set of sentences in the KB, or only on the worlds de­ scribed by them. We are interested in methods that satisfy Dalal's Principle of Irrelevance of Syntax, that is, the meaning of the KB that results from an update must be independent of the syntax of the original KB, as well as independent of the syntax of the update itself.

Dalal [1988b] was the first one to relate his approach to the Giirdenfors postulates, pointing out that his pro­ posal for the revision operator satisfies them. He did not analyze contraction, elimination, or retraction. In this paper, we go further by giving a model-theoretic characterization of all revision operators that satisfy the postulates. Our main theorem, in Section 3, shows that these operators are precisely the ones that accomplish an update with minimal change to the set of models of the KB. Dalal's method is seen to be a special case; we also discuss how the methods of Borgida, Winslett, Satoh, Weber, and Fagin, Ullman and Vardi fit into this frame­ work.

Giirdenfors et al. show that the definition of a revision operator satisfying the rationality postulates uniquely determines a contraction operator that satisfies the cor­ responding postulates for contraction; conversely, revi­ sion can be defined in terms of contraction. In Section 4, we translate this definition to the case where the KB is a finite set of propositional sentences and show that con­ traction amounts to adding to the models of the KB the models of the KB revised with ...,J.l.. We justify the defi­ nition further by showing that it is a sufficient condition for guaranteeing that old knowledge is not unnecessarily discarded.

It is generally recognized that not all sentences in a KB will have the same epistemic status. For example, an in­ tegrity constraint, or a definition of a concept in terms of others, should probably be treated differently than a fact about the domain. Gardenfors and Makinson [1988] and Fagin, Ullman, and Vardi [1983] approach the problem in a similar way: rank the sentences in the KB accord­ ing to their importance or "epistemic entrenchment" and take this into account when minimizing change from the old KB to the new one. In Section 5, we follow a dif­ ferent route. We distinguish between the KB and a set of integrity constraints IC and show how to modify the revision and contraction operators to ensure that the constraints are satisfied.

Finally, in Section 6 we treat a new operation, elimi­ nation, and show that it cannot in general be simulated by contraction, and in Section 7, we show that retraction is in general not achievable.

2 Preliminaries

Throughout this paper, we consider the language L of propositional logic, and we denote the set consisting of all the propositional letters in L by 3. We represent a knowledge base by a propositional formula 1/J.

We use the standard terminology of propositional logic except for the definitions given below.

An interpretation of L is a function from 3 to {T, F}. We often denote a interpretation by a tuple representing each propositional letter's value, e.g., if 3 = {a, b, c, d} then < T, F, T, F > is the interpretation which maps a, b, c, d toT, F, T, F respectively. A model of a propositional formula t/J is an interpretation that makes t/J true in the usual sense. Mod(t/J) denotes the set of all the models of 1/J .

Let M be a set of interpretations of L. Then, form(M) denotes a formula whose set of models is equal toM.

Let t/J be a propositional formula and let a be a propo­ sit.ional letter. Then, t/J;t is defined as a formula ob­ tamed from t/J by replacing every occurrence of a with true, and 1/J;; is defined as a formula obtained from t/J by replacing every occurrence of a with false. We define res a ( t/J) as 1/J;t V 1/J;;. If n is a set of propositional letters, { a1, a2, ... , an}, resn.( t/J) is defined as resa 1 (res a, ( ... (res a,. ( t/J)) ... )) .

Let I be an interpretation of L, and let n be a subset of 3. Then, lin is an interpretation over n obtained from I by restricting its domain to 0 . The complement of n in :::: (i.e., ::::- 0) is denoted by nc.

3 Revision

Given a knowledge base t/J and a sentence J.l, t/J o J.l de­ notes the revision of t/J by J.li that is, the new knowledge base obtained by adding new knowledge J.l to the old knowledge base 1/J.

3.1 The Giirdenfors Postulates for Revision

Gardenfors and his colleagues propose the following pos­ tulates which they argue must be satisfied by any reason­ able revision function. These postulates are formulated in a very general setting, but we restrict the discussion here to the propositional logic case. Instead of a finite KB, they consider a knowledge set, that is, a deductively closed set of formulas. Given knowledge set K and sen­ tence J.l, K* J.l is the revision of K by J.l · K+ J.l is the smallest deductively closed set containing K and J.l.· K.t is the set consisting of all the propositional formulas.

( G*1) K* J.l is a knowledge set.

(G*2) J.1. E K* J.1.

(G*3) K*J.l~K+J.l

(G*4) If ...,J.l. ¢ K, then K+ J.1. ~ K* J.1.

(G*5) K*J.l = K.t only if J.l is unsatisfiable.

(G*6) If J.1. := t/1 then K*J.l = K*t/1.

(G*7) K*(J.ll\ t/1) ~ (K* J.l)+tjJ

(G*8) If ...,t/1 ¢ K* J.1. then (K* J.l)+tjJ ~ K*(J.ll\ t/1)

If we fix a way of representing any knowledge set K by a propositional formula t/J such that K = { t/J I t/J 1- t/J }, we can establish a direct correspondence between K* J.l and t/J o J.l · The following lemma characterizes revision oper­ ators that satisfy the first six postulates, (G*1)....,(G*6) .

Lemma 3.1 Let * be a revision operator on knowledge sets and o its corresponding operator on KB's. Then * satisfies (G*J) ...... (G*6) if and only o satisfies conditions (RJ} ...... (R4} below.

(R1) t/J o J.l implies J.l ·

(R2) If t/J 1\ J.1. is satisfiable then t/J o J.l = t/J 1\ J.l ·

(R3) If J.1. is satisfiable then t/J o J.l is also satisfiable.

(R4) If tP1 = tP2 and J.l.I = J.1.2 then tP1 o J.l.I = tP2 o J.1.2 .

This Lemma gives us a good grasp of the meaning of the first six postulates: new knowledge (J.l.) is retained in the updated KB (R1), his Principle of Irrelevance of Syntax (R4), a guarantee that the obvious path will be taken when there is no conflict (R2), and a condition preventing a revision from introducing unwarranted in­ consistency (R3) . What about the remaining two postu­ lates? The following lemma rephrases them in terms of o .

Lemma 3.2 (G*7) and (G*B) are equivalent to (R5) and {R6} respectively in the same sense as Lemma 3.1.

(R5) (tP o J.l) 1\ t/1 implies t/J o (J.ll\ t/J).

(R6) If ( t/J o J.l) 1\ t/1 is satisfiable then t/J o (J.ll\ t/J) implies (t/JoJ.l.)At/1.

To grasp the intuitive meaning of (R5) and (R6), con­ sider the set of models of the KB, Mod('f/;). Suppose that there is some metric for measuring the "distance" between Mod('f/;) and any interpretation I. We want our revision operator to effect minimal change, that is, we want the models of 1/J o J.L to be those models of J.L which a.re closest to Mod('f/;) with respect to our distance met­ nc.

Rule (R5) says that our notion of closeness is well­ behaved in the sense that if we pick any interpretation I which is closest to Mod('f/;) in a certain set, namely Mod(J.L), and I also belongs to a smaller set, Mod(J.LA¢), then I must also be closest to Mod('f/;) within the smaller set Mod(J.L A¢).

A violation of rule (R6) would imply that an interpre­ tation I may be closer to the KB than J within a certain set, while J is closer than I within some other set. To see this, consider a model I of'f/;o(J..LA¢), that is, a model of J.L A¢ that is closest to Mod('f/;). Suppose I is not a model of ( 1/J o J.L) A¢. The precondition of (R6) says that there is some interpretation J that is a model of 1/J o J.l and also of¢. That is, J is a model of¢ that is closest to Mod('f/;). But then J is closer to Mod('f/;) within the set Mod(¢) than I, while I is closer to Mod('f/;) than J within the set Mod (J.L A ¢). In the next section we for­ malize the notion of an interpretation being closer to the KB than another one and relate it to the postulates.

3.2 Orders between Interpretations

The postulates (G*7) and (G*8) represent the condition that revision be accomplished with minimal change. In this Subsection, we give a model theoretic characteriza­ tion of minimal change.

Let I be the set of all the interpretations of L. A pre­ order ~ over I is a reflexive and transitive relation on I. Consider a function that assigns to each propositional formula 1/J a pre-order ~1/J over I. We say this assignment is persistent if the following three conditions hold:

1. If IE Mod('f/;) then for all I' E I, I ~1/J I' holds.
2. If IE Mod('f/;) and I'¢. Mod('f/;) then I' ~1/J I does not hold.

That is, every model of 1/J is less than or equal to every other model and no non-model can be less than or equal to a model. We define <,p as I <,p I' if and only if I ~1/J I' and I' f:,p I.

Let M be a subset of I. An interpretation I is minimal in M with respect to ~1/J if I E M and there is no I' E M such that I' <,p I. Let

If we regard ~1/J as a measure representing the close­ ness between Mod ( 1/J) and an interpretation, i.e., I' ~1/J I means that I' is closer to Mod ( 1/J) than I, then Min( M, ~1/J) can be seen as the set of all the closest interpretations in M to Mod('f/;).

Theorem 3.1 Revision operator o satisfies Conditions {Rl}----(R6} if and only if there exists a persistent assign­ ment that maps each KB 1/J to a total pre-order ~1/J such that Mod('f/; o J.L) = Min(Mod(J.L), ~,p).

The persistent assignment of the Theorem maps KB's to total pre-orders. If we allow two interpretations to be incomparable under some pre-order, then existence of the pre-order is no longer sufficient to guarantee condi­ tion (R6) . Instead of (R6), two weaker conditions char­ acterize the existence of a persistent assignment to par­ tial pre-orders. A later version of this paper will provide the details.

3.3 Review of Proposals from the Literature

3.3.1 Dalal's Revision

Dalal [1988a, 1988b] uses the number of propositional letters on which two interpretations differ as a mea­ sure of "distance" between them. This distance measure induces an ordering among interpretations as follows. First, define the distance between two interpretations I and J, dist( I, J), as the total number of propositional letters whose interpretation is different in I and J. Next, define the distance between Mod ( 1/J) and I as

Then, we can define a persistent assignment of a total pre-order ~1/J as I ~1/J J if and only if

And Dalal's revision operator o D can be defined by:

Thus, it follows from Theorem 3.1 that Dalal's revision operator o D satisfies Conditions (R1 )----(R6).

Example 3.1 Let L have only four propositional let­ ters, a, b, c, d. Consider the following five interpreta­ tions:

Let

Then, we can obtain

3.3.2 Borgida's Revision

Let o B be the revision operator proposed by Borgida [1985] and extended in [Dalal, 1988a]. He concentrates on sets of propositional letters on which a model of 1/J and a model of J.l differ.

We say that two interpretations, I and J, differ on a set of propositional letters, n, if n is the set of propo­ sitional letters a such that the truth value of a in I is different from its truth value in J. Diff(I, J-t) is the col­ lection of all the sets of propositional letters on which I and some model of 1-' differ. Then, Borgida's revision op­ erator o B is defined as follows. If 1-' is inconsistent with t/J, then an interpretation J is a model oft/JoB 1-' if and only if J is a model of 1-' and there is some model I of t/J such that the set of propositional letters on which I and J differ is a minimal element of Diff(I, J-t). Otherwise, i.e., if 1-' is consistent with t/J, then t/J o 1-' is defined as t/J " 1-'·

If t/J has only one model I, we can represent the models of t/J o B 1-' as the set of minimal elements of the partial order 5:1 defined by J 1 5:1 h if and only if the set on which I and h differ is a subset of the set on which I and J2 differ. This fact makes us expect that oB might be defined in terms of a persistent assignment of a partial pre-order to each KB. However, the following example shows that o B cannot be defined in this way.

Example 3.2 Consider Example 3.1 again. We add the following two interpretations:

Let

Then, we can obtain

Suppose that there is some persistent assignment of a partial pre-order 5:.;, that captures the o operator. Then, h </:..;, J4 follows from t/JoB ¢J4 =form( h. J4). Js </:..;, J4 does from t/J oB 1/Js = form(J4, Js). On the other hand, either h <.;, J4 or Js <.;, J4 follows from t/J oB I/J6 = form( h. Js) . This is a contradiction.

In terms of Conditions (R1)-(R6), the following Lemma holds

Lemma 3.3 Assume that t/J is consistent. Then, Borgida's revision operator oB satisfies {R1}-{R5), but does not satisfy {R6 ).

3.3.3 Winslett's Revision

Winslett [1988] proposes a revision operator which is suitable for reasoning about action. Her revision opera­ tor is defined for the first order calculus case and called the possible models approach. We restrict this operator to the propositional case and denote it by Opma .

If the new knowledge 1-' is inconsistent with the old knowledge base t/J, then Winslett's operator opma coin­ cides with Borgida's operator oB. However, even if 1-' is consistent with t/J, Winslett defines Opma in the same way as the inconsistent case. This means that Opma violates Condition (R2) , i.e., when t/J A 1-' is consistent, t/J Opma 1-' may not be equivalent to t/J A 1-'·

Example 3.3 Let L have only two propositional letters, a and b. Let t/J =(a A -.b) V (-.a A b) and 1-' =a. Then, we obtain t/J opma 1-' =a and t/J oB 1-' =(a A -.b).

To interpret this example in the context of [Winslett, 1988], suppose a represents the fact that a book is on the floor and b means that a magazine is on the floor . Then, t/J states that either the book or the magazine is on the floor, but not both. Now, we order a robot to put the book on the floor. The result of this action should be represented by the revision of t/J with a. After the robot puts the book on the floor, we know a, but we do not know whether b is true or not. Hence, the new state of the world should be described not as a A -.b (Borgida's revision), but as a (Winslett's revision).

In terms of Conditions (R1)-(R6), the following holds.

Lemma 3.4 Assume that t/J is consistent. Then, Winslett's revision operator opma satisfies {RJ) and {R3)-(R5), but violates {R2} and {R6 ).

3.3.4 Satoh's Revision

Satoh [1988] proposed a revision operator for first or­ der knowledge bases by using the notion of circumscrip­ tion. If we apply his revision operator to the propo­ sitional logic case, we obtain the revision operator os which corresponds to a global version of Borgida's revi­ sion operator.

Satoh considers the minimal elements of Diff( t/J, J-t), where

He defines an interpretation J to be a model of t/J os 1-' if and only if J is a model of 1-' and there is some model I of t/J such that the set on which I and J differ is a minimal set of Diff(t/J, J-t).

This definition makes the closeness between models of t/J and models of 1-' depend on both t/J and 1-'· Hence, we cannot expect os to be defined in terms of a persis­ tent assignment of a pre-order to each KB. The following example shows that this expectation is correct.

Example 3.4 Consider Example 3.1 again. We obtain t/J os I/J1 = form(J2, Ja), t/J os I/J2 = I/J2, and t/J os 1/Ja = 1/Ja.

Suppose there is some persistent assignment of a pre­ order 5:.;, that captures the os operator. Then, t/J os I/J1 = form(J2, Ja) implies either J2 <.;, J1 or Ja <.;, J1 . However, J2 </:..;, J1 follows from t/J o ¢J2 = ¢J2, and Ja </:..;, J1 follows from t/J os ¢J3 = ¢J3, a contradiction.

In terms of Conditions (R1)-(R6), the following holds.

Lemma 3.5 Assume that t/J is consistent. Then, Satoh 's revision operator os satisfies {R1}-{R5), but does not satisfy {R6}.

3.3.5 Weber's Revision

Weber [1986] also concentrates on sets of propositional letters on which a model of t/J and a model of 1-' differ. His revision operator ow can be easily defined by elimina­ tion, which we discus in Section 6. Thus, we only point out that ow cannot be defined in terms of a persistent assignment of a pre-order to each KB, since ov yields the same results as os in the case of Example 3.4.

In terms of Conditions (R1)-(R6) , the following holds.

Lemma 3.6 Assume that both .,P and J.l consas­ tent. Then, Weber's revision operator ow satisfies (R1}-(R5), but does not satisfy (R6).

3.3.6 Fagin, Ullman and Vardi's Revision

The approach of Fagin, Ullman and Vardi [1983], when applied to deductively closed sets of sentences, yields a revision operator oF such that, if .,P and J.l are inconsis­ tent, .,Po F J.l is equivalent to J.l· Hence, oF can be defined by the persistent assignment that maps each .,P to the pre-order ~"' such that I ~1/J I' if and only if either I is a model of .,P or neither I nor I' is a model of .,P.

Because it is not very satisfactory to throw away all the old knowledge each time an inconsistent update is attempted, these authors favour sets of sentences that are not deductively closed; however, in this case their method produces a result which depends on the syntax of the KB, violating the Principle of Irrelevance of Syntax.

4 Contraction

When a sentence J.l that was previously believed be­ comes uncertain, we apply a contraction operator to the KB to ensure that J.l is not implied by the up­ dated KB. Note that this is different from revising the KB with -,JJ. Given a KB .,P and a sentence JJ, .,P e JJ denotes the new knowledge base obtained by contract­ ing J.l from .,P. Gardenfors and his colleagues have an­ alyzed contraction carefully [Alchourr6n et al., 1985, Gardenfors and Makinson, 1988], but the database and AI literature has concentrated much more on revision.

4.1 Connection between Contraction and Revision

Alchourr6n, Gardenfors, and Makinson [1985] also pro­ pose rationality postulates for contraction, (G-1)-(G-8). According to their notation, K- J.l is the new knowledge set obtained from the old knowledge set K by contract­ ing J.l·

(G-1) K- J.l is a knowledge set.

(G-3) If JJ ¢ K, then K- J.l = K.

(G-5) K ~ (K-p)*p

(G-6) If J.l =¢,then I<- J.l =I<-¢

We refer to [Makinson, 1985] for the justification of these postulates. If we represent each knowledge set by a propositional formula, as we did in Section 3.1, the following properties easily follow from (G-1)-(G-6).

( C-1) If .,P implies J.l and J.l is not a tautology, then .,P e J.l does not imply J.l and tP implies tP e p; otherwise, tP e J-l is equivalent to .,P.

(C-2) (.,P e JJ) 1\f-l implies .,P.

(C-1) shows that e realizes contraction iff-lis implied by .,P and that otherwise e does not influence the KB.

(C-2) shows that the contraction of J.l from .,P is strong enough to recover, when conjoined with p, all the facts in the original KB .,P.

Alchourr6n et al. [1985] showed that contraction and revision are closely related and can in fact be defined in terms of each other. They proved that, given a revision operator* that satisfies (G*1)-(G*8), if we define the contraction operator - by

then contraction operation - satisfies ( G-1 )-( G-8). Conversely, given a contraction operator - that satis­ fies (G-1)-(G-8), if we define revision* by

then this revision operator satisfies (G*1)-(G*8).

If we rewrite (R --+ C) in our terminology, we get tP e J.l = (.,P v tP 0 -,J-l), because the set consisting of both .,P and .,P o -,JJ is inconsistent when .,P implies f-l· This means that the result of contracting J.l can be obtained by adding some models of -,J-l to the models of the old knowledge base. Adding some models of -,J-l is necessary to guarantee that .,P e JJ does not imply f-l· However, we might think it wise to also add some models of -,.,p 1\ J-l or delete some models of .,P. The following Theorem shows this is not desirable; the requirement that the new KB be obtained by adding only models of -,JJ to the models of .,P is necessary and sufficient for guaranteeing that old knowledge¢ is recoverable from tP e J-l together with f-l·

Theorem 4.1 The following conditions are equivalent.

1. tP implies ¢ if and only if tP e f-l implies f-l J ¢.

1. Mod(.,P) = Mod(.,P e p) n Mod(p.) .

4.2 Complex Contraction

It is not hard to imagine using compound sentences in a revision, e.g. "it will rain or snow tomorrow." It might be harder, at first glance, to imagine a need to contract a complex sentence. However, consider the following ex­ ample.

Example 4.1 Let a represent the fact that roads are covered with snow, let b represent the fact that roads are frozen. Suppose that we know roads are slippery if and only if they are covered with snow or frozen. Suppose we know there have been no accidents all day, casting doubt on our belief that roads are slippery. The way to update the knowledge base is precisely to contract a V b (i.e., tP e (a v b)).

Note 4.1 Example 4.1 brings out an interesting point. Let c represent the fact that roads are slippery. Sup­ pose that we have the knowledge base .,P defined by c 1\ (c =a V b). That is, we know that roads are slippery if and only if they are covered with snow or ice. If we use the contraction function e defined from Dalal's re­ vision function, .,P e c is equivalent to a V b. Hence, by contracting the knowledge that the roads are slippery, we also lose the notion of what "slippery" means. This example suggests that we are not quite modelling things in the right way. The next section shows how to do it right .

5 Integrity Constraints

Knowledge bases contain not only sentences offact about the world, but also integrity constraints that are in­ tended to ensure that the KB is an appropriate repre­ sentation of the world. In the deductive database litera­ ture, it is common to regard constraints as sentences ex­ pressed in the same language as the KB. Reiter [1988] ar­ gues that it is more appropriate to represent constraints in an epistemic modal logic when the KB is a set of first-order sentences. We adopt a different point of view here; we express knowledge and constraints in the same language, but treat them differently under update. In­ tegrity constraints are considered invariant, and updates are restricted to produce KB's which are consistent with the constraints. Winslett [1988] and Satoh [1988] take a similar approach. We present a modification of revision and contraction that accomplishes this and avoids the unintuitive results of Note 4.1.

Let IC be a propositional formula which represents an update-invariant component of the knowledge base. That is, we want the KB to imply IC at all times. (Note this is not the only possible way to model integrity con­ straints; see [Reiter, 1988] for a discussion of other ways.) For each revision function o and each contraction func­ tion e, We define ole and ere by

and

Intuitively, when revising the KB with JJ we make sure that the constraints will hold in the result by attaching IC to JJ. When contracting JJ, we avoid an accidental contraction of IC by replacing JJ with IC :::> JJ.

The following theorem shows that ole and ere inherit desirable properties about o and e, respectively. We consider the following condition corresponding to (R3).

(R3') if JJ A IC is satisfiable then t/J ore JJ is also satisfiable.

Theorem 5.1

1. If o satisfies conditions {R1}---{R6), then ore does {R1}, {R2), {R3'}, {R4)---{R6). In particular, if t/J implies IC then t/J ore JJ implies both JJ and IC.
2. Similarly, e re inherits properties of e. In partic­ ular, if e satisfies the conditions corresponding to {G-1}---(G-6}, then
3. (a) if t/J implies JJ and IC does not imply JJ then tP e re JJ does not imply JJ.
4. (b) if tP does not imply JJ then tP e re JJ is equivalent to 1/J .
5. {c) if t/J implies IC then t/J e re JJ also implies IC.

Before this section, we have abided by what Dalal calls the Principle of Primacy of Update : after revis­ ing KB t/J with sentence JJ, the new KB must imply JJ. This assumption is almost universal in the literature. In practice, it is of course unreasonable to expect the KB to blindly assimilate any new fact without questioning it. It is much more likely that a KB manager will se­ riously object to incorporating a sentence that violates an integrity constraint. Now that we consider integrity constraints explicitly, we see that primacy of update no longer holds; if JJ is inconsistent with IC, then ore is undefined (or produces the inconsistent KB). Similarly, if IC implies JJ, it is impossible to contract JJ by using ere 0

Example 5.1 We use the KB t/J from Note 4.1. Let IC be c = (a v b) . Suppose that both ole and ere are defined by Dalal's revision function ov. Then, t/J ore -,c (i .e., t/Jov(IC A-,c)) is equivalent to (c = aVb)A-,aA-,bA -,c, and tP ere c (i.e., tP v tP ov ...,(Ic :::>c)) is equivalent to c =a V b.

6 Elimination

Elimination is used to discard all the knowledge con­ cerning n where n is a set of propositional letters. We denote the new knowledge base obtained by elimination as t/J 0 n . Then, the new knowledge base should have the following properties.

• (E1) Let r be the set of all propositional formulas, <{J , such that <P is implied by t/J and that no letter in n occurs in </J. Let <T be a formula in which some letter in n occurs. Then, f implies <T if and only if t/J 0 n implies <T.
• (E2) Let <P be a formula in which no letter inn occurs. Then, t/J implies <P if and only if t/J 0 n implies <{J.

Intuitively, (E1) means that t/J 0 n loses all the non­ trivial information about n . (E2) means that t/J0f2 does not lose any information about nc 0

The following theorem shows that Conditions (E1) and (E2) uniquely determine the elimination function.

Theorem 6.1 t/J0f2 satisfies Conditions {E1} and {E2} if and only if t/J 0 n = resn( 1/J).

Weber's revision operator ow we referred to in Sec­ tion 3.3.5 is now defined as follows. If neither t/J nor JJ is unsatisfiable, then t/J ow JJ is defined by ( t/J 0 11) A JJ , where n is the union of the minimal sets of Diff( 1/J, JJ) . If either t/J or JJ is unsatisfiable, then t/J ow JJ is defined as 1/J.

Winslett [1987] proposes another revision operator oM defined by t/Jo M JJ = ( t/J0f2)AJJ where n is the set consist­ ing of all the propositional letters which occur in JJ. The revision operator violates the Principle of lrrevalence of Syntax because n depends on the syntactic representa­ tion of JJ. She tries to represent contraction by revising the knowledge base with a tautology, e.g., tP e a is rep­ resented by t/J oM (a V -,a).

The following theorem shows that elimination cannot be represented by contraction in general.

Theorem 6.2 Let o be a update operator defined by a persistent assignment of total pre-order $..p to each KB 1/J . Let e be the contraction operator defined by t/J e JJ:: ( t/J V t/J o ...,JJ) corresponding to the equation ( R - C). Let n be a set of propositional letters. Then, the following two conditions are equivalent.

1. There is no JJ such that t/J e JJ:: t/J 0 n.
2. There are two interpretations, I and I', such that

• (a) I <.pI',
• {b) I is not a model of t/J, but there is some model oft/;, J, satisfying Jln· = Iln·,
• {c) Iln· = I'ln·

Example 6.1 Let t/J is equivalent to a /1. (b:) c) /1. (c:) d) /1. (d:) b). Let 0 = {a, b }. Then, t/; 0 0 is equivalent to c =d.

On the other hand, let e be the contraction func­ tion defined by Dalal's revision function. Let I = < F, F, F, F > and I' = < F, T, F, F >. Then, I and I' satisfy Condition (2) of Theorem 6.2. Hence, for any J.L, tP e J.L is not equivalent to tP 0 n.

7 Recovery

Suppose we change our mind about an update we just performed and want to take it back; this is "what we call the recovery operation. How can it be implemented?

First, consider the recovery of revision. Let o be a revision function that retains complete new knowledge. Suppose that t/J is any formula and J.L is a formula that has exactly one model. Then, it is easy to show t/J o J.L = J.L. In this case, the new knowledge base depends only on the added new knowledge and is independent of the old knowledge base. Therefore, we cannot in general recover the old knowledge base t/J from the added new knowledge and the updated knowledge base.

On the other hand, if a contraction function satisfies (G-1) ....... (G-6) then the following holds.

1. If tP implies J.L then tP = ( tP e J.L) /1. J.L .
2. If t/; does not imply J.L then t/; ::: t/J e J.L. Note that t/;~(t/J8J.L)/I.J.L.

Hence, we can recover the previous contraction only if we know whether J.L was implied by the old knowledge or not.

8 Conclusion

Our main result is a model-theoretic characterization of revision schemes that satisfy Gardenfors' rationality pos­ tulates in the propositional case. Future research direc­ tions include extending these results to the first order predicate calculus and applying the results about revi­ sion to areas such as diagnosis from first principles, ab­ ductive reasoning, and database updates.

We have also presented some basic properties of con­ traction and introduced the operations of elimination and recovery: We have shown that recovery is in gen­ eral unachievable; a future research direction is how to carry along syntactic information in the knowledge base in order to make recovery possible.

Acknowledgements

We would like to thank Marianne Winslett for clarify­ ing the difference between her approach and Satoh's, and Mukesh Dalal for pointing out our earlier misun­ derstanding of Borgida's approach. We are grateful to Ray Reiter for introducing us to this area.