A Tutorial on Default Logics

A Tutorial on Default Logics

-

English
23 Pages
Read
Download
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

A Tutorial on Default LogicsGRIGORIS ANTONIOUGriffith UniversityDefault Logic is one of the most prominent approaches to nonmonotonic reasoning,and allows one to make plausible conjectures when faced with incompleteinformation about the problem at hand. Default rules prevail in many applicationdomains such as medical diagnosis and legal reasoning.Several variants have been developed over the past years, either to overcome someperceived deficiencies of the original presentation, or to realize somewhat differentintuitions. This paper provides a tutorial-style introduction to some importantapproaches of Default Logic. The presentation is based on operational models forthese 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 andTheorem Proving—Nonmonotonic reasoning and belief revision; I.2.4 [ArtificialIntelligence]: Knowledge Representation Formalisms andMethods—Representation languagesGeneral Terms: Languages, TheoryAdditional Key Words and Phrases: Default Logic, nonmonotonic reasoning,operational models1. 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 aBut there are occasions where addi-problem, it may be able to rely ...

Subjects

Informations

Published by
Reads 40
Language English
Report a problem

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: ga@cit.gu.edu.au.
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
applying the rule. But that would mean
Defaults naturally occur in many ap-that no game could be scheduled in the
plication domains. Let us give an exam-winter, which would create a revolution
ple from legal reasoning. According toin Germany! It is important to under-
German law, a foreigner is usually ex-stand the difference between having to
pelled if they have committed a crime.know that it will not snow, and being
able to assume that it will snow. De- One of the exceptions to this rule con-
faults support the drawing of conclu- cerns political refugees. This informa-
sions based upon assumptions. tion is expressed by the default
ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø
Ø
Ù
Ø
Ø
Ø
340 • G. Antoniou
ton [1987b]; Lukaszewicz [1990]; andcriminal~X! foreigner~X! : expel~X!
Poole [1994].
expel~X!
2.2 The Syntax of Default Logic
in combination with the rule
A default theory T is a pair ~W, D!
politicalRefugee~X!3 expel~X!. consisting of a set W of predicate logic
formulae (called the facts or axioms of
Hierarchies with exceptions are com-
T) and a countable set D of defaults. A
monly used in biology. Here is a stan-
default d has the formdard example:
Typically, molluscs are shell-bearers.
w : c ,...,c1 nCephalopods are molluscs. are not
x
It is represented by the default
where w, c ,...,c , x are closed1 n
mollusc~X! : shellBearer~X! predicate logic formulae, and n . 0.
The formula w is called the prerequisite,shellBearer~X!
c ,...,c the justifications, and x the1 n
together with the rule consequent of d. Sometimes w is denoted
by pre~d!, $c ,...,c % by just~d!, and1 n
cephalopod~X!3 mollusc~X!
x by cons~d!. For a set D of defaults,
cons~D! denotes the set of consequentsÙØ shellBearer~X!.
of the defaults in D. A default is called
normal iff it has the form w : c c.Defaults can be used naturally to model /
One point that needs some discussionthe Closed World Assumption [Reiter
is the requirement that the formulae in1978], which is used in database theory,
a default be ground. This implies thatalgebraic specification, and logic pro-
gramming. According to this assump-
bird~X! : flies~X!tion, an application domain is described
by certain axioms (in form of relational
flies~X!
facts, equations, rules, etc.) with the
following understanding: a ground fact is not a default according to the defini-
(that is, a nonparameterized statement tion above. Let us call such rules of
about single objects) is taken to be false inference open defaults. An open default
in the problem domain if it does not is interpreted as a default schema,
follow from the axioms. The closed meaning that it represents a set of de-
world assumption has the simple de- faults (this set may be infinite).
fault representation A default schema looks like a default,
the only difference being that w, c ,1true : w
..., c , x are arbitrary predicate logicn
w formulae (i.e., they may contain free
variables). A default schema defines a
for each ground atom w. The explana- set of defaults, namely
tion of the default is: if it is consistent
ws : c s,...,c sto assume w (which is equivalent to 1 n
not having a proof for w) then conclude
xs
w.
Further examples of defaults can be for all ground substitutions s that as-
found in, say, Besnard [1989]; Ethering- sign values to all free variables occur-
ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø
Ø
Ø
Ø
Ø
Ø
Ù
A Tutorial on Default Logics • 341
ring in the schema. That means free T 5 ~W, D! with W 5 $green,
variables are interpreted as being uni-
aaaMember% and D 5 $d , d % with1 2versally quantified over the whole de-
fault schema. Given a default schema
green : likesCars
d 5 ,1
likesCarsbird~X! : flies~X!
flies~X!
aaaMember : likesCars
d 5 .2
and the facts bird~tweety! and likesCars
bird~sam!, the default theory repre-
sented is ~$bird~tweety!, bird~sam!%, If consistency of the justifications was
tested against the set of facts, then both
$bird~tweety! : flies~!/flies~tweety!,
defaults could be subsequently applied.bird~sam! : flies~sam!/flies~sam!%!.
But then we would conclude both
likesCars and likesCars, which is a2.3 Informal Discussion of the Semantics
contradiction. It is unintuitive to let the
Given a default w : c ,...,c x, its
/1 n application of default rules lead to an
informal meaning is the following: inconsistency, even if they contradict
each other. Instead, if we applied the
If w is known, and if it is consistent to
first default, and then checked applica-
assume c ,...,c , then conclude x.1 n tion of the second with respect to the
current knowledge collected so far, theIn order to formalize this interpretation
second default would be blocked: from
we must say in which context w should
the application of the first default we
be known, and with what c ,...,c1 n know likesCars, so it is not consis-
should be consistent. A first guess
tent to assume likesCars. After thesewould be the set of facts, but this turns
examples, here is the formal definition:out to be inappropriate. Consider the
default schema
d 5 w : c ,...,c x is applicable
/1 n
friend~X, Y! friend~Y, Z! : friend~X, Z! to a deductively closed set of formulae
E iff w [ E and c [y E,..., c1 nfriend~X, Z!
[y E.
which says “Usually my friends’ friends
are also my friends”. Given the infor- The example of Greens and AAA mem-
mation friend~tom, bob!, friend~bob, bers indicates that there can be several
competing current knowledge basessally! and friend~sally, tina!, we would
which may be inconsistent with one an-like to conclude friend~tom,
other. The semantics of Default Logic
tina!. But this is only possible if we
will be given in terms of extensions that
apply the appropriate instance of the
will be defined as the current knowl-
default schema to friend~sally, tina! edge bases satisfying some conditions.
and friend~tom,! sally}. The latter for- Intuitively, extensions represent possi-
mula stems from a previous application ble world views which are based on the
1
of the default schema. If we did not given default theories; they seek to ex-
admit this intermediate step and used tend the set of known facts with “rea-
the original facts only, then we could sonable” conjectures based on the avail-
not get the expected result. able defaults. The formal definition will
Another example is the default theory be given in the next subsection. Here we
just collect some desirable properties of
1With other instantiations, of course. extensions.
ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø
Ø
Ø
Ø
Ø
Ø
Ø
Ø
Ø
342 • G. Antoniou
2.4 An Operational Definition of—An extension E should include the set
Extensions
W of facts since W contains the cer-
tain information available: W # E. For a given default theory T 5 ~W, D!
letP5~d , d ,...! be a finite or infi-0 1
—An extension E should be deductively nite sequence of defaults from D with-
closed because we do not want to pre- out multiple occurrences. Think of P as
vent classical logical reasoning. Actu- a possible order in which we apply some
ally, we want to draw more conclu- defaults from D. Of course, we don’t
sions, and that is why we apply want to apply a default more than once
default rules in addition. Formally: E within such a reasoning chain because
no additional information would be
5 Th~E!, where Th denotes the de-
gained by doing so. We denote the ini-ductive closure.
tial segment of P of length k by P@k#,
— provided the length of P is at least kAn extension E should be closed un-
(from now on, this assumption is always
der the application of defaults in D
made when referring to P@k#). With
(formally: if w : c ,...,c x [ D,
/1 n
each such sequence P we associate two
w [ E and c [y E,..., c [y E1 n
sets of first-order formulae, In~P! and
then x [ E). That is, we do not stop
Out~P!:
applying defaults until we are forced
to. The explanation is that there is no —In~P! is Th~W ł $cons~d!?d occurs
reason to stop at some particular
in P}. So, In~P! collects the informa-
stage if more defaults might be ap-
tion gained by the application of the
plied; extensions are maximal possi-
defaults in P and represents the cur-ble world views.
rent knowledge base after the defaults
in P have been applied.
These properties are certainly insuffi- —Out~P! 5 $ c?c [ just~d! for some
cient because they do not include any
d occurring in P}. So, Out~P! collects
“upper bound,” that is, they don’t pro- formulae that should not turn out to
vide any information about which for- be true, i.e., that should not become
mulae should be excluded from an ex- part of the current knowledge base
tension. So we should require that an even after subsequent application of
extension E be minimal with respect to other defaults.
these properties. Unfortunately, this re-
Let us give a simple example. Considerquirement is still insufficient. To see
the default theory T 5 ~W, D! with Wthis, consider the default theory T 5
5 $a% and D containing the following
~W, D! with W 5 $aussie% and D 5
defaults:
$aussie : drinksBeer/drinksBeer%.
Let E 5 Th~$aussie,%!. a : b b : c
d 5 , d 5 .1 2It is easily checked that E is minimal b c
with the three properties mentioned
above, but it would be highly unintui-
For P5~d ! we have In~P! 5 Th~$a,1tive to accept it as an extension, since
b%! and Out~P! 5 $b%. For P5~d ,2that would support the following argu-
d ! we have In~P! 5 Th~$a, c, b%!ment: “If Aussies usually drink Beer 1
and if somebody is an Aussie, then as- and Out~P! 5 $ c, b%.
sume that she does not drink Beer.” Up to now we have not assured that
ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø
Ø
Ø
Ø
A Tutorial on Default Logics • 343
the defaults in P can be applied in the
order given. In the example above, ~d ,2
d ! cannot be applied in this order (ap-1
plied according to the definition in the
previous subsection). To be more spe-
cific, d cannot be applied, since b [y2
In~~!! 5 Th~W! 5 Th~$a%! which is
the current knowledge before we at-
tempt to apply d . On the other hand,2 Figure 1. A process
there is no problem with P5~d !;in tree.1
this case we say that P is a process of T.
Here is the formal definition:
Th~$a, b%! is an extension of T, in fact—
P is called a process of T iff d isk its single extension.
applicable to In~P@k#!, for every k
Definition 1. A set of formulae E issuch that d occurs in P.k
an extension of the default theory T iff
there is some closed and successful pro-Given a process P of T we define the
following: cess P of T such that E 5 In~P!.
In examples, it is often useful to ar-

P is successful iff In~P! ø Out~P! range all possible processes in a canoni-
5 À, otherwise it is failed. cal manner within a tree, called the
process tree of the given default theory

P is closed iff every d [ D that is T. The nodes of the tree are labeled
applicable to In~P! already occurs in with two sets of formulae, an In-set (to
P. Closed processes correspond to the the left of the node) and an Out-set (to
desired property of an extension E the right of the node). The edges corre-
being closed under application of de- spond to default applications, and are
faults in D. labeled with the default that is being
applied. The paths of the process tree
Consider the default theory T 5 ~W, starting at the root correspond to pro-
D! with W 5 $a% and D containing the cesses of T.
following defaults
2.5 Some Examples
a : b true : c
d 5 , d 5 .1 2 Let T 5 ~W, D! with W 5 À and D 5
d b
$true : a/ a%. The process tree in Fig-
ure 1 shows that T has no extensions.
P 5 ~d ! is successful but not closed1 1
Indeed, the default may be applied be-
since d may be applied to In~P ! 52 1 cause there is nothing preventing us
Th~$a, d%!. P 5 ~d , d ! is closed but2 1 2 from assuming a. But when the default
not successful: both In~P ! 5 Th~$a,2 is applied, the negation of a is added to
d, b%! and Out~P ! 5 $b, c% contain2 the current knowledge base, so the de-
b. On the other hand, P 5 ~d ! is a fault invalidates its own application be-3 2
closed and successful process of T. cause both the In and the Out-set con-
According to the following definition, tain a. This example demonstrates
which was first introduced in Antoniou that there need not always be an exten-
and Sperschneider [1994], In~P ! 5 sion of a default theory.3
ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø
Ø
Ø
Ø
Ø
Ø
Ø
344 • G. Antoniou
Figure 2. A process tree.
2.6 Reiter’s Original Definition ofLet T 5 ~W, D! be the default theory
Extensions
with W 5 À and D 5 $d , d % with1 2
In this subsection we present Reiter’s
true : p true : q original definition of extensions [Reiter
d 5 , d 5 .1 2 1980]. In 2.3 we briefly ex-q r
plained that the most difficult problem
in describing the meaning of a default is
The process tree of T is found in Figure
to determine the appropriate set with
2 and shows that T has exactly one which the justifications of the defaults
extension, namely Th~$ q%!. The right must be consistent. The approach
path of the tree shows an example adopted by Reiter is to use some theory
where application of a default destroys beforehand. That is, choose a
the applicability of a previous default: which plays the role of a context or belief
set and always check consistency
d can be applied after d , but then q1 2
against this context. Let us formalizebecomes part of the In-set, whilst it is
this notion:
also included in the Out-set (as the
negation of the justification of d ).2 —A default d 5 w : c ,...,c x is
/1 n
Let T 5 ~W, D! with W 5 $green, applicable to a deductively closed set
aaaMember% and D 5 $d , d % with1 2 of formulae F with respect to belief set
E (the aforementioned context) iff w
green : likesCars
d 5 , [ F, and c [y E,..., c [y E1 1 n
likesCars
(that is, each c is consistent with E).i
aaaMember : likesCars Note that the concept “ d is applicable to
d 5 .2
likesCars E” used so far is a special case where
E 5 F. The next question that arises is
The process tree in Figure 3 shows which context to use. First, note that
that T has exactly two extensions when a belief set E has been estab-
(where g stands for green, a for lished, some formulae will become part
aaaMember, and l for likesCars). of the knowledge base by applying de-
ACM Computing Surveys, Vol. 31, No. 3, September 1999A Tutorial on Default Logics • 345
Figure 3. A process tree.
ous obstacles in understanding the con-faults with respect to E. Therefore, they
cepts of Default Logic and in being ableshould be believed, i.e., be members of
to apply them to concrete cases.E. On the other hand, what would be a
The following theorem shows that Re-justification for a belief if it were not
iter’s extension concept is equivalent toobtained from default application w.r.t.
the definition in subsection 2.4.
E? We require that E contain only for-
mulae that can be derived from the axi- THEOREM 1. Let T 5 ~W, D! be a de-
oms by default application w.r.t. E. fault theory. E is an extension of T (in
Let us now give a formal presentation the sense of definition 2.1) iff E 5
of these ideas. For a set D of defaults,
L ~E!.T
we say that F is closed under D with
We conclude by giving a quasiinduc-respect to belief set E iff, for every de-
tive characterization of extensions, also
fault d in D that is applicable to F with
due to Reiter: Given a default theory T
respect to belief set E, its consequent x
5 ~W, D!, we say that E has a quasi-
is also contained in F.
inductive definition in T iff E 5 ł E ,iiGiven a default theory T 5 ~W, D!
where E 5 Th~W! and E 5 Th~Eand a set of formulae E, let L ~E! be 0 i11 iT
the least set of that contains
ł $cons~d!%d [ D! is applicable to Ei
W, is closed under logical conclusion w.r.t. belief set E}.
(i.e., first-order deduction), and closed
THEOREM 2. E is an extension of T iff
under D with respect to E. Informally
E has a quasiinductive definition in T.speaking, L ~E! is the set of formulaeT
that are sanctioned by the default the- This characterization replaces the
ory T with respect to the belief set E.
L -operator by a construction, both ofT
Now, according to Reiter’s definition,
them using the set E as context or belief
E is an extension of T iff E 5L~E!.T set. Given a set of formulae E, this
This fixpoint definition says that E is characterization is intuitively appeal-
an extension iff by deciding to use E as ing. But notice that still it is necessary
a belief set, exactly the formulae in E to first guess E before checking whether
will be obtained from default applica- it is an extension. In this sense, the
tion. But please note the difficulty in characterization is not as easy to apply
applying this definition: we have to as the process model from subsection
guess E and subsequently check for the 2.4.
fulfillment of the fixpoint equation. The relationship of processes to the
Having to guess is one of the most seri- quasiinductive definition is that the tra-
ACM Computing Surveys, Vol. 31, No. 3, September 1999Ø
Ø
346 • G. Antoniou
versal of the process tree operational- heterogeneous information sources,
izes the idea of guessing. More formally: where it is not easy to identify which
if a branch of the process tree leads to a source is responsible for the deficiency,
or where the single pieces of informa-closed and successful process P, then
tion are meaningful, but lead to prob-the quasiinductive construction using
lems when put together.
In~P! as a belief set yields the same
A more technical argument in favor of
result. But some branches of the process
the second view is the concept of semi-
tree can lead to failed processes; this is
monotonicity. Default Logic is a method
the price we have to pay if we wish to
for performing nonmonotonic reasoning,
avoid guessing.
so we cannot expect it to be monotonic
when new knowledge is added to the set
3. PROPERTIES OF DEFAULT LOGIC of facts. However, we might expect that
the addition of new defaults would yield
In this section we discuss some proper- 2more, and not less information. For-
ties of Default Logic. Some of these
mally, semi-monotonicity means the fol-
properties can be interpreted as defi-
lowing:
ciencies, or they highlight some of Reit-
er’s original “design decisions” and show Let T 5 ~W, D! and T95~W, D9! be
alternative ideas that could be followed
default theories such that D # D9.
instead. In this sense, the discussion in
Then for every extension E of T therethis section motivates alternative ap-
is an extension E9 of T9 such that Eproaches that will be presented in sub-
sequent sections. One point that should # E9.
be stressed is that there is not a “cor-
Default Logic violates this property. For
rect” default logic approach, but rather
example, T 5 ~À, $true : p/p%! has thethe most appropriate for the concrete
problem at hand. Different intuitions single extension E 5 Th~$p%!, but T9
lead to different approaches that may
5 ~À, $true : p/p, true : q/ q%! has no
work better for some applications and extension. So nonexistence of extensions
worse for others. leads to the violation of semi-monotonic-
ity. Even though the concept of semi-
monotonicity is not equivalent to the3.1 Existence of Extensions
existence of extensions, these two prop-
We saw that a default theory may not erties usually come together (for a more
have any extensions. Is this a shortcom- formal support of this claim see Anto-
ing of Default Logic? One might hold niou et al. [1996]).
the view that if the default theory in- If we adopt the view that the possible
nonexistence of extensions is a problem,cludes “nonsense” (for example true :
then there are two alternative solutions.p p), then the logic should indeed be
/
The first one consists in restricting at-allowed to provide no answer. According
tention to those classes of default theo-to this view, it is up to the user to
ries for which the existence of exten-provide meaningful information in the
sions is guaranteed. In his classicalform of facts and defaults;
paper [Reiter 1980], Reiter alreadyafter all, if a program contains an error,
showed that if all defaults in a theory Twe don’t blame the programming lan-
guage. are normal (in which case T is called a
The opposite view regards nonexist- normal default theory), then T has at
ence of extensions as a drawback, and
would prefer a more “fault-tolerant” logic;
one which works even if some pieces of 2Some researchers would disagree with this view
information are deficient. This view- and regard semi-monotonicity as not desirable;
point is supported by the trend towards see, for example, Brewka [1991].
ACM Computing Surveys, Vol. 31, No. 3, September 1999