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

34 CHAPTER t. tNTRODUCTfON

requisites has now to be carried out inside {x : ~b(x)}. The modifications are

straightforward (for Vxr : r and Vxgat(z) : el(z), we have to consider

{z : ~ A ~bt(z)}). We see again the advantage of a system which is poor by the

number of its axioms and thus avoids excessive commitments, but whose base

structure - i.e. whose language, in our case extended FOL - is expressive enough

to permit multiple and strong extensions in a natural and straightforward way-.

Reasoning about defaults

Consider the following sentence: "It is not true that the museum is normally

closed on monday." - in our notation -~Vxr This sentence opens the door

to a lot of problems, some of them closely related to the discussed homogeneity

questions. How do we correctly reason about defaults? To emphasize again, we

work on an underlying "semantics of normal cases", and explicitely do not refrain

ourselves to a conventional reading of default theories as abbreviations for classical

theories. Instead, we suppose that we describe the world under consideration by

choosing precisely this form of theory.

So, intuitively, we read -~Vxr roughly as: for a non-negligeable part of the uni-

verse (for instance "half" of the universe), qS(x) is not true. Of course, -,Vxr

--+ Vx-~r will usually not be true, (as "half" is not "most") but the converse

Vz-,r -~ -~Vzr seems reasonable in all intended interpretations.

The following problem leads us directly to questions of independence between

defaults: Is (Vxr A Vz(r --+ ~b(x)) ~ Vx~b(z) correct? If we read V

just as "normally", this seems so. But, is the default theory {Vx(r A ~b)(z)}

the same as the default theory {Vz(r A ~)(z), Vzr By Reiter's definition

and intention, certainly not, as we may know -~(r A ~b)(z), but r may stilt be

possible, so we can still conclude r in the latter case, but not in the former.

So, what does a default theory 'mean? We think, the answer is quite simple: it

means in addition to "normally ... ", that all those normalities are independent,

if possible. I.e., the default theory {VxC(z), Vx~b(x)} means, that normally r

normally 4, but, moreover, if r then still normally ~)(x), and if not qS(x), then

still normally ~b(z). Thus, in the latter case, the set {z : --r A '~b(x)} is also

large in. the set {z: -~r

Thus, the conclusion Vx(r ~ Vzr is justified, but here we know noth-

ing any more about independence (i.e. if r A ~ fails, ~5 might still be consistent,

but fail most of the time too).

Moreover, there is a problem with completeness here.

Suppose we admit the rule schema Vx~(x) A Vx(~(x) --+ ~b(x)) -+ Vx~b(a:) and

use the resulting new defaults as indiscriminately as the old one, we run into

a completeness problem: Let r :+-+ r V 0(x). Suppose we know -~r

but 0(a) is consistent, then we deduce 0(a) by the rule Vz(r V O)(z) for all

such consistent formulae 0, resulting from the single defauIt Vxr Our final

formalism will admit the rule schema Vzr /', Vz(r -+ ~(x)) -+ Vzr

but it will stop the applicability of Vz~;,(x) to nonmonotonically conclude ~b(a)

unless explicitely authorized, if more inIbrmation (such as -~r is present. So

1.4. BASIC DEFINITIONS AND NOTATION

35

this will not be a problem of reasoning about normal cases, but of the ensuing

nonmonotonic reasoning.

We might adopt the convention - which is done implicitely in default theories, and

quite often violated in the intended semantics - that all defaults are independent

in the above sense. This, however, will not help with the tbllowing:

VxC(x)

V Vx~b(x). This seems a reasonable theory, I do not know which of r or ~b is

normally the case, but maybe I know for sure Vz((r V ~b)(x) -+ ~r(z)), so !

may conclude Vx~r(z). In addition, independence does not seem necessary here.

So, to asssume that all

mentioned

defaults in a default theory are independent,

seems overly restrictive. Simple syntactic rules like implicit independence in

conjunctions are unsatisfactory too, as the desirable equivalence -~(-~VxC(x) V

~v.r ~+ vxc(x)A vzr shows.

In other words, what is needed, is a default theory consisting of two parts. In the

first part, we express independence:

I ndepe'adent(C,~b), independent(a, r)

etc.,

and then we are free to formulate any boolean combination of VzC(x), Vx~b(z),

and of V~(~), W~(~) etc.

The problem of irrelevant information in other formalisms

To show that our above problems are not limited to the particular default system,

let us shortly discuss homogeneity in the light of minimal models. If we minimize

-,fly(z),

we do so within all (extensions of) predicates, as long as consistency

(and the classical theory) is preserved, so the same counterintuitive results in

e.g. our above largebird(x) example will arise. Of course, we might avoid this

by limiting minimization to the domain of those predicates we explicitely admit

- thus changing the formalism - but the basic problem rests the same.

To summarize, we feel that the formal treatment of defaults presupposes many

additional conditions to hold in order to give intuitively correct results.

The answer we give to this problem in Chapter 3 is very simple - none. We take

the point of probabilists, who need the explicit information about (probabilistic)

independence to go from P(x) to P(m I Y)' We leave it to the reader (and user)

to strengthen our formalism with as many assumptions on independence as he

wishes - provided he stays consistent. As the basic system is so weak - it just gives

the building blocks, and is thus highly flexible - he can move in many directions.

1.4 Basic definitions and notation

1.4.1 Notation

We use the usual interval notation for subsets of the reals: (a, b) := {x E N : a <

< b}, (a, oo) := {x e ~: a < z}, In, b) := (a, b) u {a} etc.

For two functions f : X --+ Y, g : Y --~ Z, let g o f : X --+ Z be defined by

(g o f)(z)

:=

g(f(z)).

For f: X --* I7, A _C X, B C_ Y let

f[A]

:= {f(x) : z ~ A},

,.an(f)

:=

T'a',~ge(.t') := f[X],

f-liB] := {~ ~ X:

f(z) ~ B}.

A + x will denote A tO {z'}, when the context is dear.

36

CHAPTER 1. INTRODUCTION

B1 means that there is exactly one element.

Unless stated otherwise, arrows in diagrams will point upwards.

Definitions, Lemmas, Propositions, Exapmles, Diagrams etc. are collected within

Chapters.

1.4.2 Set theory

We shall use some set theoretic results and prerequisites, in particular, some basic

facts about ordinals, cardinals, transfinite induction will be used, and the axiom

of choice will be assumed to hold. Some reformulations and consequences thereof,

e.g. the usual elementary cardinal arithmetic, are used without explicit reference.

We assume familiarity with these matters, which the interested reader can find

e.g. in [Jec78], [Kun80], or [Lev79].

V is the set-theoretic universe we work in - the class of all sets.

We use ~P to denote the power set operator, [I{X~ : i E I} := {9: g : I --~ I.J{X~ :

i E I}, Vi E I.g(i) E X~}

is the general cartesian product, C is the complement

with respect to some fixed universe. +ltJ denotes disjoint union.

Given a class of pairs X, and a set X, we denote by

X[X

:= {< a,i >E X : x E

X}, so if X is a function

f, fiX

is the usual notation for the restriction of f to

a subset of its domain.

Card(X) shall denote the cardinality of X, c~ + the cardinal successor of ~, if c~ is

a cardinal.

Definition 1.1 We recall that a relation -4 on W is called modular iff there is

a set U, totally ordered by -~ I and a function f : W --+ U such that x ~ y

f(x) -.< If(y).

Note that this is a very strong property. Loosely speaking, it reflects the existence

of a "rotating scale" by which to measure distances. (Imagine marking a total

order U, with minimal element 0 as origin, on a ruler and having the elements of W

noted by points on a sheet of paper. Fix now the origin of the ruler somewhere on

the sheet, and rotate the ruler around that point. This will generated a modular

relation on W.) It is equivalent to require that ~ be irreflexive, transitive, and

satisfy the condition that x -< y, z ~ y imply z -4 z.

Definition

1.2 Given a set X,

Jr(X) C_ 7)(X) is called a filter (over X), iff (1)

X E F(X), (2) A E Jr(X), A G B C X --+ B r Jr(X), (3) A,B C Jr(X) --~

AnP ~ 7(x).

1.4.3 Topology

Standard references for topology are e.g. [Ke175] or lent77].

Definition 1.3 A topological space is a pair <

X,T

>, where X is a set and

T C :P(X) satisfies (a) ~,X E T, (b) A C T finite ~ NA E "/-, (c) A c_ T

UAET.

1.4. BASIC DEFINITIONS AND NOTATION

37

So T is closed under finite intersections and arbitrary unions.

The elements of T are called open sets, A _C X is called closed iff X - A E T,

and clopen iff A is closed and open. Thus, ~ and X are always clopen.

B __ T is called a basis for 7. iff (a) all A E 7. are the union of some elements

of B, (b) B is closed under finite intersection. B C T'(X) is said to generate a

topology 7" iff T is the least system satisfying (a)-(c) above and containing B.

Definition 1.4 B C_

T is called an open cover of X, iff I.JB = X. A C X is

called a neighbourhood of z E X iff there is B E T such that z E B C A.

Obviously, the system of neighbourhoods of z forms a filter.

< X, 7. > is said to be compact iff any open cover B C 7" of X contains a finite

subset B! C B, which is still an open cover of X. (Sometimes, T2 - see below - is

also demanded.)

If .3, C B C ;o(X) such that for all B E B there is A E A with A C_ B, then .4

is said to be dense in B.

Definition 1.5 d : X x X --+ ~ is called a metric on X iff (a)

d(z, y) >> O,

(b)

d(z,

y) = 0 iff z = y, (c)

d(z, y) = d(~], z),

(d)

d(z, z) <_ d(z, y) + d(g, z)

for all

z,y,z E X.

d defines a topology on X by taking the topology generated by the system of

open circles

U,(z)

:= {y E X:

d(z,9)

< r}, r E ~, z E X. < X,T > is called a

metric space iff there is a metric which generates its topology.

We now introduce the separation properties:

Definition 1.6 < X, 7" > is said to satisfy To iff for all x, x/E X there is A E 7"

such that xEAandx/~_AorztEAandzCA.

< X, T > is said to satisfy T1 iff for all z, zt E X there are A, At E T such that

x E A and

xt r A

and

xl E A1

and

z f~ At.

< X, T > is said to satisfy T2 iff for all z, zt E X there are A, A/E T such that

xEAandzlE

At

andANAt=~.

< X, T > is said to satisfy Ta iff for all z E X, B C X closed, z ~ B, there are

A, AI E T such that z E A and B C At and AN Al = !3.

< X, T > is said to satisfy

T4

iff for all B, B/C X closed, B N Bt = 0, there are

A, At E "l- such that

BCAandBtGAtandANA!=~.

Definition 1.7 Given two topological spaces < X, 7- >, < X/, TI >, a function

f : X ~ Xt is called continuous, iff for all

At E Tt f-liAr] E T.

In such

situations, we will also write f :< X, T >~< XI, T/> to note dependency from

the topologies. Given two metric spaces < X, T >, < X/, T/> defined by d and

dl, a function f :< X, T >--*< XI, TI > is called uniformly continuous iff for all

r/> 0 there is r > 0 such that for all

z E X f[U~(x)] C U~,(f(z)).

38

CHAPTER1. INTRODUCTION

1.4.4 Theory of measure and integration

A standard book for the theory of measure and integration is [Hal50].

Let X be some set.

Definition 1.8

-4.4 C T'(X)

is called a or-algebra over X iff (a) X E -4, (b) A E "4

--+ X-AE -4,

(c) {A~ :i Eco} CA--+ U{A; :i Eco} E .4.

The definition of a a-algebra generated by some

B C_ P(X)

parallels that of a

generated topology.

"4 is called an algebra iff it satisfies (a) and (b) above, but is closed under finite

unions only.

If .4 is a ~-algebra, a function # : "4 --+ R will be called a measure iff (a) #(9) = 0,

(b) #(A) >_ 0 for all A E .4, (c) If {A~ : i E co} C_ .4 is a set of pairwise disjoint

sets,-then #(U{A~ : i E co}) = s i E co}.

Definition

1.9 Let E be a a-algebra on X. P : E --+ [0, 1] is called a probability

measure on E, iff 1. P(O) = 0, 2. If {A~ : i E co} C_ E and for alli ~r j < co

Ai N Aj = (~, then P(U{Ai : i E co}) = E{P(A~):: i E co}, 3.

P(X) = 1.

Given a probability measure P, x,y E E, and

P(y) > O, P(z ] y)

is defined by

P(xny)

P(~ ly):= -p(~) 9

Definition

1.10 The standard ~r-algebra B on {R is that generated by the open

intervals (its elements are called Borel sets), and its standard measure is defined

by taking the lengths of the intervals as start, and extending to disjoint unions.

Definition

1.11 Given. two spaces < X,'4 >, < Xt,-4f > where .4,-41 are or-

algebras, and a function f : X --+ XI, we call f measurable, iff for all At E -41

f-l[Af] E A.

A function f :< X,-4 >--~< R, B > is called simple iff it is measurable and has

only finitely many different values, g* will then be the set of those f : X -+

such that there is a sequence of simple f;, i < w with

f;(x) <__ fj(x)

for all x E X

and all i _< j and

f(x) = sup{f~(z)

: i < co} ibr nit x E X. ($* is the set of

measurable functions from < X, "4 > to < R, B > .)

Definition

1.12 Given a measure # on M, the integral of a simple function

is defined as E{#(f-~[y]) * y : y e ran(f)}. This is extended to f E $* by

f fd#

:=

sup{f fld#

: i E co}, where the ]) approximate f from below as above.

This is the definition of the Lebesgue integral.

1.4.5 Logic

In most cases, we work in propositional logic.

/2 etc. will denote a language. The set of variables of a propositional language 12

will be denoted by v(/2). For a given language 12, a theory will be a set of formulas,

no deductive closure is assumed.

The

shall denote the set of/2-theories. Usually,

T etc. denote theories, r etc. denote formulas.

1.4. BASIC DEFINITIONS AND NOTATfON 39

• will stand for falsity, like r A -~p, true will stand for truth, e.g. r V -~r

We sometimes write A{r : i E I}, when this is intuitive, to denote the theory

i e I}.

TVTtwilldenote {r dtETt}.

A logic will be an arbitrary function from The to The, associating to a set of

s (the hypotheses) another set of/:-formulas (the consequences). A

logicl~-, is called compact iff for each T, r with TI" r there is 2r'/C T, T/finite

with Tll~ r

We will adopt the usual notation I- for the classical consequence relation,

(unindexed) for the classical semantical consequence relation. IN and related

symbols will denote the consequence relation of other logics. (At some places,

symbols like ~ will be misused, but this will then be clear from the context.)

To abbreviate, we will often denote the set of consequences of a theory by the

very intuitive bar notations for closure under a logic, T :-= {r T b 4}, T := {r

TI~

r

Con will stand for classical consistency, e.g. Con(T) says that T is consistent,

Con(T, T') says that T U TI is consistent, etc.

Given a propositional language s s classical models m are defined as usual:

For each p E v(s we fix arbitrarily m b p or m ~: p. The definition is extended

inductively to formulas by m ~ -7r iff m ~: r and m ~ r A r iff m ~ r and

m ~ r (and m ~ r

V

r iff m ~ r or m ~ r unless

V

is introduced via -, and

A etc.). Thus, each classical model is fully determined by its values on v(s

in other words, classical models can be identified with functions from v(s to

{true, false} or 2 : {0, 1}.

We denote by Me the set of all classical s and by M(T) or MT the set

of the models of some s T, i.e. the set of those ra E Me such that m ~ r

for all ~ E T.

For a/.;-model m, Th(m) is defined as {r ~ r for X C_ Me, Th(X) := {r

Vm E X.m ~ r }.

Dc C "P(Ms shall be the set of definable subsets of Ms, i.e. A E Dc iff there is

some T C_ s such that A = M(T). If the context is clear, we omit the subscript

s from De-

Finitely axiomatisable theories and the standard topology

We now show that in the standard topology - which essentially says that a model

m is in the closure of a set of models X iff for any fbrmula r with m ~ r there

is ml E X with mt ~ r too - the dopen sets are exactly the sets of models of a

single formula.

Definition 1.13 The set .A := {M.(r : r a ZLformula } __ 7~(ML) is ciosed

under finite unions (M(r U M(r = M(r V r Therefore, ft. forms a basis of

closed sets for the standard topology T defined by 0 6 Tiff Ao := Mc - O

is an (arbitrary) intersection of elements from A, i.e. iff Ao = M(T) for some

ZLtheory T, so the closed subsets of Mc are the sets M(T). Let for X C Mz X

40 CHAPTER I. INTRODUCTION

be the closure of X in T, i.e. the intersection of the closed sets containing X.

(The operator - being reserved for other purposes.)

A

Fact 1.14 (a) rnE X iffVr ~ r 3ml ~ X.rn!~ (9),

(b) for X C Y C X Th(X) = Th(Y),

(c) X = M(Th(X)),

(d) X c ML is ~topen ig X = M(r for some formla r

Proof (a) ~' --,": Suppose there is r such that m ~ r but for no rnt ~ X

rm ~2" Then M(-~r closed, includes X, but not rn, so rn ~ X. " *--": If

m ~ X, there is a theory T with X C_ M(T), m r

M(T).

So there is r E T,

m ~ -,r but for all rnl E X ml ~ r

(b) " D" is trivial. " C_": If there were_ r E Th(X) - Th(Y), then there would be

m E Y - X, m ~ -~r but for all ml E X ml ~ r contradicting (a).

(c) M(Th(X)) is the least closed set containing X.

(d) "~-": M(r and M(-,r are both closed. :'~": Let X be clopen, so by

definition, X = M(T), Mc - X = M(Tt) for two theories T,T'. Without loss

of generaiity, T is deductively closed. Suppose for no r E T X = M(r So

C

for all r E T M(T) r M(r so M(r P1M(TI) 7~ (3, so Con(r But by

M(T) f~ M(Tt) = (~, not Con(T,T'), so by compactness of classical logic and

closure of T under classical consequence, there is r E T such that not Con(C, T@

Contradiction. []

Definability

Fact 1.16 and Example 1.1 below' will show that, in general, not all subsets of

Mz; are definable.

Definition 1.15 For

X

G ~P(Mc), a function

f

: .u ---+ P(Mc) will be called

definability preserving (dp), iff for all Y E Ds M X f(Y) E De.

If Dc C_ X, then f : X -4 P(ML) defines a logic T ~-+ T S on s by T S := {q~:

Vm E f(M(T)).m ~ r So, if f = id, then T s = T.

Note that f(M(T)) C M(TQ always holds, but not necessarily f(M(T)) =

M(T]), the latter only iff f is dp - see Example 1.1 (1) below. The logics we

shall consider will mostly be strengthenings of classical logic, and will often be

defined semantically by some such f, i.e. T := T f _D T. Thus, for such f,

N(M(T)) c: M(TS) C M(T).

Fact 1.16 1. tf v(s is infinite, then D, # P(Mc),

2. 0, MzEDL,

3. D~ contains all singletons,

4. Dz. is closed under arbitrary intersections,

5. Ds is closed under finite unions.

(Thus, the elements of DL are the closed sets of a suitable TyTopology on Ms

1.4. BASIC DEFINITIONS AND NOTATION 41

Proof 1.: Let card(v(s = ~ > w, then, as each r E s is finite, card(Z) = ~,

so card(D) <_ card(7~(s = 2 ~, but card(ML) = 2 ~, so card(7~(ML)) = 2 (2~) >

2 ~. (The argument collapses in the finite case, as then card(v(Z)) < w = card(C).)

4.: Let Ai E D, i E I, A,- = M(T~), T := U{Ti : i E I}, A := M(T). Then m E

N{A~ : i E I} ~ Vi E I.m ~ T~ ~ m E A.

5.: Let A = M(T), Al = M(Tr), and B = M(T V T@ Then m E A U A/

Ye E T.m ~ r V Ve E Tl.m ~ g) ~ Vr V e E T V T/.m ~ r V r +-+ m E B. []

Example 1.1 Let v(Z) := {pi : i E w}, and too, mS ~ Mz be defined by

m0 ~ {pi: i < w} and m[ ~ {=pi} U {pj: j < w,i 7~ j}.

(1) Let M/:= Mc - {too}. We show that M/is not definable. Suppose there is

r such that r holds in all m E MI, but not in too, so mo ~ -~r but by finiteness

of r there is a finite fragment of rn0, consisting of the propositional variables in

r which decides r and there is m E M/, which coincides with m0 on that finite

fragment, so m ~ --r contradiction. (Each m E Mc is essentially a function

f,~ : v(Z) --+ 2, and if a C v(Z) contains the propositional variables of r then

for all m,m' such that f,~[a = f,~,[a we have m ~ r iff m/ ~ r So M/is not

definable, and f : D -+ P(Mz) defined by

Mt iff M(T) = Mc

f(MT) := M(T) otherwise

is not definability preserving.

(2) We conclude by giving an example of a countable definable set of models, and a

countable set of models which is not definable. Let T := {p~ Vpj : i, j < w, i # j},

M := {too} U {m[ : i < w}, M/ := {m[ : i < w}. Obviously, M and M/ are

countable, and M(T) = M : If m E Mc makes more than one Pi false, T does

not hold any more in m. But M! is not definable: The same argument as in (1)

works, as for each finite fragment of m0 there is m/E M/such that m/and m0

agree on that fragment. []

We shall now give some of the proof-theoretic properties considered in [KLM90]

and [LM92]. They partly go back to [GabSh], see also [Mak94] for a discussion.

Definition 1.17 The axioms of P and R.

(Strictly speaking, most of these axioms are rules, and a system X of c~ I" fl's is

said to satisfy P (or R), iff it is closed under the corresponding rules.)

(1) Right Weakening: F c~ ~ fl, 7i ~ ~ =* 71 "~ fl,

(2) Reflexivity: c~l.-~ c~,

(3) AND: o~j,--, ,8, o~},---, '-/~ a},--, ~A'7,

(4) oR: "7, ~ -7 v %

(5) Left Logical Equivalence (LLE): F a ~--~ fl, fll~ 7 => c~I~ 7,

(6) Cautious Monotony (CM): al--~ fl, c~t~ 7 =a c~ Afll~ %

(7) Rational Monotony (RM): al~-. /3 ~ (c~[~ ~7 or aA 71~ fl).

The system P consists of (1)-(6), R of (1)-(7).

These properties were first defined for single tbrmulas, some of them generalize

in a straightforward way to arbitrary sets of formulas, e.g. the following is the

infinitary version of Cautious Monotony: T C T/_C T --~ T/C T.

42

CHAPTER 1. INTRODUCTION

It is sometimes

a

non-trivial problem

whether

the situation carries over from the

finitary version of these rules to the infinitary version.

We mention several important properties, proofs and others can be found in

[KLM90] and [LM92]:

Fact 1.18 P entails

(1) Cut: ~t~ 9,~A91 ~ 3' ~ ~1 ~ 3',

(2) Cumulativity (GUM): al,,~ ~ =~ (c~l,-~ 3' ~ c~A~[N 3'),

(3) One half of the

Deduction Theorem: c~ A ;~ IN "~ ~ c~ I~ ~ ~ 7 (see the

generalized version, infinite conditionalization, condition (=4) in Theorem 2.81),

(4) Distributivity: a A-,,8t~-, 3', a A ~IN 3' =a a t~ ~/-

An infinite version of Distributivity is A M B C A ~'1B.

Definition 1.19 We now give the formal definition for Reiter's default system

(see [ReiS0]), For simplicity, we work in propositional logic.

a:~

Recollect that a default has the form W-' where a, r 3' are classical formulas.

Let 2x := (W, D), where W is a classical theory, and D a set of defaults.

Given a theory S, F(S) is the smallest set satisfying (D1) W c F(S), (D2) F(S)

~:o F(S),-~fl P(S), then E F(S).

is closed under ~-, (D3) If -7 E D, and a E ~ 7

A theory E is an extension, iff F(E) = g.

Chapter 2

Preferential structures

related logics

and

We first (Section 2.1) discuss in detail preferential structures. We then (Sec-

tion 2.2) turn to the Stalnaker/Lewis semantics for counterfactual conditionals,

which in intuition and mathematics are very close to preferential structures, and

finally address (in Section 2.3) a problem that has developped in the context of

preferential structures: the approximation of a logic from below.

2.1 Preferential structures

2.1.1 Introduction and basic differences

Circumscription was one of the first formal approaches to NMR - see e.g. [Gin89],

[GPP86], [Lif85], [Lif86], [McC80], [McC86], [Mor85], [Mot87J, [PM86], [Sch88-2].

If T is a first-order theory, then its circumscription C is a (usually stronger)

first or second order theory, whose semantical counterpart are, essentially, the

minimal models of T : The order is by set inclusion, either on the domains, or

on the extension of one fixed predicate - the rest of the interpretation is kept

fixed. We thus have a partial order on the models of T, and consider only the

C-minimal ones.

This was generalized by Bossu/Siegel [BS85] and Shoham [Sho87] to consider

models, ordered by some binary relation. Imielinski [Imi87j then tried to establish

a connection between Circumscription and Reiter Defaults - we will return to it

below in Section 2.1.3.

On the other hand, general proof-theoretic properties of nonmonotonic logic were

examined by Oabbay (see [Gab85]), Makinson [Mak89] - for an exellent overview

and discussion see Makinson [Mak94] - and others. A confluence of both direc-

tions of research is found in [KLM90] and [LM92], where S.Kraus~ D.Lehmann,

M.Magidor (D.Lehmann, M.Magidor respectively) have linked proof theoretic to

semantic approaches of nonmonotonic logics in a number of important results.

We now define preferential and ranked models, modifying notation slightly as

compared to [KLMg0] and [LM92] (see Remark 2.4 below).

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

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