Coherent Systems (eBook)

Karl Schlechta (Autor)

eBook Download: PDF

2004 | 1. Auflage
468 Seiten
Elsevier Science (Verlag)
978-0-08-050219-9 (ISBN)

Infos

One aspect of common sense reasoning is reasoning about normal cases, e.g. a physician will first try to interpret symptoms by a common disease, and will take more exotic possibilities only later into account. Such normality can be encoded, e.g. by
a relation, where case A is considered more normal than case B. This gives a standard semantics or interpretation to nonmonotonic reasoning (a branch of common sense reasoning), or, more formally, to nonmonotonic logics. We consider in this book the repercussions such normality relations and similar
constructions have on the resulting nonmonotonic logics, i.e. which types of logic are adequate for which kind of relation, etc.

We show in this book that some semantics correspond nicely to some logics, but also that other semantics do not correspond to any logics of the usual form.

Key features:

? provides a coherent picture of several formalisms of nonmonotonic logics.
? gives completeness and incompleteness results for many variants of preferential, distance based, and other semantics.
? gives probably the first systematic investigation of definability preservation and its consequences.
? gives new proof techniques for completeness results.
? is centered on semantics

---

One aspect of common sense reasoning is reasoning about normal cases, e.g. a physician will first try to interpret symptoms by a common disease, and will take more exotic possibilities only later into account. Such "e;normality"e; can be encoded, e.g. by a relation, where case A is considered more normal than case B. This gives a standard semantics or interpretation to nonmonotonic reasoning (a branch of common sense reasoning), or, more formally, to nonmonotonic logics. We consider in this book the repercussions such normality relations and similar constructions have on the resulting nonmonotonic logics, i.e. which types of logic are adequate for which kind of relation, etc. We show in this book that some semantics correspond nicely to some logics, but also that other semantics do not correspond to any logics of the usual form. - Provides a coherent picture of several formalisms of nonmonotonic logics- Gives completeness and incompleteness results for many variants of preferential, distance based, and other semantics- Gives probably the first systematic investigation of definability preservation and its consequences- Gives new proof techniques for completeness results- Is centered on semantics

Inhalt

Cover 1
Contents 10
Foreword 6
Summary 16
Acknowledgements 20
Chapter 1. Introduction 22
1.1 The main topics of the book 22
1.2 Historical remarks 33
1.3Organization of the book 36
1.4Overview of the chapters 36
1.5Specific remarks on propositional logic 45
1.6Basic definitions 47
Chapter 2. Concepts 58
2.1Introduction 58
2.2Reasoning types 60
2.3Basic semantical concepts 91
2.4Coherence 113
Chapter 3. Preferences 122
3.1Introduction 122
3.2General preferential structures 132
3.3Smooth minimal preferential structures 146
3.4 The logical characterization of general and smooth Preferential Models 159
3.5 A counterexample to the KLM-system 167
3.6A nonsmooth model of cumulativity 172
3.7Plausibility logic 178
3.8The role of copies in preferential structures 195
3.9A new approach to preferential structures 197
3.10Ranked preferential structures 212
Chapter 4. Distances 244
4.1 Introduction 244
4.2Revision by distance 253
4.3 Local and global metrics for the semantics of counterfactuals 282
Chapter 5. Definability Preservation 292
5.1Introduction 292
5.2Preferential structures 305
5.3Revision 333
Chapter 6. Sums 340
6.1 Introduction 340
6.2The Farkas algorithm 348
6.3Representation for update by minimal sums 350
6.4 Comments on "Belief revision with unreliable observations" 370
6.5 "Between" and "Behind" 382
Chapter 7. Size 388
7.1Introduction 388
7.2Generalized quantifiers 393
7.3 Comparison of three abstract coherent systems based on size 400
7.4 Theory revision based on model size 417
Chapter 8. Integration 432
8.1Introduction 432
8.2Reasoning types and concepts 437
8.3Formal aspects 443
Chapter 9. Conclusion and Outlook 454
Bibliography 456
Index 461

Textauszug

Chapter 2

Concepts

Karl Schelechta    Université de Provence and Laboratoire d’Informatique Fondamentale (CNRS UMR 6166) Marseille, France

2.1 Introduction

In this chapter, we will first consider a list of different types of commonsense reasoning. We will discuss them, and base them loosely on what we consider basic semantical concepts, like distance, size, etc.

We think that these concepts are present in human thinking, in some form or the other. But we are also prepared to modify and generalize them, as it suits our purposes. Thus, what we call a distance will not necessarily be the same concept as the distance from Bachenpfuhl to Eberswutz, or from Marseille to Pernes-les-Fontaines. We still feel that our notions of distance have sufficient in common with usual distance to merit their name. Our approach is then a bootstrap procedure. We begin with a vague and naive concept, and generalize or refine it as it seems necessary. We are not only guided by the application to logic — e.g. the syntactic property of cumulativity leads naturally to the semantic notion of a smooth relation — but also by abstract considerations like generalization, etc.

We do not pretend to have given all possible or reasonable interpretations of common-sense reasoning types in an exhaustive study, and are conscious of the essay character of these pages. In a way, it is a stroll through a lush rain forest of logics and problems, with a lineean project in the back of our mind.

A moment’s reflection will often show that there are many alternative interpretations of our notions possible. For instance, when we consider the notion of center, and base it on distance, we can define “center” by the distance to other elements of the set considered, or to those outside the set — see Section 2.2.1.1. It seems impossible to exhaust all possibilities, so we often just indicate alternatives, to give the reader some suggestions what one can do. What should be done depends on the concrete case at hand, and cannot be decided beforehand. We strongly insist here that this multitude of possibilities is not due to an incapacity of the author to decide one way or the other, but is imposed by the possibilities of reasoning and determined by the adequacy to the problem. The multitude of approaches comes from the multitude of situations one might wish to treat. The systematisation is in the fact that we often find the same basic notions, but not in the way they are used or composed. Yet, finding over and over the same basic concepts is already very useful for a systematic and formal treatment of several cases. So, the reader should not feel confused by the multitude of possibilities, but rather see the basic concepts behind, and, use whatever seems adequate to him for his problem. We will pursue some approaches in great detail, others not as far, or not at all, but hope that the reader will find in the techniques explained in detail also ideas how to treat the other approaches in more detail. So, this part of the book can be read on different levels. Either as an introduction to what could be done, and how we can analyse some types of common-sense reasoning, or, as headlines whose chapters have been written to various depths, and incitations to the (advanced) reader to fill in the missing details for the other chapters.

We then describe the basic concepts we saw in more detail in Section 2.3, in particular, we show some natural transformations from one to the other. E. g., we will discuss how a size (with addition) for elements can be transformed in a natural way to a ranking of sets. We will re-emphasize the ubiquity of our basic semantical notions of human reasoning by describing the situation we saw in the first part from above, now as seen from those basic concepts. The fact that there are some (also formal) connections between the notions should not obscure the fact that basic intuitions seem to diverge sometimes.

We then turn to another basic concept in reasoning, coherence. Abstractly, this is the “transfer” of conclusions from situation T to situation T′. For instance, in classical, monotonic, logic, we have that T ├ ϕ implies T′ ├ ϕ, if T ⊆ T′. Such transfer operations allow us to do relevant thinking, we can transfer conclusions from one situation to another one, and need not start anew every time. Such transfer is also possible in nonmonotonic logic, e.g. when the logic is cumulative. We describe now the situations we have already seen from the perspective of coherence. For instance, we look at the coherence conditions imposed by a preference relation on the models. We will mostly investigate here the algebraic side of the picture, e.g. the properties imposed on the model choice functions by a preference relation, or a distance.

This perspective gives us a unifying view, but we do not go as far as to formulate a theory of possible or reasonable coherence properties. (We would probably enter there the domain of analogical reasoning in more detail than we wish to do. For instance, it might be a reasonable assumption that, if we transfer ϕ from T to T′, and T″ is between T and T′ (by some measure), then we should also be able to transfer ϕ from T to T″.) Moreover, as coherence is (usually more than) half of the logic, in particular, coherence properties are often the key to representation results, this perspective gives us a good starting point for the more technical Chapters 3–7 to come.

It is somewhat difficult to begin our analysis. We will see that most notions we look at reveal themselves as interdependent, so it is somewhat arbitrary where we enter the mesh-work. Nonmonotonic reasoning can sometimes be seen as choosing the “best” elements (and reasoning with them), certainty is sometimes based on the same choice, counterfactuals (in the Lewis/Stalnaker interpretation) work with closest (or best, seen from our point of view) elements, likewise theory revision (in a slightly modified approach), etc. We will just begin somewhere.

We conclude with a remark on terminology: D. Makinson, in [Mak03] has made the difference between completeness and representation results, we just merrily use both in naive terminology, and go even farther: we sometime also speak about characterization. But in all cases, it will be clear what we mean (at least we hope so).

2.2 Reasoning types

Common to all formalisms we consider is that they (usually) work with model sets other than those of classical logic. Instead of considering M(T), the set of classical models of T, we work with some other set of models, say M′. Nonmonotonic logics consider normal cases, leave exceptions aside, theory revision considers only closest cases, as do counterfactual conditionals, certainty looks how well one formula is embedded in another, etc. Often, we “forget” in a controlled way some models, or, we “forget” the exact limits of the model set, and look how far we can go without running into disaster.

2.2.1 Traditional nonmonotonic logics

Being nonmonotonic is a property, not a name for a unique logic. In all likelihood, the following “logic” is nonmotonic: ϕ  ψ iff the last two digits of the Gödel numbers of ϕ and ψ are the same. Any formal, abstract approach to reasoning with information of differing quality will be nonmonotonic: better information can override weaker information.

But traditionally, the term nonmonotonic is used for logics stronger than classical logic in the sense of (SC) — see Definition 1.6.5. This is due to the motivation behind their introduction: to create a logic able to conjecture beyond certain knowledge (formalized by classical logic). Nonmonotonic logics, NML for short, were designed to formalize aspects of reasoning about the “normal”, “interesting”, “important”, “useful” cases, the “majority”, or the like. This is underspecified as it corresponds to somewhat different intuitions, and is one of the reasons why there is a multitude of NML’s: after all, if they are adequate, they have to code the intuition somehow into the formalism, so different intuitions will usually generate different formalisms. Note that such logics about normality, etc. will also be naturally nonmonotonic, as any fact, e.g. about the normal case need not be plausible any more once we add the information that the case at hand is not normal.

We now discuss some of these intuitions or interpretations.

We follow the tradition of being stronger than classical logic, so all nonmonotonic logics are represented by a model choice function f s.t. f(X) ⊆ X, property (μ ⊆) in Definition 1.6.5.

Here are some reasonable interpretations of a nonmonotonic consequence relation α  β:

(1) in the normal, important or interesting α–cases, β holds,...

Produkt-Details

• Erscheint lt. Verlag: 21.9.2004
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• ISBN-10: 0-08-050219-9 / 0080502199
• ISBN-13: 978-0-08-050219-9 / 9780080502199