A Tutorial on Default Logics

Grigoris Antoniou

Informations

• Publié par: Iddu
• Nombre de lectures: 40
• Langue: English

Extrait

A Tutorial on Default Logics
GRIGORIS ANTONIOU
Griffith University
Default Logic is one of the most prominent approaches to nonmonotonic reasoning,
and allows one to make plausible conjectures when faced with incomplete
information about the problem at hand. Default rules prevail in many application
domains such as medical diagnosis and legal reasoning.
Several variants have been developed over the past years, either to overcome some
perceived deficiencies of the original presentation, or to realize somewhat different
intuitions. This paper provides a tutorial-style introduction to some important
approaches of Default Logic. The presentation is based on operational models for
these approaches, thus making them more easily accessible to a broader audience,
and more easily usable in practical applications.
Categories and Subject Descriptors: I.2.3 [Artificial Intelligence]: Deduction and
Theorem Proving—Nonmonotonic reasoning and belief revision; I.2.4 [Artificial
Intelligence]: Knowledge Representation Formalisms and
Methods—Representation languages
General Terms: Languages, Theory
Additional Key Words and Phrases: Default Logic, nonmonotonic reasoning,
operational models
1. INTRODUCTION: DEFAULT REASONING data. Classical logic indeed has the ca-
pacity to represent and reason with cer-
When an intelligent system (either com-
tain aspects of incomplete information.
puter-based or human) tries to solve a
But there are occasions where addi-
problem, it may be able to rely on com- tional information needs to be “filled in”
plete information about this problem, to overcome the incompleteness, be-
and its main task is to draw the correct cause certain decisions must be made.
conclusions using classical reasoning. In In such cases the system has to make
such cases, classical predicate logic may some plausible conjectures, which in the
be sufficient. case of default reasoning are based on
However, in many situations the sys- rules of thumb, called defaults. For ex-
tem has only incomplete information at ample, an emergency doctor has to
hand, be it because some pieces of infor- make some conjectures about the most
mation are unavailable, or because it probable causes of the symptoms ob-
has to respond quickly and does not served. Obviously, it would be inappro-
priate to await the results of possiblyhave the time to collect all relevant
Author’s address: School of Computing & Information Technology, Griffith University, Brisbane, QLD
4111, Australia; email: [e-mail].
Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted
without fee provided that the copies are not made or distributed for profit or commercial advantage, the
copyright notice, the title of the publication, and its date appear, and notice is given that copying is by
permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to
lists, requires prior specific permission and/or a fee.
© 2000 ACM 0360-0300/99/0900–0337 $5.00
ACM Computing Surveys, Vol. 31, No. 3, September 1999338 • G. Antoniou
CONTENTS actually, we can talk about a family of
default reasoning methods because they
1. Introduction: Default Reasoning
share the same foundations.2. Default Logic
In this paper we present the motiva-2.1 The Notion of a Default
2.2 The Syntax of Logic tions and basic ideas of some of the
2.3 Informal Discussion of the Semantics most important default logic variants,
2.4 An Operational Definition of Extensions
and compare them both with respect to
2.5 Some Examples
interconnections and the fulfillment of2.6 Reiter’s Original Definition of Extensions
3. Properties of Default Logic some properties. When designing a tuto-
3.1 Existence of Extensions rial, it is good to have some aims
3.2 Joint Consistency of Justifications against which the final product can be
3.3 Cumulativity and Lemmas
tested. The particular aims of this tuto-4. Justified Default Logic
rial paper are the following:4.1 Motivation and Formal Presentation
4.2 Lukaszewicz’ Original Definition
5. Constrained Default Logic —To present the basic ideas of Default
5.1 Motivation and Definition Logic to persons without prior knowl-
5.2 A Fixpoint Characterization
edge in the area. Only basic under-
5.3 Interconnections
standing of classical logic is required.6. Priorities on Defaults
6.1 Motivation
—To equip the reader with skills and6.2 Static Priorities
6.3 Dynamic methods so that they can apply the
7. Other Variants of Default Logic concepts of Default Logic to concrete
7.1 Rational Default Logic
situations. This is achieved by the use
7.2 Cumulative Default Logic
of operational models which can be7.3 Disjunctive Logic
7.4 Weak Extensions applied in a straightforward manner
8. Conclusion to examples without having to make
any guesses, as is the case with the
usual fixpoint or quasiinductive defi-
nitions.
extensive and time-consuming tests be-
—To give the reader a sense of thefore beginning with treatment.
diversity of the topic.When decisions are based on assump-
tions, these may turn out to be wrong in
The paper is organized as follows: Sec-
the face of additional information that
tion 2 presents the basics of Reiter’s
becomes available; i.e., medical tests
Default Logic. Section 3 discusses prop-
may lead to a modified diagnosis. The
erties and design decisions of this ap-
phenomenon of having to take back
proach, and outlines some alternative
some previous conclusions is called non-
intuitions on these issues. Sections 4–6
monotonicity; it says that if a statement
describe some basic default logic vari-
w follows from a set of premises M and ants: Justified Default Logic [Lukasze-
M # M9, w does not necessarily follow wicz 1988], Constrained Default Logic
from M9. Default Logic, originally pre- [Schaub 1992], and approaches to pri-
sented in Reiter [1980], provides formal oritization [Brewka 1994]. In Section 7
methods to support this kind of reason- we briefly discuss some further default
ing. logics, namely Cumulative Default
Default Logic is perhaps the most Logic [Brewka 1991], Rational
prominent method for nonmonotonic [Mikitiuk and Truszczynski 1995],
reasoning, basically because of the sim- Disjunctive Default Logic [Gelfond et al.
plicity of the notion of a default, and 1991], and weak extensions [Marek and
because defaults prevail in many appli- Truszczynski 1993].
cation areas. However, there exist sev- No prior knowledge of Default Logic is
eral alternative design decisions which required since this is a tutorial paper.
have led to variations of the initial idea; However, we assume that the reader is
ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø
Ø
Ø
Ø
Ø
A Tutorial on Default Logics • 339
familiar with notation and the basic The same example could have been
concepts of classical logic. represented by the default
2. DEFAULT LOGIC football : takesPlace
,
takesPlace
2.1 The Notion of a Default
A rule used by football organizers in together with the classical rule snow
Germany might be: “A football game
3 takesPlace. In case we know snow
shall take place, unless there is snow in
then we can deduce takesPlace in clas-the stadium.” This rule of thumb is rep-
sical logic, therefore we cannot assumeresented by the default
takesPlace, as required by the default.
In this representation, the default saysfootball : snow
. “Football matches usually takes place,”
takesPlace
and exceptions to this rule are repre-
sented by classical rules such as the
The interpretation of the default is as
above one.follows: If there is no information that
Defaults can be used to model proto-there will be snow in the stadium, it is
typical reasoning, which means that
reasonable to assume snow and con-
most instances of a concept have some
clude that the game will take place (so
property. One example is the statement
preparations can proceed). But if there
“Typically, children have (living) par-is a heavy snowfall during the night
ents” which may be expressed by thebefore the game is scheduled, then this
defaultassumption can no longer be made. Now
we have definite information that there
child~X! : hasParents~X!
is snow, so we cannot assume snow, .
therefore the default cannot be applied. hasParents~X!
In this case we need to refrain from the
previous conclusion (the game will take A further form of default reasoning is
place), so the reasoning is nonmono- no-risk reasoning. It concerns situations
tonic. where we draw a conclusion even if it is
Before proceeding with more exam- not the most probable, because another
ples, let us first explain why classical decision could lead to a disaster. Per-
logic is not appropriate to model this haps the best example is the following
situation. Of course, we could use the main principle of justice in the Western
rule cultures: “In the absence of evidence to
the contrary assume that the accused is
football ÙØ snow3 takesPlace. innocent.” In default form:
The problem with this rule is that we accused~X! : innocent~X!
have to definitively establish that there .
innocent~X!will be no snow in the stadium before