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

54

CHAPTER 2. PREFERENTIAL STRUCTURES

Proof

-a

<LM,-~

:~-'-~"

~ ~-LM, ~ A ~ eLM, /3 ~ ct <LM, 3 A .-n(/~ <LM, oz) e-,.

~,~e X). ~

The results of G~irdenfors and Makinson

Some of the results in [GM91] relating orderings and logics can be described -

very briefly - and connected to our definition as follows:

[GM91] work with a slight generalization ~- t of ~-, such that

1. }- C_ ~- I (as a relation)

2. I- / is compact

3. A + x' N A--~' C A + (x V y-)', (where T' := {r T }-/r

-, (%' -,

4. ~- I is a Tarski consequence relation, i.e., A C A, = A, A C_ B --*

A~ __ B'. The authors calll~ consistency preserving with respect to F- I iff AI~ _1_

--* A ~- LL. The logic I- / is connected to preferential models as follows: Any

cpm JM gives rise to such a logic t- I by "forgetting about

-<": A ~ tx :~

Vm E MM(A).ra ~ x (instead of

#~(A)

for I~). M~(A) is here the set of

models of A in the structure 3,t. To simplify the picture, we largely ignore I- I -

we will not miss any basic ideas and just assume that ~- / =~-, i.e. essentiMly that

all models in ML occur in the structure.

Fact 2.13 1) ([GM91]) Given F- and t~, ]~ satisfying R, and consistency pre-

serving with respect to t-, the definition

(*) 9 _<aa~ y :~ (true ~ x A y or ~(.~ A y) l§ ~)

gives an order _<au on /2, satisfying the postulates EE1-EE3 of an epistemic

entrenchment relation (defined in Chapter 5). (a

<aM

fl :~ (a <--aM /3 and

9 : aM :taM

2) (GM91) Conversely, given such _<aM satisfying EE1-EE3, t~ _<aM defined by

(**)

a[~ <aMX :~-~ (a ~- a or 3b(a A b I- x and -~a <aM b))

will satisfy" R, and be consistency preserving.

Remark 2.14 (This Kemark is our own.)

a) From (*), we conclude: x <-Gu y ~ -~y <- ~x and a <Gu ~ ~ ~ < -~a

b) <-a~ satisfies also EE5.

c) Note that changing _<aM by lifting true to become the only top element (up

to equivalence by K) won't change the logic defined by (**). So we can assume

without loss of generality that EE5 holds. The important thing is, that then

<aM Y ~ (true ~ x A y or ~(x A y)I~ <_~MX), i.e.(*) holds:

d) If

~UM

satisfies EE1-EE3,EE5, and I~ 4~ <_oM is defined as in (**), then

1) x <aM Y ~ (true ~- z A y

or -~(z A y)lV t z) and thus

2) al~ x ~ (a~-zor ?b(aAbl-x and --b < a)). (Note that <aM has become

< as defined in 2.1.2.i. Moreover, -~b < a ~ -~b <

true

(in R) --~

truel~ b

by 8)

a) in Fact 2.7.)

Thus the amount of additional information we can use depends on the size of

a: K a is very large, e.g. true, we can use many additional b's. If a is small,

2.1. PREFERENTIAL STRUCTURES

55

e.g. • nothing is smaller than Z, so we can't use any additional b's, which gives

consistency preservation.

Proof a)

true b zAy e+ -~xV-~y

~- _1_ (by a semantic argument). By consistency

preservation, -~x V "~y ~- • ~ -~x V -~y l~ • Thus x <au y ~ ~x V -~y I~ _[_

or-~xV-~y]r x ~-+ -~z r -~y ~ -~y < ~x. And ~ <au /3 ~ /3 fay_ ~

b)

<_au

also satisfies EE5: It suffices to show

true <_au y --~

true I- y.

Suppose there is :q,

true <_au y, true ~/ y,

so

true ~/ true A y.

Thus, by

definition,

~(true A y)17 ~ true.

Contradiction.

d)

1) 37 ~-~GM

Y e-+ (true ~- X A y

or -~(z

y <aM x +-~ (true V z A y

and -,(z A y)

~' --+" Y <GM a -4 X A ff ~GM Y "<GM Z,

If

true }- x A y,

then x }- y, so z _<GM

A y)17 ~ z): Equivalently, we can show

1~

but ~(z A y) A z ~- x, thus -~(z A y)),-~ z.

y -4 y f:aM x. " ~-"

Case 1 (of Def. of

I~ ): Let

true ~/x A y

and -~(x A y) t- x. Thus -~x ~- x, so

true ~- z,

thus

true ~/y,

so by EE5

y <aM x.

Case 2:

true ~/x A y

and exists b su& that ~(x A y) A b ~- x,

b ~GM xAy. Then

b f_aM x

or

b raM Y. If b raM z,

then z <aM b, so

~x I~ x, so -~x I~ • so by consistency pres. ~x f- _1_, so

true ~- z,

and b <_GM x.

Contradiction. Thus b <~M z and b 2~CM Y, so 5' <aM b <GM x ~ y <aM z.

2) al ,-~ x +-+ (a F- z or

3b(aA b F- x

and -~b < a)): As (*) is

satisfied, we

use a) to

see that a <aM /3 *-+ -~fl < -~c~. So the defining condition for l~ is equivalent to

al~ x e-+ (a J- x or

~b(a A b }- x

and ~b < a)). []

We are now in a position for a reconstruction of the completeness results:

Completeness

results

Our intention is to give the reader the essential ideas, and we feel free to use

semantic arguments (as already above) - in hindsight, so to say.

We closely follow the respective articles.

Completeness proof for P in [KLM90] Any logic IN satisfying P can be

represented by a smooth, irrefexive, transitive cpm, i.e. there is such .M such

We use the notation of [KLM90].

l~ecollect that: a ~KLM fl :e-+ c~ V 9 ] N c~. The representing structure M =<

M,~> is defined by M := {< rn, c~ >: rn is a normal world for c~, i.e. m ~}

and < m,~ >-<< n,/3 > :~ ~ _<KLM fl and m ~: /3. (This is the canonical

model.)

Lemma 2.15

a <--IfLM fl, Tl'l ~ ~,/~ --4 rl% ~ 3.

56

CHAPTER 2. PREFERENTIAL STRUCTURES

Proof aV~l~ c~ -~

m(,8) FIp(a) C_#(fl) --~ (~1~ ~ --, a!~ ,3 ---, ~).

Lemma 2.16

a

~KLM /3 ~KLM "[, rg~ ~ ~,"7 -+ 'In

>

~.

Proof

c~ <KLM /3 <--KLM "/ ---* #(a) N m(',/) C #(/3) -+ (/3 I~ ~ ~ c~ l" 7 ~ ~).

(Supposem 6 #(c~),m ~7, mr By .3V7l~ /3, there isml-4m, mr~/3,

by a V/3 [,-~ a, there is m~ _-_4 m~, 'rra~ ~ c~. Contradiction.: m ~ % m/ > ,3,

mt~

~ a with

,mlt --< m/ -4 m. ) []

Lemma 2.17 Transitivity of -<: < m>c~2 >, < ml,c~l >~ -~a~., < m0, ao >~

=c~ with < m0, ao >-<< m~,a~ >-<< ma, a2 > .

Proof The crucial thing to show is < too, do >~

~c~.

But < m0, ao >~ c~2

< m0, a0 >~ ~ (by Lemma 2.16). Contradiction. ~.

Lemma 2.18 < m, /3 >E >(~) ~ <rn,3>pce,/3<_KLMa.

Proof '%-": Suppose < m,/3 >~ a, < n,7 >~ a,,=/3 with < n,3' >~4<

m,/3 > . By 7 __KLM /3 _<n'LM a and Lemma 2.16, <

n,'y

>~/3. Contradiction.

~'-+': Suppose/3 ~KLM c~,i.e, c~V/31.~ /3, let n ~ aVfl, n > ~/3, so n ~ c,

< m,/3 >~ ch < n,c~V/3 >~ ~,-~/3 with < n, aV/3 >-<< m,/3 >. So < m,/3 >~

c3

Remark 2.19 c~ V /3 1.~ /3 does not imply (in P) that there is r, c~ V/3 {~ r,

/3176 r: m ~ a,/3, mr ~ c~, ~/3, 'rail ~ a,/3 with m/-< m. Here a V/3 IVt /3. And

c~V/31~ r ~--~-(eA~/3) V(c~A/3)=aA(~V-~/3)--:o~l-r,/31~ r~--~aA/3Fr.

Lemma 2.20 & is smooth, where a := {< ra,/3 >: m ~ a}.

Proof Let

<( m, fl ~>~ o& If fl

<--KLM Ct,

i.e. a V ,3 IN /3, then <

ra, fl >e

if(a) by Lemma 2.18. Otherwise, there is 'n ~ aV~,-,/3, a: < m,3 >~ 5,

< n, aV /3 >~ a,-~/3 with < n,c~V /3 >-<< m,~ >

Burthen

< 'n, a V /3 >E p(a)

by Lemma 2.18. []

Crucial for the representation is:

Fact 2.21 1) < m,a >6 >(c~),

2) <

><

< m,/3

a.

Proof 1) is trivial by definition of ~ .

2) < m, fl >~ #(c 0 --+ fl <_KLM a (by Lemma 2.18) ~ <

m,/3

>~ ~ (by Lemma

2.15)

2.1. PREFERENTIAL STRUCTURES 57

Completeness proof for ~ ([LM92]) Any logic I~ satisfying R can be

represented by a smooth, ranked, irrefexive, transitive cpm. We use notation of

[LM92]. Recollect that ce <LM /3 :+-+ c~ V /3 I~ ~/3. The representing structure

A.'l =< M,-~> is defined by M := {< m,c~ >: m is a normal world for c~, i.e.

ra ~ ~} and < m, cz >--<< n,/3 > :~ ~

<LM /3.

This is again the canonical

model.

Lemma 2.22 In P holds: /3

<LM ~ --~ /31~ ~

Proof c~Vfll-~ -c~--*fli~ ~a. []

Lemma 2.23 Transitivity of -~ holds in P.

Proof c~ <LM /3 <CM 7 --+ c~ < y (by Fact 2.7, 2b, and our above comparison

result.) Moreover, c~

<LM

7 ---+ c~]~ ~7 by Lemma 2.22. []

Lemma 2.24 In P holds:

Con(a, fl) --+ a V fllg~ -~fl

Proof

Con(a, ~3) ---, c~ 7g -,/3 -+ a V /3 {J-, -~/3 []

Lemma 2.25 InPholds: <m,e>E/z(/3)-4 aVfll9 ~ ~c~,c~V/3Ir -'fl

Proof < m,c~ >E #(fl) -+ < m,c~ >~ a,/3 --+ aVflI7 ~ ~fl by Lemma

2.24. Suppose c~ V/3 [~ -~c~, thus /3 <LM a, and /3 [~ ~a. Then < m,c~ >,

< n, fl >~-fl,-~a

with <

n,/3

>-~< m,a > so <

m,a

>~ #(fl). []

Corollary 2.26 In P holds: < m, c~ >E #(a).

Proof Let <

n,fl

>-<<

m, oe

>, ~hen <

n, fl >~ ~a. []

Lemma 2.27 In R holds: 5 is smooth.

Proof Let < m,/3 >~ ~. By Lemma 2.24, oe V/319 ~ -.a.

Case1: aV/3[N ~/3. Thena<LM/3, al~ ~fl, and<rn~/3>~ce,<n,a>~-~/3,

with < n, o~ >-~< m,/3 >, < n, c~ > is minimal in & by Corollary 2.26.

Case 2: c~ V fl[r -~/3. If < m,/3 >r #(a), then < rn,/3 >~ a, < n,7 >~ a with

<n, 7>-4<m,/3> for some<n, 7>.

Then by Lemma 2.24 7 geM a. By R, 7

<LM fl, 7 ~.LM a ~ o~ <LM

fl

a V fl]~ -7/3. Contradiction. ~.

Lemma 2.28 In R holds: < m, a >E #(/3) --*- < m, a >~ ~.

Proof By Lemma 2.25, c~ V/3 {5# ~a. Now, /3 1 ~-, "~ ---* a V/3 {~ /3 ---+ 7 (see

the completeness proof in [KLM90I). By R, and ce V/3 ]5~ -,a, a IN /3 ---, 3' for

/31~" 7. As < rn, c~ >~/3, < m,a >~7 for all flJ~ 7. []

Rankedness is a direct consequence of R, see Fact 2.7, 10), and c~ <LM /3 ~ /3 < c~

for a, /3 {~ -consistent.

58

CHAPTER 2. PREFERENTIAL STRUCTURES

Completeness proofs for [LM92] and [GIM91] We use the ideas in [GM91]

to give a second proof for the [LM92] result, too. The reader will notice that the

axiom R (or its consequences) is used here extensively.

Let < be total and transitive, and x < y ~ y f x. Let x + := {y : x < y},

X := {x} U {y: -~z < y}, 1}I := {rn C_ s m is maximal [--consistent ], and for

models m -< n :~ there exists x such that m ~ x +, n b -~x.

Then:

Lemma 2,29 1) a) z<y_<z-§ z < z,

b) x<y < z--~ x < z,

c) yE X- {~} ~ ~+ c_ X,

d) yEx + ~y+Cx +,

2) ~ is transitive,

3) -4 is ranked,

4)

co~(~, z+) ~

~+ <

x,

5) consequently: n ~ X -+. n E p(z),

6) the structure is smooth,

7) ~ e

,(~) -~ ~ ~ x.

Proof 1) trivial.

2) Let p ~ -~y, n ~ y+,-~x, rn b z+ with m -< n -< p. We show m ~ y+. Now,

x < y or y < x. But y < x ~ x E y+, but n ~ y+,-,x. Contradiction. So z _< y,

and thus y+ C_ z +, so rn ~ y+.

3) We show m-< n,p 74 n -~ rn --<p: Let

n ~ ~z, m ~ z +

with m -~ n. As

p g n, p ~ x +, so there is y E x +, p ~ -~y. But by ld) y+ C_ z +, so rn -< p.

4) Co~(~, z+) -~ ~x r z+ ~ z ~ ~ ~ ~ < ~ -~ z+ c_ x.

5) Let n b X, p --< n, p ~ x. Thus, there is z such that p b z+, n ~ ~z. But

then z + C X. Contradiction.

6) Let m ~ z, n ~ X. Case h n --4 m, then we are done by 5). Case 2: n 74 m,

but there is p -4 m such that m ~ z,-~z, p b x, z + with p --< m. By 4), z + g X,

so n D z +, thus n -< m. Contradiction.

7) Let rn ~ x,-~y for some y E X. By lc), y+ C X. Let now n ~ X, so n -< m.

Contradiction.

[]

To finish [GM91], we just have to note that by 5) and 7) and Definition, the

normal worlds for x and #(x) coincide, thus z LN <y ~ x b~ Y-

We turn to the [LM92] completeness result.

Fact 2.30 (In P): For x, let ~ := {x} U {y: -~y V zl~ y} and ~ := {y: x}~ y}.

Then .rn ~ ~ ~-~ m ~ 7.

2.1. PREFERENTIAL STRUCTURES 59

Proof "~": Letm ~,y~2, so-~yVxl,- y, but thenxj~ y.

"~--": Let x J,-~ z, m ~ ~. Consider y := --x V z. Then -~y V x = -,(--x V z) V z =

(:~ A -.~)

v ~ = z I'-" z, so --.y v :~ I~ -.x v ~ = ~,so ~ t= ~,--,x v ~, thn~ ,~ ~ z.

Define now x ~ zy :~ -~y ~ -,x and x </y

:~--~

-~y < ~x (both <, < in the sense

of Definition 2.6). By Fact 2.7, 3c) and 8c) (in R!) < t is total and transitive,

moreover x < ly ~-~ y ]s Ix.

We conclude by showing m ~ X ~ m ~ ~, where X :-- {z} U {y : -,z < ~y}.

Case 1: x I" 2-. Then x ~ 2_ by consistency preservation, so re(x) = re(X) =

m(~) = ~. Case 2: xlr 2_. But now-~y < z ~xV-~y]--, y, thus-,x <~y

x V -~y ]~ y, so X = ~, and we conclude by above Fact.

The rank

This might be the right place to shortly mention another order defined in [LM92],

the order by rank of a formula in a database, measuring exceptionality.

Definition 2.31 Let a conditional knowledge base K be given, i.e. a set of

~f~ ;~I,, c~,9 ~ z;.

a) c~ is called exceptional for K, iff K preferentially entails true ]~ -,or. c~ I~ fl is

called exceptional for K, iff c~ is exceptional for K. E(K) is the set of al~ fl E K

exceptional for K,

b) Ca := I(, C~+, := E(C,), Cx := N{Cp: p < A} for limit A.

c) If a is exceptional for all C,, we set rk(c~) := co (where co > p for "all"

ordinals p). Otherwise, set rk(c~) := r iff ~- is least such that c~ is not exceptional

for C,.

We note the following result, whose part b) uses notation and a theorem of

[LM921.

Fact 2.32 a) 1. If r'k(c~ V ~) < co, then o~ <LM ~ --~ rlc(c~) < rk(fl). 2. Thus

< ~ ~ ~k(~) < rk(Z). 3. Usually, rk(~) < ~k(~) ~ ~ <s,/~.

b) If It" is admissible, then rk(c~) < 'r'k(/3) in It" ~/3 < c~ in I(.

Proof a) 1.: CTk(~v~) ~ c~ V fli ~-, =~ (where ~ means: preferentially entails).

We first show CTk(~vp) ~ true

j~

--/3: Let m E ix(true). Case 1: m ~ c~ V/5,

then m G ff(c~Vfl), so m ~ ~Z- Case 2: m ~ c~ Vfl, so m ~ -~fl. Now,

rk(c~ V fl) = min(rka,r'kfl). If" rk/~ < rka, then rk(a V r = rkfl. But C~kz ~=

true],,~ -~fl. Contradiction.

3.: Consider the model rot/ ~ c~,/?, rm ~ -,c h -,/~, m ~ o~,--fl with mz ~ rnH.

Then true[,,, -,fl, true[@ -~c~, c~ V fl[Ir ~fl. Thus rka = 0, rk/? > 0, a eLM /3-

b)

"--,": Let rk be defined in If. 'r'ka < rk~ ~ rk(c~ V fl) = min(rkc~, r'k~) = 'r'kc~ <

r'kfl = rk((crV~) A~) ~ cr V/31~ ?i-~fl --~ a <LM /3 in I(. Suppose c~Vfll,-~ NZ.

Then either

60

CHAPTER 2. PREFERENTIAL STRUCTURES

Case h 'rk(~ V/9) < rk((c~ V/9) A

~'rue)

(in K), contradiction, or,

Case 2: (~ V/9 has no rank (in K) --+ c~,/9 have no rank --~ rlcc~ r

'r'kfl

(in K).

Thus,

rka

< rk/9 (in K) --+ a V/9t7~ ~/_, thus also

,3

< c~ in K.

"~-": Let ~V/91r • ~V/~l~ ~9 inT. Case 2 of ~vgl~ -~/9: ~v;~ has

no rank, but then c~ V fl ]~ _L. Contradiction. So Case 1 holds: rk(c~ V fl) <

rk((~ V/9) h/9) = rk/9 (in K) So by

"rk(c~ V fl) = rnin(rkcqrk/9), 'rkc~ < r~/9. []

2.1.3 Defaults and preferential models

Introduction: outline and definitions

Outline In a Research Note published in the AI Journal [Imi87], Imielin-

ski has examined the '~modular translation" of defaults into preferential models.

The a~rticle is difficult to read, as the definitions and results presented there are

somewhat vague. This Section 2.1.3 is intended to clarify these matters. The

situation here is less abstract and rather more special than that described by the

general results of [KLM90], [LM92], and our own of Section 2.1.4 below. Thus,

the machinery is a bit finer, but the basic ideas are the same. We follow closely

Imielinski's terminology, for this reason we have chosen ~ to be reflexive, and

examine one definition of minimality, which seems to fit Imielinski's article. (We

also have examined to a certain degree another possible interpretation of mini-

reality, which is called weak minimality here. The results are partly parallel. A

crucial difference is that (in the finite case), non-empty sets have a nonempty

subset of weakly minimal elements - so this definition is closer to smooth cpm's.

We will not go into details, however.) So, this Section is somewhat independent

of the rest of the chapter and should be seen as a service to the reader who has

wondered about [Imi87].

For the convenience of the reader, we repeat here in the introduction some defi-

nitions of [Imi87], and add some of our own.

In Section 2.1.3.3 we examine in detail the translation of one default into prefer-

ential semantics. The central result there is Proposition 2.53.

A look at the many different situations of Proposition 2.53 makes the search

for translations of more than one default into preferential semantics seem quite

hopeless. This is somewhat in contrast with the rather simple description in

Proposition 2.50. We should note, however, that our results in Section 2.1.3.3

are much more detailed than those in Section 2A.3.2, and that the preorders of

the positive cases there are much more natural, so we have to invest into more

specialized proofs, whereas Proposition 2.50 only gives the general picture. So,

after all, the problem of translating several defaults into preferential semantics

might not be hopeless, Proposition 2.50 might give a hint where to look.

The situation changes again, when we look at translating defaults to circumscrip-

tion in predicate calculus. What we feel to be a modular translation in the spirit

of [Imi87] is made precise in Definition 2.40. The preorder of minimal models is a

rather special one. In particular, when minimizing, we can't change the domain,

which stays fixed. That gives us immediately the sad result of Lernma 2.76: A

normal closed default without prerequisites that can't be translated modularly

2.1. PREFERENTIAL STRUCTURES 61

into circumscription. Similar ~.;echniques give still more negative resuits in the

subsequent Lemma and CoroIIary.

So we feel that circumscription and defaults are rather orthogonal ways of non-

monotonic reasoning.

Our Lemmas 29 and 31 for preferential semantics seem to contradict Theorems

4.4/4.5 of [Imi87]. What is the solution? First of all, one can't really tell, because

[Imi87] does not always present precise definitions. Second, a look at the proof of

Theorem 4.4 in [Imi87] will show that the E(V(m))'s there may be formulae in the

extended language. So Theorems 4.4 and 4.5 of [Imi87] should read for clarity "

.... seminormM defaults without prerequisites in the extended language". Third,

this still leaves our cases of Lemma 2.56 c) in contradiction. As you will see, we

use the "Ab" there. A look back at the proof of Theorem 4.4 in [Imi87] will show

that the "Ab" admitted in Definition 4.2 of [Imi87] has disappeared. So "order

semantics" in Theorem 4.4 in [Imi87] should be replaced by "order semantics

without any "Ab"".

Technical overview of Section 2.1.3 The main part of Section 2.1.3 deals

with the propositional case. The definitions are summarized in Section 2.1.3.1.

We examine in detail the translatability of one default into a preferential model

jld depending on the number of possible occurrences of the (classical) models of

the language:

-

each model occurs exactly once (MO) - we use the abbreviation in parallel to

[Imi87],

-

each model occurs at most once (this corresponds to adding a formula Ab,

MOAb),

- each model occurs at least once (this corresponds to enlarging the language,

MO*),

- the number of occurrences is not restricted (this corresponds to MO*A~ ).

A general limit for the finite case is expressed in Proposition 2.50, where preferen-

tim models are essentially characterized by the deduction theorem (cf. Theorem

2.81 for the infinite case). Proposition 2.52 shows that not all above cases coincide,

and Proposition 2.53 classifies the translatability of different types of defaults.

The proofs of Propositions 2.52 and 2.53 are to found in the subsequent Lemmas

2.54-2.74, where the properties of different defaults and preferential models are

examined in detail.

Turning to the predicate logic case in Section 2.1.3.4, we see that even very simple

types of defaults can't be translated to circumscription, the reason being that the

minimal model relation corresponding to circumscription is a very special one,

rigid for many properties, e.g. for domain preservation.

Definitions

Definition 2.33 We examine here reflexive and transitive cpm's. Thus, in the

rest of the Section, ~ will always denote a reflexive, transitive binary relation,

called a preorder, x will be called minimal with respect to ~, iff there is no

62 CHAPTER 2. PREFERENTIAL STRUCTURES

zl r z, z! ~ x. x will be called weakly minimal with respect to ~, iff x! ~ z

implies z __ xl.

Definition 2.34 In the first-order case, let dom(m) be the universe, or domain

of m, i.e. the underlying set of the model.

Definition 2.35 Let ~ be a preorder on Mz, A E/2.

#(A) := {m E M(A): m is minimal in M(A)} = {m E M(A): -~3rnl # m(mt E

M(A), mt ~ rn)},

wit(A) := {m E M(A): m is weakly minimal in M(A)} : {m E M(A): -~3m, ~r

m(ml E M(A), ml -A_ m, m ~_ rnl)}.

If we work in different languages, we will sometimes write #* for it in ML* etc.

it(B), wit(B) for B C_ M~ is defined analogously.

Let A be a set of formulae of/2, cr a formula of 12 (in these cases, we wiIl frequently

abuse notation and just say A, o- E s etc.). We define

A ~ ~ :~ Vm E it(A).rn ~ ~, and

d ~ ~ :~ Vme ~it(A).m ~ o.

The empty order is defined by m -4 ml :ee m = ml, and r ~-~ ~b will denote the

following (important) preorder on ML :

m -4 mf :~ (m ~ ~b and ml ~ r or m = ml (< is trivially refexive and

transitive).

For formulae and sets of formulaeA, B, cr, r, we will freely use A + B, A A B,

A + cr etc. to denote A U B, A U {o'} etc. The meaning will always be clear from

the context.

Definition 2.36 Let 12 C 12". For m E Me (or Me.) let E(m) := (~:m ~ ~,

atomic or negation of atomic}.

For m E ML* let E-(m) := E(m) N/2

Let pr : Me* --~ ML be defined by: pr(mJ) is that m with E-(ml) = E(m), the

latter formed in s

A:B

Definition 2.37 Let W E/2, D := -d-, a default with A,B,C E s (we also say

D E s by abuse of language).

Let Ext(W, D) be the (unique, if it exists) extension of the default theory (W, D)

(see Definition 1.19).

Furthermore, let (W, D)[~ per iff ~r E Ezt(W, D).

Definition 2.38 Let D be as above. We say

1) D E MO*~ iff there is an extension 12" of s and < 12", Ab, __> is a modular

translation of D into preferential semantics, i.e. a) Ab C s b) ~ a preorder on

ML,,c) VW,~E /2 ( (W, /9)1- ~ ~WOAb>~).

2) MO* means MO~A~, Ab not necessary, MOA~ means MO~6, 12" = 12 suffices,

MO means MOA~, Ab not necessary.

If we have to be very dear, we say MO*, MO + for MO in/2*, in L; + etc.

We will use MO etc. freely as sets, or predicates, whatever seems more conve-

nient.

2.1. PREFERENTIAL STRUCTURES 63

Definition 2.39 Let s be a first-order language, tbr simplicity with predicates

only, II C_ s P E /2, s C s (In the sense on circumscription, II will be the set

of "floating" predicates which we vary, P will be the predicates to be minimized.)

Then ~ :=

~c.,n,e,

a preorder on Me. will be defined as follows:

rn _~ rn/iff 1)

dora(m) = dora(re')

(where

dora(.)

is the universe of the first-order

model), 2) [[O]],~ : [~O]]-~, for O r rl, Q r P, 3) [[P]]m c [[p]]~,.

Let S C Me., call m E S minimal in S (m E #(S)) with respect to ~ := ~c*,rI,P

iff

1) rn ~ S,

2) there is no

rnl E S, ml ~ rn,

but not

rn ~ ml,

i.e. there is no

rnl E S

such that

i) dom(m) = dom(m'),

ii) [[Q]],~ --= [[Q]],~, for Q r I], Q r P,

C

iii) [[P]],~, • [[PJ],~.

Definition 2.40 Let s be a first-order language, D a default in s We say that

D has a modular translation into circumscriptive preferential semantics (D E

MCO*Ab )

iff there is s :=/i 5 _D s a formula

Ab

:=

AbD

E s a set of predicates

1-I := liD C_ s a predicate P := PD E /2, such that for all W, r E s

W+Ab~c.,n,~.

r (W,D)t~ De.

Preorder semantics

Unless otherwise stated, we will work in this chapter with

finite

languages of

propositional calculus.

Some introductory facts on weak preorders:

Lemma 2.41 #(A) C

w#(A)

Proof Straightforward. []

Lemma 2.42 A ~_~ c~ + A ~___ cr

Proof Lemma 2.41. []

Lemma 2.43 Let 3 a preorder on X, Y C X, Y r 0 finite, then

wit(Y) r O.

Proof Assume

w#(Y)

= (~, construct an infinite descending chain of different

elements in Y by induction. Choose m0 E Y arbitrarily. Let rn~ -~ ... __ m0 be

defined. As

ms ft w#(Y),

there is m~+l _~ rn~, mn+l E Y and not ms ___ m~+l.

By transitivity, rn,~+l • rni for 0 < i < n, since otherwise

m~ ~_ ... ~

rni

=

mn+l.

So we have {rni: i < w} C Y, rni ~r rnj for i :/j. Contradiction. []

Remark 2.44 Obviously, Lemma 2.43 is no longer true for Y infinite, as a con-

struction with infinite descending chains without minimal elements will show.

Remark 2.45 For the empty order, we always have w#(A) = #(A) = A.

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

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