Schlechta K. Nonmonotonic Logics: Basic Concepts, Results, and Techniques

4.2. TECHNICAL DEVELOPMENT

!45

as a logic, taking as input a conjunction of literals from sl ... as, and giving as

output a conjunction of literals from tl ... tk.

Say that tk stands for the unimportant drug mentioned above. So given a set of

literals from sl 9 9 sn, I~ 1, ]"~ 2, i N s - representing the two expert systems and

the real expert - give identical answers with possible exception of tk. Order the

si and ti according to their index.

(a) We thus know that the maximal difference between any two of the three

logics is of size

1/k,

which can be tolerated from the medical point of view, so

the choice of one system is as good as any other. On the other hand, we may

also be interested in the average difference. For that, we multiply the expected

probability - i.e. the measure - of each symptom set with the difference between

the logics considered, i.e. calculate the integral of their difference. Administering

the drug tk unnecessarily causes unnecessary expenditures, vice versa, failure to

administer it when adequate will affect slightly the patient's well-being, and may

result in his reluctance to recommend the clinic - causing costs too. Assume this

cost can be estimated reasonably. We can then make a commercially well-tbunded

decision for one of our systems.

(b) Suppose, on the other hand, that we are still in the test phase of one expert

system as above, but know already from its internal structure that the decision

for tl. 9 tk-1 depends only on sl ... s~_,~. In our terminology, we can characterize

it as uniformly continuous for

1/k:

If the input differs by less than

1/(n - m),

then the output differs by less than

1/k,

which is tolerable. To test the system,

it suffices thus to test all values on sl... s .... instead of testing it on the full set

9 S 1 . . . 8 n .

Chapter 5

Theory revision and probability

5.1 Introduction

Recent interest in theory revision has partly centered around the work of

Ggrdenfors and his co-authors ([AGM85], [AM82], [GarB8], [GM88], [Mak85]).

The problem of theory revision is to "add" a formula to a theory, while preserv-

ing consistency, or to "subtract" a formula from a theory. In the process, only -

in some sense - minimal changes are to be made to the given theory and certain

plausible conditions to be satisfied. In general, however, logic, minimality, and

those conditions do not uniquely determine the process. In [GarB8] and [GM88],

this problem of choice in theory revision (more precisely: maxichoice contrac-

tion/revision) finds a natural solution in the concept of epistemic entrenchment:

An order on the formulae tells us which to choose. The orders of [Gar88] and

[GM88] have, however, theoretical as well as computational drawbacks: 1) They

are tailored to fit the requirements of theory revision and will not respect other

natural demands like r < ~b iff ~ < -7r (if I tend to believe more in ~b than in

r then I might tend to believe more in -7r than in ~). 2) For each revision of a

new theory (in a fixed language) we have to find a new order, so iterated revision

means iterated effort in ordering. Note that "theory" is used here in a technical

sense: a deductively closed set of ibrmulae (the deductive closure of a database).

Thus two theories might be closely related, and are not necessarily as different,

as say a physical and a medical theory. So iterated theory revision in this sense

is a very common phenomenon for cognitive systems.

The main aim of this chapter is to show how to overcome these drawbacks: 1)

To prove that one order of a very simple kind will do for all theories of a given

language and thus for all revisions (Proposition 5.8). 2) To show how to con-

struct such an order with particularly nice and natural properties for countable

propositional languages (Fact 5.18 and Proposition 5.19).

For a different treatment of iterated revision, see Spohn's work, e.g. [Spo88].

The last chapter is independent of the first part. In Sections 5.1 and 5.2 we

consider what Ggrdenfors and his co-authors call maxichoice contraction - choos-

ing a maximal subset KI of K, such that K! ~ A. As pointed out in [AGM85],

[GarB8] and [Mak85], maxichoice contraction suffers from a completeness prob-

148

CHAPTER 5. THEORY REVISION AND PROBABILITY

lem. Our point in Section 5.3 is, that theory revision with underlying axiom

sets is plagued by essentially the same problems (and some more). We consider

systems < K, A >, where K is a deductively closed set of formulae, and A is a

set of axioms for K. Theory revision for < K, A > will essentially amount to the

choice of a suitable subset of A. Proposition 5.23 shows that there is a contin-

uum between too coarse axiom sets (and too coarse revision) and too fine-grained

axiom sets (resulting in full completeness at revision).

To prevent possible misunderstandings, in particular in the light of the discussion

in Section 1.1, let us clarify the following. Theory revision works on a background

logic, denoted ~- here, and primarily intended as classical logic. "Consistency"

is with respect to this logic ~- . Theory revision can generate a new, in general

nonmonotonic, logic I,-~ , e.g. by setting A I ~-, r :~ AI [- r where A/is the most

reliable part of A, selected by theory revision. For a more technical discussion of

the connection between nonmonotonic reasoning and theory revision, the reader

is referred to [MG91]. The subject is taken up in more detail, and in a special

case, in Section 5.2.

For the convenience of the reader, we now repeat the - for our purposes - main

definitions and results of Gs and Makinson. But before that, let's give

an example to point out the basic problem of underdeterminacy.

A problem of theory revision

Let T be a theory, i.e. a deductively closed set of formulae. Suppose {A, B} C_ T,

thus A A B E T, and we would like to revise T to a maximal theory T! C_ T such

that A A B ~ TI. So {A, B} C_ T is impossible, and we have to withdraw A, B,

or both. (Leaving aside extreme cases like l- A ~ B) "both" is unsatisfactory, as

Tt should be maximal So we can and have to chose which of A or B, but logic

won't tell us which. If we have an order A < B telling us that we like A less than

B, we are finished.

This is the idea of

Gs and Makinson's solution

In the following, we adopt Gs and Makinson's terminology to make this

article more readable for those familiar with their work. They denote by "theory

contraction" the process of removing a formula from a theory, and by "theory

revision" adding a formula A to a theory T so that the resulting theory TI is

consistent (if A is) and

A E TI.

This is made precise in the following

Definition 5.1 Given a language s an inference rule ~- (we will not be more spe-

cific here, and the interested reader is referred e.g. to [GarB8]), and a "knowledge

set" K, i.e. a set of formulae of s closed under [-, then

a function K-: Formulae of s -~ Sets of Formulae of L: is called a contraction

function for K, iff it satisfies the postulates (K-l) to (K-8) below, and

5.i. INTROD UCTION !49

a function K*: Formulae of Z; --+ Sets of Formulae of s is called a revision function

for K, iff it satisfies the postulates (K * 1) to (K * 8) below.

Proposition 5.2 Both notions are interdefinable by the following equations: K*

A := (If - -~A) + A (where L + B is here the deductive closure of L U {B})

i.e., if K- is a contraction function, then K* so defined is a revision function, and,

K- A := K n(K *~A)

i.e. if K* is a revision function, then K- so defined will be a contraction function.

The proofs are straightforward.

We now state the axioms for K- and K*, some very short comments are given in

parentheses, the reader wilt find more motivation e.g. in [Gar88]:

Definition 5.3 (K-l) K - A is a knowledge set (i.e. deductively closed under

~-),

(K-2) • - A c_ K,

(K-3)

If A r K, then K - A = K (the desired result already applies to K),

(K-4) If ~/A, then A ~ It" - A (success, if possible),

(K-5) It" __ (K - A) + A (where L + B is the deductive closure of L U {B}, the

"postulate of recovery"),

(K-6) IfF-A~B, thenK-A=K-B,

(K-7) (K - A) A (K - B) _C_ It" - (A.A B) (a condition of minimatity),

(K-8) If A r K - (A A B), then K - (A A B) C If - A. (In general, the more

specific a formula is, the less the change necessary for revision. If A f/_ K-(AAB),

however, then contraction by A A B will do already.),

an d,

(K*I) K * A is a knowledge set,

(K*2) A E 1( * A (success),

(K*3) K * A G K + A (the purpose of K * A is to "add" A to K, if consistently

possible),

(K*4) If -~A r K, then I( + A C If * A (see K*3),

(K*5) K * A = K• (K• the inconsistent theory) only if F- --A (preserve consis-

tency, if possible),

(K*6) IfbA~B, thenK*A=K*B,

(K*7) K 9 (A A B) C_ (K * A) + B (consider K*2 and minimality for motivation),

(K*8) If -~B ~ K * A, then (K * .4) + B ___ If * (A A B) (see K*4!).

By the above interdefinability result, it suffices for our purposes to consider con-

traction only in the following.

As already pointed out, a suitable order on the formulae of Z; will give rise to a

unique contraction function for maxichoice contraction. Gs and Makin-

son consider relations of "epistemic entrenchment", where A _< B means that B

is more deeply entrenched, and we are more willing to give up A than to give up

B, if need be, and provided we have a choice. This is made precise in

150

CHAPTER

5. THEORY

REVISION AND PROBABILfTY

Definition 5.4 Let <_ = _<a" be a relation relative to a knowledge set K on the

formulae of 12 such that

(EEl) If A _< B and B _< C, then A <_ C (transitivity),

(EE2) if A F- B, then A < B (If A F- B, then we believe at least as much in B as

in A.),

(EE3)

for any A and B, A < A A B or B < A h B (Essentially this property

makes _< a total order, and gives the necessary decision for contraction.),

(EE4) when K r K• (the set of all formulae of 12), then A r K iff A < B for all

B (It is here that K matters!),

(EE5) if B _< A for all B, then F- A (Only Truth is maximally entrenched).

We then call _< a relation of epistemic entrenchment for K.

We may read < as strength of belief, where everything outside K is not believed

at all.

Again, we have an interdefinabi!ity result:

Proposition 5.5 The function K- and the ordering <K are interdefinable in the

following sense:

DefineK-AbyBEK-A:~BEKand(A<AVBor~-A) (A<Bmeans:

A_<B, and not B <_ A).

If _< satisfies (EE1)-(EE5), then K- so defined will satisfy (K-1)-(K-8).

Define A _< B (on the formulae of s by A < B :~ A r K- (AA B) or ~- AA B.

If K- satisfies (K-1)-(K-8), then _< so defined will satisfy (EE1)-(EE5).

Outline of the results presented here

As emphasized, any < satisfying (EE1)-(EE5) will depend essentially on K. Thus,

for iterated revision, as K changes, we need a new order <-K for every step. Our

Proposition 5.8 will show that, given an episternic preference relation _< for s

i.e. a total ordering of the formulae of g which satisfies some very natural re-

quirements (and which correspond well with the order of the Lindenbaum-Tarski

algebra), we can construct from that <

foraI1K

an order _<h- satisfying (EE1)-

(EE5). Proposition 5.9 witl show the inverse: Given an epistemic entrenchment

relation, we have a epistemic preference relation too, such that the construction

of Definition 5.6 will recover the epistemic entrenchment relation again.

Propositions 5.16 and 5.t9 will show how to naturally define an order satisfying

the prerequisites of Proposition 5.8.

We assign subsets of the (real) unit interval [0,1] to the propositional variables

of a given language in a suitable independent way (Definitions 5.11 and 5.13).

Based on this assignment, we can ascribe well-behaved probability measures to

formulas (Definition 5.14, Lemma 5.15), resulting in an epistemic preference re-

lation (Proposition 5.16). The result is improved to uniqueness up to logical

equivalence in Proposition 5.19. The rest of Section 5.2 treats an extension and

a backward approach. In Section 5.3, we turn to theory revision based on axiom

sets, discussing essentially the completeness problem of maxichoice contraction

in the framework of axiom sets.

5.2. EPISTEMIC PREFERENCE RELATIONS 151

5.2 Epistemic preference relations

Definition

5.6 a. Call a relation < on the formulae of Z: an epistemic preference

relation for s iff < is a binary relation such that

1. AI- B--* A <_B,

2. < is transitive,

3. < is total,

4. VB.B < A ~ F- A.

b. Let K be closed under F-, and an epistemic preference relation _< for s be

fixed. Define A -< .B iff

D1.

AF-Bor

D2.

A ff K or

D3.

B = A A C and A <_ C and A A C = B G K.

Furthermore, define -~ as the transitive closure of ~ ..

Fact 5.7 There is a standard way of establishing A -4 B: Let A, C E K, then

there is B such that A~.AABbyD3, andAAB_~.CbyDliffA<A--*C.

Proposition 5.8 If

_< is an epistemic preference relation for/2, and ~ defined

as in Definition 5.6, then -z, satisfies (EE1)-(EES).

Thus, given one global epistemic preference relation for s we can easily obtain

epistemic

entrenchment relations for all knowledge sets K of s

Proof We first show two claims, the proof will then be trivial.

Claim 1: For no A E K, B ~ K we have A ~ B. Proof: Suppose the contrary.

Let A = A1 _ .A2 ~ 9 ..._ .A~ = B. We have to "cross the border between

K and s - KI! somewhere: There is Ai _ .Ai+I such that

Ai E K, Ai+I f[ K.

Examine the cases of _ .. D1 can't be, as

Ai E K, Ai ~- Ai+l

implies Ai+l E K.

D2 can't be, as Ai G K. D3 can't be, as

Ai+l f[ K.

Contradiction, [] (Claim 1)

Claim 2:

VB.B -~ A --~ I- A

Proof: (Induction on the length of the _~ .-chain.)

By Condition 1., it suffices to consider B :=

True. True ~_ "D1 A --~ F- A. True

-<: OD2

A can't be, as

True G K. True ~

*D3 A .~

True A C --+ True <__ C --+

F- C by maximMity of

True

and 4. of _< . [] (Claim 2)

We prove the proposition: (EEl) is trivial by definition. (EE2) by D1. (EE3)

We have to proveA-~AABorg~AAB. By 3. of<_,A<_BorB<_A. Case

1: AA B E K. If

A < B,

then A ~ .A A B by D3. B < A analogously. Case 2:

A A B r If. Then

A {[ I(

or

g ~[ I(,

continue with D2. (EE4) "-+": A r If --~

A ___ .B by D2 for all B. "*-": Let K # K• A _~ B for all B. Suppose A E K,

By K ~ K• there is B ~' K, and by prerequisite A -< B, contradicting Claim 1.

(EE5) Claim 2. [] (Proposition 5.8)

G~rdenfors (in personal communication) has raised the question whether we can,

given a relation of epistemic entrenchment, define from this relation an epistemic

preference relation and recover the episternic entrenchment relation again as in

Definition 5.6. The answer is "yes" (in a simplified version due to David Makin-

son) :

152

CHAPTER 5. THEORY REVISION AND PROBABILITY

Proposition 5.9 Let <_K be an epistemic entrenchment relation for a knowledge

set K. Then, by definition, _<K is an epistemic preference relation and _ defined

for this --<K and K as in Definition 5.6, b. is equal to _<a. []

We now turn to the task of defining such a total order on the formulae of s in a

natural way.

Let, in the following, D be the Lindenbaum-Tarski algebra for the language s and

the empty theory. (Thus, elements of D have the form [05], where 05 is a formula

of t;, and [05] = [~b] iff k- 05 ~ ~b. Moreover, [05] A [~b] := [05 A ~3], -[05] := [-~05], and

[05]

<

[@1 [05] A [q = [05]0

We have a first constructive result:

Lemma 5.10 Extending the natural ordering on the formulae of /2 given by

D to a total order, preserving

[Trite]

as the only maximal element, will give

an epistemic preference relation for /2, and thus, by Proposition 5.8, epistemic

entrenchment relations -<a" for all knowledge sets K of/2. []

Next, we assign probability values to formulae of/2, i.e. each ~b E/2 will have a real

value •(05), and the natural order of the real numbers will order the formulae too.

Of course, logically equivalent formulae should be given the same probability.

We proceed indirectly, assigning first probabilities to models, and defining the

probability of a formula as the sum of the probabilities of its models. The above

equivalence condition will then be trivially true. It is easily seen (Proposition

5.16), that our construction will give an epistemic preference relation < for s as

needed to define the epistemic entrenchment relations <__K 9 We can improve our

result and the equivalence condition to obtain (q5 _< ~b and ~b _< 05) iff ~- 05

~b (Proposition 5.19). For this end, we use algebraic closure properties of the

reals (Fact 5.18). We can thus construct in a natural way a total (and natural)

extension of the natural order of the Lindenbaum-Tarski algebra D, such that

([05] < [@] and [~b] < [05]) is equivalent to [qS] = ['~b]. In conclusion, we remark that

the whole process can be easily relativized to a fixed theory, by considering only

models of that theory (see Definition 5.21).

But first, we need some constructions:

Let A be the or-Algebra (i.e. the Rl-complete Boolean algebra) of Lebesgue-

measurable sets restricted to subsets of the unit interval [0,1). Let # be the usual

Lebesgue measure.

Definition 5.11 Let < zi : i E co > be a sequence of reals in the open interval

(0,1)-

Define by induction: ao := [0,x0), b0 := {0, z0, 1}. Let a~, b~ be

defined

(,~ c co).

b~ will be a set of 2 ~+1 + 1 elements, a~ a disjoint union of 2 '~ non-empty intervals.

Let b,~ = {yj : j < 2 n+~ + 2}, the yj in increasing order. Define a~+~ := U { [ yj,

yj+(yj+l-yj)*x,~+~ ) : j < 2 n+l +1 } and b~+l := b~ tO {16+(yj+l-yj)*x.=+l:

j < 2 ~+~ + 1}. Finally, set a~ := [0,1) - a,~. (See Example 5.1 below.)

Let B be the Rt-complete subalgebra of A generated by

{ai : i E co}

5.2. EPISTEMIC PREFERENCE RELATIONS 153

Fact 5.12 For the ai thus defined we have:

!) ~(a~) = x~,

2) #(a~) = 1 -#(a.) (trivial),

3) #(A{cn : n E X}) = H{#(c~) : n E X} where c~ is either a= or ~ for X C

finite, by the "independence" of the construction. This property is essential to

all that follows. []

Let, in the rest of the Chapter, s = {pi : i E w} be a countable language of

propositional calculus.

Definition 5.13 a) Define f: s --~ {ai: i E w} by f(Pi):= ai, i.e. #(f(Pi)) = xi.

b) Let A4 be the set of assignments of truth values to finite subsets of s t E J~, t

defined on s 1 C_/:. (It suffices to consider finite subsets, as standard propositional

calculus admits only finite formulae.) Define g(t) := N{ai: pi E s l, t(pl) = true}

n N{m: p, c s t(pd

= false}.

Thus, #(g(t)) = #( n{m: pi E s t(pi) = true} N N{ai: pi E s t(pl) = false}

) = I~[{zi: pi E s t(pi) = true} * II{1 - xi: Pi E ~2/, t(pi) ---- false}, and we

have defined for every assignment t EAd a real value p(g(t)). There is a natural

way to extend this function to formulae:

Definition 5.14 Let r be a formula with propositional variables p, E s162 _ s

finite.

a) Let Val(r := {t E 2td: dora(t) = s t(r = true, i.e. q~ is true under t}.

b) So we can define t,(qS) := E {I,(g(t)): t E VaI(r

(See Example 5.1.)

Example 5.1 Let s = {p,q}, t(p) = true, t(q) = false, t1(p) = false, t1(q) =

true, r = p +e -~q. Then ao = [0, xo), al = [0,go

*

xl) U [Xo, xo -t-

(I --

go)

*

Xl),

9(t) = [Xo * xl, Xo), g(tl) = [Xo, Xo + (1 -- Xo) * xl). Thus, #(ao) = Xo, #(al)

=

a:l,

,(r = #(g(t)) + #(9(t/)) = Zo* (1 -- Xi) + (1 -- ZO) * Zl.

Our construction has the following properties:

Lemma 5.15 1) u(r is independent of dora(t) in the following sense: Let Z;r C

s C_ s finite. Then u(6) := E {#(g(t)): t E Val(c))} = E {tt(g(t)): t EAd,

= t(r = t ue}.

2) By definition of Vat and ,./, logically equivalent formulae will have the same

rest value L'(r

3) }- r --~ ~b implies t,(r _ ~,(g;).

4) =

i

-4r

5) Exactly the valid tbrmulae wilt have real value ,(r = 1.

6) u(r _< u(r ~ ,(~r _< ~,(-~r (by 4).

7)

4r v r < .(r ~ e r --, r

8) We can't expect u(r A r = ,(r * ~,(9) or u(r V ~b) = ,(r + u(r just think

of r = r These equations can only be valid if r and r are independent. For

this reason, we gave first a value to models, which are independent, and then to

formulae. []

154

CHAPTER 5. THEORY REVISION AND PROBABILITY

We have thus proved our main constructive result:

Proposition 5.16 Let

pi : i E co

be given a probability xi E (0, 1), then this

gives rise naturally to probabilities ~,(r for any formula in s such that 1) - 6) of

Lemma 5.15 are valid, and thus to an epistemic preference relation <__ for s i.e.

satisfying 1. - 4. of < in Definition 5.6, and thus the prerequisites of Proposition

5.8. []

Fact 5.17 Let 0 < a < b < 1. Augment the natural order of the reals by setting

x _<+ y for all a _< z, y _< b, i.e. "identify" all elements of the interval [a,b]. Let

L, be defined as in the construction leading to Proposition 5.16 and set r __< 4 iff

~'(r -< ~'(4) or L,(g?) _<+ ~,(r Then __< is still an epistemic preference relation on

s

Example 5.2 Consider now/2 := {A,B, C}, and set

#f(A)

:= 1/2,

#f(B)

:=

1/3,

#f(C)

:= 1/5, a := 5/30, b := 10/30, and identify in the interval [a,b] as

described in the above Fact. Then ~,(A) = 15/30, ~,(B) = 10/30, t/(AAB) = 5/30,

~,(AV C) = 18/30, ~,(B V C) = 14/30, ~((A A B) V C) = 10/30. By identification,

(A A B) V C < A A B, but neither A V C _< A nor B V C < B. []

So far, it is quite possible that ~,({4) = ~'(4), but [;/ r ~ 4. We now make ~,

injective (modulo ~). Thus, we improve our result such that (r < 4 and 4 < r

iff I- r ~ 4. Choosing the zl of Definition 5.11 above according to the following

fact on the reals will do the trick:

Fact 5.18 Let X :=

{xi : i E w} C I C_ ~, I

uncountable be given. Then

there is xl E I such that z/ is not equal to any real that can be obtained by

finite addition, subtraction, multiplication, division from elements of Q tl X.

(Card(I) > card(Q

U X) = ~0 suffices for the proof.) []

We choose the

zi

for the above construction of the ai in Definition 5.11 according

to this fact.

Suppose that r 4 are not equivalent, but u(r = u(4). Thus, there is an assign-

ment t such that t(r r t(4). So U{g(t): t E Vat(C)} r U{g(t):

t E Val(4)}

(w.l.o.g. all t with the same domain p0...pn, and n chosen least such that the

assumption is valid), but ~,(r = ~'(4). Thus, u(r = E{II{y~j : j = 0,...,n} :

i = 0,...,m}, u(4) =

E{fI{yli,j

: j = 0,...,n} : i = 0,...,rnl}, where the

Yi,j,

yli,j

are either

zj

or 1 - zj. After multiplication, the equation looks like this:

sl + ... + sk = tl + ... + tt, the s~ and t~ are of the form: 1 or_+ 0cTl* ...* ZTh,

and each

xj

occurs at most once in each summand. After cancelling summands

of the same form that occur on both sides of the equation, x~ will still occur

in at least one of the summands, as n was chosen least. So, we can solve the

equation (linear in x~) for xn and have ~n =

f(xo...

X~-l), where f is composed

of addition, subtraction, multiplication, division - contradicting Fact 5.18. As

the z~ can be chosen within any distance > 0 from a desired value, choosing xi

according to this fact is no real restriction.

5.3. REMARKS ON DIFFERENT APPROACHES

155

We have thus obtained our injectivity result and shown:

Proposition 5.19 Let pi : i E w be given a probability

zi

E (0,1), chosen

according to Fact 5.18, then this gives rise naturally to probabilities v(~b) tbr any

formula in s such that 1) - 6) of Lemma 5.15 are valid, and (~fi _< ~ and ~ < ~fi)

iff~- ~ ~ ~.

In other words, this defines a total (and natural) extension of the natural order

of the Lindenbaum-Tarski algebra D, and, in addition, ([q~] _< [~] and [~] < [~])

iff

[r = []

Remark 5.20 So far, we have worked over the empty theory and its

Lindenbaum- Tarski algebra. It is easy to extend our results to non-empty theo-

ries, by considering only models of that theory in our Definition 5.14.

Thus, we can define e.g.

Definition 5.21 Let T be a theory in

s

-- /2 finite,

E {tL(g( t) ):dom(t)=s dJ=true,t( ~ )=truef orall~ET}

~'T (q~)

:=

~{,(g(t)):do~(t)=c,,~(~)=,,-,,~So~-~ll~e:r}

and/2/ := /2:, U/2r Set

So VT(~b) and ur(~bt) will be equal, if[ the models that make T true treat • and

~bl in the same way.

Remark 5.22 We can work backwards in the following sense too: Suppose we

are given a set of formulae {r i E [} and preferences (probabilities) ~-(r for

all i E [. Can we find a sequence

:ci : i E w

such that, constructing as above,

~r(r = u(r := E {tt(g(t)) :

dorn(t)

= Z;~, t b r The answer is trivial and

canonical. We have a number of equations 7r(r = E { II{xj :

t(pj) = true}

9 II{(1-xj)

: t(pj) = false}: t E Val(r

} and any solution {zj : j E w,

zj E (0, 1)} (if there is one) of this system of equations, and

{aj:

j E w} chosen

as above will do what we need.

5.3

Measuring theories, and an outlook for a

different treatment of theory revision

In this Section, we discuss three somewhat different approaches to theory con-

traction. In the first two, we extend our measure from formulae to theories, and

use it to do contraction. The first attempt is very naive, and mentioned only for

illustration. The second approach is again, as in Section 5.2, "maxichoice con-

traction" in the sense of [AGM85], [Gar88], [Mak85], and as such plagued by the

well-known completeness result: K - A U {-~A} is a complete theory (see below

for a proof).

In the third case, we take a totally different approach and consider pairs < K, X >

, where K is a theory, and X an axiom set for K~ see also [Neb89]. This approach

suffers from another defect: it is highly dependent on the syntactic structure of

the axiom set: The "coarser" the axiom set is (in the one extreme the conjunction

Schlechta K. Nonmonotonic Logics: Basic Concepts, Results, and Techniques

Подождите немного. Документ загружается.