Schlechta K. Nonmonotonic Logics: Basic Concepts, Results, and Techniques
Подождите немного. Документ загружается.
Lecture Notes in Artificial Intelligence
Subseries of Lecture Notes in Computer Science
Edited by J. G. Carbonell and J. Siekmann
Lecture Notes in Computer Science
Edited by G. Goos, J. Hartmanis and J. van Leeuwen
1187
Karl Schlechta
Nonmonotonic Logics
Basic Concepts, Results,
and Techniques
Springer
Series Editors
Jaime G. Carbonell, Carnegie Mellon University, Pittsburgh, PA, USA
J6rg Siekmann, Universit~it des Saarlandes, Saarbrticken, Germany
Author
Karl Schlechta
CMI, 39 Rue Joliot-Curie
F-13453 Marseille Cedex 13, France
E-mail: ks @ gyptis.univ-mrs.fr
Cataloging-in-Publication Data applied for
Die Deutsche Bibliothek - CIP-Einheitsaufnahrne
Schlechta, Karl:
Nonmonotonic logics : basic concepts, results, and techniques
/ Karl Schlechta. - Berlin ; Heidelberg ; New York ; Barcelona
; Budapest ; Hong Kong ; London ; Milan ; Paris ; Santa Clara
; Singapore ; Tokyo 9 Springer, 1997
(Lecture notes in computer science ; 1187 : Lecture notes in artificial
intelligence)
ISBN 3-540-62482-1
NE: GT
CR Subject Classification (1991): 1.2.3, F.4.1, 1.2
ISBN 3-540-62482-1 Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from SpringeFVerlag. Violations are
liable for prosecution under the German Copyright Law
9 Springer-Verlag Berlin Heidelbelg 1997
Printed in Germany
Typesetting: Camera ready by author
SPIN 10549941 06/3142 - 5 4 3 2 1 0 Printed on acid-free paper
Preface
Nonmonotonic logics were created as an abstraction of some types of common
sense reasoning. They have the surprising property - for logicians trained on
classical logic - of being nonmonotonic in the following sense: increasing the
axiom set will not necessarily result in an increase in the set of formulas deducible
from these axioms. Such situations arise naturally, e.g., in the use of information
of different degrees of reliability. We might draw a tentative conclusion based
on some information, but will withdraw the conclusion in the light of new, more
reliable, and contradictory information. Nonmonotonic logics were created to
treat such reasoning in abstract terms, but without going into the details of
reliability, as necessary, for instance, for statistical reasoning.
The field has evolved quite rapidly from the more or less descriptive leveI to
serious investigation, and it is now common to have formal semantics and proof
systems, linked by soundness and completeness theorems. This book is intended
to give the reader a flavour of the ideas and techniques to be found in these logical
investigations.
Part of this work was carried out while the author was at the LILOG project
of IBM Germany, Stuttgart. IBM provided its financial support for our work
and a generous framework, which enabled fundamental research on fascinating
problems originating from applications. I would like to thank O. Herzog (now at
the University of Bremen) and C. Rollinger (now at the University of Osnabrfick),
who at that time directed the project, and C. Habel (University of Hamburg) for
his support, and for pointing out to me the existence of nonmonotonic logic. Sven
Lorenz took the burden of implementation from the author.
David Makinson, Paris, cooperated with many comments, encouragements, open
problems, and his contagious enthusiasm. Yuri Gurevich, Ann Arbor, helped to
clear several topics of this introduction in long discussions. Hans Rott, Konstanz,
corrected a mistake in an original version of Chapter 5. Finally, many persons'
papers and many referees' comments improved substance and presentation. JSrg
Siekmann, Saarbriicken, helped with constructive criticism to approximate this
text to the form of a book.
Parts of this book have already appeared elsewhere. Sections 2.1.4-2.1.5 have
appeared in [Sch92], Section 2.2 in [SM94], Section 2.3 in [Sch91-2], Chapter 3 in
[Sch95-1], Chapter 4 in [Sch95-2], Chapter 5 in [Sch91-1] and [Sch91-3], Section
6.1.5 in [Sch93], Section 6.1.6 in [Schg0].
October 1996 Karl Schlechta
Contents
Introduction 1
1.1 Preliminaries ............................. 1
.2 Our philosophical position ...................... 2
1.2.1 Logic as a tool ........................ 2
1.2.2 Basic semantical notions ................... 4
1.2.3 Abstract semantics ...................... G
1.2.4 Restricted monotony and irrelevance ............ 6
1.2.5 Logic and structural information .............. 7
1.2.6 Summary and program .................... 8
1.3 Introduction to nonmonotonic logics and its problems ....... 8
1.3.1 History and an example ................... 8
1.3.2 Some basic differences .................... 9
1.3.3 A (simplified) introduction to Reiter's theory of defaults 10
1.3.4 Static and dynamic aspects of defaults ........... 10
1.3.5 Introduction to preferential structures ............ 12
1.3.6 Introduction to defaults as generalized quantifiers ..... 18
1.3.7 A two-stage approach ..................... 21
1.3.8 Introduction to logic and analysis .............. 22
1.3.9 Introduction to theory revision ............... 23
1.3.10 Introduction to structured reasoning in diagrams ..... 25
1.3.11 The problem of irrelevant information ............ 31
1.4 Basic definitions and notation .................... 36
1.4.1 Notation ............................ 36
1.4.2 Set theory ........................... 36
1.4.3 Topology ............................ 3"/
1.4.4 Theory of measure and integration ............. 38
1.4.5 Logic .............................. 39
Preferential structures and related logics 43
2.1 Preferential structures ........................ 43
2.1.1 Introduction and basic differences .............. 43
2.1.2 Orderings on s and completeness results .......... 46
2.1.3 Defaults and preferential models ............... 60
2.1.4 Supraclassicality + cumulativity + distributivity
does not entail classical representability ........... 74
viii
CONTENTS
4
2.1.5 A representation theorem for preferential models ...... 75
2.1.6 General smoothness ...................... 78
2.1.7 Limit preferential models ................... 84
2.2 Local and global metrics for the semantics
of counterfactual conditionals .................... 90
2.2.1 Introduction .......................... 90
2.2.2 Basic definitions ........................ 94
2.2.3 Results ............................. 94
2.2.4 Outline of the construction for theorem 2.120 ....... 96
2.2.5 Detailed proof of theorem 2.120 ............... 97
2.3 Extension by finite approximation from below ........... 99
2.3.1
2.3.2
2.3.3
2.3.4
2.3.5
2.3.6
Introduction .......................... 99
Cautious monotony does not extend ............. 100
Weak distributivity entails partial distributivity ...... 101
On different infinite extensions of I ............. 102
Extension by unbounded subsets .............. 103
A final example ........................ 104
Defaults
3.1
3.2
3.3
as generalized quantifiers 105
Introduction .............................. 105
Defaults as generalized quantifiers .................. 108
3.2.1 Semantics and proof theory ................. 109
3.2.2 Strengthening the axioms .................. 116
Sceptical revision of partially ordered defaults ........... 118
3.3.1 Introduction .......................... 119
3.3.2 Basic definitions and approaches ............... 119
Logic and analysis 125
4.1 Overview, motivation, and basic definitions ............. 125
4.1.1 Overview ........................... 125
4.1.2 Motivation to consider continuous logics
and the intuition behind our definition of the topology . . t26
4.1.3 Further applications of topology and of our construction
in logics ............................ 129
4.1.4 Average difference between two logics ............ 130
4.1.5 More applications of the distance between theories ..... 131
4.1.6 Relation between the motivational and the technical part . 133
4.2 Technical development ........................ 133
4.2.1 Outline of the technical part ................. 133
4.2.2 The topological construction ................. 135
4.2.3 A measure on
The,
integration of the difference
between two logics ...................... 143
4.2.4 A toy application ....................... 144
CONTENTS ix
Theory revision and probability 147
5.1 Introduction .............................. 147
,5.2 Epistemic preference relations .................... 151
5.3 Measuring theories, and an outlook for a different treatment of
theory revision ............................
155
Structured reasoning 159
6.1 Inheritance diagrams ......................... 159
6.1.1 Introduction .......................... 159
6.1.2 A detailed survey of inheritance
theory a la Thomason (et al.) ................ 160
6.1.3 Review of other approaches and problems ......... t78
6,1.4 A parallel definition for the sceptical and extension-based
approach ............................ 194
6.1.5 Directly sceptical inheritance cannot capture
the intersection of extensions ................ 198
6.1.6 A semantics for defeasible inheritance ............ 210
6.2 Networks of inference - J. Pearl's book ............... 214
6.2.1 Introduction .......................... 214
6.2.2 Independence relations .................... 217
6.2.3 Distributed computing in DAGs ............... 224
Bibliography 233
Chapter 1
Introduction
1.1 Preliminaries
This text can be read from two different points of view. First, it tries to emphasize
connections between different formalisms, and uncover general concepts. Second,
it gives detailed techniques and results.
The formal part of the text is self contained, but assumes a certain mathematical
maturity of the reader. It is not a text written for beginners in logic.
Wherever we go into detail, all definitions will be given. Some parts of this book
have already appeared as articles in journals or conference proceedings. In those
parts, some straightforward proofs will be omitted or given in outline only.
Proofs by other authors will usually not be given, we will, however, sometimes
take the liberty of presenting such proofs in overview, to highlight points, and
make comparisons.
There are two notable exceptions to the above:
In Section 6.1, we give an extended and leisurely introduction to defeasible in-
heritance theory 5~ la Thomason et aI. [HTT87] and continue at a much faster
pace with an overview of (some) other approaches to defeasible inheritance. A
thorough examination of the Thomason approach will, however, enable the reader
to understand the main ideas in the field. The second exception is a presentation
of several chapters of Pearl's book [Pea88]. This is not only done to point out
this very important work, rich in ideas, but also to help a more formally oriented
reader with the study of this somewhat "unscholarly" text.
The reader will notice the absence in the discussion of logic programming, au-
toepistemic and modal logic and deeper proof-theoretic examinations: The rea-
sons lie largely in inclination and education of the author, and are mostly coinci-
dental. The author has largely limited the discussion to areas where he has done
research himself. Moreover, the classical approaches like circumscription, default
reasoning, truth maintenance systems will only so far be presented here as to
make the discussion of problems, extensions and solutions plausible and under-
standable. For a general overview, the reader is referred to e.g. [Bre87], [Bre91b],
[Bes89], [Som891, [MT93] for a detailed discussion, to [Rei87] t'ol- a more abstract
view. Collections of papers can be found e.g. in [Gin87], [RKGS89]. An excellent
2 CHAPTER I. INTRODUCTION
overview of research done in logic programming - apart from the classical book
[Llo87] - is to be found in [DHS90].
1.2 Our philosophical position
1.2.1 Logic as a tool
Classical logic, be it propositional logic or first-order logic (FOL), can be seen as
a method of ideal reasoning about mathematical objects. Logic is thus a tool, as
a language is a tool, a language is used to speak about a domain, and a logic is
used to draw (failsafe) conclusions about the domain.
In this view, the domain has priority, and language and logic come second,
The domain is, in general, an extra-mathematical entity, we want to speak and
reason e.g. about possible developments, legal and moral obligations, choices,
properties some objects normally have, etc. Formal semantics (e.g. Kripke struc-
tures) are an abstraction of the concrete domain into a mathematical object. The
formal language is chosen to represent relevant aspects of the semantics, and the
logic is chosen to correspond to failsafe reasoning about the domain. This corre-
spondence is assured by soundness and completeness of the logic with respect to
the formal semantics. Soundness assures that we do not conclude anything which
is not sound for our semantics, i.e. does not hold in all structures, completeness
assures that we can conclude anything which holds in all structures.
The question whether the formal semantics captures well the intended domain,
is a philosophical question. The formal semantics as well as the logic and lan-
guage are mathematical objects. Soundness and completeness are mathematical
theorems about correspondence of mathematical objects.
It seems much more difficult to take the big step directly from a domain we want
to speak and reason about to a language and logic. Historically, this approach
has often led to logical systems which were found out - after considerable work
had been invested into them - inconsistent, trivial, or inadequate.
The problem seems to be that this big step tries to do two quite different things
at a time: First, a philosophical step, which is the abstraction from a domain,
and a mathematical step, which is the construction of an adequate logic. The
philosophical question of adequacy of the abstraction of the domain to a formal
semantics seems to be much easier to discuss separately from the mathematical
question of adequacy of the logic to the formal semantics.
The intuitive semantics of nonmonotonic logics
Classical logic was tailored as ideal reasoning about mathematical objects (from
a platonist point of view). Nonmonotonic logics are made to fit the, or some,
objects of common sense reasoning.
But, first, what are nonmonotonic logics? In classical logic, if a formula r is a
logical consequence of a set of formulas T, in symbols T ~- r and if Tr is another
set of formulas with T C TI, then TI ~- r too. Thus, the set of consequences
1.2. OUR PHILOSOPHICAL POSITION 3
increases monotonically with the set of prerequisites. This is not the case with
nonmonotonic logics. There we have some T C_ T4 some 4 with T l~ ~, but
TI]7~ 4, where ]~ is the consequence operation of this nonmonotonic logics. At
first sight, this seems strange.
But, if T and Tt contain information of different value or reliability, it may very
well be that we accept 4; as reasonable on the basis of T, but a new formula in
Tt, added to T, might contradict the grounds which led us to accept 4;. If the new
formula is considered more reliable than the old reason to believe q~, we will not
necessarily accept q5 any more as reasonable.
Likewise, if we reason about the usual, typical or normal cases, it might very well
be that the normal cases in which T holds, satisfy 4;, too. But, the normal cases
in which Tt holds, need not satisfy ~ anymore, even if Tt includes T. This is the
case if "normality" is chosen relative to the theory, as then a T-abnormal case
can become Tt-normal. As a matter of fact, the perhaps best examined semantics
for nonmonotonic logics (preferential semantics) is based exactly on such a choice
of normal cases.
To summarize, classical logic fits mathematical objects, where - on a first level
- there is no distinction in importance of the objects. For example, even a very
bizarre counterexample is a valid counterexample. Nonmonotonic logics, on the
other hand, fit more the objects of common sense reasoning, where some cases -
and some information - are more important than others.
Logic versus reasoning systems
This book discusses logic, not reasoning systems. A logic is a tool for failsafe,
ideal reasoning about a domain, and efficiency is not an issue. We want to be
able - in principle - to prove everything which is true, and nothing, which is not
true. Logic is a fundamentally idealistic enterprise.
For example, most reasoning about mathematical objects is not done by perform-
ing classical inferences, but by reasoning educated by classical logic, and checked
by classical logic.
A reasoning system is concerned about giving reasonable answers in reasonable
time to precise questions. As such, it should be an efficient tool. In contrast, a
logic can be inefficient, and, as a matter of fact, nonmonotonic logics are very
inefficient. (This has been demonstrated in a number of articles by Gottlob
([EO92], [EG95], [Got92], [Got95a], [Oot95b]).
Usually, the type of questions one poses to a reasoning system is quite narrowly
defined. A doctor, a human reasoning system, will be asked to make a diagnosis,
to suggest a treatment. An unusual question, like "how many drugs do you know,
whose name's 5th letter is an 'r' ?" will pose @ite a problem. A reasoning system
is built to answer specific questions, but not to give an exhaustive picture of a
situation, examine all possible consequences, compute the deductive closure.
A reasoning system can also fail in minor details of the answers. Usually, there is
a hierarchy of importance for a reasoning system. If time is lacking, a reasoning
system should try to answer the most urgent questions, giving perhaps just a