9512.net

# Defeasible logics

Defeasible Logics
P. Geerts, E. Laenens Dept. of Mathematics and Computer Science University of Antwerp D. Vermeir Dept. of Computer Science Free University of Brussels, VUB

Contents
Introduction Pearl’s system Z 0.2.1 Deriving a natural ordering of defaults 0.2.2 System : resolving remaining ambiguities by explicit means 0.3 Conditional entailment 0.4 The argument-based system of Simari and Loui 0.5 Brewka’s preferred subtheories 0.6 Ordered logic and basic defeasible logic 0.6.1 Implicit version of Nute’s basic defeasible logic 0.6.2 Ordered logic 0.6.3 Explicit version of Nute’s basic defeasible logic 0.6.4 The preemption problem 0.6.5 Ryan’s formalism of ordered theories presentations 0.7 Summary and discussion Bibliography

0.1 Introduction
In this chapter, we will concentrate on the defeasible approach to nonmonotonic reasoning, as opposed to the minimalist approach and the ?xpoint approach. Formalisms following the minimalist approach, like circumscription [McC80, McC86, Lif85], look at models of a classical theory that are minimal with respect to some set of predicates occurring in the theory. Fixpoint formalisms include McDermott’s and Doyle’s nonmonotonic logic [MD80], Reiter’s default logic [Rei80], and Moore’s autoepistemic logic [Moo84, Moo88]. Default rules in these systems involve a special condition for application, which is explained in the proof theory. By applying rules in an arbitrary order, some other rules may become blocked, and eventually, a ?xpoint is derived from where no new conclusions can be reached. At a ?xpoint, every default is either inapplicable or applied. The same holds for minimal models. In the defeasible approach, defaults are treated quite differently. The intent of a default is that will normally be derivable from a theory containing this default whenever is derivable. However, it is possible to have a theory containing from which both and can be derived. If this is the case, the rule is said 1

 § ¨

? ?¤ ? ? ? ? ? ? ? ? ? ? ? ? ????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??????????????????????????????  ¨ §  

0.1 0.2

1 4 5 7 8 11 16 19 20 24 29 31 32 33 34

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????????????? ????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????????????????? ? ? ? ? ? ? ? ???????? ?????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????????????? ????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????? 

§

§  ¨ ?§

2

CONTENTS

to be defeated. Rules which can be defeated are called defeasible rules and logics using defeasible rules are called defeasible logics. In a defeasible logic formalism, extensions of theories are formed, in which each rule is either inapplicable, applied or defeated. In case of a con?ict, defeasible logics usually rely on some kind of ordering on defeasible rules or sets of rules in an attempt to resolve this con?ict. This prioritization can be implicitly present in the knowledge base, in which case it is based on some notion of speci?city, or explicitly given by the user. Both approaches have their pros and cons, which will be discussed at the end of this chapter. Whenever the ordering on rules does not allow to resolve the con?ict, a defeasible logic formalism can adopt either a credulous or a skeptical strategy. Using the credulous strategy, an arbitrary rule among the competing but incomparable ones is chosen for application. A credulous reasoner wants to draw as much conclusions as possible, so that he prefers to apply one of these rules instead of concluding nothing. As a result, this credulous strategy leads to multiple extensions. Following the skeptical strategy, no conclusion is drawn, and the con?icting rules are said to defeat each other. A skeptical reasoner wants to draw a conclusion only when he’s very sure about it, so that in case of doubt, he doesn’t conclude anything. This strategy always yields a unique extension. Another way to arrive at a unique extension is to be credulous, derive multiple extensions and then take the intersection of these credulous extensions. In this case, we obtain the conclusions of which we can be very sure, because they are true in every possible world. This approach can be considered as being skeptical after taking into account all possibilities, and is therefore called the indirectly skeptical approach. The indirectly skeptical approach usually seems to ?t closer to our intuition than the directly skeptical approach, but it is also the most costly regarding computations. Formalisms following a directly skeptical approach can differ in the way they deal with ambiguities. Whenever there is an ambiguity about a proposition which cannot be solved by considering priorities, will not be a conclusion because of the skeptical attitude. However, a formalism can forget about this ambiguity, and therefore also forget that there was a reason to believe , or it can register as an ambiguous proposition which can still interfere with other conclusions. The ?rst approach will be called ambiguity-blocking, while the second one is ambiguity-propagating [Ste92]. In order to treat all formalisms alike, we will make some notational conventions which we will adhere to throughout this chapter. A literal is a propositional constant or the negation of a propositional constant; and are complements of each other. Where is any literal, we denote the complement of as . Where is a ?nite set of literals and is a literal, a strict rule is denoted , and a defeasible rule is . Strict rules are sometimes referred to as sentences or necessary facts, denoted while defeasible rules are also called default rules or defaults. Some formalisms allow a third kind of rule: a defeater, denoted . A defeater can defeat a defeasible rule, but can never support inferences directly. A defeater will therefore also be called an interfering rule. An example of a strict rule is “Everything in Brussels is in Belgium”’. “Birds ?y” is a defeasible rule, because it can be defeated when we acquire more



§











? §

?









? ?§





?

 ?§ ¨





0.1. INTRODUCTION

3

information. An example of an interfering rule is “A sick bird might not ?y”. We usually omit the set brackets when the antecedent set has only one member, and we usually omit an empty antecedent set altogether. Thus is usually written and is usually written . Antecedents of strict rules and defeaters are non-empty sets, but defeasible rules might have empty antecedents. A defeasible rule with an empty antecedent can be considered as a presumption. For a rule , we use the notations for the body of the rule and for the head. Because some formalisms consider the body of a rule as a conjunction of literals instead of a set, we also introduce the notation for the conjuncted body of , i.e. the conjunction of literals present in the body of . Put otherwise, when is a rule , then , and . Whenever a formalism is de?ned for a ?rst-order language, we will simply consider the grounded instances of the rules containing variables. Although some formalisms also allow more complex rules involving e.g. disjunctions, we will restrict the rules in this discussion to the ones described above. A knowledge base is a set of rules . Some defeasible logics consider all rules to be defeasible, others also allow strict rules and occasionally, interfering rules can be found. When necessary, we will refer to the strict, defeasible and interfering parts of as , and , i.e.

A defeasible theory is a knowledge base together with a (possibly empty) set containing literals, representing the observations. Observations are also called evidences or contingent facts. Sometimes, some kind of additional structure is added to represent explicit priorities. In this case, the knowledge bases and defeasible theories are said to be ordered (or prioritized). From a technical point of view, ordered defeasible theories can live without strict rules and observations: their impact can be simulated by giving the corresponding defeasible rules top priority. Although the additional structure for representing explicit priorities can take different forms, we usually can rewrite a defeasible theory with ordering as a general ordered theory ? , where (? ) is a ?nite totally or partially ordered set of nodes, a ?nite set of defeasible rules, and a function assigning a set of rules to each node. In this framework, strict rules and observations can be treated the same way as defeasible rules, provided that they are can also assigned to a node with top priority. The set of nodes ? 0 be considered as a set of perspectives, labels or weights. Typically, there will be a unique top node, which will be called 0 . Furthermore, all the information at has the same level of priority or certainty and has precedence over the information at where

T

abX 6

X

?

Y `X

P WI

I

???I

X (?

 TI 1I P VUSRQ(I §



? 1 A DCF

? 9 ? ?§ E ?§ ?

and

?

?

?

?

¨ ? ? ?

)0'(&\$" ¨ %# !  ?§ ? ?  ?§ ? ¨

? 1 A DCF

? 1 A DCB

 ?§ ? 1

¨ 9 ¨ ?§ E ?§ ?

9 ? § @ ? § ?

1

?

1

X

¨



 4 51

 2 831

  ?§ 

 6 ?71

§   ?§ ?¨?

G

6 71

?

 ?§ ?¨?

¨

¤

4 2 51 31

 § ¨

?

¨ 
1 H

4

CONTENTS

. When the knowledge base is totally ordered, we agree that the ordering is given by 0 . 1 Some formalisms discussed here, interpret the default implication ( ) and the strict implication ( ) as unidirectional, using modus ponens as inference rule. The consequence relation for these formalisms will be denoted by . Others however interpret the implications as material ones, using the classical consequence relation . As a result of this, they allow contraposition. In other words, from the default “birds ?y” ( ), they conclude that non?iers, by default, are not birds. It can be argued whether or not contraposition is a desirable property of a nonmonotonic formalism. E.g. [Gin94] for the default “humans tend not to be diabetics”, it seems unreasonable to conclude from this that diabetics tend not to be human. If contraposition is not applicable in a formalism, it can be simulated by explicitly adding the contraposed information whenever required. However, when a formalism does allow contraposition, this reasoning mechanism cannot be disabled. The interpretation of implications and the allowance of contraposition are controversial topics on which the defeasible logics tend to disagree. Depending on the interpretation of rules, (in)consistency should be understood as (in)consistency with respect to the classical consequence relation , or to the restricted consequence relation . An interpretation of a defeasible theory is a function assigning a truth-value to each proposition occurring in . An interpretation is a model of if it satis?es every observation and strict rule occurring in , i.e. if for each , and for each . Because a defeasible theory can contain defeasible and interfering rules which can be defeated, one can hardly expect that each rule is satis?ed in a model. Indeed, a defeasible or interfering rule can be veri?ed, satis?ed or falsi?ed. A model is said to verify if , to satisfy if and to falsify if . In this chapter on defeasible logics the following formalisms will be discussed: basic defeasible logic [Nut92, Nut88], ordered logic [VNG89a, VNG90, GVN94, GLV91, Lae90], conditional entailment [GP92], Brewka’s system of preferred subtheories [Bre89], Pearl’s system Z [Pea90] and the argumentation-based system of Simari and Loui [SL92]. We will compare and catalogue these formalisms with respect to their basic design choices such as the approach to express priorities among defaults, the attitude towards con?icting defaults (skeptical or credulous), the interpretation of rules and the allowance of contraposition.

0.2 Pearl’s system Z
Pearl’s system Z [Pea90] is a defeasible logic formalism by means of which a total ordering can be imposed on most sets of defeasible rules. System Z is based on a probabilistic interpretation [Ada75, Pea89] of rules: a defeasible rule is interpreted as asserting that the probability of is high, given that represents all the available evidence. As a result, system Z transforms a set of rules into a totally

?

 ¨ §

?

H

A

 ?§ ?

?

¨

G

§

?

 ?  ?  ?§ ? § 8 ?¨ 9 ?  ?§ ? ¨ 9 ¤ ?

?9

? ?9

¤

¤



G

G

¤

2 31 A ?

?

?9

G

¤

Y X

 ?§ ?

???? ? ? X X
 ?§ ?

?

§  ?§ ? ?¨ 9

§  ?§ ? ¨?¨Q 9

T

a ?X

¨ ??

¤

? ?6

¤

?

X

0.2. PEARL’S SYSTEM Z

5

ordered partition 0 1 , whenever possible. Such an ordered partition of a set of defeasible rules is called the Z-ordering. The idea is that lower ranked rules contain more normal, or less speci?c, information. The consequence relation of system Z is based on the preference relation among models [Sho87b, KLM90] which results from the rule ranking.

0.2.1

Deriving a natural ordering of defaults

In system Z, knowledge bases contain only defeasible rules. The default implication is interpreted as material implication . In other words, a rule

is treated as the logical formula

Therefore, no restrictions are imposed on models: because there are no strict rules which have to be satis?ed, a model is an ordinary interpretation. The derivation of the Z-ordering is based on the notion of toleration.

The process of ?nding a Z-ordering for a set of defaults is de?ned as follows: every rule that is tolerated by all the other rules in is in 0 . Next, every rule that is tolerated by the remaining ones (the rules in 0 ) is in 1 . Continuing in this way, the process stops with a full partition, the Z-ordering, or with some rules which are not tolerated by the remaining ones. If there is a full partition, the set of defaults can be considered to be Z-consistent. Z-consistency is also called p-consistency in [Ada75] is not Z-consistent, or -consistency in [Pea88]. For example, because none of the rules is tolerated by the other one. System Z can only derive conclusions for Z-consistent sets of defaults. For such a set of defaults , the ranking among rules can be translated into preferences among models. The rank of a rule is given by iff . The rank associated with a model is given by

The next de?nition gives us a reasonable notion of entailment, based on the idea that a formula is a plausible consequence of if the models of are preferred to the models of .



? T

¤

which is the rank of the highest-ranked rule falsi?ed by formula is given by

plus 1. The rank of a

?1

1

De?nition 1 Let be a knowledge base containing only defaults. A subset said to tolerate a rule if there is a model that veri?es and satis?es all rules in

? ??

1

? §    ?

?  V

1

¨

a

I  ?§ ¤ U? §

1

1

? T 9

1 A CS?

) RI

?

 ¨

1

? ¨ ? RI ? ? ? I ) ) Y ?

1

? § B? ? ? ? ? ) ) Y

1

¤9 

1 ¤ @?1

)

§  ? ¨ ?§

?

 ?§ ? ¨ 9

 1

¤§ ¤

T

§

?

¤

 ?   VT §

¤ 9  8 ¤ § ¤  ?  ?

Y

1 &I

???I ¤
?

?

1 &I

1

1

1

 !

? T

¤



T

?

¨

is .

6 De?nition 2 Let be a Z-consistent set of defaults and observations. A literal is said to be Z-entailed 1 by
1 2

CONTENTS

1

2

As a result of this entailment de?nition, system Z can considered to be skeptical: whenever both formulae 1 and 1 have the same 2 2 Z-rank, no conclusion about is possible. In contrast to other formalisms based on probabilistic or preferential model ideas, like p-entailment [Ada75], -entailment [Pea88] and r-entailment [LM88], Z-entailment properly handles irrelevant features, e.g. from “birds ?y” we can conclude that “red birds ?y”. Z-entailment also sanctions rule chaining and allows contraposition, due to the classical logic interpretation of defaults. One of the shortcomings of system Z is that it suffers from the so-called drowning problem, as illustrated in the following example. Example 1 Consider the knowledge base

0

1

When 1 , we get that 1 , because 0 and 1. This illustrates the fact that rules ( and ) can be chained. For 2 , system Z entails , because 0 and 2. Therefore, we can conclude that contraposition (of the rule ) is allowed. For the set of observations 3 , we get that 3 , because 1 and 2. The ambiguity about is solved correctly, based on speci?city reasons: being a penguin is more speci?c than being a bird. The presence of the irrelevant feature causes no problem. However, is not a Z-entailed conclusion: 1

Although a penguin is an exceptional bird with respect to the ability to ?y, nothing prevents him from having wings. As a consequence of the Z-ordering, a penguin is declared to be an exceptional bird in all respects, so that no property of birds can be inherited. This weakness of system Z, which can also be found in some other
1

Pearl uses the name 1-entailment instead of Z-entailment, and consistency instead of Z-consistency.



  TH 8V8

 ?T 

? T ¨§ ¤

 ? T ¤?  § ¤  ? ? § ¤

¤

 

 VT 

   ?

I (? ?

?

T T8 ?? 01RI § ?  H ? ¨     ? ?  § T ? ¨ T¤ ¤ T §§ ¤ T ??? 01RI § H  1

? (?

¨

¨?? ¤

? T ?  § ¤   ? T ?  § ¤ ¤ ? ¤

?

T ?Q? ¤I

¨  I 8 ¨  ? T

¨ ?I

?

Let stand for penguin, for bird, for ?y, The Z-ordering induced by is

for wings and

  ? Y ? ? ? ? ? ? ? ?

for something feathered.

? (?

¨

T ?Q? ¤I

¨ ?I

T

¨ ? I 8 ¨  I ? ¨  ? T

  ? Y? ???? ? ? ?

T

1

where

is the Z-ordering induced by .

 ??? G  1 0&I §  G ? I ? ? ? I ? I ? H H ?
1 2

, denoted

?

Y

a set of , if



  ? Y ? ? ? ? ? ? ? ? ? § ¤

? 

 ? Y ? ? ? ? ? ? ? ? ?§ ¤ ¨ ?
T ?  1 1
?

? T ?I ¤

 

?



 1

?

8VT 

1

? T¤

? T ?  § ¤ ¤

H

?



?
H

? (?





?

0.2. PEARL’S SYSTEM Z

7

systems, is called the drowning problem [BCD 93]: the inability to sanction property inheritance from classes to exceptional sub-classes. Another problem of this consequence relation is that the commitment to a unique integer ranking sometimes yields unintuitive results. Example 2 Consider the knowledge base

together with the observations . Let stand for genetically-altered penguin, for sick and let , and be as in the previous example. The Z-ordering gives us 0 , 1 and 2 . Because , we get , which is not what we expect. To remedy this kind of problems, a more re?ned ordering is required.

0.2.2

System

: resolving remaining ambiguities by explicit means

System [GP91] can be considered as an extension of system Z, evolved by the (correct) observation that not all priorities among rules are speci?city-based. Therefore, there are priorities which cannot be extracted from the knowledge base, but should be encoded on a rule-by-rule basis. To make this possible, each default is supplied with an integer, signifying the strength with which the rule is stated. Similar to system Z, we want to make each model as normal as possible, by assigning to it the lowest possible non-negative integer permitted by the constraints. Once again, this ordering is unique. -ordering is slightly more complicated because of the The process of ?nding this presence of the strength associations, and computes the ranking of models and rules recursively in an interleaved fashion. The step by step procedure for computing the ranking for a set of defaults and its models is de?ned as follows: Let 0 be the set of rules tolerated by . For each rule with strength in 0 , set . As long as there are rules without rank, we can compute the rank for models falsifying only rules having a rank and verifying at least one of the other rules, by the formula

The de?nition for -entailment is similar to the one for Z-entailment. The additional rule strengths make it possible to re?ne speci?city-based priorities. The following remark can be made: no matter how we choose the integers assigned to the defaults, it is impossible to obtain whenever contains more

¤

?

 ?§ ? ?

6

? ¤

¤ ¨ 

 ? ? ?§

¤ § ¤ 8?W?§ ¤ ?  6 ? ?

? ¤

? ¤

6? (?

For each rule establish its

without rank by

rank which is veri?ed in such a minimal model

¨? § ?U?6 ? 

? 6 ?§ ?  W¨ 9

:

1 , we can

? ¤

? T

1

¨ )

? ?¤

I

1

T ??? 0&I § 1  T ? ¤ V8 ?  )  §  ? VT ¤ ?  )  § ¨  )   1 H ? 8 ¨  I ? ¨   1¤ ? ? 8 ?¤ I T ¨ ? ¤ T T ¨ ? ? T ?  ¤? ) ? ¤ ?I  )   H ? ¨ ? I 8 ¨  I T ¨  )  I ? ¨  I ¨  )  ?  1 T 

? 8 T

¨ ¤ ??I

T

? ¤

?

6¤ U?  W§ 6?

¤  W§ ¤ §) ?   ¤ § ¤ 6? ? ?? ?

1

? ¤

? ¤

? ?¤ 1

? ¤

6

¤

? ??

¤

? ?¤



6 W?

1

8

CONTENTS

speci?c information than . In other words: the additional tools to encode explicit prioritization cannot override the speci?city criterion, but can only help to resolve con?icts which are not speci?city-based. The input priorities in?uence the ranking of rules, but don’t dominate: they undergo adjustements so that compliance with speci?city constraints is automatically preserved. However, some of the weaknesses of system Z are inherited, among which the inability to sanction inheritance across exceptional subclasses. The user can partially bypass this obstacle by means of the rule strengths he assigns to the involved rules. However, it is intuitively not clear [GP91] why strengths have to be assigned that way, and therefore, this solution is not entirely satisfactory.

0.3 Conditional entailment
In the system of conditional entailment [GP92, Gef92], some weaknesses of system Z are remedied. Instead of a deriving a total ordering on sets of defaults, an irre?exive and transitive (strict partial) order on defaults is extracted from the knowledge base. means that the default has higher priority than the default . The The notation admissible priority orderings should re?ect the preferences implicit in the knowledge base. The resulting preference relation on models is partial as well, and favours models violating minimal sets of (low priority) defaults. Conditional entailment can be used for theories containing strict rules 2 and defaults. Both kind of rules are interpreted as classical logic formulae, i.e. and are treated as the material implication . Whether or not a priority ordering is called admissible is determined by the notion of con?ict. A set of defaults is said to be in con?ict with a default , in the context , iff , where stands for the classical consequence relation, and for the body and the head of rule , and for the subset of containing all the strict rules. The notion of con?ict is related to the notion of toleration introduced by Pearl [Pea90]: a set of defaults is in con?ict with a rule iff is not tolerated by . De?nition 3 Let be a knowledge base containing strict and defeasible rules, in which represents the subset of defeasible rules. An irre?exive and transitive ordering on is an admissible priority ordering if every set of defaults in con?ict with a default contains a default such that . The intuitive idea behind this de?nition is that when is all the evidence that is given, a default should be applied, even in the presence of sets of defaults in . A knowledge base can have none, one or more admissible con?ict with
In Geffner’s terminology, a set of strict rules and a set of defaults form together a background context. A default theory consists of a background context and an evidence set , containing information speci?c to the hand. A falsi?ed default is called violated

¨

?

?

2

1

?

¨

4 01 A ?

?

?

4 Q1

?

?

2 Q1

?

? ? ? ?



?

?

?

§

? ¤A

?

1

?

?

?

§ 8 ?  4 1

?

?

???2 ? ?

?

?

 ?§  1 ?  ?§ 7?¨?

§

?

4 1 A 3CS?

?

?

¨ 

? ? ? 1

¨ 

 ?§ ¨? 1
?

4 51

?

4 51

0.3. CONDITIONAL ENTAILMENT

9

priority orderings. Whenever there is at least one admissible priority ordering, is called conditionally consistent. The concept of conditional consistency is similar to Z-consistency, p-consistency and -consistency. Example 3 For a knowledge base

no admissible priority ordering can be found. This set is not conditionally consistent. is a model of , meaning that satis?es all strict rules in , Usually, when some defeasible rules of will be applicable, but not applied in . These rules can be considered as falsi?ed or violated rules, and will be denoted by . De?nition 4 Let be a knowledge base containing a set of strict rules and a set of defeasible rules . An admissible prioritized structure is a quadruple , where stands for the set of interpretations, is a priority ordering over admissible with and is a binary relation over such that for two interpretations and , we have that iff and :

Priority orderings may not contain in?nite ascending chains 1 2 3 With this restriction, it can be shown (see [Gef92]) that when is a prioritized structure, the pair is a preferential structure [KLM90, Mak89, Sho87a], meaning that the relation is also irre?exive and transitive. In a preferential structure , means that is preferred to . is a preferred model if there is no model preferred to . Therefore, conditional entailment can be considered as an extension of preferential entailment, de?ned in terms of the class of admissible prioritized structures, induced by the admissible priority orderings on defaults. The following de?nition shows that the attitude towards con?icting defaults can be considered to be indirectly skeptical. De?nition 5 Let be a defeasible theory consisting of the knowledge base and a set of observations . A literal is conditionally entailed by , denoted , iff holds in all the preferred models of of every prioritized structure admissible with . It can be shown (see [Gef92]) that only minimal prioritized structures, induced by minimal admissible priority orderings, need to be considered. An admissible priority ordering is minimal when no set of tuples can be deleted without violating the admissibility constraints. As a result, the cost of computing conditional entailment can be considerably reduced. Another remark that can be made is that no admissible prioritized structures exist for conditionally inconsistent sets of rules. Because conditional entailment is de?ned in terms of such structures, it is restricted to be used for conditionally consistent sets of rules only.

???

?



 ? I 5&I 4 1

1

1

¤

1

?



 # "? !

1

? I 451RI ? I ? § ? ? ? ? ? ? ? ? ?

? 2I ?? S¤?1 §

¤



4 Q1

?

G

¤ ?? § ?

¤

¤

?

 ¤ §??¤  ¤ §??A ?  ¤ ?¤  ¤ A ?  § ? ? § ? ?  ? ? ? ¤  ¤ ?? § ? ? ? § ? ¤ ¨? ¤ ?

¤

? b ? G

¨ I  ¨ V ?b I  I ¨ ?
¤
?

? ? ?



?

?

¤

¤

?



? 1 G

??? ? ¨? I ? §

?

¨   
? ?

?

¤ ¤ §? ?

4 31

 1
?

¤  §? I ? § ?

H G

¤

4 31 1

? §?

?

1

10

CONTENTS

Like system Z, conditional entailment sanctions rule chaining, contraposition and the discounting of irrelevant features. However, it doesn’t suffer from the drowning problem and other problems caused by the commitment to a total ordering of defaults and models, as shown in the two following examples. Example 4 Consider again the knowledge base 3

introduced in example 1. First we have to look for admissible priority orderings. The set of defaults is in con?ict with because . Likewise, is in con?ict with . Because priority orderings are transitive and irre?exive, we obtain a unique (minimal) admissible priority ordering, where and . The priority of over is an important requirement caused by the allowance of contraposition. Indeed, without , we would not be able to conclude from . This can be the priority considered as a slight disadvantage of the system, because this priority does not appear , there is a class justi?ed on speci?city grounds. For a set of observations 1 of models which violate no default, and which is therefore preferred. In these models, the literals and hold, and are therefore conditionally entailed. These inferences involve default chaining ( ) and contraposition ( ). It is obvious that cannot be a conclusion in formalisms without contraposition. When an additional observation is made, 2 gives rise to three classes of minimal models. Models of the ?rst class contain and and violate default . Models of the second class contain and and violate . Models of the third class contain and violate and . Because and , models of the ?rst class are preferred, since they violate a less important default. Therefore, the literals and are conditionally entailed, illustrating that conditional entailment properly handles speci?city information and doesn’t suffer from the drowning problem. This example also shows that conditional entailment can deal with irrelevant information: the fact that the penguin has feathers is irrelevant for concluding that he will not be able to ?y. Example 5 Reconsider the knowledge base

In most formalisms allowing strict and defeasible rules, the knowledge that penguins are birds is expressed by a strict rule. To illustrate the impact of a set of defeasible rules, they usually give an alternative version of this sort of example, saying that “typical university-students are adults”, “typical adults work” and “typical university-students don’t work”. However, as we pursue uniformity, we will adhere to the penguin example

3

T B? ? T T

  ¨

?

?I?

¨ ??

¨ 

§ ?I ? § I 
T T T 8 ? 8 T



? ¨ 

? T¤

¨ ¤ ??I

? (? ?

? ¨  ? T T  I ?  V I T ¤ I ? I ? IV I T ¤ ?I ?I I T ¤ ? V I T ¤  H ?

?

?



T

¨

T ?Q? ¤I H

¨ )

 I 8 T

? ¨  ¨ 
T

T 8

¨ ?I
T

¨ ?I? ¨

? ¨  ? T ¨ ?

¨ I

¨ ? I 8 ¨  I ? ¨  ? T ¨ ?
T T¤ T 8

¨ ? I ? ¨  I ¨  ) 



¨ 

 

? 8 T ? T

? ¨  ? T ¨ ?

? T

T 8

 1

¨ I T ¨ ? ¨ ?I ? ¨ ??   ¨ ?
? I UI ? I T ¤ T


¨ 
?

 1

? T
T

¨ ?

¨ ?
T

? ¨ T¤  ¨ 
T 8

0.4. THE ARGUMENT-BASED SYSTEM OF SIMARI AND LOUI

11

introduced in example 2. The unique minimal admissible priority ordering is given by , , , , and . As a result, there are two classes of minimal models for the set of observations : models of the ?rst class contain the literals and models of the second class contain and . Both classes are preferred. Therefore, no conclusion can be made about or , which corresponds to our intuition. Unfortunately, it can be shown that conditional entailment has a problem with inheritance reasoning, as a result of allowing contraposition: Example 6 Consider the knowledge base [GP92]

There are four admissible and minimal priority orderings. When the observation is made, all four priority orderings lead to the same two classes of minimal models. Models of the ?rst class contain and , while models of the second class contain and . This last class of models doesn’t occur in formalisms without contraposition. We get that and are conditionally entailed. However, is not conditionally entailed, whereas it would be sanctioned by most inheritance reasoners. This example illustrates that conditional entailment does not subsume inheritance reasoning. This problem is acknowledged by Geffner [GP92], but no solution is proposed. System Z suffers from the same problem. In [GP92, Gef92], Geffner also proposes a proof theory for computing the conditionally entailed literals. The proof theory is structured around the notion of arguments [Lou87, Pol87a] and uses the admissible priority orderings on rules to select arguments.

0.4 The argument-based system of Simari and Loui
Simari and Loui present an argumentative approach [SL92] to defeasible reasoning. An argument can be considered as a set of defaults indicating support for a certain literal. However, this support doesn’t guarantee that the literal will be concluded: counterarguments and speci?city should also be taken into account. The system of Simari and Loui combines features of prominent argument-based formalisms: the notion of argument of Loui [Lou87], the speci?city comparator of Poole [Poo85] and the interaction among arguments as described by Pollock in his theory of warrant [Pol87b]. The problem with Poole’s speci?city comparator is that nothing is said about how to apply it to interactions among arguments. Pollock on the other hand treats the interaction among arguments properly, but doesn’t rely on speci?city. The early de?nition of Loui was insuf?cient from a mathematical point of view.

)

T 8

¨ 

? T

T UI ? I  ?I  )  I ¤
?

¨ ? ? ¨ 
?
?

¨

? T
) &I

?

 ¨

¨ ?

? ?I ?

T

?

T 8

T ¨ ) ¨ ) T 8
? ?I

¨ ?I? ¨

?I )

? I  ?I  )  I ¤
T ) ?
?

 ? T T ? 8

 1

¨ ?  ¨  ) ¨   ¨ )
?I )

? ¤ ?I  ) 
? ?



 ? T T ? 8

?

?

I?I )



¨ ? ¨ 
H

12

CONTENTS

The defeasible theories 4 which are considered in this system usually contain a set of defaults , a set of strict rules representing necessary information and a set of observations . The rules can contain free variables, but arguments are composed using grounded instances. Consequences are derived using modus ponens and, in the ?rst order case, instantiation. Contraposition is not allowed. The only condition on a is consistent. defeasible theory containing rules and observations is that In what follows, we consider strict and default rules to be grounded. Furthermore, observations are grounded literals. In Simari’s and Loui’s argument-based system, an argument structure is a consistent set of defaults needed to derive a literal. However, in contrast to Poole’s de?nition [Poo85], this set of defaults needs to be minimal. Such a minimal set does not contain a redundant rule, i.e. a rule that is unnecessary for infering the literal. Similar to Poole, an irre?exive an transitive priority relation on argument structures is derived, based on speci?city. De?nition 6 Let be a set of observations, and a knowledge base with strict part and defeasible part in the defeasible theory . Let be a set of defaults and a literal. is an argument structure iff is a minimal set of defaults for which and is consistent. For two argument structures and such that , we say that is a subargument of , denoted . De?nition 7 Let be a defeasible theory and let 1 1 and 2 2 be two argument structures. The argument structure 1 1 is said to be strictly more speci?c than the argument structure 2 2 iff 1. for each set of grounded literals it is also the case that
?

such that 2 2 ; and

1

1

and

The idea behind this de?nition is that argument 1 is strictly more speci?c than argument 2 if every nontrivial condition which activates 1 , also activates 2 , but not the other way round. This priority ordering on argument structures can then be used to solve con?icts, by selecting those argument structures which are “better” than others. For this purpose, some relations among argument structures need to be de?ned. De?nition 8 Let be a defeasible theory and let 1 1 and 2 2 be two argument structures. The argument structures 1 1 and 2 2 are said to disagree iff 1 2 yields an inconsistency. The argument structure 1 1 is a counterargument of 2 2 at iff there is a subargument of 2 2 such
In Simari’s and Loui’s terminology, a defeasible theory is called a defeasible logic structure. Such a structure contains necessary and contingent facts, corresponding to strict rules and observations, together with a set of defeasible rules.
4



I §§





I §§

I §§



I §§



  D§ § I

I §§



I §§





 1 0&I § H

I §§ I ?

?

? ??

2 1

 G

?

H

?

2 31

§

? ?

2.

such that

2

2,

2

and

1

1.

  Q§ § I

§ § §  ??9 § ? ?¤? 2 1  ??9 ?¤? 31  ?9 § 2  ? 9 § ? ?? 2 ?  ??9 ??? 31 2  ?9 §?? ?? 1 ? 2 ? I §§



I §§

4 01

2 D1



?

?

I §§

§

H

 1 0&I § H



§

 ?I R\$? §

I §§

H

1



§

?

2 1

2 1 3¨? ?

1

§

H

 1 0&I § H

?

  ID§ § 4 31

1



  IQ§ §  ? I ? § ?RI § ? ? 2 31 ?  H

?9 §

 G

?

H

H 51 4

  Q§ § I

2 31

1,

0.4. THE ARGUMENT-BASED SYSTEM OF SIMARI AND LOUI
1 1

13

2

2

, there can be a set of argument structures For a certain argument structure interfering with , i.e. counterargueing . Among those interfering argument , which could in turn be defeated. structures, there may be some defeaters of When no defeater remains undefeated, is reinstated. This inductive approach is based on Pollock’s method [Pol87b] of de?ning which arguments survive counterarguments, although he uses only one kind of label, whereas Simari and Loui use two: an -label to indicate support, and an -label to indicate interference. or argument, where stands De?nition 9 An argument structure can be an for supporting argument, for interfering argument, and is the level at which the argument is supporting or interfering.

1

1

2

2

2

2

1

1 1

2

2

2

2

1

The idea behind this de?nition is that an argument structure retains its interfering capacity as long as it is not defeated. De?nition 10 An argument structure justi?es iff such that is an argument for . A literal is an argument-based consequence of a defeasible theory , denoted , if there is an argument structure justifying . This theory of justifying argument structures is well-behaved: it can be shown [SL92] that a subargument of a justifying argument structure is a justifying argument structure as well. In other words, when 1 1 and 2 2 are two argument structures such that 2 2 1 1 and 1 1 justi?es 1 , then also 2 2 justi?es 2. The argument-based system properly handles the examples 1, 2 and 6. More speci?cally, it doesn’t suffer from the problems encountered by adhering to a total ordering or allowing contraposition. Furthermore, the system is not restricted to consistent sets of defaults, as is the case for system Z (Z-consistent sets) and conditional entailment (conditionally consistent sets). By making the distinction between supporting and interfering arguments and considering an inductive de?nition of justi?cation, the skeptical attitude towards con?icting defaults turns out to be ambiguity-propagating. However, it can be shown that an ambiguity-propagating skeptical formalism such as the argument-based system of

  B? § C  I I ?







I

I §§

?

§



  F? § I





?

 I §§



I

?



§





I §§ I §§

  B? § I

? ?





I §§

 ? 2 ?# ?

?





I §§

G





I

I

?

?

G

Y

§

3.

is a .

1

argument iff

argument

such that

defeats



I

?

§



I

?

§



? ?

Y



I

?

§

?Y?



I

?

§

2.

1 is an argument argument iff counterargument of 1 1 at some .

?

Y

?

1. each argument structure is an

0

and an

0

argument. such that is a



I §§

?

  Q§ § I



I §§

§

a

  Q§ § I

?

a

  Q§ § I   Q§ § I   D§ § I

?

  D§ § I



?

I §§

?



 I §§  I §§   D§ § I

?Y ?

  D§ § I



 I §§ I §§ §

that

and 1 1 defeats counterargues 2

are in disagreement with each other. The argument structure of 2 2 such that 1 1 2 iff there is a subargument at , and 1 1 is strictly more speci?c than .

?

?



14

CONTENTS

Simari and Loui is still not ideally skeptical: sometimes, a literal which holds in every possible world, is not directly derivable. We will illustrate both aspects of this skeptical approach by means of an example given by Stein [Ste92].

For this defeasible theory, we get the following argument structures:
0 1 2 3 4 5 6 7 8

 8 ¨ T

¤I  T
?

¤



¨

 I ? ¨  UV T TI ? ?   )  I V )  ¨  UV T ? TI   &I ?V ) ¨ ¤I ? ) ?  ¤I ? ? ?   T  I V 8 ? T   UI ? T T ?





¨ ? ¤ ?? ?I

? ?? ? V

? ? ?

¨§ ?

??

¨

? ¨

I

 ¨  &I ? ¨  UI  )  ¨  UI  ) ¨ ) T T ¨ ? ? ?? I ? ¨ ? ? ?? I ? ¨ ? ? ?? I ? ¨ ? ? ?? I ? ¨ ? ?I ? ¤ ¤ ¨ ? ? ?? I ?  ?I ? ¤ ¤ ? ?  ? I ? ? ? ? )
?  ¨ ?§

? ? ¤

 1

Example 7 Consider the set of rules

, , together with the observation set . Let stand for seedless grape vine, for grape vine, for seedless thing, for fruit plant, for vine, for arbor plant, for tree and for plant. This defeasible theory is based on information which can be represented in the following inheritance network.

?

? ? I ¤ ?

?

¨ ? ¤ ? ¨ ? ¤ ? ¨ ? ¤ ? ¨ ? ¤ ? ¨ ? ¤ ? ¨ ? ¤ ? ¨ ? ¤ ? ¨ ? ¤ ?  ? ?I ? ¤

?

?

?

?

?

?

?

?

¤ §

§

§

§

§

§

§

§

§

?

? ? ¤



















¨

§

§

§

§

§

§

§

§

§

? ? ¤ ?

?? ¤I ?



T



¨H

? ?

0.4. THE ARGUMENT-BASED SYSTEM OF SIMARI AND LOUI
9 10

15

No argument structures counterargue 0 1 2 and 5 , and the literals and are argument-based consequences. Although the argument structure 4 is a counterargument for 7 at literal , 7 is not defeated by 4 . The reason for this is that none of the two counterargueing argument structures 3 and 4 is more speci?c than the other one. As a result, is not an argument-based consequence: 6 is an argument for , but 7 is an argument for which preserves its interfering capacity, even though it is based on the ambiguous proposition . The ambiguity about is propagated forwards, allowing it to interfere with the possible derivation of . In an ambiguity-blocking skeptical formalism on the other hand, the two rules and would defeat each other, the ambiguity about would be forgotten and the rule would be left unchallenged. Unfortunately, we can also show that is not an argument-based consequence: 9 is counterargued by the undefeated argument structure 4 at proposition , while 10 is counterargued by the undefeated argument structure 7 at proposition . However, is in every possible world or credulous extension, so that the system is not ideally skeptical. Summarizing this discussion, we can consider the levels of support and interference, resulting in the following table: Level A0 A1 A2 0 1 2 IS IS IS IS IS IS IS IS IS A3 A4 A5 IS I I IS I I IS IS IS A6 A7 IS I I IS I I A8 A9 A10 IS I I IS I I IS I I

As a result, the argument-based consequences of this default theory are the literals justi?ed by the argument structures 0 1 , 2 and 5 : and . Furthermore, Simari and Loui claim that only strict speci?city is used to derive the ordering on argument structures, but this is not entirely true: besides strict rules, the defeasible rules contained in the argument structure, and therefore a minimum of defeasible information, is used. Example 8 Consider the knowledge base

together with the observations 1 . There is no speci?city between the and , so that the argument-based argument structures consequences are and . When we only have as observation, i.e. 2 , we have that the argument structure is more speci?c than , so that the ?rst argument structure defeats the second one and the argument-based consequences are and . Indeed, in the ?rst case the default rule is not

?

 T VUI ? T

¤ ? ? ?I ? I ? ¤





T



T

? ¨ 

§

)

§

¨ ?I? ¨ ?§

¨

? V

? ?

?

?



  I ? ¨  &I  ) ? )   I V¨ I ¨ ?  H

§

?

¤ ? ? ?I ? I ? ¤

§



T

§

? ?

? 8 T

 T VUI ? T



§

T

§

¨ ¤I ?  UV TI ¨ I
T T

 T V8 I ? 8 ¨  § T ? ?   ¨ ? §  T V8 I ? T  ¨  § ? I ? ?(? V  H ? ¨ ?I? ¨ ?  1

§I §I §

?

) 

§



¨?? I ? ¨ ? ?? I §

§I §

§ 

?? ? ?

§

)

T

¨ ¨

?? ¤ § ? ? ? ¤ §

) 

T 8

?

T

 

§

?I 

§

§ §

)

) ¨

§

 8 ¨ T

§

?

?

?

¤

16

CONTENTS

used to derive speci?city, as it is not contained in the second argument structure because of the minimality requirement. However, in the second case it is part of the argument for , and therefore, speci?city solves the con?ict. This discrepancy, caused by explictly adding an observation which can be explained directly by the knowledge base, might not be what we expect. A more severe problem arises from the fact that only a minimum of defeasible information is used to determine speci?city: in some cases, the system cannot properly handle irrelevant features, as shown in the following example. Example 9 When we augment the set of rules of the previous example with the rule (“Typically, something feathered is a bird”) and we consider the observation set , we get 3 argument structures about : 1 , and 3 . The argument 2 structure 1 defeats 2 , but 3 keeps its interfering capacity, so that 1 doesn’t become reinstated. Therefore, nothing can be concluded about , while intuitively we would expect , as is irrelevant with respect to . Several other formalisms for defeasible reasoning [Poo85, Vre91, Pol92, GV95] are based on arguments. However, the structure of arguments can differ. E.g. in the formalism of Vreeswijk [Vre91], strict rules and observations can be part of an argument. In this formalism, deductive arguments (arguments based on standard propositional logic) defeat arguments involving defaults. An argument based on a single default defeats an argument based on two or more defaults. Once again, the intuitive idea here is that when is all the evidence that is given, a default should be applied, even in the presence of sets of defaults in con?ict with . The only other possibility for an argument 1 to defeat a con?icting argument 2 is that both 1 and 2 are based on a single default, where 1 is based on the most speci?c reference class. In other words, the antecedent of the default used in 2 should deductively follow from the antecedent of the default used in 1 . For other con?icting arguments, no kind of speci?city is considered in an attempt to resolve ambiguities. Since the formalism is credulous, this approach usually yields a wide number of extensions or possible worlds. In [Dun95], a more general method of accepting arguments, which are treated as abstract entities, is described.

0.5 Brewka’s preferred subtheories
The system of preferred subtheories of Brewka [Bre89] deals with ordered knowledge bases and is based on the notion of preferred maximal consistent subsets, as de?ned by Rescher [Res64]. Knowledge bases in this formalism can be considered as sets of defaults, interpreted as material implications. No additional set of observations is needed here, as observations can be integrated in a knowledge base by means of defeasible rules with empty bodies. The ?rst version of this formalism can be considered as a

 ?T  I ? 8 T

§

?

§

¨ 

?

¨ ?

§ ¨ 

?

?UI ? T T § 

T

§

§

¨ ?I? ¨

T

T

§

T¤ §

?

§



§

§

§



 T VUI ? T

§

¨ ?

I? ¨  §  ? V I T ¤ ? 

T

?

§

? H¨ T ¤

§

T

§

0.5. BREWKA’S PREFERRED SUBTHEORIES

17

generalization of Poole’s Theorist approach [Poo88], where the prioritization is given by a total ordering on sets of rules. Instead of using two levels of formulae, called facts and defaults, more levels are allowed. Furthermore, even the most reliable formulae may be defeated. The idea is to use the total ordering on sets of defaults to prefer some maximal consistent subsets, namely the ones containing the most reliable information. When there is con?icting information with the same reliability, the attitude is credulous, so that several subsets can be selected. These selected subsets will be called preferred subtheories (or subbases). De?nition 11 Let ? be a totally ordered theory. A maximal consistent subset is a preferred subtheory iff 0 contains a maximal consistent subset of . 0 In other words, a preferred subtheory of can be obtained by starting with any maximal consistent subset of 0 , adding as many formulas from 1 as possible, . Note that default with respect to consistency, and continuing this process up till implications are interpreted as material ones, so that consistency must be interpreted with respect to the classical consequence relation . Once the preferred subtheories are known, the consequence relation can be de?ned in a credulous way, saying that is a consequence if there is a preferred subtheory such that , or in a skeptical way, saying that is a consequence if for all preferred subtheories . The credulous approach yields several extensions, corresponding to the preferred subtheories. Because the skeptical consequence relation is not de?ned in a direct way but by detouring through the set of all preferred subtheories, this approach is indirectly skeptical. 5 De?nition 12 Let be a totally ordered theory. A literal is a preferred consequence, denoted , iff for each preferred subtheory of . The preferred extension is given by Although the indirectly skeptical approach to the system of preferred subtheories gives results corresponding to our intuition, it also has a drawback: the number of preferred subtheories which have to be considered can become very large, so that checking whether or not a literal is a preferred consequence can become computationally costly. A suggestion to reduce the number of preferred subtheories which have to be investigated is given by the Lex consequence relation [BCD 93] where cardinality is used as a selection tool.

The credulous and (indirectly) skeptical consequence relations are referred to as weak and strong provability by Brewka.

5

1

1

9  6 bT §

X



¨ 91

§ ? 9  6 X bT ? 91 

 TI 1I P ?US&(I ? §

1

De?nition 13 Let preferred subtheory iff such that

? be a totally ordered theory. is a Lexis a preferred subtheory and for each preferred subtheory

?



? ?

X

 § T § bT Y X

 ? ?

?

1 &I  P G



?

?

? ¤ V 2 §? G @ 9

?

P

?

I

? ?

G



?

 §bT ? ? ? ? ?  bT § ??X X  TI 1I P V&S&QWI §  G  5G § 2 ??  ¤  X § bT



 ? ?

 G

G

 2 ?? ¤

1

?

? ?

 ? ?

G

1



?

I¨ (?1

18

CONTENTS

It is obvious [BDP93] that whenever a literal is a preferred consequence, it is also a Lex consequence, because each Lex-preferred subtheory is a preferred subtheory. Although this proposal seems to be an interesting attempt to reduce the cost of computing whether or not a literal should be entailed, the Lex consequence relation sometimes gives unintuitive results, as is illustrated in the following example. Example 10 Consider the totally ordered theory
0 1 2

0

1

2

This theory can be considered as a variation on the extended Nixon-diamond [HTT87, THT87], as given in the context of semantic networks. Both the ordered theory and the semantic network are given in the ?gure below.

1

¤

¤

 ¨

¨

1 2
?

Γ
?

?

?

?

?

?

 ¨

?

¨

¨

1 2 2
? ? ?

1 2 1

1

2

?

?

¤

1 2
?

?

? ¤

 ¨

?

?

I ¤

¨

?

? ?

1

?

 ¨

I

¨

I

1 1

2 2

?

?

?

?

?

?

?

¨

?

0

?

? ¨I

1

2 1 2 2

?

?

¨?

?







 §bT X  bT § § bT



X

X

?

?

?

?

?

?

where

2,

1

 T ? ?UI ¤

 ¨

I ¤

¨

I

 ¨

I

¨

I

¨

2 1

1 2

2 2

1

1

?

?

?

?

?

?

?

?

I

1

2

? V

?? ?

# ?

G b 9

?

  G 85?§

? ?

? ¤# ? ?  ?# ? ? ?

A literal is a Lex consequence, denoted subtheory of . The Lex extension is given by

, iff

9
for each Lex-preferred . 2

§ bT

9  ¨ 1 "9 

G

§ T
?

?

91

:

a ?X



a ?X

 ?

? ¨ ? ? QWI I P

 ? §
?

?


X I
?

and

I

X

I

X

?

X (?

G

§

¨

X

?



?

¨

¨

?

?



X

G

0.6. ORDERED LOGIC AND BASIC DEFEASIBLE LOGIC
?

19
? ?¤

The interpretation given to the example is the following: For 1 ( 1), it is a good thing to take 1 ( 1). On the other hand, when a person has 2 ( 2), 2 ( 2) could probably help, but taking 1 could make things worse. For 2 , no side effects can be shown, and taking this drug normally doesn’t make a patient sleepy ( ). 1 however can make a patient sleepy. John is very unlucky, because he has both 1 and 2 , and doesn’t know what to do. There are three preferred subtheories, given by
?

3

Only 3 is also Lex-preferred. As a result, following an indirectly skeptical approach, the preferred extension is given by 1 2 2 , and the Lex extension by 1 2 1 2 . The preferred extension corresponds to our intuition and illustrates the fact that the system of preferred subtheories has no problem with propagating ambiguities: the ambiguity about 1 is propagated forwards, allowing it to interfere with the derivation of . The extension obtained by the Lex consequence relation seems unacceptable for this example: taking 1 is a possibility which should not be totally excluded. Whether John has to take 1 depends on the seriousness of the case and the judgement of the doctor. Realizing that it might be dif?cult or even impossible sometimes to decide whether a rule is of more, less or the same reliability as another rule , Brewka proposes a second generalization in which it is possible to deal with partially ordered knowledge bases. In this second version, a strict partial order is given on the set of rules . Again, preferred subtheories can be de?ned based on this ordering.

It is obvious that we can translate such a set of partially ordered rules into a general ordered theory by creating a unique node for each rule, containing this rule, and by translating the partial order on rules into one on nodes.

0.6 Ordered logic and basic defeasible logic
Basic defeasible logic [Nut92, Lae90, GVN94, Gee96] and ordered logic [Lae90, GVN94, Gee96] are two related formalisms: both are directly skeptical approaches with a proof theory based on the concept of a proof tree. A proof tree contains positive conclusions for derivable formulae and negative conclusions for demonstrably nonderivable formulae. Negative conclusions are needed to show that a rule can only be

 ? S§ I 1

¤

1



?

1

6 1  ?§ 1 

?

?

?6 1 ?1

?

6 1

De?nition 14 Let be a ?nite set of rules and maximal consistent subset is a preferred ordering 1 2 , , of respecting such 1 when 1 is consistent with 1

a strict partial ordering on . A subtheory if there is a strict total that with 0 and , or otherwise. 1

? ¤

1

 ¨

 ¤? ?  ??? ?

?

I ¤

?

?

?

I

1
?

1

?

?

?

?

?

?

I

?

?

?

?

 ¨

I

?

?

¤

?



?

?

 5?§ 2 ¤  G

I

?

?

¨

?

1

? ¤  I

?

I

? ?

?

1

6 ? W?

1

?

¨I

?

I

 ?? §

?

?

?

I

¨

???

1

? ? W? ? 6 1  6 ?? I ?? §

?

2

? ¤

¨  ¨

?

I

?

?

¨

?

I

?

?

¨

?

I

?

¨I

?

¨

?

1

? ¤

¨

I

¨

I

¨

I

¨I

1 1 1

2 1 2 1 2 2

1 2 1 2 2 2

2 2

1 2

2

? ?¤

) ?¤  ?

?

) ?¤  ?

?

?

?

 ¤? ?
?

?

?

?

? ?¤

?

?

) ?¤  ?

?

?

?

?

?

? ?¤

 ?? ?

) ?¤  ? ?  ¤\$? ? ?

?

?

¨

?

?

¤

I







?

?

?

?

?

?

?

 ¤? ?
? ? ?

  G 5?§

?

?

?

?

 ¤? ?
? ?

? ?6

# ¨? §

?

?

1

20

CONTENTS

applied whenever no potential defeater is applicable. Nute’s early work on defeasible logic [Nut85, Nut88] was designed to be used for a single-perspective or single agent system, and is based on an implicit partial ordering on rules, resulting from speci?city information. As a response to this early work, ordered logic presented a formalism suited to be used in multi-perspective or multi-agent environments [VNG89b], by structuring rules in an explictly given partially ordered set of perspectives. In general, a formalism with an explicit means to express priorities can be seen as a generalization of a related formalism using implicit speci?city, because not all priorities are speci?citybased. An additional advantage of ordered logic is that the ordering is on perspectives, i.e. on sets of rules, instead of on rules, making ordered logic well suited for reasoning with multiple perspectives or multiple agents. The family of defeasible logics presented in [Nut92] contains a variant on Nute’s original defeasible logic where an explicit ordering is given, but here the ordering is on rules instead of on sets of rules. Regardless of the origin of the partial order, the idea that is used in the proof theory remains the same: an applicable rule will be applied only if every competing rule is either weaker, or can be shown to be not applicable. Both formalisms interpret rules in a unidirectional way, avoiding contraposition. Their skeptical character turns out to be ambiguityblocking: as soon as an ambiguity cannot be solved by the priority ordering, they forget about it, so that it cannot interfere with other conclusions. For ordered logic, all rules are defeasible. Rules corresponding to observations and strict rules are simply assigned to a high priority perspective. Besides default rules, Nute’s defeasible logic also takes observations, strict rules and defeaters into account. Defeaters never directly support conclusions, but can defeat rules that otherwise might be applied. The rule “Something that looks red under red light might not be red” is an example of a defeater. Except for some minor differences, mainly caused by the presence of strict rules and defeaters, the proof theory of the explicit version of Nute’s defeasible logic is similar to the proof theory of ordered logic.

0.6.1

Implicit version of Nute’s basic defeasible logic

We will start with describing Nute’s earliest work on defeasible logic [Nut86, Nut88, Nut90] in which speci?city is used to derive an implicit partial order on rules. Although in this early work, proofs are sequentially structured, we will present here a modi?ed version [Nut92] where the proof theory is based on the concept of a proof tree, clarifying the structure of the proof. A default theory following Nute can contain strict rules, defeasible rules, 6 defeaters and observations. The evidentiality symbol is used to create -sentences: where is a literal, can be read as “Evidently, p”. A sentence is a literal or an -sentence. The inference mechanism will avoid using rules that may later turn out to be defeated by restricting application to those rules that will de?nitely be not defeated. For any rule that is applied,
? ? ? ?

Nute uses the symbols a defeasible rule.

6

and

in the opposite way: in his logics,

indicates a strict rule and

 ?



?

?

?

0.6. ORDERED LOGIC AND BASIC DEFEASIBLE LOGIC

21

the proof theory will ?rst require that we show that no potential defeater is applicable. This is done by not only inferring positive conclusions like “p holds”, denoted as , but also negative ones like “demonstrably, does not hold”, denoted as . A rule 1 can only be defeated by a con?icting rule 2 when 1 is not superior to 2 . The idea is that every strict rule is superior to every defeasible or interfering rule. For the set of defeasible and interfering rules, one rule is considered to be superior to another if the antecedent of the ?rst rule is more speci?c than the antecedent of the second one. Originally, Nute allows only strict rules to determine the speci?city relations among antecedents. This kind of speci?city is called strict speci?city. Following the idea of strict speci?city, a defeasible rule is said to be superior to another defeasible rule , iff for each , a proof exists for , given the observation set , and for some , a proof exists for , given . The resulting defeasible logic will be called , indicating that only strict rules are used to uncover the implicit speci?city information. With the defeasible logic , several examples of nonmonotonic reasoning can be solved correctly. However, strict speci?city is not suf?cient: sometimes defeasible rules should also be used in determining speci?city, as illustrated in the following example.

This de?ciency is dealt with by Nute [Nut92] by introducing what is called defeasible speci?city, meaning that strict and defeasible rules are used to determine speci?city. such that a defeasible rule The basic idea is to simply adopt the proof theory of is superior to a rule just in case that for each there is a proof for , given the observation set and there is a proof for , starting from , for some . But the following example given by Nute [Nut92] illustrates that this approach is not quite right.

and observation set . This default theory can be interpreted as follows: bats ( ) are mammals ( ), bats normally ?y ( ), mammals normally do not ?y, mammals with a sonar ( ) are normally bats, and we consider a particular bat which, presumably, based on using the criterion has a sonar. It is possible to construct a proof for of defeasible speci?city just described. However, we can also construct a proof for based on by using the defeasible rule . For this theory, we get that the bat is a mammal, but also that the mammal is a bat, so that neither nor can be shown to be superior to the other one.

T 8

¨

?

T

¨ ?

? ¤

?

?

?

¨ I ? ??C? ? I T  ¨ ¨ ?¤I

?

¤

?

¨

?

G

Example 12 Consider the defeasible theory

with rules

?

) ? D? ? A D?

? ??

?

?

T

?

?I T

?

§   ¨

¨ ? C? I

T

¨ ?

? V

and observation set that is superior to

. Using , based on strict rules, we cannot show , while intuitively, this is what we want.

? T

¨ ? I 8 ¨  I ? ¨  ? T

G

Example 11 Consider the defeasible theory

with rules

?

? 

? ?
?

? ??

?

?

??

?

?

? )

? ¤?

?



 ¨ §

? C? A

 1

?

? (?

? ? ? § ¤? A

?

?

?

?





?

H

H  1

?

? ?

)

?

§

¤

  ¨
A \$) T 8

? ? ? §  ¨

¨ 

?

?? ?

?

§

22

CONTENTS

In order to solve this kind of problems, Nute limits the rules that can be used in determining defeasible speci?city to the strict rules, the interfering rules, and the defeasible rules with non-empty antecedents. Let denote this subset of defeasible rules with non-empty antecedents, i.e.

The resulting defeasible logic will be called , referring to the use of defeasible 7 speci?city . In the proof theory, nodes get labels composed of three components: the ?rst one represents what is being proved, the second one the set of literals which we consider to be true (the observations), and the third one the set of defeasible rules under consideration. The observational component is needed to show that one rule is superior to another one. The set of defeasible rules integrated into a label will mostly be the original set of defeasible rules, but it can be reduced to the subset of defeasible rules with non-empty antecedent, when speci?city is to be determined. be a defeasible theory. Where is a sentence (i.e. a De?nition 15 Let literal or an E-sentence) and is or , a proof tree for in using is a ?nite tree where each node is labeled , where is a sentence, is or , is a set of literals and is a set of defaults such that the root is labeled and each node satis?es one of the following conditions:
? ¤

7 In [Nut92], where defeasible logics are represented as sets of conditions which have to be satis?ed by each node in a proof tree, is originally called , standing for the set of conditions

%

?

? ?

 

?

?

 

? #?



¨

 

¨



 ' 

§

? ?

is originally called
  

, standing for the set of conditions

?

I

? I ? b ?

% &

? ?

 



 ? ?

?

 \$

? #?

 "

¨

 ¨

?

¨

 "!    

? A ¤?

§ ? ¨??

?

I

?

?

(D5)

is labeled ( is a defeasible rule

) and

has a child node labeled ( such that

) and there

?

?

I

? I ? b ?

?@? A ? D§ A ) I

2 31 A b ?

?

?

?

2 31

¨?§ ? I ? Q? ?

?

I \$? I ?

? ?

?

I

? I ? D? )

?

(D4)

is labeled ( ) and has a child node labeled ( ) and there is a strict rule such that for each has a child node labeled ( ) and for each , there is and a child node of labeled ( ).

?

I \$? I ?

?

?

I

?

(D3)

is labeled (

) and

has a child node labeled (

2 A 01 ¨?

?

?

I

?I ?

)

? ?A

?

?

AS? ? § ? I ? I Q? ?? ? I ? Q? ?

?

I

?I ?

?

§

A )

?

(D2)

is labeled ( ), and a child node of

, and for every strict rule labeled ( ).

, there is

).

2 1 A ?

?

?

I

§ ?I ?

)

?

A ?

? D§ A ) I

?

I

?

?

(D1)

is labeled ( such that for each

) and either or there is a strict rule has a child node labeled ( ).

?

 451&I I 2  § ¤ ¨H ? ?

?

?

? §

G



2



? 5CB¨ 4 1 A  ?
? ?

:
?

? 4 ?1

?

 ¨? I

?

 ¨

?I

? ¤

? ? ?§

¤ 51  ? 51 4 4

¨

¤  1 0&I § H

?I ?

 G
?

?

? ?

?

0.6. ORDERED LOGIC AND BASIC DEFEASIBLE LOGIC
?
?

23 ),

2) for each strict rule

, either ), or has a child node
?

a) there is and a child node of labeled ( ), or such that for each has a b) there is a strict rule child node labeled ( ), or c) there is a defeasible rule or an interfering rule such that for each , has a child node labeled ( ) and either for each has a child node labeled ( ), or there is and a child node of labeled ( ). Condition (D1) captures the monotonic derivability of a literal, while (D2) shows when a literal is demonstrably not monotonically derivable. (D3) says that any literal that is monotonically derivable is also evidently the case. (D6) expresses that a literal can be shown to be not evident when its complement is monotonically derivable, unless the literal itself is also monotonically derivable. Conditions (D1), (D2), (D3) and (D6) can be considered as the monotonic kernel of the defeasible logic . Condition (D4) says that the consequent of a strict rule is evident if its antecedent is evident, the complement of its consequent is not strictly derivable and the rule is not defeated by another strict rule. Condition (D4) could be replaced by a stronger one [Nut92], where strict rules are used “more strictly” than here, in the sense that they are not allowed to defeat each other. (D5) says that the consequent of a defeasible rule is evident if the complement of its consequent is not strictly derivable, its antecedent is evident, the rule is not defeated by a strict rule, and the rule is superior to any other
?
? ?4 &D§ I ? 1I ? 4 1 I  ?7&RI ) ? D? ? \$? I ? ? I A b ?  ?

? I ? Q? A

?

?

?

I

?

? I ? D? )

?

?

?

?

?

2 1 A ?

A ? Sb

?

?

?

I \$? I

A S?

? D§ A ) I  D? A 

¨

 ??

¨ §

3) for each defeasible rule

, either

I

? I ? D? )

?I ? A

?

?

2 1 A

? ?

?

?

I

?b ? ?A

 A C3?

?I ? ?

§

a) there is b) there is labeled (

and a child node of labeled ( such that for each ), and

?

I

?I ?

2 1CA ? ?

? §

§

A )

?

)

6 71

?

?

(D7)

is labeled ( 1)

) ),

has a child node labeled (

?

?

I

? I ? I ? Q? ? ?I ? I ? ?  I ? Q? ?

?

?

(D6)

is labeled ( child node labeled (

),

has a child node labeled ( ).

? ? \$? I ? ? I ? ?4 &RI ? Q? 1I  ) ??5&IQ§ I 4 1 ? ? ? ? \$? I ? ? ? I

?

?

?

§ A )  S? A  A C3?

a) there is b) for each for some

and a child node of labeled ( , there is a child node of labeled ( , there is a child node of labeled (

), or

) and

6 1 Fb A ?

?


?

A ? Fb

¨


3) for each defeasible rule either

or interfering rule

) and ). has a

?
,

? A

?

2 A ? 01 Fb

2) for each strict rule labeled ( ), and

, there is

I \$? I

?

?

?

I \$? I ?

? D§ \$) I A

1) for each

has a child node labeled (

) ? D?

and a child node of

? ?

24

CONTENTS

defeasible or interfering con?icting rule which cannot be shown to be non-applicable. (D7) says that a literal is demonstrably not evident if the literal is demonstrably not monotonically derivable and every rule which could derive the literal can be shown to be non-applicable or defeated. De?nition 16 Where is a defeasible theory and a sentence (i.e. a literal or an E-sentence), is -derivable from , denoted , if there is a proof tree for in using , and is demonstrably not -derivable from , denoted , if there is a proof tree for in using .
?
? ? ¤ ? ? ?  ?? ??? G  ? ¤

Example 13 Reconsider the defeasible theory from example 11. The proof tree below is -derivable. A part of this proof tree deals with showing that shows that is superior to . Because this example doesn’t involve defeasible rules with empty antecedent, the third component in the labels can be omitted.

0.6.2

Ordered logic

The goal of ordered logic is to provide a theoretical foundation for knowledge based applications which support nonmonotonic or defeasible reasoning and which incorporate the knowledge of multiple experts in a principled way. The logic makes it possible to explicitly model internal perspectives or multiple agents and to resolve con?icts between competing perspectives without obscuring their opinions. While useful nonmonotonic formalisms are available in which priorities are taken into account, they

 (? I ? ? ?

 ?

? I ? §

?

 ?§

 V I ? ?

 V I ? ?

?  ?§

? §

 V I ? ?

?? ?§

 V I ? ? ?

 V I ? ?

? §

T ? 8 ? §

 V I ? ?

 ? I ? ?

?  ?§

T

? §

?

With the proof theory
? ¤

, the examples above can be correctly solved.

G

? ¤

?

?

?

?

?

G

?



G



?

?

? ¤

?

?

¨ ?

?

?

G?

?

?

?

?



?

? ? ¤ ? §?? G
T

G

 ?

  ?

 V I ? T § ? ?

T 8

¨ 

0.6. ORDERED LOGIC AND BASIC DEFEASIBLE LOGIC

25



§

 ¨ §

26

CONTENTS

that causes the problems. We could also say that in typical or normal cases where every member of is true, so is . But we can and often do adopt con?icting rules and , where it is possible that everything in both and is true. Such con?icts can only be resolved by giving one of the rules precedence over the other. One might interpret this as meaning that one rule is more reliable than the other, but has precedence over . that is not the interpretation we intend. Suppose This does not mean that is more reliable than in the sense that we are better justi?ed in adopting than we are in adopting . Each rule could be the very best possible rule for the case where its condition is satis?ed, “all other things being equal”. It is just when and are both satis?ed, all things aren’t equal where is concerned. A situation where and are both satis?ed may not be a typical or normal situation in which is satis?ed. The possibility of giving precedence over , by putting at a strictly higher node, offers a way of solving an ambiguity in a theory where intuitively there should not be one. Obvious examples of such theories are taxonomic hierarchies in which subclasses don’t answer the description which is typical for the class to which they belong, such as the penguin example (example 11). Whereas examples of this kind can also be correctly solved by speci?city-based formalisms, the explicit priority structure can be used to solve many other problems. Another way of looking at the partial order is as an “in?uence” relation between and are perspectives in ? with and , then perspectives. If is a perspective that is in?uenced by perspectives and . Typically, there will be a top perspective 0 such that 0 for all perspectives ?. 0 can be regarded as the ?nal consolidation of all perspectives in the theory. Similarly, there may be a unique bottom node. Again our proof trees will need positive conclusions like “ holds” (denoted as ) and negative ones like “demonstrably, does not hold” (denoted as ). Conclusions are derived with respect to a certain node, and since each node in an ordered theory can represent a distinct perspective, different conclusions will normally be derivable at different nodes. The ?nal integrated conclusions are the ones that hold in the unique top node (if any). In contrast to Nute’s approach, no evidentiality symbol is used. De?nition 17 Let ? be a partially ordered defeasible theory, a literal and . An - proof tree for at a node in is a ?nite tree 8 where each node is labeled , where is a literal and is or , such that the root is labeled and each node satis?es one of the following conditions:
This proof theory is similar to a theory presented in [VNG89b], but there is an important difference. In the version presented here, rules at higher perspectives have precedence over rules at lower perspectives. In the earlier version, higher perspectives could only “see” lower perspectives, but lower perspectives took precedence. This is less natural than the current approach for modeling multiagent reasoning, but it is a promising theory for defeasible object oriented programming, see [LVVC89]. The proof theory presented here can be found in [GVN94], where the symbol is used for defeasible rules.
?

8

2



 ¨ §

  ¨ 

? ?X ? VX a

?



  ¨

?

P b6 X X a ?X 6 ? ?X ? X

?

§

  ¨

G

?

?

6

 ?§ ¨
6 X
¤

X

?

§

¨

X

 ¨ §

?

§

?

2



?

 ¨ §

 TI 1I P ?US&(I § ?  H G



 ¨ §

?

? ?X



?

 ¨  ?

a ?X

  ? ¨
I6



§

?

X

?

?

? I ¤ S¨

?

X

?

A 0¤

 ?§ ¨
A 6

? ?X
X

0.6. ORDERED LOGIC AND BASIC DEFEASIBLE LOGIC

27

Condition (OL1) expresses defeasible rule application: a rule can be applied only if its antecedent holds and it is not defeated by an applicable competing rule. Condition (OL2) states that we can show that a literal doesn’t hold if all rules that could conclude it are either not applicable or defeated by a competing rule. Condition (OL3) allows one to conclude , when the only way to satisfy is to satisfy , which is e.g. the case for a theory containing a single rule . Intuitively, the existence of a proof tree for at a perspective in means that is provable at in . The existence of a proof tree for at perspective in means that we can show that cannot be proven at in . De?nition 18 Let ? be a partially ordered defeasible theory. A literal is OL-derivable from at node , denoted if there is an OL-proof tree for at . Such a literal is also called an OL-consequence of at . A literal is demonstrably not OL-derivable from at , denoted if there is an OL-proof tree for at . When the node under consideration is the unique top node, we simply say that is OL-derivable from (demonstrably not OL-derivable from ), denoted ( ). Example 14 Consider the ordered theory
0 1 2

2

1

and
0 1 2

? ?



? ? ¨?¤?I ? ? ¤

X ?

¨ ?

¨

¨

X ?

?

?

?







X

where

0





G

G

X G

X

X



G

?

 ? ???

?



G

 TI 1I P VUS&(I ?

 ? ? ???

? ?



G

?  ¨  

G

X

X

X

I

G

X

I

G  TI 1I P VX &S&QWI §  G

 §bT X  §bT § bT



X (?

G

§

X

X

?





?

? ?



G

?

?



? ?? G

X

X

?

?





?

(OL3)

is labeled and has an ancestor labeled labeled nodes in between.

? A C5?

?

node labeled

.

such that there are no positively

?

6

P



§ ? A b T ?

¨

?



2.

, where for each

and

? a VX ? ? X § A )

X

? X

? )

? ?X

?

1.

has a child node labeled

for some

; or , such that has a child

6

P



§ T A ?

? ?

?

(OL2)

is labeled

and

, where

, either

?

? 3? A



X

?

a ?X

6

a VX

P

??

¨ ?§ 



§ T bCA ?

 ¨

?

2.

where child node labeled ;

and

a?X ? ? X A )

§

X

? X )

? ?X

?

1.

has a child node labeled

, for each

; and , such that has a

6

P



?

§ T A ?

¨ ?§ 

?



?

(OL1)

is labeled

and

, where

X

a ?X

a VX

?

such that

X

?

? ?? G

? 

28

CONTENTS

In this example, stands for rain, for sunny and for being in Belgium. This theory can be interpreted in different ways. From a single perspective point of view, a person could be walking in the borderland between Belgium and France, without knowing exactly on which side of the border he is. He knows that Belgium is a country where it frequently rains. However he believes that, when the sun is shining, it will not be raining, regardless whether he is in Belgium or not . At node 1 , he assumes that he is in Belgium, but he knows nothing about the weather. Therefore, he concludes that it will probably be raining: the rule is applicable at 1 while its competing rule is not . When suddenly the sun starts to shine brightly, he becomes very sure about the weather, information captured at node 0 . Therefore, with the information available at node 0 , he will conclude that it will not be raining: is applicable at 0 and all rules at or below 0 with consequent are weaker (i.e. at a node below 1 ). The same conclusions can be made when we look at the example as containing the knowledge of two experts. Expert 1, who ?nds himself in a darkened room, has the knowledge contained in perspective 1 and concludes that it rains. Expert 2 can take a look outside and sees that the sun is shining. He knows more than expert 1, namely what is available at perspective 0 , and concludes that it doesn’t rain. Example 15 Consider the ordered theory
0 1 2

1

0

2

and
1 2

This is a typical example of a perspective ( 0 ) that is in?uenced by two other perspectives ( 1 and 2 ). When asking advice about the weather prospects for tomorrow, the “expert” at perspective 1 believes that the weather will be bad ( ) and that you should take an umbrella ( ) with you when you go for a walk. The “expert” at 2 believes the weather won’t be bad. Therefore, at perspective 1 , the conclusion holds where is obtained by applying . At perspective 0 , the condition used to derive at 1 does not hold since it is defeated by at 2 . Rule is therefore not applicable at 0 , and cannot be proven at 0 . This proof theory is well-behaved, i.e. we can show that no literal is at the same derivable and demonstrably not derivable. In other words, when is a time literal, we don’t have and at the same time. However, it can be the case that nothing can be proven about some literals, as shown in the following example.
?

?

X



X

? ?X

??

 ¨

X

X

?

?

?

? ? ?  ¨ ¨ I ? ?? ? Q?? ¨

?

X ?

?

?

?

¤

¨

X

? H

X

?

I

? ??

 ?? ?

X ?

?

?

X





G

X

where

0

? b

¨ ?¤

X

X

 TI 1I P VUS&(I ?

?

?

X

?

X

I

¨ ?

X

X

I

¤

X (?





§

X

X

X

X

§ bT § bT

 ? ?? ?

X

?

?

X

G

?

?

X

X

?

?

?

X

¤

?

? H

? b
?

¨ ?? ?

X

¨ ?¤

??

X

0.6. ORDERED LOGIC AND BASIC DEFEASIBLE LOGIC

29

1

Example 16 Consider the ordered theory
0

with
0

0.6.3

Explicit version of Nute’s basic defeasible logic

In his family of defeasible logics, Nute also surveys a logic for dealing with explicit priorities [Nut92, GVN94], which we will call . An important difference with ordered logic is that in , the partial order is given on the set of defeasible rules and defeaters, instead of on nodes 9 . When a defeasible rule competes with a strict rule, the defeasible rule is always defeated. To adjudicate between two defeasible rules or between a defeasible rule and a defeater, the partial order is consulted. be a defeasible theory and let be a partial order on De?nition 19 Let . Where is a sentence (i.e. a literal or an E-sentence) and is or , a proof tree for in using is a ?nite tree where each node is labeled , where is a sentence and is or , such that the root is labeled and each node satis?es one of the following conditions:
?

? ?

%

?

? ? ? ? #?  ? ??   ¨  

9

In [Nut92] the logic

is originally called .

, standing for the set of conditions

?

 ? ?¤ ? ?

Furthermore, it can be shown that two complementary literals cannot be at the same time. In other words, when is a literal, we don’t have both .

¤

? H

G

?

?

?

¨

¤

P

2

?



?

? D?





 1 0&I §  G H

?

?

?

?

? Q?

?

?

¤ ? D?

? H

It turns out that However, using tree of at 0 .

doesn’t hold at 0 , because there is no -proof tree of , we cannot show that doesn’t hold, because there is no

at 0 . -proof derivable and

??

 ¨

X

X

? H ?

X

0

? H

 T ?  VUI V

? ?

?

?

 ¨  I ¨ 

??

¨ ??

¨ I  ¨

¨

X

?

?



I &I ? ¤

X



X

X (?

§ T

§

¨



? b

¨

?

 

G

X

?

¤

? ¨
¨

¨



¨ ?

2

? ??

?



¨
¤
6 71

2



  

?

4 51

 

G

30

CONTENTS

using defeasible speci?city, This proof theory is similar to the one for except for conditions (D5) and (D7), where now the explicit partial order is used for resolving con?icts instead of speci?city-based arguments. This explicit partial order is also the reason why we no longer need to include a set of literals into the labels. Note that the partial order is given on defeasible and interfering rules, so that no defeasible rule is ever superior to any strict rule in conditions (D5) and (D7). De?nition 20 Where is a defeasible theory, a partial order on and a sentence (i.e. a literal or an E-sentence), is -derivable from using , denoted , if there is a proof tree for in using and , and is demonstrably not -derivable from using , denoted , if there is a proof tree for in using and .

G 6 B? Q1 1 4



?

? ? ? RI ? ? ?

P

?



?

?§? ?? G ? ? Q? ? ?



? D? )

 ?¨C5? ?§ ? A   ? ? ?§

a) there is and a child node of labeled such that b) there is a rule has a child node labeled for each .

?

? P

?

G

? D?

?

?

?

P

?

? b   ?§

?

?

671F? ? 451B? 251 A ? ?  ?§ ? ?¨CA ) 4 1 5F? 2 CS? 1 A

2) for each rule

with

P

G

? ?

? ?

?

?

? Q?

 1 0&I §  G H

G ?  ? Q? ? ? ? ? ? ?  ? ????

G

?

1)

has a child node labeled

? ? ?

?

(D7)

is labeled

and , either , or and

?

? ?

? I ? ? ?

? ? b?

(D6)

is labeled .

has a child node labeled

and

has a child node labeled

?

¨ §

?

?

?

?



  ?§ 3

?

 ?§ ? A ?¨C3? 6 1 4 1 7E? 7E? 2 1 B? A

2) for each rule there is

with and a child node of labeled

, either .

? ?

? D§ \$) I A

1) for each

has a child node labeled

? ? b

) ? Q?

?

4 1 A 5FS?

¨ §

?

(D5)

is labeled rule

and has a child node labeled such that

and there is a defeasible

, and , or

??

?

?

each

) ? D?

? ? b

? A C7? ? Q§ ¨) I A

?

231CA ?b ? 2 1 A 3E\$?

? ? Q?

?

? ?§

(D4)

is labeled

and has a child node labeled and there is a strict rule such that for each has a child node labeled and for , there is and a child node of labeled .

?

?

? ? ?

?

(D3)

is labeled

and

has a child node labeled

.

§

A \$)

2 01 A ?

?

? )

?A

? ?I RV? ?

? ? ?

?

(D2)

is labeled a child node of

, and for every strict rule labeled .

, there is

2 01 A ?

? §

?

)

A \$?

H

? ID§ A ) ?

?

(D1)

is labeled for each

and either or there is a strict rule has a child node labeled .

? §

H

?

such that

and



P

0.6. ORDERED LOGIC AND BASIC DEFEASIBLE LOGIC

31

0.6.4

The preemption problem

Ordered logic and all versions of basic defeasible logic presented thus far all suffer from the preemption problem. This problem emerges in the context of inheritance reasoning with exceptions. Let us illustrate the notion of preemption by means of an example [GVN94]. Suppose that normally a computer science professor at a junior college is poor, even though computer science professors at junior colleges normally have a Ph.D. in computer science, and people who have a Ph.D. in computer science normally are not poor. Suppose also that ne’er-do-well, disinherited scions of wealthy families normally are poor, even though such individuals are clearly scions of wealthy families, and scions of wealthy families normally are not poor. If John is both a computer science professor at a junior college and a ne’er-do-well, disinherited scion of a wealthy family, we would intuitively conclude that John is poor. However, if we represent this knowledge in an inheritance network, we have to face the problem [THT87] that none of the positive links to the property “poor” is more speci?c than both negative links to the same property. The same problem arises in ordered logic and Nute’s defeasible logic, after translating this inheritance network into an ordered theory, and adapting a skeptical attitude. To solve this problem, inheritance reasoners like SIR [HTT87] impose the requirement that a compound path is permitted only when every con?icting path is preempted. More speci?c, SIR requires that a positive path is permitted provided only that the part up to the last link is permitted and for every negative link competing with the last link, either there is no permitted positive path up to its start node or there is another positive link such that there is a permitted path through the start node of this positive link ending in the start node of the negative link. Using this principle, we arrive at the conclusion that John is poor in the inheritance network resulting from the example. We can translate this principle into ordered logic by making the restriction that a rule can only be defeated by a competing rule which is not itself defeated by a strict competitor. This preemption principle can easily be integrated into the skeptical proof theory for ordered logic, yielding the following proof theory. De?nition 21 Let ? be a partially ordered defeasible theory, a literal and or . A proof tree for at node in is a ?nite tree where each node is labeled , where is a literal and is or , such that the root is labeled and each node sastis?es one of the following conditions:

6

P



§ BA ? T

¨ ?§

? ?

?

(OL2)

is labeled

and for each rule

, where

, either

 A C3? 6 P`§ X ? X

X

a ?X

?

a X

6

P

?

??



? ?X § bT A b ?

?

§

¨

X

?

2.

where and , a child node labeled , or there is a rule and , such that has a child node labeled

 § bTA ? ¨  § ? X A ?@Q?  ? a?X ? ? X A )

§

X

? X )

? ?X

?

1.

has a child node labeled

, for each

; and

6

P



?

§ T A ?

¨ ?§ 

?



?

(OL1)

is labeled

and

, where

such that

such that has , where for each .



2



X

a ?X

G

6

¤

X

a VX

¨

2   TI 1I P ?US&(I §  G
?

?

?

¤

?? ¨¤
?

32

CONTENTS

If we introduce the propositions (poor), (computer science professors at junior colleges), (disinherited ne’er-do-well scions of wealthy families), (holders of a Ph.D. in computer science) and (scions of wealthy families), we can formalize the example in the following ordered theory. The original OL proof theory, given in de?nition 17,
?

would derive no conclusion about whether John is poor or not, while the proof theory extended with the preemption principle arrives at the intuitively correct conclusion that John is poor. Similar solutions are presented for the family of basic defeasible logics [Nut92].

0.6.5

Ryan’s formalism of ordered theories presentations

Ryan [Rya92] proposes a framework for reasoning with ordered theory representations which is comparable to ordered logic. Instead of providing an ordering on sets of rules, the ordering is given on sentences. Whereas ordered logic is originally a directly skeptical formalism, Ryan’s formalism can be considered to be indirectly skeptical: the entailed conclusions are the ones that hold in all maximal models, where maximality is understood according to an ordering of interpretations which favours those satisfying as many (high priority) sentences as possible. Due to the use of sentences instead of sets of rules, another ordering is required: for each sentence, a satisfaction ordering on interpretations is de?ned re?ecting the degree to which an interpretation satis?es the sentence.

  ¨

 ¨ ?

?

? ?

?

?

)

? ¨

¨

¨ ?

¨

)

)



?

?

? ?

  ¨

 ¨

)

?

?

?

(OL3)

is labeled and has an ancestor labeled labeled nodes in between.

such that there are no positively

¨



?

?

? D? A

node labeled and

 3? A  § bT @ § A X ?

6

P

?I ? § 6 V§ P ??X X X ?X  § ? A b ¨ ?  T ?

2.

, where and , such that has a child for each , and for each rule where has a child node labeled for some .

? a VX ? ? X § A )

X

? X

? )

? ?X

?

1.

has a child node labeled

for some

; or

0.7. SUMMARY AND DISCUSSION

33

0.7 Summary and discussion
The defeasible logics discussed in this chapter can be grouped into two families, according to how they try to eliminate ambiguities. One family, containing Pearl’s system Z, Geffner’s conditional entailment, Simari’s and Loui’s argument-based system and Nute’s basic defeasible logics and , relies on speci?city information implicitly present in the knowledge base in order to solve con?icts. This family can be summarized in the following table, in which we emphasize the different basic design choices. IMPLICIT PRIORITIES Z CE ABS sets of defaults argument con?icting defaults structures defaults total irre?exive+ irre?exive+ irre?exive+ transitive transitive transitive skeptical skeptical skeptical skeptical (indirect) amb.prop. amb.block. Y Y N N Y Y Y Y N Y Y Y Y Y Y Y defeasible defeasible strict defeasible
?

subject of priority kind of priority attitude contraposition observations strict rules default rules kind of speci?city

The second family, containing Brewka’s system of preferred subtheories, Nute’s basic defeasible logic EBDL, ordered logic and Ryan’s formalism of ordered theory presentations, makes use of an additional structure to represent explicit priorities. EXPLICIT PRIORITIES PS OL EBDL subject sets of sets of defaults+ of priority defaults defaults defeaters kind of total/ partial irre?exive+ priority partial transitive attitude credulous skeptical/ skeptical credulous contraposition Y N N Both uses of prioritization have their pros and cons. An approach in which priorities are explicitly supplied by the user can be useful, because the ?exible means for deciding among competing defaults allows us to give solutions for several examples of nonmonotonic reasoning which cannot be solved using implicit speci?city information. Explicit priorities are useful when preference criteria other than speci?city,

?

?

?

?

? ?

?

?

?

?

?

?

34

CONTENTS

such as recency, authority, reliability, .. are required. However, when speci?city is the preference criterion, the user ?nds himself obliged to perform the redundant task of explicitly providing priority information which is implicitly present in the knowledge base. This explicitly given priority information might even contradict the implicitly present priorities, which may not always be as intended. Therefore, both approaches need to be considered. Recently, several attempts have been made to combine the best of both worlds into a single formalism. System [GP91] relies on implicit speci?city information but allows explicit priorities in the sense of additional rule-strenghts. Here, strenghts can be used to re?ne the speci?city-based priorities. They undergo adjustments, so that compliance with speci?city-type constraints is automatically preserved. As a result, speci?city can never be overridden, or defeated. However, it has been argued that sometimes it might be necessary to give precedence to selection criteria other than speci?city. E.g. in the area of legal reasoning [Bre94], it might be the case that a more recent general law overrides a more speci?c older law, i.e. that the recency criterion is stronger than the speci?city criterion. A formalism able to deal with this kind of reasoning is presented in [GV95]. In this argument-based formalism, speci?city is considered to be the preference criterion by default. However, additional priorities can be added from the very beginning, making it possible to re?ne or even defeat the speci?city criterion. Furthermore, this formalism allows to reason about priorities. By presenting priorities within the logical language [Bre94], statements concerning priorities can be derived, but also defeated.

? ¤

Bibliography

[BCD 93] S. Benferhat, C. Cayrol, D. Dubois, J. Lang, and H. Prade. Inconsistency management and prioritized syntax-based entailment. In Proceedings 13th International Joint Conference on Arti?cial Intelligence, pages 640–645, 1993. [BDP93] S. Benferhat, D. Dubois, and H. Prade. Argumentative inference in uncertain and inconsistent knowledge bases. In Ninth annual conference on Uncertainty in Arti?cial Intelligence (UAI), pages 411–419, 1993. G. Brewka. Preferred subtheories: An extended logical framework for default reasoning. In Proceedings IJCAI-89, 1989. Gerhard Brewka. Reasoning about priorities in default logic. Technical report, GMD, Postfach 13 16, 53731 Sankt Augustin, Germany, 1994. Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Arti?cial Intelligence, 77(2):321–358, 1995. P. Geerts. Ordered logic and prioritization in nonmonotonic reasoning. PhD Thesis. University of Antwerp, UIA, 1996. H. Geffner. Default Reasoning: Causal and Conditional Theories. MIT Press, 1992. M.L. Ginsberg. AI and Nonmonotonic Reasoning, volume Handbook of Logic in Arti?cial Intelligence and Logic Programming, pages 1–33. Oxford University Press, 1994. D. Gabbay, E. Laenens, and D. Vermeir. Credulous vs. sceptical semantics for ordered logic programs. In J. Allen, R. Fikes, and E. Sandewall, editors, Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning, pages 208–217, Cambridge, Mass, 1991. Morgan Kaufmann. 35

[Bre89] [Bre94] [Dun95]

[Gee96] [Gef92] [Gin94]

[GLV91]

?

36
?

BIBLIOGRAPHY
M. Goldszmidt and J. Pearl. System : a formalism for reasoning with variable-strength. In Proceedings AAAI-91, pages 399–404, 1991. H. Geffner and J. Pearl. Conditional entailment: bridging two approaches to default reasoning. Arti?cial Intelligence, 53:209–244, 1992. P. Geerts and D. Vermeir. Credulous and autoepistemic reasoning using ordered logic. In Proceedings of the First International Workshop on Logic Programming and Non-Monotonic Reasoning, pages 21–36. MIT Press, 1991. P. Geerts and D. Vermeir. A nonmonotonic reasoning formalism using implicit speci?city information. In Proceedings of the second International Workshop on Logic Programming and Non-monotonic Reasoning. The MIT Press, 1993. Patricia Geerts and Dirk Vermeir. Speci?city by default. In C. Froidevaux and J. Kuhlas, editors, Symbolic and Quantitative Approaches to Reasoning and Uncertainty, ECSQARU95, number 946 in Lecture notes in Arti?cial Intelligence, pages 107–216. Springer Verlag, July 1995.

[GP91] [GP92] [GV91]

[GV93]

[GV95]

[GVN94] P. Geerts, D. Vermeir, and D. Nute. Ordered logic: defeasible reasoning for multiple agents. Decision Support Systems, 11:157–190, 1994. [HTT87] J.F. Horty, R.H. Thomason, and D.S. Touretzky. A skeptical theory of inheritance in nonmonotonic semantic networks. Technical Report CMU report CMU-CS-87-175, 1987.

[KLM90] S. Kraus, D. Lehman, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Arti?cial Intelligence, 44:167–207, 1990. [Lae90] [Lif85] E. Laenens. Foundations of ordered logic, 1990. PhD Thesis, University of Antwerp UIA. V. Lifschitz. Computing circumscription. In Proceedings 9th IJCAI, pages 121–127. Los Angeles, CA, 1985. Also in ’Readings in nonmonotonic reasoning’, M.L. Ginsberg. D. Lehmann and M. Magidor. Rational logics and their models: a study in cumulative logics. Technical Report TR-88-16, Dept. of Computer Science, Hebrew University, Jerusalem, Israel, 1988. R. Loui. Defeat among arguments: A system of defeasible inference. Computational Intelligence, 3(2):100–106, 1987.

[LM88]

[Lou87]

?

BIBLIOGRAPHY
[LSV90]

37

E. Laenens, D. Sacca, and D. Vermeir. Extending logic programming. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 184–193. ACM, Association for Computing Machinery, 1990. E. Laenens and D. Vermeir. Assumption-free semantics for ordered logic programs: on the relationship between well-founded and stable partial models, 1990. University of Antwerp, Tech. Report 90-19. E. Laenens and D. Vermeir. A ?xpoint semantics of ordered logic. Journal of Logic and Computation, 1(2):159–185, 1990. E. Laenens and D. Vermeir. A logical basis for object-oriented programming. In Proc. European Workshop on Logics in AI, Amsterdam, pages 317–332. Springer Verlag, 1990.

[LV90a]

[LV90b] [LV90c]

[LVVC89] E. Laenens, B. Verdonk, D. Vermeir, and A. Cuyt. A logic for objects and inheritance. In Proc. of the Advanced Database Symposium, Kyoto, pages 55–60. Information Processing Society of Japan, 1989. [Mak89] D. Makinson. General theory of cumulative inference. In Proceedings 2nd International Workshop on nonmonotonic reasoning, pages 1–18. Springer Verlag, 1989. J. McCarthy. Circumscription - a form of non-monotonic reasoning. Arti?cial Intelligence, 13:27–39, 1980. J. McCarthy. Applications of circumscription to formalizing common sense knowledge. Arti?cial Intelligence, 28:89–116, 1986. Also in ’Readings in nonmonotonic reasoning’, M.L. Ginsberg. D. McDermott and J. Doyle. Non-monotonic logic i. Arti?cial Intelligence, 13:41–72, 1980. R.C. Moore. Possible-world semantics for autoepistemic logic. In Proceedings 1984 Non-monotonic reasoning workshop (AAAI), pages 344– 354. new Paltz, NY, 1984. Also in ’Readings in nonmonotonic reasoning’, M.L. Ginsberg. R.C. Moore. Autoepistemic logic. In P. Smets, editor, Non-standard logics for automated reasoning, pages 105–136. 1988. D. Nute. Conditional logic. In D. Gabbay and F. Guenthner, editors, Handbook of philosophical logic II. 1985. D. Nute. LDR: a logic for defeasible reasoning, 1986. ACMC Research Report 01-0013.

[McC80] [McC86]

[MD80] [Moo84]

[Moo88] [Nut85] [Nut86]

38 [Nut88] [Nut90]

BIBLIOGRAPHY
D. Nute. Defeasible reasoning and decision support systems. Decision support systems, 4:97–110, 1988. D. Nute. Defeasible logic and the frame problem, volume Knowledge representation and defeasible reasoning, pages 3–21. Kluwer academic publishers, 1990. D. Nute. Basic defeasible logic, pages 125–154. Intensional Logics for Logic Programming. Oxford University Press, 1992. J. Pearl. Probabilistic reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, 1988. J. Pearl. Probabilistic semantics for nonmonotonic reasoning : A survey. In Proceedings 1st International Conference on Principles of Knowledge Representation and Reasoning. Toronto, 1989. J. Pearl. System z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In Theoretical Aspects of Reasoning about Knowledge (TARK-III), pages 121–135. Morgan Kaufmann, 1990. J. L. Pollock. Defeasible reasoning. Cognitive Science, 11:481–518, 1987. J. L. Pollock. Defeasible reasoning. Cognitive Science, 11:481–518, 1987. J.L. Pollock. How to reason defeasibly. Arti?cial Intelligence, 57:1–42, 1992. D. Poole. On the comparison of theories: Preferring the most speci?c explanation. In Proceedings IJCAI-85. 1985. D. Poole. A logical framework for default reasoning. Arti?cial Intelligence, 36:27–47, 1988. R. Reiter. A logic for default reasoning. Arti?cial Intelligence, 13:81–132, 1980. N. Rescher. Hypothetical reasoning. North-Holland Publ., Amsterdam, 1964. M. Ryan. Ordered presentations of theories, 1992. PhD Thesis. Y. Shoham. Reasoning about change. MIT Press, 1987. Y. Shoham. A semantical approach to nonmonotonic logics. In Proceedings of the Symposium on Logic in Computer Science, pages 275–279. 1987.

[Nut92] [Pea88] [Pea89]

[Pea90]

[Pol87a] [Pol87b] [Pol92] [Poo85] [Poo88] [Rei80] [Res64] [Rya92] [Sho87a] [Sho87b]

BIBLIOGRAPHY
[SL92]

39

Guillermo R. Simari and Ronald P. Loui. A mathematical treatment of defeasible reasoning and its implementation. Arti?cial Intelligence, 53:125– 157, 1992. L.A. Stein. Resolving ambiguity in nonmonotonic inheritance hierarchies. Arti?cial Intelligence, 55:259–310, 1992. D.S. Touretzky, J.F. Horty, and R.H. Thomason. A clash of intuitions: The current state of nonmonotonic multiple inheritance systems. In Proceedings IJCAI-87. 1987.

[Ste92] [THT87]

[VNG89a] D. Vermeir, D. Nute, and P. Geerts. A defeasible logic for multi-expert systems. In Proc. of the Intl. Symposium on Computational Intelligence 89. Elsevier Publ. Co., 1989. [VNG89b] D. Vermeir, D. Nute, and P. Geerts. A logic for defeasible perspectives. In Proc. of the 1988 Tubingen Workshop on Semantic Networks and Nonmonotonic Reasoning, Vol. 1, pages 1–27. SNS-Bericht 89-48, 1989. [VNG90] D. Vermeir, D. Nute, and P. Geerts. Modeling defeasible reasoning with multiple agents. In Proc. of the HICSS, Vol. III, pages 534–543. 1990. [Vre91] G. Vreeswijk. The feasibility of defeat in defeasible reasoning. In Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning (KR91), pages 526–534, 1991.