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

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

14 CHAPTER I. INTRODUCTION

can neither be entered nor left by approximation: If xi is a sequence of elements

in a clopen set, then its limit (if it has any) is in X, as X is closed. If x~ is a

sequence of elements not in X, then its limit is outside X, as the complement of

X is closed. Thus, this restriction seems to go somewhat against the spirit of the

limit approach.

In the end, one might also criticize the fact that Boutilier lets the modal operators

O and [] do all the "nasty" work, which turns out so unpleasant in an attempt of

a direct construction: From the semantical point of view, ~ and ~ are quantifiers

over possible worlds which cooperate with the relation -<, and it is precisely the

interplay of both quantifiers which presents difficulties. But, it is always easy to

criticize in hindsight ....

Interpretation

We have so far deliberately left open the base logic and its models in M, as well

as the intuition behind the "importance" of models of the base logic.

Deontic Logic:

Deontic logic reasons about the normatively acceptable situations, and about

what ought to be done (by humans, robots etc.). Reasoning about normatively

acceptable actions can be split into two subquestions: Reasoning about the nor-

matively acceptable states, and reasoning about the problem of acting in a way

conducive to those states. The latter question can be considered separately, at

least in a first approximation.

In this framework, the preferred or more important models are those which are

normatively more acceptable. Thus, preferential structures provide a natural

semantics for deontic logic, and, in fact, were examined as such before the advent

of nonmonotonic logics, apparently first by B.Hansson, see [Han69]. This was

pointed out by D.Makinson in [Mak93].

Nonmonotonic logic:

In the context of nonmonotonic logic, "importance" may be read as "normality":

We are primarily interested in reasoning about the normal cases, and the preferred

models are the most normal ones - where birds can fly, houses have doors etc.

As a matter of fact, preferential structures in their various forms provide an im-

portant and relatively well-studied kind of semantics for nonmonotonic logics.

They have been a powerful tool for investigation, providing - via additional prop-

erties of the relation -~ - a technique for constructing semantics of logical systems

of different strengths.

The semantics of preferential structures was thus rediscovered for nonmonotonic

logics. Limit preferential structures for nonmonotonic logics were introduced by

G.Bossu and P.Siegel in [BS85]. The minimal case was, independently, first exam-

ined by Y.Shoham ([Sho87]) as a generalization of the minimal model semantics

for circumscription. More or less general cases of preferential structures are char-

acterized by soundness and completeness theorems in [KLM90], [LM92], [Sch92],

[Sch96-1] for the minimal case, in [Boug0a], [Bou90b],

[t~ou92],

and in this paper

for the limit case. For an overview, see also IMak94].

1.3. INTRODUCTION TO NONMONOTONIC LOGICS

In hindsight, it is no surprise that a local preference by a binary relation tends

to emerge, when we examine choice functions which single out some states as

more important or interesting than others. Such local preferences seem to corre-

spond well to intuitions, and simplify the situation by making the choice context-

independent.

In [Mak93], still other natural applications of preferential structures are discussed.

If we look back at the example given in Section 1.3.1, we see that the minimal

and the limit approach coincide in this simple case.

As noted already when presenting the example, not all classical models for a

given language s need occur in the base set M of a preferential structure .Ad

(e.g., in our example, some m/! ~ p A -,q is missing). Moreover, some classical

models might occur several times, even infinitely often. Take for example Z; with

one propositional variable p and consider the structure YM :=<

{<m,i

>: i <

~o},-<>, m a classical model with m ~ p, and <

m,i

>-<<

m,j

> iff j < i.

By abuse of language, we shall also write < m, i >~ p, etc. Then #(M) = ~, so

true

~4 _L in the minimal reading, but

true

~4 r iff r is a classical consequence

of p, in the limit reading.

More details and examples of logics which require several copies of classical mod-

els to be representable by preferential models can be found in [Sch96-1]. The

intuitive justification is, that we speak about the world in a richer language, than

the language used for reasoning. Thus, the seemingly (for reasoning) logically

equivalent models are, in fact, different, but only in the extended language.

In the literature, there are two notational variants to handle possibly repeated

occurrence: In [KLM90J and [LM92J, a function f : M ---* Mc from an arbitrary

base set M assigns a classical model to each element, the present author works

instead with indexed classical models, as already done above.

Strengthenings of the conditions for the relation -4

Various additional conditions for the relation -< have been introduced and exam-

ined for minimal preferential structures.

The most natural one is perhaps transitivity.

An important condition, which results in nice properties of the semantic con-

sequence relation ~ is smoothness (terminology of D.Lehmann and his co-

authors) or stopperedness (terminology of D.Makinson): Given a theory T, and

a non-minimal model m of T, there is m/-< m, which is a minimal model of T.

Consequently, if

M(T) 7~ ~,

then p(T) r 0. "Smoothness" or %topperedness"

can be violated in essentially two kinds of situation. First, suppose X consists of

an infinite descending chain of elements zi. Then, no

zi ff X

is minimal in X,

and no xi has a minimal y E X below it. Second, suppose that X :=

{x,y,z},

with x -< y --< z, but not x -< z. Then z is not minimal in X, and there is no

a E X below z which is minimal in X.

The counterpart for the consequence relation ~ is Cumulativity (see [KLMg0]

and [Gab85]) which says that two theories

T, Tt

with

T C_ Tt C_

{4: T ~ r

have the same consequences: T ~ 0 iff T! ~M r We may read this as "normal

CHAPTER 1. INTRODUCTION

use of Lemmas": K we have already deduced the "Lemma" q5 from T, we neither

lose nor win in terms of possible deductions by starting from T tO {r

As a matter af fact, again a very general algebraic representation result can be ob-

tained: A choice function f can be represented by a smooth minimal preferential

structure iff it satisfies the conditions (0), (1) and

(2)

f(A) C t? C A ~

f(A) =

f(B)

and if its domain satisfies closure under finite intersections and unions (see

[Sch96-1], Theorem 2.1).

Another strengthening of -~ is rankedness, which may be seen as the existence

of a "rotating scale with fixed origin": < is called ranked (on M), iff there is an

order-preserving (in both directions) function f : (M, 4) -~ (X, -,~ *), where ~ *

is a total order on X. Then two <-incomparable elements

m,mt ff M

behave

exactly the same way with respect to <: r~ < m iff n -~ ml, and m < n iff

m/< n. The corresponding property of ~M is Rational Monotony: If c~ ~ 7,

then c~ A/3 ~ "~ or a ~ 7/3 (see [LM92]). General representation results are

again to be found in [Sch96-1].

Generalizations

We can consider choice functions on arbitrary sets, which need not be sets of

models.

We have already seen above two characterizations of such functions defined by

minimal preferential structures.

The strength of our algebraic representation results lies in their generality. We

can more or less easily obtain soundness and completeness results as Corollar-

ies for nonmonotonic logics with classical propositional logic as background, see

[Sch92], [Sch96-11, and Section 2. But, these results can also be read with classical

predicate logic in the background, giving representation theorems for preferen-

tim structures over models for predicate logic. Using these algebraic representa-

tion results, we have also obtained completeness and incompleteness results for

Plausibility Logic. This is a sequent calculus for a very poor language without

connectives, introduced by D.Lehmann, see [Leh92a], [Leh92b], [Sch96-31.

The Stalnaker/Lewis semantics for counterfactual conditionals presents essen-

tiMty the same algebraic ideas as preferential structures. Thus our algebraic rep-

resentation results are easily adapted to counterfactual conditionals in [Sch96-4].

But these representation results (or at least their ideas) can be used in still more

gelaeral situations, where we do not compare single models, but whole "threads" of

developments in dynamic situations. This is done in [Sch95-3], where we consider

preferences on developments.

In the first part (Theorem 2.8 there), we show that a deontic choice function of

"good" developments defined in [Tho84] can be represented by a ranked, stop-

pered relation on all developments. Thus, we do not compare single models, but

developments in a branching time structure. Again, we leave open the question of

acting "morally". We do not discuss ways to achieve such desirable developments,

or to continue them and not to go "astray". We only discuss - as R.Thomason

1.3. INTRODUCTION TO NOI"IMONOTONIC LOGICS 17

does in [Tho84] - the "quality" of the developments, and show that again a local

choice by a binary preference relation suffices. The preference relation can even

be assumed to have very nice and strong properties.

In the second part (Theorem 3.4 there), we give a characterization of coupled

logics which can be obtained from a preference relation on developments: Assume

the information S and T at time points ~ and t respectively about a development

to be given, and a preference over developments. We examine the theories Sl

and T/determined by the end-points (i.e. models) of the preferred developments

among those which pass through S- and T-models. This defines a pair of coupled

logics, < S, T ~ < $/, T/>.

Historical remarks

Semantically, Circumscription corresponds to minimal classical models: the mod-

els of a circumscribed theory are roughly those in which the extension of some

predicate is minimal by set inclusion. This was generalized independently by

Shoham and Bossu/Siegel (see e.g. [BS85], [Sho87]) to consider models, ordered

by some binary relation. On the other hand, the general proof-theoretic properties

of nonmonotonic logic were examined by Cabbay (see [Gab85]) et al. A confluence

of both directions of research is found in [KLM90] and [LM92], where S.Kraus,

D.Lehmann, M.Magidor have linked proof-theoretic to semantic approaches of

nonmonotonic logics in a number of important representation theorems. They

use, however, some finiteness assumptions whose relevance is shown in Section

2.1.4, where we give an example (Example 2.3) which proves that one of their

results fails in the general infinitary version. In the following Section 2.1.5 we

work without any such finitary restrictions and obtain a positive result. We show

the central role of infinite conditionalization, discussed in [Mak94], Section 3.4.

As a matter of fact, this property almost fully characterizes "logically nice" -

definability preserving - classical preferential models (Theorem 2.81). Further

detailed discussions of semantic and proof-theoretic properties of nonmonotonic

logics can be found in [Mak89], and especially in the already quoted [Mak94].

Researchers in Artificial Intelligence should, however, bear in mind that some

central semantical concepts of nonmonotonic logics were introduced in different

contexts (deontic logic, counterfactual conditionals) by philosophers, long before

nonmonotonic logics were born. The work of B.Hansson was already mentioned

above, D.Lewis discusses both the "limit" and the "minimal" variant in depth

in his famous book [Lew7a], along with possible justifications and formal conse-

quences. The probably first such examination in nonmonotonic logics, compara-

ble in depth and technical maturity to the work of Lewis, the articles by Kraus,

Lehmann, and Magidor [KLM90], [LM92], appear only more than 15 years later!

Thus, conceptually and technically, Artificial Intelligence has lacked behind in

the beginning - at least in some areas - by almost a (scientific) generation. The

reputation of Artificial Intelligence - and its researchers - still suffers from tile

lack of culture, and, above all, from the lack of modesty, of its early years.

CHAPTER 1. INTRODUCTION

1.3.6 Introduction to defaults as generalized quantifiers

Motivation

To cover the static aspect of defaults, we have - as shortly described already above

interpreted open normal defaults, i.e. of the form ~

or ~

with at least

one free variable, as generalized quantifiers: "Normally, birds fly" b/~d(~):]b(~)

' IZy(~) '

is translated into "Most birds fly" or :~The elements of a large or important

subset of the set of birds fly", and written

Vxbird(m) : fly(x),

in an extension

of the language of first-order logic. (We will use "large" and "important" etc.

interchangeably - what really matters will be the formal definition.) This is given

a dear semantics in the form of a system of such "important" subsets of the

set of birds. The system will be defined to be almost a filter. We thus add

additional structure - in the form of such a system - to first-order models to

provide a semantics for the new quantifier. In such an enlarged structure, the

default "Normally, birds fly" will hold, iff there is an "important" subset of the

set of birds, all of whose elements fly.

Discussion of the system Y

We have deliberately chosen a very weak formalization of the concept of "large"

subsets, weaker than a filter: If B is the base set, then any system N'(B) of

important or large subsets of B has to satisfy

(1) B is large: B E

.M(B),

(2) supersets of large subsets are large: A C A/C B, A E N'(B) -~ A, E

H(B),

(3) the intersection of two large subsets is non-empty: A, AI E X'(B) -+ A N A/

The third property is the most interesting one. A filter would require the interseo

tion of two large subsets to be large itself', we content ourselves with non-empty

intersection. This permits e.g. a simple probabilistic interpretation of A E N'(B)

by "more than half the elements of B are in A'. In the intended interpretation

it is property (3) that permits us to deduce that "normally r and "normally

-~r together are impossible: there is no element which satisfies both r and

We do not think that any weaker system could still capture the notion of 5m-

portant" or "large" subsets. In particular, (a) may be strengthened to the filter

property

A, AI E N'(B) --+ A f~ At E H(B),

but this would already preclude the

abovementioned probabilistic reading. Note however, that our properties cap-

ture also a "prototypical" reading: if b E B is an arbitrary element of B, then

{A C B : b E A} is a system as required.

Syntax

In the formal development, we have first treated normal open defaults without

prerequisites, i.e. of the form :2251 rewritten or interpreted in our notation as

Vxr Thus, We have treated Vx as some kind of quantifier which lies between

1.3. INTRODUCTION TO NONMONOTONIC LOGICS

3 and V. It seems - at least to us - unreasonable to say that normally r holds,

when there is no x such that r On the other hand, if Yzr holds, it seems

reasonable to say that ~ normally holds. So, we have gzr ~ Vzr -*

3xr As said above, it seems unreasonable to say that normally r holds,

and at the same time, that normally -~r holds. We thus have the axiom

Vxr ~ -~Vx-~r i.e. {Vzr Vz-~r wilt be inconsistent.

The extension of first-order logic to a sound and complete axiomatisation for

our semantics, allows us not only to derive defaults - e.g., if "normally, r

and r implies r then also "normally, r - but gives us a notion of

consistency of default theories too. Thus, we have obtained a criterion of the

admissible - the consistent - any logic should have.

Discussion of our system

Further advantages of our approach As we work in the full first-order

framework, with defaults in the object language, we have achieved far more than

we first aimed for: Not only negated defaults - in our birds example, there would

then be no important subset of "birds" all of whose elements fly - have a clear

meaning, but so do arbitrary boolean combinations of defaults, nested defaults,

arbitrary combinations of defaults with ciassical quantifiers etc.

A local semantics We also wanted to give a local semantics - as opposed to

a global semantics (e.g. by possible worlds) - in the following sense: Just as the

operators A, -~ or the quantifiers V, ~ have local meaning in a classical model: i.e.

they really hold (in the obvious sense), or do not hold, we think, a default should

have local meaning too. As our "large" subsets are subsets of one universe, we

have achieved locality as wanted.

To make things clear, let me illustrate the opposite point of view. More philo-

sophically and linguistically oriented people tend to say: "Normally r may be

true, even if in the world, there is no single case of r (This was put forward

e.g. by N.Asher and M.Morreau in discussion.) Put polemically, this has always

reminded the author of political arguments. Like: "Sure, human rights are re-

spected in our country. The fact that everyone is in jail and tortured has nothing

to do with it."

Advantages of a weak system Choosing a very weak system has several

advantages:

First, it is easier to extend a weak system by adding axioms on the proof theoreti-

cal side, and additional properties on the semantic side, preserving soundness and

completeness, than to retract some axioms and properties. Second, we thus give

a broad interpretation~ which can easily be modified to suit special domain (i.e.

semantic) purposes or personal tastes. Third, we are not forced to make many

r commitments, but provide a tool kit to incorporate the desired

postulates. Such extensions will be discussed in Section 3.2.2.

CHAPTER

INTRODUCTION

In summary, we might say that we have tried to cover the minimal properties of

the static part of "normally", giving a local interpretation in an extended FOL

model, where 34 ~ "normally r iff there is a large subset A of .Ad's universe

such that for all a e A 34 p q~(a).

K7 can reveal deeper conflicts than V Let us further point out here that

the interpretation of defaults as the classical universal quantifier precludes in

general a theory revision approach: Any default theory thus read will usually be

inconsistent, by the mere presence of exceptions.

From a more philosophical point of view, we might say that our formalism al-

lows us to detect finer default inconsistencies of the form "normally" qS(z)" and

"normally -~r than classical logic. Vxr and -~r are already classically

inconsistent. As we shall see in the formal part, Vxr and r are very

well compatible, as exceptions are toIerated. On the other hand, Vxr and

Vz-,r are inconsistent. A classical interpretation "sees" too many inconsis-

tencies, precisely because it is too rigorous, "normally" is not necessarily "all".

Our weaker reading, in the sense that we interpret "normally" not as %I1", but

as something like a qualitative "most", penetrates through the outer layer of clas-

sical or pseudo-conflicts (pseudo in our context) to those which may exist on the

level of normality itself.

Relativising to defaults with prerequisites

The open normal default with prerequisite V,(x!:6(~) is read as a bounded gener-

alized quantifier, written Vz e {y: r : r abbreviated Vz~b(z): r

understand it as saying that all z which satisfy ~b, will normally satisfy q~ too.

Of course, this is very different from

Vz(~b(z) -* r

The former will be true

iff the set X of things which satisfy ~b and do not satisfy ~b, is small in the set

of things which satisfy ~b, whereas the latter will be true iff X is small in the

universe. Again, we shall have rules like Vx(~b(z) -+ b(x)) -+ Vz~b(z) : $(z) -+

[a.r A

All essential techniques and ideas are present in the case without prerequisite, the

extension to defaults with prerequisites is straightforward and works by simple

relativization.

We shall not give other (e.g. non-normal) types of defaults an (intuitive) se-

mantics here, but mention that a seminormal default might be seen as having

a computational meaning: To assume the full strength of the supposedly true

situation might be too costly in case of error and revision. Defaults of the form

:~, where ~ has no free variables, are not treated. Intuitively, we would read them

as implicitely quantifying over all models under consideration.

Some remarks on the historical background

The word "generalized quantifier" is perhaps not 'very well chosen: Traditionally,

the interpretation of a generalized quantifier is by a subset of the universe which

1.3. INTRODUCTION TO NONMONOTONIC LOGICS 21

is large by cardinaiity. But if the universe U has infinite cardinatity ~, then there

are disjoint subsets of U of size ~. So, if "large" is read as "cardinality a," this

contradicts our main axiom of normality, A, B E N'(U) ~ A ~ B r ~, expressing

that '~normally, q~" and ~normally, --~'~ together are incoherent. So there is a

profound difference between the traditional concept of a generalized quantifier,

and our ideas. They are designed to speak about very different things.

An exception is e.g. [Kau84], where the interpretation of a generalized quantifier

by a given filter is examined.

The concept of a generalized quantifier was introduced by Mostowski in IMos57],

completeness for the interpretation as "there exist uncountably many" was stud-

ied by Keisler in [Kei70]. Standard models for %here exist many ~' were investi-

gated and corresponding completeness shown by Krivine and McAtoon in [KM73].

Very short discussions can be found in the Handbook of Mathematical Logic, in

contributions by Barwise [Bar77], p.44-45, and Keisler [Kei771, p.100-101.

The first detailed account of our theory of defaults as generalized quantifiers in the

LILOG framework have appeared in [Cor89], [Lor90], and in a different context

in [Sch90].

i.3.7 A two-stage approach

In our approach to defaults by generalized quantifiers, we have relegated the

dynamic aspects of defaults to the third Chapter, where we use - essentially - a

maximal coherent subset of the information chosen according to specificity, and

to the implementation, discussed in [Lor90], where as many x as possible are put

into r when the default "normally r demands it.

In a two-stage approach to appear in [Sch96-5], we start with the static aspect

of defaults, and choose then among the extended FOL models of a default the-

ory T, (defaults interpreted as generalized quantifiers), the "good" models by a

preferential relation.

The first step assures us that the defaults have an objective meaning, the second

captures the "inference-greedy" aspect by making true as many instances of the

defaults as possible.

The fact that we choose only among the extended FOL models guarantees that

the minimal, static requirements are met, i.e. that the default theory "means

something objectively", that really the default properties hold for a "large" sub-

set. The preference relation makes the properties hold for as many elements as

possible. E.g., for the theory ~ ~-~j 5(z) will not only be true for a large subset -

sufficient for the interpretation as generalized quantifiers - but for all elements of

the universe, as there is nothing which contradicts this extension. I :~(~) ~/

~(~), ~(~) J~

however, will be ruled out immediately as inconsistent.

Basically, a model M is considered better than a model M! for the theory T, iff

(1) for all defaults in T, M satisfies all positive instances of the default that MI

satisfies (where c is a positive instance for the default :e(~) iff ~b(c) holds in that -~,

model - the case for defaults with prerequisites is analogous), (2) for no default

in T, there is a negative instance which holds in M, but not in M! (where c is a

CHAPTER !. rlNTRODUCTION

negative instance for the default :e,(;) iff -~r holds in that model - the case for

7~Y'

defaults with prerequisites is again analogous), (3) there is at least one default in

T, with one positive instance e in M, which is not positive in Ma

This definition is essentially taken from [BS93].

Note that enlarging the universe might introduce new negative instances without

destroying old positive ones. This is the justification of the condition (2).

As our formalism with generalized quantifiers allows us to deduce defaults, e.g. by

the axiom schema Vxqi(x) h gx(r ~ ~b(z)) -+ Vz~b(x), it is not clear which

defaults enter into the definition of the relation "M is better than MF. But,

consider a theory of two defaults Vzr and Vz~b(x), then we can deduce the

defaults

Vx(r

V -~b(x)) and Vx(~b(x) V -~r which could block an attempt

to extend the positive instances: Suppose that VxqS(z) and Vx~b(x) hold in

MI, as well as -,r A

-~'~b(a)

and -,r A ~;b(b). Suppose further that there is

model M, which agrees with MI with the exception that r and r hold,

too. Obviously, M is a better model, by the above definition, for the two defaults

Vxr and Vxr and this corresponds to intuition. If we apply the Definition

to the derived defaults, however, we see that M is no longer better: Changing

-~r to r introduces a negative instance for the default Vz(~,(z) V -~r

(Making also ~b(a) true might be forbidden.) We therefore consider either only

the defaults present in the original theory, or, alternatively, a set of defaults

mentioned explicitly.

The following example justifies a limit preferential structure approach, beyond

the abstract consideration, that the existence of ideal situations is perhaps not

always guaranteed. Consider a language with one unary predicate

P(z),

the

default VzP(a:), and the classical theory which says that we have infinitely many

instances of

=P(x).

All

models will be infinite. We have no best models, as we can

always make another element a positive instance. The theory is consistent, and

we would like to deduce at least that we have infinitely many positive instances

too. So not all models will have the same intuitive value, but none is the best. So

we have infinite descending chains, leading to an inconsistent set of conclusions in

the minimal preferential structure approach: The set of minimal models is empty,

and semantical entailment was defined by universal quantification over the set of

minimal models.

1.3.8 Introduction to logic and analysis

We use the notion of distance, discussed in Section 1.3.5, as primitive in still

another context, to be described now.

Classical logic has relatively little structure. Its models iorm just a set (or class,

if you like). The semanics of nonclassical logics have often more structure, like

accessibility relation for modal logic, distance relations for counterfactual condi-

tionals, preference relations for deontic and nonmonotonic logics, a notion of size

again for nonmonotonic logics. So, in non-classical logics, models are not only

equal or different, but they might be close or distant, sets of models may be big

or small. So it comes as no surprise that a notion of distance between models

1.3. INTRODUCTION TO NONMONOTONIC LOGICS

and between theories proves to be useful in still other non-classical situations.

In Chapter 4, we are primarily interested in the distance between theories. We

define this distance semantically, by a distance between models, which carries over

to distances betweeen models, and thus between theories (defined as the distance

between their sets of models). This avoids problems with syntactic reformulations

of logically equivalent theories, and seems, in general, to be the sounder approach.

One notion of distance, built on a partial order of "importance" of the propo-

sitional variables is examined in detail in Chapter 4. It permits to define the

distance between individual models and between sets of models in the same way.

The distance is, roughly, the first (by importance) propositional variable tbr which

the models or sets of models do not coincide. In this particular case, the notion

of distance is then further reduced to a relation of order or importance on the

propositional variables.

This seems to be a naturM way to measure distances between models. Technically,

it results in nice topological properties. The space thus constructed is almost

metric, and uniformity properties, like uniform continuity, uniform approximation

can be defined. Separation properties and connections between continuity and

compactness of a logic are shown.

We use this distance to - define a topology on the set of theories. This permits us

to characterize a logic as continuous, which is a measure of well-behavedness or

stability of a logic: If the input (the set of axioms) changes a little, the output (the

set of consequences) changes a little, too. - define a distance between logics, and

thus profit e.g. from the semantics existing for one logic to see the (approximate)

meaning of the other. - say that a sequence of logics approximates another logic,

which opens a way of speaking about approximate reasoning in formal and precise

terms. - give precise meaning to the much-used notion of graceful degradation. -

say e.g. that an abstract of a text is close to its original.

Finally, the underlying notion of importance opens new approaches to theory

revision and relevance, by neglecting unimportant information.

Finally, we use the same distance and partial order to define a measure on the

space of theories~ leading to the definition of the average difference between two

logics, i.e. the integral of their local differences.

1.3.9 Introduction to theory revision

Theory revision took its origin as an abstraction of a problem from legal reasoning.

When a new law is passed, the old body of laws may contain obligations, which

contradict the new law. In that case, the new law is supposed to have precedence

over that part of the old laws which contradicts it (unless the old law has, by

principle, precedence over the new one, like federal law has over state law). Yet,

in case of conflict, it is not intended that

all

of the old laws should become invalid,

onty that part which contradicts the new taw. A - in some sense - minimal change

should be made to the old laws to incorporate without contradiction the new law.

Abstracting from the legal or deontic context, we want to incorporate a formula

into a theory T, such that T is minimally modified to some T/, such that TID {4~}