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

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

CHAPTER 1. INTRODUCTION

is consistent. One can thus consider revision as a two-stage process, where we

first take a minimal amount of information away from T, so that the rest TI is

consistent with the new formula 4), and TI U {r is the final result of the revision

process.

One sees very quickly that, in general, the minimal modification of T to aecorno-

date r is not uniquely determined. For instance, if T = {r and 4) = -,(c~A r),

we can sacrifice cr or % sacrificing both as fairness dictates would not be a minimal

change.

The approach of Alchourron~ G~irdenfors, Makinson (AGM)

AGM consider, as motivated above, two operations. The first, called contraction,

noted T-C, takes a theory T and a formula r and results in a minimally modified

theory Tt such that T1 U {-7r is consistent. The second, called revision, noted

T * r takes a theory T and a formula 4), and results in incorporating r into T in

a consistent way, with minimal changes.

AGM have approached these operations from the outside, and established a num-

ber of properties, one should reasonably expect to hold for contraction and re-

vision. AGM call these properties rationality postulates. For instance, it seems

reasonable to expect that (the deductive closure) of T, 4) is a subset of the (de-

ductive closure) of T. (Of course, one can also consider minimal changes, which

violate this condition in general. Take, e.g., a finite propositional language, and

stipulate that T - r should have exactly as many models as T, if possible.) As

motivated by its historical origin, 4) will be a consequence of T * 4). If possible,

i.e. if r is consistent, T * 4) will be consistent, too.

AGM show that the two operations are interdefinable by T* 4) := (T-(-7r

and T - r := T fl (T * (-~r

To solve the problem of underdeterminancy of "minimal change", AGM have in-

troduced a (partial) order on the formulas of the given language, called "epistemic

entrenchment". In our above example, if ~ is less entrenched that r, this pref-

erence dictates the choice, cr will be sacrificed, and r upheld. AGM have again

established a number of "rationality postulates" for such relations of episterrfic

entrenchment. E.g., 4) [- 'r implies r < ~b : if r is a logical consequence of 4),

then, being logical people, we believe at least as much in "~b as in r

AGM have shown equivalence of the rationality postulates for epistemic en-

trenchement relations to the rationality postulates for revision e.g. in the follow-

ing sense: If revision is defined in a natural way from an epistemic entrenchment

relation which respects these postulates, then the revision operation will respect

the rationality postulates for revision.

A problem with eplstemic entrenchment relations

One disadvantage of the epistemic entrenchment relations is that they depend

on the old theory T. Indeed, one of the postulates for epistemic entrenchment

relations says essentially: r ~ T iff r _< ~b for all 'r

1.3. INTRODUCTION TO NONMONOTONIC LOGICS

Thus, if we base revision on epistemic entrenchment, we cannot fix one epistemic

entrenchment relation for revisions of all theories T, but need a new relation _<:r

for each theory T. In particular, for iterated revision, we need several epistemic

entrenchment relations. We show in Chapter 5 how to do with one single relation

oI~ formulas, called epistemic preference relation there, from which a relation of

epistemic entrenchment can be constructed for every theory T. We further show

that such an epistemic preference relation can be constructed in a natural way

from a probability measure on the set of models of a (countable) propositional

language, and we can thus base theory revision on a semantic structure, consisting

of a set of possible worlds, and a notion of size.

So, here too, we see that some problems can be reduced to the notions of (distance

and) size.

We will return to theory revision in Section 3.3, when discussing a theory revision

approach to default information in a order sorted langt~age, using our notion of

consistency of default theories.

1.3.10 Introduction to structured reasoning in diagrams

Description of the situatio~l

Inheritance diagrams are directed (acyclic) graphs, with two types of arrows,

positive and negative ones, and two types of nodes, class nodes and element

nodes. Most problems can be discussed already with class nodes only. With

this simplification, nodes can be interpreted by sets, positive arrows by "soft"

inclusion, an arrow a --~ b means "most z ~ a are in b," or "normally, a's are b's",

negative arrows are interpreted by "soft" inclusion in the complement: a 74 b

reads "most z E a are not in

bit,

or, "normally, a's are not b's".

Note that the negative arrow is thus a very strong negation of the positive arrow.

A path is a concatenated sequence of arrows, following their orientation. The

intuitive reading immediately shows that negative arrows should be permitted

only at the end of an accepted path. Such paths with at most one negative

arrow (at the end), will be called potential paths. In our diagrams, arrows point

upwards, unless specified otherwise. For instance, in Diagram 1.1, c --~ b --* d

and a --* c 74 d are potential paths.

We consider a net P as information from which to draw conclusions of two kinds:

First, we may say that r permits some ':line of reasoning;', i.e. a "path" of

concatenated arrows of F, like or: a -* c 74 d in Diagram 1.1, second, that F

permits a result, like "most a's are not d's" here, if this is the conclusion of

a permitted line of reasoning. Permitted paths and results will also be called

"valid" or

"accepted"

in F, sometimes written F ~ ~r et*:.

In the absence of any conflicts, all potential paths are considered valid. Given

e.g. the two simple diagrams a --* b --* c and d --* e 74 f, it is permitted to

concatenate the arrows to the valid paths from a to c or from d to f respectively,

with the resulting conclusion that most x E a are in c, and most x E d are not

in f. The problem is to single out the valid paths among the potential paths

CHAPTER 1. INTRODUCTION

Diagram 1.1

b c

In all diagrams, arrows point upwards, unless specified otherwise

by suitable definitions, when there are conflicts, and the conclusions justified by

arguing along valid paths.

Thus, a defeasible inheritance net permits a very limited - in contrast to standard

logics, where there are usually infinitely many ways to prove a resuR - number of

potential lines of reasoning or arguments by concatenating arrows to paths and

drawing conclusions, like a -~ b and b ~ c to a --* b --+ c, which thus stands for

the argument: "Most elements of a are in b, most elements of b are in c, thus -

probably, or defeasibly - most elements of a are in c."

More formally, one tries to identify valid paths in such diagrams, in a - the first

basic distinction - upward or downward chaining process, constructing valid paths

inductively from valid initial segments and arrows, or from valid final segments

and arrows.

Contradiction and preclusion

The basic situations o[ conflicting information are exemplified by the Diagrams

1.1 and 1.2:

In the Diagram 1.1, we can go from a to d via three potential paths a --~ b --~ d,

a --~ c --~ b -~ d, a --~ c -/4 d, where the positive results contradict the negative

one. But, in this case, c is a "soft" subset of b, so the information about d given

by c is considered more specific, and more reliable than the information about d

given by b. Thus, as most z E a are in b and most x E a are in c, both informations

apply to elements of a, but the information given by c is preferred, as the path

1.3. INTRODUCTION TO NONMONOTONIC LOGICS

Diagram 1.2

b c

a -4 c -* b with the arrow c 74 d "precludes" all positive paths from a to d. We

thus resolve the contradiction and conclude that most z E a are not in d.

If the arrow c ~ b is absent, as in Diagram 1.2, we cannot compare, and the

contradiction Can't be resolved.

Extensions versus direct scepticism

In Diagram 1.2, the contradicting arguments a ~ b --~ d and a --~ c 7# d are

of equal strength, so the arguments and thus the conclusions "most a are in

d"/"most a are not in d" are in unresolvable conflict.

There are two ways to proceed: either by "direct scepticism", or by branching

into different extensions (and taking perhaps some intersection in the end). This

is the main distinction between defeasible inheritance formMisms. As a first ap-

proximation, an extension is a suitably chosen maximal consistent subset of the

given information, whereas direct scepticism admits only (preferred) uncontested

information. More precisely: Defeasible inheritance systems may" contain conflict-

ing information. Some such conflicts can be resolved by a criterion in terms of

specificity or preference of one information over the other (by "preclusion", also

called "preemption") while others are unresolvable by such preference. Both the

directly sceptical and the extensions approach will treat the first type of conflict

in the same way, choosing the preferred information. However, they differ on the

second: a directly sceptical approach will come to no conclusion, and admit nei-

ther the positive nor the negative information as valid. The extensions approach

will branch at this point, constructing two different extensions, one where the

positive information is considered as valid, the other where the negative informa-

tion is accepted. The extensions approach can, in a second step, be turned into

28 CHAPTER 1. INTRODUCTION

an (indirectly) sceptical one by considering only the information contained in all

extensions.

Thus, in Diagram 1.2, the "directly sceptical" approach, will not accept any ar-

gument relating a to d, and thus no conclusion linking a and d, the second, the

"credulous" or extensions-based one, will split into two "extensions" or "belief

sets", one where a --+ b ~ d is accepted, the other where a --+ c 7# d is be-

lieved. The "indirectly sceptical" approach will, in a second step, either accept

the arguments which are in all such extensions, or the resulting conclusions,

which are derived by some argument in all extensions (see [MS91] for a discus-

sion). In Diagram 1.1, all approaches will agree in accepting as valid arguments

a --+ c -/4 d (and a ~ c ~ b), as the contradicting one a --+ b --+ d will be

considered weaker, there will be only one extension, and the conclusion "most a

are not in d" will be considered valid in all approaches.

Our main result on inheritance is the proof that the directly sceptical approach is

fundamentally different from the one based on the intersection of extensions. It

impossible to modify the directly sceptical approach, e.g. by introducing new

path values, so that it will give the same results as the intersection of extensions

unless one cheats.

Common features of all approaches to

defeasible inheritance

There is a multitude of approaches to reasoning in such diagrams, but they have

some common features: 1) No ex falso quodlibet, contradictions should be kept

local. This is illustrated by the following example: In Diagram 1.3, we have added

a separate point e to Diagram 1.2:

Any logic, which sees a contradiction in Diagram 1.2, and admits the rule EFQ

(ex falso quodlibet), would conclude e.g. that "most a's are e's". As reasoning

in diagrams proceeds by potential paths, and there is no path from a to e, this is

impossible here.

2) More specific inibrmation should win in case of conflict.

3) Lacking differences in specificity (':unbiased conflict"), contradictions should

be handled fairly.

In addition, to get started, we shall assume that all arrows in P are accepted

paths in P of length 1.

The central effects of the arrows are thus: - they limit the number of admissible

expressions - they limit the number of admissible argumentations: the paths are

the admissible argumentations. It is essentially this property which makes the

systems tractable.

The problem of a semantics

Inheritance diagrams seem to be simple, but they are not. As a matter of fact,

there are a lot of subtle distinctions between different approaches to identify the

valid paths. Lacking a convincing semantics, i.e. one which is not constructed

in hindsight, one can find arguments in favour and against each approach. In

1.3. INTRODUCTION TO :\IONMONOTONIC LOGICS 29

Diagram 1.3

b c

hindsight, one has perhaps concentrated too much on the inherent problems, and

not enough on their use.

We first give in Section 6.1 a detailed introduction into the subject, discuss several

approaches and their differences. We give a semantics using systems of weak

filters as for open normal defaults in Section 6.1.6. But, our semantics is given

in hindsight, and does not permit to single out one formalism as adequate.

One of the differences between inheritance diagrams and logic is that the language

of the former is very poor. This is one of the reason why it is so difficult to express

them in other formalisms, without introducing new, unwanted conclusions.

The author has meanwhile come to the conclusion that one should perhaps not

try to give inheritance diagrams a semantics. Instead, they should be taken as

primitive, with some arbitrary fixed approach to find the valid paths, and used to

combine local theories, valid for each node, by inheritance and some mechanism

of theory revision. But this is the subject of still ongoing research.

The book "Probabilistic reasoning in intelligent systems" by Pearl

In Section 6.2, we give an introduction to this very interesting book by &Pearl

[Pea88]. Unfortunately, the contents of this book is hidden behind some formal

negligences, we take an effort to explain Pearl's ideas in detail, in, we hope,

correct fbrm.

The kind of reasoning Pearl considers is quite close to the one done in inheritance

diagrams. Influences of variables, like illness, fever, are represented by arcs in

CHAPTER i. fNTRODUCTION

diagrams, and reasoning proceeds along these arcs. Pearl's interest is centered on

the question which variables influence which, or, in other words, which are irrel-

evant, and thus to resolve the information contained in a diagram by considering

smaller subdigrams.

So, in a totally different context, we find again the problem of irrelevance.

Argumentation and inheritance

We conclude by arguing that it is not the limited language of inheritance systems

which, makes them suitable for fast computation, but the limited ways conclu-

sions may be reached. We see the essential aspect of inheritance systems in the

inherently limited proof structure (':proof" in a way to be modified later on), and

not the 'simple' C - or C-relation.

First, the positive part of our argument. Roughly speaking the set of all potential

proofs is the set of all paths in the inheritance system. Even if we take preemption

into account, the number of possible proofs and disproofs stays very limited as

compared to usual logics. It is this liImtation which makes inheritance systems

tractable.

On the other hand - and this is the negative part of our argument - we can make

e.g. t, he subset-relation as complicated as we wish, consider e.g. {x C X: qS(z)}

where ~5 can be

anything,

undecidable etc. But, here we leave the structure of

the inheritance systems itself, and do not confine ourselves to the manipulation

of arrows, paths etc.

Inheritance systems can be seen in the more general context of argument systems:

Proofs and argumentations have in common:

1. Both are closed, finite systems, and all conclusions are drawn essentially

without leaving the system, 2. both are structured.

Differences between proofs/argumentations:

1. Argumentations are nonmonotonic in principle. (In hindsight, one may con-

sider our approach as following T~omason's criticism that usual nonmonotonic

logics are not radical enough.) 2. One proof is as good as any other, and two

proofs are not better than one. But, confirming one argument by another, may

modify the situation. 3. Arguments have weights: They are strong, far-fetched,

independent from each other. These are natural properties of arguments, and,

with exception of the last property, not of proofs. 4. Argumentations can be

considered naturally as a game of several participants. 5. The sequence of steps

is more important in argumentations than in proofs: giving p after q means im-

plicitely (in a good argumentation) to consider the point p, and still to uphold

The notions "preemption", "more specific informgtion" etc. of the theory of in-

heritance describe characteristic properties of argumentations (non-monotonicity,

importance of sequence). Thus, we see inheritance systems as structured sets of

arguments, which describe in a natural way (essentially concatenation) a fixed,

limited set of (chains of) argumentations. The results of an inheritance system

are the choices of one or several chains of arguments (or their results, i.e. con-

1.3. INTRODUCTION TO NONMONOTONIC LOGICS

necting start and end of such a chain by the appropriate arrow) from the set

of possibly conflicting argumentations. Tractability (or lack of) results from the

definition of the choice-operation (via preemption etc.).

We may also refer the interested reader to Nelson Goodman's discussion of the

"true emerald paradox" and his attempted solution [Goo55]. He will find many

ideas of the approaches to defensible inheritance in Goodman's considerations

about projectibility of a predicate.

1.3.11 The problem of irrelevant information

We discuss this problem largely within our interpretation of defaults by general-

ized quantifiers, in order to have a precise and semantically meaningful formalism

at our disposal.

We describe the problem of irrelevant information and show that "traditional"

nonmonotonic logics have difficulties with its treatment: Grosso modo, they iden-

tify irrelevance with logical consistency. We argue that these problems become

even more acute when we do not only reason with defaults, but also about de-

faults.

The fact that most things in the world are essentially independent of each other

is vital for our survival. Consequently, the concept of independence or irrelevance

plays a crucial role in our reasoning.

To be more precise, we are interested in the following question: Suppose we feel

entitled to conclude ~p from r ~ !,-~ % and learn that v~ also holds. Can we

still conclude ~b? Thus, irrelevance is a 3-place relation < ~, qS, t~ >, defined

e.g. by ~b I~ ~p =a q~ A ~9 I" g~. (Of course, one may also define stronger forms

of irrelevance e.g. by ~b IN ~p =~ ~b A v~ IN ~p and 4; A -~v~ ].-~ ~p or ~b I" ~b r

~bA v~ I~ ~b.) In probability theory, irrelevance or independence is defined by

P(x ]

~) = P(z [ y, z).

In mathematical logic, ~b is said to be independent of an axiom

system A, iff Con(A) implies

Con(A,

r and

Con(A,-~r

where "Con" stands

for consistency. We also meet the same concept in inductive reasoning under the

label of homogeneity, and we shall use the words irrelevance, independence, and

homogeneity indiscriminately.

In nonmonotonic reasoning, considerations of independence play a doubly impor-

tant role:

First - in an argument due to J.Pearl - whereas monotonic logic is still local in the

sense that once a proof has been found, it stays valid irrespective of the rest of the

database, nonmonotonic logic is badly non-local: Usually, we may be able still to

find a stronger counterargument, so, in most cases, we have to search the whole

database. Thus, the need to find restrictions on the relevant information is even

more urgent than in the case of monotonic logic. But irrelevance or independence

is precisely such a restriction.

Second, it seems very questionable whether consistency is always the right notion

to determine applicability of defaults - see the discussion below.

There are two extreme ways of reacting to the problem: The first assumes that

everything is relevant, the second, that everything is irrelevant - each unless ex-

CHAPTER 1. INTRODUCTION

plicitely said otherwise. The first direction is taken by probability theory. Irrele-

vant information is to be made explicit, otherwise "one cannot move" (&Pearl).

(The present author polemically conjectures that the problem of irrelevance has

been seen long ago in probability theory, because it has a clear semantics, which

some nonmonotonic logics did and do not have.) The same approach is taken

in the author's interpretation of (open normal) defaults as generalized quanti-

tiers, see Chapter 3. (Adding appropriate axiom schemata can, however, turn the

theory also into the second direction.) This opposite direction is taken e.g. in

"rational (preferential) logic" (see [LM92]), where is answer is given by the axiom

[ ~" 7 -+ (c~ h/7 I~-, 7 or c~ [~ -~t3) - i.e. if ~ is not irrelevant, then we must be

able to conclude -,/3 from a.

A systematic investigation of independence is found in [Pea88] and presented in

section 6.3.

But let us first turn to the problem itself. We may describe it in the context of

NMR as

A problem of language and homogeneity

Consider the world of birds, and the default rule that birds normally fly, which

we shall abbreviate by

Vxfly(x).

This is thus to be read vaguely as "almost all z

(in the domain) fly" or "the important z fly" or the like. Suppose we know that

penguins, emus and ostriches don't fly, albatrosses do, and we have the axiom

Vx[targebird(x)

~-, penguin(x) v emn(x) v ostrich(x) V albatros(x)]. Suppose

we are told of some particular bird Tweety largebird(Tweety). Will we conclude

that Tweety flies? Formally - i.e. in the sense of Reiter's Default Theory, see

[Rei80] - yes, as it is consistent, since Tweety may be an albatros. Intuitively, no,

because the non-flyers are a majority among the largebirds. So, normally, birds

fly, but it is not the case that large birds normally fly, maybe even large birds

normally don't fly. Contrast this with the colour of birds: We (as ornithological

laymen) tend to believe that the colour of birds' feathers has nothing to do with

their flying capabiIities. So, if we know that Tweety is white-feathered, we will

still intuitively believe that it flies. Suppose I tel1 you now that Tweety is white-

feathered, lays spreckeled eggs of light blue and white co[our, lives in Africa, has

a long red beak, black feet, and a blue tail. What do you suspect, will Tweety

fly? You might feel uncertain now, as the description is so narrow as to fit maybe

only one species - which does not fly. The story looks like a trap (if you don't

believe so, would you take a bet?).

Another, more formal, and more drastic example. Suppose we know fly(a),

and someone tells us Tweety=a V

-,fly(Tweety).

It is consistent to assume

Tweety=a, thus that it flies, so we assume it and conclude that Tweety flies (and

maybe that Tweety=a!).

Analysis of the problem

Formal reasoning with the default

Vxfly(z)

presupposes that logically consistent

definable subsets are "probabilistically consistent" too. I.e., if things normally fly

1.3. INTRODUCTION TO NONMONOTONIC LOGICS

in the universe of birds, so do :he elements of all subsets which are definable by

some predicate, and which might consistently contain some flyer. If the language

is empty, then there is no problem, but the richer the language (see the African

bird above), the more there might be counterintuitive results, unless we somehow

stop the applicability of the default

VxfIy(x).

In other words, the conventional

formal use of the default

Vxfly(x)

presupposes that every definable subset {x :

r of the universe which is consistent with the flyer subset {x:

fly(x)}

behaves

just as the universe itself, we say that it is normality-homogenous for

fly(x),

which we abbreviate by

h~(fIy(x),

r We may also say, to take up the above

vocabulary, that r is an irrelevant property for

Vxfly(x).

(Analogously, we might

define logical homogeneity, ht(r ~), by Jxr --~

3x(r

A ~p)(z), and probabil~stic

homogeneity, hp(r ~b), by {x: r A ~(x)} r (~ --* ,([~',~i"({~:r = "({~:r162 (where

# is the probability measure).) As the African bird example shows, it might

well be possible that

hn(fly(x),

r for i < n, but a boolean combination (e.g.

conjunction) of the r need not be normality-homogenous for

fly(x).

To summarize: 1) We cannot suppose that

Vxfly(x)

is homogeneous with re-

spect to every predicate r as the large-bird(x) example shows. 2) It might be

that

h~(fly(x), r

and

h~(fIy(x),-~r

3) It might be that

h,~(fIy(x),

but not

h~(fIy(x),-,r

4) Is it possible that neither

h~(fIy(x),r

nor

h~(fIy(x),-~r

This depends on the properties of "normal" subsets, and

will be discussed below in Chapter V. 5) It might be that

h~(fly(x),

r and

h,(fly(x),r

but not

h,~(fIy(x),r

r - and vice versa, i.e. that

h~(fly(x),

r A ~b(x)) but neither

h~(fIy(x),

r nor

h~(fly(x), r

In conclusion, we might say that every normal default without prerequisites

Vxb(x)

carries with it a homogeneous properties set

H~(d)

= {r i E I}, where

the r are formulae such that

h,~(d,

r An intuitively correct use of the

default

Vxfly(x)

in the birds world can only be done when all the information

we have about a particular bird Tweety is contained in

H,~(Vxfly(x)).

Reasoning with defaults:

iterability

Suppose we have the default theory Vxr Vx~p(x), and conclude r A r

by default. Thus, we conclude not only that normally r and, normally, r

but,

in addition, normally r and r In other words, the set {x: r162

has to be large in the universe, i.e. the intersection of the large subsets {z : r

and {x : r is itself large. We call this iterability of defaults.

It is easy to think of many cases where each of the sets {x : r is large in

the universe, and N{{z : r : i E I} is not empty (thus it will escape logical

inconsistency), but small in the universe, thus iterability does not hold.

The reader is invited to consider the Lottery Paradox in the light of the above

remarks.

Our base axiom system for V permits e.g. neither Vxr A Vx~p(x) ~ Vx~ A

r nor Vxr --* Vx~r(x) : r but, of course, they can be added if so

desired.

The discussion on iterability and homogeneity in the case of defaults with pre-