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

64

CHAPTER 2. PREFERENTIAL STRUCTURES

Proof Trivial.

The following Lemmas 2.46 and 2.47 are very simple, but. central for the further

development. (Cf. the almost identical Lemma 2.5.)

Lemma 2.46 (a) W C W, -+ it(W)A

M(WI) C it(W,)

for W, WI C_ L;.

(b)

W C Wf --4 w#(W) M M(WI) C wp(Wl)

for ~] W1 C 12.

Proof (a) Let m e #(W) A M(Wt). Suppose there is

m/ -4 m, m 7k m/,

m, E M(Wt) C

M(W), by W C= Wq thus m r #(W). Contradiction.

(b) Essentially the same proof as for (a) will work. Let

m E w#(W) r-i M(W 0

Suppose there is rm -< m, not

m ~ rm, rn~ E M(W*) C_ M(W),

by W _C Wt, thus

m f~ wit(W).

Contradiction. c1

Lemma 2,47 (a) A + r ~ ~b + A ~ r -+ ~b for all formulaeA, qh, ~.

(b) A + r >~< ~ -+ A >,,_< r --+ ~b for all formulaeA, r r

Proof (a) Suppose there is m E/,(A), m ,~ r A ~b. Thus m E

M(A

A r by

Lemma 2.46 (a) m E #(A A r but m ~ ~b. Contradiction.

(b) As for (a), using

Lemma

2.46 (b). []

We will leave the investigation of weak minimality here.

Lemrna 2.48 Let s be a finite language of propositional calculus, and I~ a logic

for s Then

{~ satisfies ibr all A, r '~b E Z;

a) abr al~ r

b) A+r r d[~ r162

c) A is classically closed,

d) A=At-+ A=At,

iff

there is a semantic representation v :

P(Mc) --+ P(Mc)

of{~

(i.e. AI~ q5 iff v(M(A)) ~ r iff A ,~ 4) such that

a') 4w) c w,

b') w c wt --+ w c

for M1 W,W' C ML.

Remark: The important properties are b) and b').

Proof " ~-"

Let v be a representation ofl,-~ .

a) Let Ak gb, wehave tosEow AI n ~. By a'), v(M(A)) C_

M(A).

As At- r

m ~ r for all

m e v(M(A)),

so d ~, 6- By representation, d }~ r The argument

works for inconsistentA, too.

2.1. PREFERENTIAL STRUCTURES

65

b) By representation, it suffices to assume A + r ~ ~b, and show A ~, r --* ~p.

Let W :-=

M(A A c}), WI

:=

M(A)

and m E ,(WI). Suppose m ~ r --+ ~b, so

m ~ CA-~,. By m E zJ(W/) C Ia/'l and m ~ r m E W. By b') rn E t,(W), so by

A + r ~, ~b, m ~ r Contradiction.

c) Let B C A, B [- ~b, we have to show A I" ~b. By representation again, A ~, B.

AsB~-r162 ~b.

d) This is immediate from

M(A) = M(A).

Define u as follows: Let

X C Me, Bx

:=

Th(X), u(X)

:=

M(Bx).

We have to show that u is a representation ofl.-~ , and a') and b') hold.

First, A I ~ ~b e-~ A ~ ~b: We use d) to obtain

r,(M(A))

:=

M(BM(A)) =

M@-, (AM(A)))

= M((A)) = ~V[(A) So A ~u ~b :+--~ Vrn E

~,(M(A)).m ~ r +-+

Vm E M(~).ra ~ ~b +-+ ~ ~- ~b ~ gl~.. zb,

the last equivalence by c).

a') t,(X) C_ X: Suppose m E ,(X), so

m ~ Bx.

By a)

Th(X) C Bx

and

m ~ Th(X).

So m E X. Remark: We use here that

X ~-+ Th(X)

is injective for

finite propositional calculus.

b') X _C X/--+ ~/(XI)MX g ~,(X): Let m E L,(XI)V1X, we have to show m E t,(X),

orm

~ Bx.

Let r E

Bx, so Th(X) l

~,, r AsX

C XI, Th(XI) C_ Th(X), let

rh(X) = Th(Xt) + a.

As

m E X, m ~ Th(X) = Th(Xt) + G,

so m ~ O.

As

Th(X) = Th(Xr)

+ G ],-~ r by b),

Th(XI)I ~., G --+ ~b

(We use here, that

G can be made one single formula). Finally, as m E u(X/), by definition of ~,

ra~G--+~b, andbym~G, wehavem~r []

Lemma 2.49 Let Y C TO(A), f : Y --~ Y such that for all W, WI E Y

a) f(w) c_ w,

b)

W C W, -+ f(W,) M W g f(W).

Then there is I and a preorder __. on A x I such that

f(W) = pr[#(pr-l[W])]

see Definition 2.35 for p and pr : A x I -~ A with

pr(< x, i

>) := z ).

In other words, f can be represented by a suitable preorder on an extension of A.

Remark: We do not need A to be finite here!

The proof is very close to the one tbr Proposition 2.83, and omitted.

however, that the definitions diverge slightly in the two cases.

Note,

We thus obtain

Proposition 2.50 Let Z: be a finite language of propositional calculus, and iN

an inference rule on Z;.

Then I~ E

MO*

(in an obvious generalization of Definition

2.38)

iff

IN satisfies tbr all A, r ~b E Z;

a) ACA,

b) A+r '~b -+ AIN r

c) ~ is closed under k-,

d) (A) = A.

66 CHAPTER 2. PREFERENTIAL STRUCTURES

Proof " --+" Use the ideas of Lemma 2.46 and 2.47.

" ,--" Let, : $)(ML) -~ P(Mc) be a representation ofl~ by Cemma 2.48. Extend

1; to s so we can define ~ on Me. by Lemma 2.49 with L,(W) = pr[t~*(pr-l[W])]

(duplicate layers if necessary). We then have A I ,'~ "~ ~ A ~, ~ ~ Vm(m E

,(M(A)) ~ ~ ~ ~) ~ Vm(m ~ p*(A) --, m b ~),

the latter as ~*(A) =

#*(pr-~[M(A)]), and pr(m),m coincide on/2. []

Defaults and preferential semantics

We first summarize resu!~s on extensions for one default. They will be used in the

sequel without further mentioning. The proofs are all direct from the Definition

in [Rei80] and trivial.

Lemma 2.51 Consider (W, D = A:~

-e-)-

The extensions of (W, D) can be described as follows:

Case I:

W ~ C: Th(W) is (the only) extension

Case II.l:

WVC, W[-A:

W [/C, W ~- A, W k" -~B, W + C [- ~B: Th(W)

W [/C, W [- A, W ~ -~B, W + C [;/-,B: impossible

W ~/C, W [- A, Con(W, B), W + C ~- ~B: no extension

W ~ C, W t- A, Con(W, B), W + C [/~B: Th(W + C)

Case II.2:

W g C, W g A: Th(W) is (the only) extension []

Remark: If t- A,

i.e. D = :B

~, we will always be in Case I or II.1.

c c

Proposition 2.52 MO # MOAb • MO* = MO*Ab

Proof The inequalities will be shown implicitly, by solving the different cases

of Proposition 2.53. The inclusions are either trivial or follow from Lemma 2.73.

[]

Proposition 2.53 (The main result of the Section,)

The modular translatability of one default of a finite propositionM language into

preferential semantics is completely described by the tbllowing table of cases of

the default ~:

~Con(A, B): MO (Lemma 2.56 a), empty order,

Con(A, B), Con(-,A), Con(A,-~C): -@IO* (Lemma 2.59 a),

Con(A, B), Con(-~A), ~- A ~ C: MO (Lemma 2.56 b), empty order,

Con(A, B), k- A, t- B --4 C: MO (Lemma 2.63), ~C ~-~ B,

Con(A, B), k A, b t B -+ C: -~MO (Lemma 2.58),

Con(A, B), ~- A, [- C --~ B: MO* (Lemma 2.69), -,C ~ B,

Con(A, B), t- A, ~- C --~ B, f- B: MOAb (Lemma 2.56 c),

2.1. PREFERENTIAL STRUCTURES 67

Con(A, B), l- A, F C ---+ B, ~/ B: -~MOAb (Lemma 2.68),

Con(A, B), ~- A, ~/ C ~ B, Con(B, C): -,MO* (Lemma 2.59 b),

Con(A, B), t- A, ~/ C --+ B, Con(B, C): MO* (Lemma 2.74), -~MOA~ (Lemma

2.6s).

For most positive cases, we have indicated the translating preorder. The numbers

show the proving Lemmas.

Remark: On our way, we will meet a default translatable into preferential se-

mantics, which is not equivalent to any set of seminormal defaults in the same

language (Lemma 2.69 and 2.71).

We now proceed to prove the above Propositions.

The proofs

Lemma 2.54 IfVW ((W,D)~ Dcr ~ Wt- ~), thenD is translated by the

empty order into preferential semantics.

Proof W ~• cr ~ W ~ a ~ W b- ~r, since #(W) = M(W). (Remark 2.45) []

Lemma 2.55 If VW ( (HI, D)I ,-~ D o"

~ W + C ~- o- )

for some fixed C, then D

is translated by the empty order and Ab := C into preferential semantics.

Proof W+C~W+U~W+C~-~.C3

We can settle now 3 cases:

Lemma 2.56 a) -~Con(A, B) implies D E MO.

b) Con(A, B), Con(~A), F- A -+ C implies D C MO.

c) Con(A, B), F- A, Con(B,'~C), ~- B implies D E MOAb.

Proof a) The default can never fire, use Lemma 2.54. b) The extension will

always be trivial, Lemma 2.54 again, c) The extension will always be Th(W+ C),

use Lemma 2.55. []

Lemma 2.57 If D E MO, then (W,D) has an extension for all W.

Proof Suppose (W,D) has no extension, so W is consistent. By Lemma 2.51,

we see W ~ C, W ~- A, Con(W, B), W + C l- -1]?. Let _ represent D. Consider

m ~ W A B, m E Me, WI := E(m). M(WI) = {m}, so #(W/) = {m} r 0,

thus Wt ~=5 _L. On the other hand, Wl ~- A, W/+ C ~- --B, and by the choice

of Wt, Con(WI, B). If Wt ~- C, then by W + C ~- ~B, and W C_ Wt, WI ~- ~B.

Contradiction. Thus (W/, D) has no extension by Lemma 2.51 and (W/, D)I~ D

J_. Contradiction. C:]

Lemma 2.58 If ~- A, ~/B ~ C, then D ~ MO.

68

CHAPTER 2. PREFERENTIAL STRUCTURES

Proof

Con(B, -,C),

so let W := B A-,C, then (W, D) has no extension. Finish

by Lemma 2.57. []

Lemma 2.59 a) If

Con(A,B), Con(-~A), Con(A,-,C)

then ~- ~ ll//O~b

(imielinski).

u) If ~- A, Con(B, ~C), Con(C,-~S), Con(B, C) then ~ ~ ?dO~.

Proof We show that the central property W + r b~ !b --+ W b~_ r -* ~b

contradicts the translatiom The extensions are determined by using Lemma

2.51. (I owe this simplification of my original proof to R. Keller)

Let D := A~. Suppose we have a translation (into s

(W,D)I'-' ncr ~ W+Ab

~_ O.. By Lernma 2.47 (a), W + r ~___ ~) --+ W b~ ~ ~ tS~ So (W + r D)]~ D~)

(w, D)I~ ~r ~ ~,

1) Assume

Con('~A), Con(A, B, C), Con(A, ~C).

Let W := (~, r := A, ~b := C.

So (A, D)I ~,, Do. ~ a + C t- O. by

Con(A, B, C),

so

(A, D)},'-, pC. (O, D)1,.0 .Do

b O. by

Con(-,A).

But ~/A --~ C, as

Con(A,-,C),

so (0, D)tr DA --~ C

2) Assume

Con(~A), Con(A, t3, ~C).

Let W := ~, r := A A (-,C V =B), r := •

(r D) has no extension and thus (r D)I "~ De. (0, D)[~.

D ~ ~ F O..

Suppose

b r --~ ~b. Then b -~r But

Con(C)

by

Con(A,-,C),

so ((~, D)tr t)r --~ ~b.

3) Assume

~- A, Co'n(B,-~C), Con(C, ~B), Con(B, C).

Le{ W := A, ~ := C

-~B, % := • Note that W + r ~ r Again, (W + r has no extension, so

(W + qS, D)l- olb. (a, D)1,-~ DCr ~ (f~, D)l ~-, Da ~ C b O.. By

Con(C, ",B),

we

see that (W, D)I~ De -* r

b) is 3)

a) Suppose

Con(A, B, C),

then 1) solves this case. If =Con(A,B,C), then

AAB [--

-~c, so, as Con(A, m, Con(A, B,-,C). []

The remaining cases require more work, they all have a translation into prefer-

ential semantics.

We start by examining more closely the preorder =C ~ B, ingroduced by [mielin-

ski. So this is the assumed preorder until further notice.

Lemma 2.60 a)

~Con(W, B) ~ #(IV) = M(W),

b)

-,Con(W, B).~mplies

W ~ O. ~ (W, 7)1:B ~., Do.,

~) M(w

+ c) <_

#(w).

Proof a) is trivial

b)

W ~ cr ~ #(W) ~ o" ~ M(W)

~ O. ~ W b O. by a) But

-,Con(W,B)

E~t(W, ~) : Th(W). So W b_~ O. ~ W ~ O. ,~ (W, ~-)I~ 0o.

c) is trivial again. []

Lemma 2.61 Assume

Con(W, B).

Then

a) (~, r ~,, b w A B or ~Con(W,m~C)) ~ (~(W) -- M(W + C)) -~

(~(w) : ~ ~ w t- -,c),

b) (3~ml ~ W A B and

Con(W, B, -,C)) ~

I,.(W) =

M(W + C) U M(W + B).

2.1. PREFERENTIAL STRUCTURES 69

Proof The last implication in a) is trivial.

~) (r _.__>tt

~' D" by Lemma 2.60 c) " C_" Let m

E

#(W), m ~ -~C. Assume ml # rr~// b

W A B. By definition of --,C ~-* B, rnt, mlf --<_ m. Since m! # role, m # .ml or

m # m1I, so me -~ m or mzl -< m. Contradiction. Assume -~Con(W,B, -,C).

By Con(W, B), let ml ~ W A B, so rrzl ~ m. By -~Con(W, B,-~C), 'm 5s mf.

Contradiction.

" ~" Assume

3trot ~ W A B, Con(~V, B,-,C).

Thus 'ml ~ W A B A ~C. By

assumption, there is no other ~n E M(W A B), so rrzl must be minimal in M(W),

but ml

b

--C.

b) " _D" By Lemma 2.60 c) and uniqueness of ml b W A B. '~ C" Let m E #(W),

m ~ -~C A -lB. By Con(W, B), there is 'ml ~ W A B. Now m # mf, and by Def.

rnl ~ m, so m r #(W) . Contradiction. []

Remark:

By augmenting s to s we can always force the existence of m! # rnl! ~ WA B.

This technique will be often used in the sequel.

We assume now F- A and, furthermore, that Con(W, B) implies (3mz # 'ml~

W A B or -~Con(W, B, ~C)), piece together our above results and compare with

Lemma 2.5t.

LetD:=~ :_Bc

Case 1: -,Con(W, B): Then W b~ ~ ~ (W, D)I ,,~ z)o. by Lemma 2.60 b)

Case 2: Con(W, B): Then W ~ o. ~ W + C I- ~r by Lemma 2.61 a)

Case 2.1W~-C: Then(W,D) l~ DO.~W~-~ W+C~-o. ~W~_-<

Case 2.2WVC, w+CV~B: Then (W,D) I- D ~ W+C~-O.~ Wbso

Case 2.3 w V c, w + c ~- ~B: No extension, (W, D)I" so. ~ _L ~- o.

Case 2.S.1 W ~- -~C: Then (W, D)I" Do. '--' W ~_< o.

Case 9.3.2 Con(W, C): Then (W, D)J~ Dcr + W ~ o.

So, the only thing that can go wrong is Case 2.3, thus:

Lemma 2.62 Assume t- A. Assume further that Con(W,B) implies (~ml 5r

roll ~

W

A B

or -~Con(W, B,

=C)).

Then =C ~-~ B is a translation of m = J~- iff V W 6 s (Con(W,B), W ~/C,

W+CI--~B~ W~-=C) o

Lemma 2.63 F- A, b B ~ C implies D 6 MO by ~C ~-+ B. (Imielinski)

Proof ~Con(W, B, ~C) by ~ B -+ C. Con(I~V, B) and W + C t- ~B together

can't be, for the same reason, o

The condition in Lemma 2.62 is too nasty, let's improve it.

Lemma 2.64 V I/V 6 s (Con(W, B), W ~/ C, W + C }- ~B --+ W F ~C) iff

%- B -~ C or ~ C~ B).

70 CHAPTER 2. PREFERENTL4L STRUCTURES

Proof a) Con(W,B),W~/C,W+C~--,B-~ WP-,aiff

Con(W,

B), W + C t- -.B --, W [- ~C

iff

Co,~(w, B) -, (w + c ~ ~B ~ w ~ -~c) if[

Con(W, B) ~ (Con(W, C) ~ Con(W, B A C)) iff

Con(W, B) i Con(W, C) --* Con(W, B A C).

b) V W E s (Con(W,B) A Con(i,V,C) ---* Con(W,/3 A C)) iff i- B ---+ C or

~-C-+ B.

Proof: ~' *-" is trivial. "-*": Let W := -~(B A C) Then Con(W,B) if[ ~/B -~ C,

Con(W, C) iff b/C --~ B (this is simple arithmetic) and -,Con(W, B A C). Thus

[- B --+ C or [- C --* B. []

This, together with Lemma 2.62 proves:

Lemma 2,65 Assume b A and that Con(W, B) implies (Bin1 # m// ~ W A B

or ~Con(W, B, ~C) ).

Then -~C ~-~ B is a translation of D = ~4~ iff }- B --* C or ~- C --+ B. []

We now establish a limit on what we can do in MO, if we add Ab.

Lemma 2.66 Let t- A, Con(B,-~C), D := A~ E MOAb. Then F- Ab ~ C.

Proof Let (W, D)1N D c~ ~ W + Ab ~ c~ for some suitable A5, -<, and all @i

~- C ~ Ab:

We first show [- -,B ~ A& Suppose not, then Con(~B, ~Ab). Let m ~ ~BA ~Ab,

consider W := E(m). As W t- ~B, Th(W) is the only extension, so (E(m), D)iN

D ~ ~-~

E(m) 1- O. ~-+ m ~ O.. By prerequisite, (E(m), D)I~ Do. ~ E(m)+Ab ~_ O.

_1_ ~- O.,. Contradiction.

Case h I- C ~ -~B: By the above, t- C ~ Ab.

Case 2: Con(C,B): Choose W0 := 0. So 0 + Ab ~ O. ~ (0, ~)[~ ,o. ~ C ~ ~,

as Con(B). Thus M(C) ~ #(Ab) C M(Ab), and t-- C --* Ab.

~- Ab-~ C:

Suppose Con(Ab A -~C), we derive a contradiction. Suppose first -~C A Ab I-

-lB. Choose Wi := -,C. So -~C + Ab ~ ~ ~ (~C, A:B

--e-) 1~ Do. ~ • ~" O., as

Con(B,-~C). Choose W2 := -~C A Ab. So --C A Ab ~ ~ ~ (-~C A Ab, _4_~)l~ t)o.

-~CAAb I- O.. Thus -~Con(AbA-~C),. Contradiction. So Con(-~CAAbAB). Take

rnl ~ -~C A Ab A B, consider W3 :: E(mt), so M(E(ml)) = #(E(ml)) = {m,},

we obtain E(ml) : E(ml) + Ab ~-~ O. ~ mt ~ O.. But, as m/ ~ -~C AB,

(E(ml),--K-)A:B l,.o D ~ ~ _k b O.. Contradiction. Thus I- Ab -~ C, and we are

finished. []

Lemma 2.67 ~- A, Con(B,-~C), D := ~ E MOAb implies ~- -~B --~ C.

Proof See the proof of Lemma 2.66. []

Lemma 2.68 Let b A, Con(B,-,C), Con(-,B). Then D := ~ E ?clOak.

2.1. PREFERENTIAL STRUCTURES 7I

Proof Suppose D E MOAb.

Let W0 := C ~ -lB. By Con(B,~C), we have also Con(C -~ ~B,B) and

Con(C -+ -~B,-~C). Furthermore, C A (C --+ -~B) b --t?, so (W0,D) has no

extension. Now Wo + Ab = (C -+ -,B) A C +-+ C A -,B (by Lemma 2.66, Ab = C),

but C A ~Ab ~.~ c~ ~ (Wo, D)[~-, D~r ~ 5_ ~- or.

Let W~ := C A -~B. So C A -~B = (C A -~B) A C ~ o" ~-* (Wt,D)l~ OCt

CA-~B t- ~, thus ~Con(CA-,B). :But by Lemma 2.67, b -,B --~ C, and Con(~B),

so Con(~B A C). Contradiction. [2

We now leave the simple world of s and enlarge Z: to s The important fact will

be that we have several "layers" of Mc in Me,: Let r E s - s we will then

have ibr each m ff Mz: ml,m2 E/1/Ic., each coinciding with m on s but ml ,~ r

> -,r

Lemma 2.69 Let ~- A, ~//3' ---+ C, t- C ~ B. Then D := -~ is translated by

-,C ~ B into M~..

Proof The extension of Z: to s ensures for Con(W,B) the existence of ml

roll ~

W A

B, we

can apply Lemma 2.65. []

We next show that a default as in Lemma 2.69 is not equivalent to any set of

seminormal defaults in the same language.

Lemma 2.70 Let Th(W) be maximal consistent, & a set of seminormal defaults.

Then Th(W) is an (and the only) extension of (IV, D).

Proof It is enough to show that Th(W) is a candidate in the definition of

P(Th(W)) (see Definition 1.19).

Conditions D1 and D2 of the Definition of a default extension are trivial.

Condition D3: Let AI:B~,...,B['

o, e _a, A, E Th(W), ~B~ r Th(W), so

Con(Th(W), B~), and W I- B~ by maximality. By seminormatity, }- B{ --+ Ci. So

W I- G and G E Th(W). 0

Lemma 2.71 Let k A, }/B -+ C, b C -~ B. Then D := ~ is not equivalent

to any set of seminormal defaults in the same language.

Proof Con(B A-~C). Extend B A-~C to a maximally consistent set of formulae,

W. So Con(W, B), W ~/C, W + C b -,B, as W + C is inconsistent. So (IV, D)

has no extension and (W, D) [~ DZ. If zX were an equivalent set of seminormal

defaults, (IV, D)}~ ~)G ~-~ (IV, A) I~ D cr ~ W k- G by Lemma2.70. But Wis

consistent. Contradiction. []

There is just one positive case left, and, so far, we have only used the trivial

order or -~C ~-~ t3. The last case wilI be solved differently. We will stop here for

a moment and prove the remaining inclusions of Proposition 2.52.

72 CHAPTER 2. PREFERENTIAL STRUCTURES

Lemma 2.72 Let s C Z2 +, and pr be the projection. Let pr : Me+ ~ Me. and

-e,*, ~+ be preorders on M~:,, Me+.

Then #*(A) = pr[#+(B)] implies A ~_~. a ~ B ~<+ cr forA, ~ ~ s B E z; +.

Proof "--~": Assume A ~. o', let ra E #+(B), we have to show m ~ o'.

pr(m) E #*(A), so pr(m) ~ (r, but .m, pr(m) agree on s

"+--": Assume/3 ~5+ ~r, let 'm E/F(A). Thus, there is mt E #+(B), pr(m/) = m.

Thus m/~ o-, and again m = p'r(m,) ~ c,. O

Lemma 2.73 Let s be any language, D E MO~. Then there is an extension

s of 12" and a preorder such that D E MO c+ 9 Thus, MOnk ~ MO ~, and MO*ab

= MO*.

Proof The trick is to substitute Ab by "shortcircuiting" all m ~ -,Ab by a

second layer of models. (Note that this would not work for weak minimality, by

Lemma 2.43.)

Let W+Ab ~_. a ~

(W, D)l~

D~, Ab E s Extend s to s by one additional

predicate p. Split Me+ into two layers of Me., one where p holds, the other where

~p holds. Let pr: Me+ --* Me, as usual.

Define ~+ as follows:

ml 5 + rr~ iff

1) ml, m2 are in the same layer and pr(ml) _* pr(m2) and 'ml ~ Ab or

2) pr(m~) = pr(m2) and m~ ~ -lAb or

3) ml, ms are in different layers, ms ~ -lAb, ml ~ Ab, p'r(ml) ~* pr(m2) or

4) ml = m2.

Explanation: Condition 1 erases all models non-minimM because of some element

in M(-,Ab). Condition 2 makes all models of ~Ab non-minimal. Condition 3 is

technical, it ensures transitivity.

Transitivity is now easily checked by examining all possible cases and left as a

(trivial) exercise. So our conditions fully describe the preorder.

We have to show W + Ab ~. ~ ~ W ,~§ ~ for al! W, cr E s

By Lernma 2.72, it suffices to show/~*(W + Ab) = pr[#+(W)].

Proof:

" D" Let m E #+(W) + m ~ -lAb, pr(m) E M*(W + Ab). Suppose there is

'ml -~* pc(m), mt ~ W + Ab. Let .mtt be in the same layer as m, p'r(mtt) = mr.

As mtt ~ Ab, and mttr 'm, rnt/ ~+ 'm. Contradiction.

r C" Let m E #*(W+Ab), pr(mt) = m. So rnl ~ WA Ab. Suppose there

is mr/ ~ M+(W), .rrz, ~_+ m/, m// 7! m/. If 'm, -4 + m! by condition 1, then

pr(m1~) ~* m, and pr(mlt) ~ W + Ab. By minimality of m, we have m = pr('mH)

and m! = m,. Condition 2 and 3 can't apply, since ml ~ Ab. So m/E #+(W). []

There is one positive case left to show. Feeling comfortable now with layers, we

will do it next.

2.1. PREFERENTIAL STRUCTURES 73

Lemma 2.74 Let P A,-~Con(B. C), Con(B, ,C), Con(C, =B). Then D - A:B

E MO*.

Proof Extend Z: to s by, say, new p,q, so A/it. has 4 layers of ~lc. Divide

ML. into two layers with 2 sublayers each.

Define a preorder ~ on Me* as follows:

ml -A m2 iff

1) mi E layer 1 and ml ~ B or

2) mi E layer 2 and m~ ~ -~C or

3) ml = m2.

Transitivity is trivial, so this is indeed a preorder.

If W F "~B, then Ezt(W, D) = Th(W), so (W, D)I N Do. ~ W ~- O.. If Con(W, B),

W + C I- -~B, so (W, D) has no extension, so (W, D)I -,~ z)o. ~ _1_ F or.

Thus, we have to show:

a) W ~- -~B implies pr[#*(W)] = ML(W).

b) Con(W, B) implies #*(W) = (~.

On a): " C" is trivial. "D_": Let m C Me, m ~ W. Let ml E layer 1, pr(ml) = rn,

and assume there is mtt ~_ ml, ml; r rnl, mH ~ W. But W F -,B, mH ~ WA ~B.

So ml E #*(W) and m E pr[#*(W)].

On b): As Con(W, B) and F B ~ -,C, Con(W, -,C). Assume there is m E #*(W).

If m E layer 1, by Con(W,B), there is ml ~ W A B, ml E layer 1. So ml ~* m.

But, remember, layer 1 consists of 2 sublayers, so there are always 2 models of

W A B, so m! 7~ m can be assumed, and m is not minimal. Contradiction. If m

E layer 2, argue just the same way, using Con(W, -~C). So, #*(W) = (~. []

Defaults and circumscription

In this Section, we work in predicate calculus.

Lemma 2.75 Let dora(m) be finite, m E S C Me. Then 3rot E #(S).ml ~ m

(the order as in Definition 2.39).

Proof If not, construct a strictiy descending chain of models m = m0 5--

m I }--

...in

S. But [[P~,~ _. dom(m), so that's impossible. []

Lemma 2.76 Let A := 3x, xl.x 7~ x;, D := ~, then D f! MCO~b.

Proof Suppose D E MCO*Ab, fix appropriate s II, P. Let W := ~. As

Con(W,A), (HI, A)I ~ DO" ~ A F ~r. Let WI := ~x.x = x. As -,Con(W,,A),

(Wr A) IN D ~

~

WI

F

O.,

Now, W

n LAb = Ab ~_~

O. ~

A

F

O., so Ab ~ A.

Thus, in all minimal models of Ab, A is valid.

Claim: A is valid in all models of Ab. Proof: Suppose not, let m E M(Ab),

m ~ -,A, so dora(m) = {x}. By Lemma 2.75, there is ml _< m, m/ E #(Ab), so

dora(m1) = {x}, (remember: the domain can't change![) and by Ab ~ A, we

have m! ~ A. Contradiction.

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

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