---
title: "Preference-Based Semantics for Nonmonotonic Logics"
authors:
  - "Frans Voorbraak"
doi: ""
url: "https://ijcai.org/proceedings/1993/82"
pdf: "https://ijcai.org/proceedings/1993/0082.pdf"
venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence"
year: 1993
pages: "584-590"
track: "Knowledge Representation"
keywords:
---

# Preference-Based Semantics for Nonmonotonic Logics

Frans Voorbraak

*Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 584-590.

## Abstract

A variant is proposed of the preference-based semantics for nonmonotonic logics that was originally considered by Shoham [1987; 1988]. In this variant it is not assumed that preferences between standard models are aggregated into one preference order. This allows the capturing of all main nonmonotonic formalisms, including Default Logic of Reiter [1980]. The preferential models introduced in this paper are motivated from an epistemic point of view, and are therefore called epistemic preference models. The consequence operations induced by epistemic preference models are characterized. Further, the view is defended that the rationality of cumulative monotonicity does not imply that nonmonotonic logics have to be cumulative, but only that a rational agent should not believe a set of default rules that induces a noncumulative consequence operation.

## Full text

## 1 Introduction

Shoham [1987; 1988] introduces preferential semantics as a possible unifying framework of nonmonotonic logics. In this framework, a nonmonotonic logic is reduced to a stan­ dard logic plus a preference order on the models of that stan­ dard logic, and nonmonotonic entailment is considered to be preferential entailment, where r preferentially entails <p iff <p is true in every model M such that (I) r is true in M and (2) r has no model N which is preferred to M.

In this paper we propose a generalization of Shoham's framework which is obtained by allowing (not necessarily transitive) preference relations between sets of models. From a technical point of view, considering sets of standard mod­ els is not an essential generalization, since sets of models of a standard logic L induce a partial variant of L, which is again standard. However, using arbitrary preference relations instead of preference orders is essential, since it allows more freedom to express preference.

* The investigations were supported by the Foundation for Philosophical Research (SWON), which is subsidized by the Netherlands Organization for Scientific Research (NWO).

A consequence of the additional freedom is that in our ap­ proach Default Logic of [Reiter, 1980], which is one of the major nonmonotonic formalisms, can be given a preference­ based semantics, whereas in Shoharn's original approach this turned out to be difficult, if not impossible. However, our relaxation of the constraints on preference-based semantics is not an ad hoc move solely motivated by the need to capture Default Logic, but it follows from our interpretation of the preference relation.

We interpret the preferences between (sets of) models as epistemic preferences (of an ideally rational agent) between world descriptions. Since an agent usually has only partial information about the world, epistemic preferences are most naturally captured by preferences between sets of models, corresponding to partial world descriptions. In our view, an agent has in general epistemic preferences of different kinds, which are not always easily combined into one preference order. For example, an agent may have preferences induced by factual information, induced by default information, or induced by lack of information:

Example 1.1 Consider an agent with the following be­ liefs: (1) Typically, it does not rain in California, (2) It now rains in California. On account of beliefs (1), the agent prefers world descriptions in which it does not rain in California. However, this default preference is overridden by the preference induced by the factual belief (2) that it does rain. Since the agent does not have any (factual or default) beliefs about the weather conditions in Kansas, he prefers world descriptions which leave undecided the question whether it rains in Kansas.

In our analysis of the situation, an agent has a preference for the less specific or more ignorant world descriptions, un­ less there is some (default or factual) information to the con­ trary. This leads us to consider the lexicographic aggregation of strict partial orders, which itself is in general not a strict partial order. (See section 2 below.) Requiring the aggregated preferences of an agent to form a strict partial order should in our opinion be considered to be a rationality requirement on the (default and factual) beliefs of the agent and should not be interpreted as a requirement on nonmonotonic logic. Similar remarks hold for the smoothness condition of [Kraus et al., 1990], the boundedness condition of [Makinson, 1989], etcetera. We return to this issue in section 5.

The rest of this paper is organized as follows. In section 2 some preliminary definitions and results concerning prefer­ ence relations and preferential semantics are treated. In sec­ tion 3, Default Logic is given a preferential semantics. Section 4 contains a description of the consequence opera­ tion characterized by the prefereniial models of this paper. Cumulativity and other rationality requirements are discussed in section 5. Finally, in section 6, the main conclusions are mentioned.

Proofs of the results can be found in the full paper [Voorbraak, 1993].

## 2 Preliminaries

Throughout this paper, > denotes an asymmetric, and there­ fore irreflexive, binary relation

Definition 2.1 For any asymmetric > ,

- (i) x - y ¢=>def not x > y and not y > x.
- (ii) x = y ¢=>def x - z iffy - z, for all z E X.
- (iii) x ~ y ¢=>def x > y or x = y.
- (iv) x ~ y ¢=>def x > y or x = y.

In addition to definition 2.1 we use standard notation, such as < for the converse of > and ':1- for the complement of >. Notice that = is an equivalence relation, that > n = = 0, and that= = ~ n ""· It follows that instead of> one may choose ~ as primitive notion, and define > as ~ n ~-Of course, also~ can be chosen as primitive.

The intuitive reading of x > y is "y is preferred to x". The intuitive reading of the other relations mentioned in def­ inition 2.1 is as follows:

- x - y: x and y are preferentially unrelated. (-is called indifference relation.)

x = y: x and yare equally preferred.

x ~ y: y is at least as preferred as x.

x ~ y: y is identical to x or y is preferred to x.

We use the preference relations to model the (nonmono­ tonic) reasoning of a rational agent and it is usually assumed that a relation expressing rational preference is a strict partial order, i.e., a relation which is not only asymmetric, but also transitive. However, we explicitly allow intransitive prefer­ ence relations, since, as mentioned in the introduction, it is perfectly reasonable for an agent to have a preference for less specific world descriptions, unless there he has some infor­ mation to the contrary.

The preferences of such an agent can be described by the lexicographic aggregation of two preferential criteria, which lets a second preference criterion apply if (and only if) the first criterion is indifferent with respect to the choices at hand. For weak orders, the notion of lexicographic aggrega­ tion is well-known. (A weak order is a strict partial order for which ~ is total or complete, in the sense that either x ~ y or y ~ x holds.

Since for weak orders - = =, while in general - and = are distinct, there exist at least two reasonable notions of lexicographic aggregation in the general case. We will use only one of these, so we do not bother to distinguish be­ tween weak and strong variants.

Definition 2.2 Let for all positive integers i $ n, > i be an asymmetric binary relation on X. A.((> 1·· .. , > n)). the lexicographic aggregation of> }, ... ,>n. is defined induc­ tively as follows: A.(( )) = 0, and A.((> 1· ... , > m + 1)) = A.((>}, . . . ,>m)) u (-I n ... n -m n >m+I)

Let us write A.(>t ·... ,>n) instead of A.((>l·····>n)). Notice that A.(>) = > and that (x,y) E A.(> 1.>2) iffy is !­ preferred to x, or x andy are !-indifferent andy is 2-preferred to x. One easily shows that for weak orders > 1 ·. .. ,>-n on X, A<>l ·... ,>n) is again a weak order on X. However, the following example shows that the lexicographic aggregation of two strict partial orders on X is itself not necessarily a strict partial order on X.

Exam pie 2.3 Let > 1 be the strict partial order { (x3 ,x 1)} and let > 2 be the weak order { (x },X2).(x2,X3).(x 1.x3)}. Then > =def A.(> 1·>2) is not transitive, since x 1 > x2 and X2 > X3, but not X} > X3.

We will use preference relations to denote preferences of an ideally rational agent between sets of models correspond­ ing to partial world descriptions. It follows that the prefer­ ence relations should not distinguish sets of models that cor­ respond to the same world description, i.e., that validate the same set of formulas of the language under consideration. Instead of imposing this constraint on the preference rela­ tion, we will divide out the indistinguishability relation.

Throughout this paper, L denotes a standard logic. That is, the consequence operation CnL of L satisfies inclusion (f k CnL(f)), idempotency (CnL(r) = CnL(CnL(r))), and monotonicity (r k ~ ~ CnL(r) k CnL(l1)) . .;EL denotes the language of L and ModL is the class of L-models. The preference relation is defined on {.M. k ModL I for some :E k .;EL, .M. = { M I M I= L :E}} . Hence each relevant set .M. of L­ models is characterized by some subset of .;EL· Equivalently, one can define the preferences on { :E k .;EL I CnL(:E) = :E}, the set of L-theories.

In [Kraus et al., 1990] a state is merely labelled and not identified with a set of worlds. (Cf. def. 2.9 below.) We have taken a similar position in [Voorbraak, 1992], but there we describe the same (epistemic) states in different formal lan­ guages, whereas in this paper we restrict ourselves to a sin­ gle language, viz . .;EL, which makes it reasonable to identify objects which cannot be distinguished in that language.

Before we give the formal definition of our models for preferential entailment, we introduce some notation. l=h,L k \iJ>(ModL)x.;EL is the satisfaction relation given by .M. 1= h L <p iff for all ME .M., M I=L <p. (The notation derives fro'm [Voorbraak, 1991], where sets of models are called hyperval­ uations.) Notice that l=h,L induces a standard consequence operation. For any set .M. k ModL, 1/.M.IIL abbreviates { cp E .;EL I.M. l=h,L <p} and for any L k .;EL, \\1:\\L =ctef {ME ModL I M I=L :E) . \\L\\L is also written as MODL(:E).

.M. + =ctef {ME ModL I for all <p E 1/.M./1 M I=L <p} . The notion of .M.+ and its notation derive from Levesque [1990]. He shows that .M. + is a maximal set of L-models, in the sense that there is no proper superset of .M.+ which is equiva­ lent to .M. +, and that .M. + is the unique maximal set of L­ models equivalent to .M.. The set of world descriptions of L, WDL =ctcf {\\L\\L ILk .;EL} .

The subscript L will sometimes be omitted when confu­ sion is unlikely to occur. The following proposition lists some properties of the introduced notions.

## Proposition 2.4

- (i) 11(:-.\J::\\)11 = CnL(L)
- (ii) \\1\_1/.MJ/)\\ = .«+
- (iii) If CnL(L) = 1/.MJ/, then \'\1::\\ = .M +
- (iv) For all .M E WDL, .M = .M +.

We are now ready to define our models for preferential en­ tailment, which we call epistemic preference models, in or­ der to distinguish them from several other models proposed in the literature, and in order to emphasize that we explicitly assumed the preference relation to express preferences be­ tween epistemic (belief) states.

Definition 2.5 An epistemic preference model for L is a triple (WDL,> ,F-), where > is an irreflexive relation on the set of world descriptions WDL. and I= is l=h,L restricted to WDLX9;L·

Definition 2.6 Let (WDL,> ,1=) be an epistemic prefer­ ence model. .M E WDL preferentially satisfies q>, notation .M I=L,> q>, iff .M I=L q> and for all N < .M., N IF q>. q> is a preferential consequence of r, notation r I=L,> q>, iff for all .M. E WDL, .M I=L,> r implies .M. I= q>.

We write CnL,>(r) for { q> e 9;L I r 1= L, > q>} and we omit the subscript L if it is clear which standard logic is used. Notice that a epistemic preference model is determined by L and the preference relation > on WDL.

Epistemic preference models have a status quite similar to the one of possible worlds models in modal logic, since they can be enriched by adding further conditions on >. An obvi­ ous condition is transitivity. To give another example, an epistemic preference model (WDL,> ,1=) is called proper iff set inclusion is contained in """ u ~, i.e., for all .M.,N e WDL, .M. ~ N implies .M. """ N or .M. ~ N. Proper epis­ temic preference models implement the intuition that a ra­ tional agent should not be indifferent with respect to epis­ temic states .M and N if .M. ~ N.

For comparison, we also provide here the models for pref­ erential entailment that were proposed in [Shoham, 1987; 1988], [Makinson, 1989], and [Kraus et al., 1990].

Definition 2.7 A Shoham model for L is a triple (ModL,> ,1= L). where > is a strict partial order on ModL.

Definition 2.8 A Makinson model is a triple (ID?.,> ,1= ), where ID?. is an arbitrary set, > is a binary relation on ID?., and I= an arbitrary satisfaction relation ~ ID?. x9; L. A Makinson model will be called L-faithful iff for every .M. e ID?. the set { q> E 9;L I .M. I= L q>} is closed under CnL.

Definition 2.9 A KLM model is a quadruple (S ,e ,> ,1= ), where S is an arbitrary set of states, e : S ~ C!J>(ModL) is a labelling function, > is a binary relation on S, and 1= ~ Sx9;L is defined as follows: for all s e S and for all q> e 9;L, s I= q> iff f(s) l=h,L q>.

Preferential entailment for the above models is defined completely analogous to 2.6. It is easy to see that any epis­ temic preference model and any Shoham model is a (L-faith­ ful) Makinson model and is equivalent to a KLM model. The precise relation between Makinson models and KLM models is the subject of [Dix and Makinson, 1992]. For any Shoham model there exists an equivalent .epistemic prefer­ ence model.

From a technical point of view, KLM models or Makinson models are perhaps better suited than epistemic preference models to play the role of basic preference mod­ els. However, since often epistemic intuitions are used to in­ formally justify the preferential models, it is advisable to take these intuitions serious and consider preferences be­ tween "real" epistemic states. In the following section we show that epistemic preference models are more general than Shoham models.

## 3 Preference-based semantics for Default Logic

In the previous section we mentioned that any Shoham model has an equivalent epistemic preference model. The fol­ lowing proposition guarantees that whenever a logic has a preferential semantics in terms of Shoham models it also has one in terms of epistem.ic preference models. It follows that all nonmonotonic logics treated in [Shoham, 1987; Shoham, 1988] can also be captured in our approach. This includes Predicate Circumscription [McCarthy, 1980], the "minimal knowledge" approach of [Halpern and Moses, 1985], and some variants of Reiter's Default Logic, but not Reiter's Default Logic itself. However, Default Logic can be captured by epistemic preference models.

For convenience, we repeat some basic definitions of [Reiter, 1980]. The underlying standard logic Lis assumed to be ordinary first-order logic. A default (rule) is an expres­ sion of the form a: ~1·····~n I w (n ~ 1), where a (the prerequisite), ~1 ,. ..· ~n (the justifications), and w (the con­ clusion) are first-order formulas. Without loss of generality, we assume these formulas to be closed. A default theory is a pair CZiJ = (D,r), where D is a set of defaults and r is a set of closed formulas of L. E is called an extension of (D,r) iff E is a fixed point of the function f : C?J> 9; ~ '?}> 9;, where f(:E) is defined to be the smallest L-theory containing rand every w such that a: ~1 ..... ~n I wE D, a E f(L) and for all i E { 1 , .. ,n}, -,~i ~ :E.

As a basis for our preferential semantics for Default Logic we use the semantics proposed in [Etherington, 1988], which already makes use of preference relations.

Definition 3.1 Let o = a : ~ 1 , .. . ~n I w be a default. <o, the preference relation corresponding to 8, is defined as fol­ lows: For any .M.,N ~ ModL, .M. <oN iff (1) N l=h La, (2)-.:Ji.N"I=h,L -.~j,and(3).M.=.N- {MIMIFLW} ::t:N.

Intuitively, .M. <o .N means that on account of o the world description .M. is preferred to the world description N. In case the set of defaults is finite, the preference relation <D corre­ sponding to a set of defaults D is simply the transitive clo­ sure of the union of the preference relations corresponding to the elements of D. For default theories with infinitely many default rules, a slightly more complicated definition is called for.

Definition 3.2 Let D be a set of defaults and let ID'l be a set of models. <o, the preference relation corresponding to D over C!PID'l is defined as follows: .M. <o .N iff there exist Ot.~···· E D and subsets .N o..N I>.N 2···· of ID'l such that.N =.No >ot .Nt >lil ){2 >o3··· 'and .M. = n.Nj.

If ~ = (D ,r) is a default theory, then <21J denotes the re­ striction of <o to the sets of worlds in which r is valid. In [Etherington, 1988] it is shown that extensions of a default theory (D,r) correspond to the formulas valid in the <21J­ minimal elements which are ~-stable, where .M. is called <:!lJ­ stable iff 3D'~ D such that.M. <o· \\1\\L and every justifi­ cation f3 of a default o E D' is true in some M E .M..

The preferential semantics for Default Logic will be given in two stages. Before the models corresponding to sets of de­ faults are given, we first define preference models for default theories. The preference relation associated with a default theory ~ is a variant of <CZ!J which takes the role of stability into account

Definition 3.3 Let CZlJ = (D,r) be a default theory. The epistemic preference model associated with CZlJ is the model (WDL,>21J,I= ), where >21J = A.(>o,>21J) and >o is defined as follows: .N >o .M. iff .M. = 0 "# .N and there is no <21)-min­ imal and CZ!J-stable .N' <21J .N. To avoid stacked subscripts, we write I=21J and Cn2n for the preferential consequence relation and operation of (WDL,>21J,I= ).

Proposition 3.4 If (WDL,>2ll ,I=) is the epistemic prefer­ ence model associated with ~ = (D,r), then for any ~ ~ ~L. Cn2n(~) = (l{E IE is an extension ofCZ!J and~~ E).

An immediate corollary of proposition 3.4 is the mono­ tonicity of Cn2n. Hence as long as one keeps the default the­ ory constant, the reasoning is monotonic. Default conse­ quence is nonmonotonic because (the facts of) default theo­ ries are updated in the light of new information. To capture this in terms of preferential semantics, we need preference models associated with sets of defaults. The preference rela­ tion for such a model will be more or less a global version of the relation used for a default theory.

Definition 3.5 Let D be a set of defaults. The epistemic preference model associated with D is the model (WDL,>o,l=), where >o = /..([>o,c) and [>Dis defined as follow.s: .N [>D ~ iff .N > (D,//.N II) .M. To avoid stacked subscnpts, we wnte t=o and Cno for the preferential conse­ quence relation and operation of (WDL,>o,l= ).

Proposition 3.6 If (WDL,> o,l=) is the epistemic prefer­ ence model associated with a set D of defaults, then for all r ~ ~L. Cno(r) = (l{E IE is an extension of (D,r)} .

In contrast to >21J of 3.4, > o of 3.6 is in general not a strict partial order. In fact, it can be shown that some sets of defaults cannot be captured by transitive epistemic preference models. However, in [Voorbraak, 1992] it is proved that transitive preference models can capture Default Logic, provided the notion of preferred model is strengthened to .M. I=L,> riff .M. 1= r, for all.N -< .M., .N ~ r, and for all.N' (.M. c .N' ~ \\r\\L implies .M -< .N'). A similar result has been obtained independently by Lin and Shoham [1992].

As far as we know, our preferential semantics for Default Logic is the first that uses the original definition of preferred model (at the cost of allowing intransitive preference rela­ tions).

## 4 Nonmonotonic consequence operations

We prefer the sceptical interpretation of nonmonotonic log­ ics and consider the the intersection of extensions to repre­ sent the consequences of a default theory, even though this intersection is not necessarily itself an extension. However, we compromise to the more brave or credulous authors by also considering extension operations next to the nonmono­ tonic consequence operations.

Definition 4.1 An extension operation Ext for L is a function C!P(~L) ~ C!P(C!P(~L)) satisfying the following three conditions: (for all r.~ ~ ~L)

(i) If~ E Ext(r), then r ~ ~.

(inclusion)

(ii) If r' E Ext(r) and r ~ ~ ~ r ', then rlExt(~) ~ r '.

(iii) Ext(r) = Ext(CnL(r)).

(cumulative transitivity)

(L-invariance)

Definition 4.2 Cn: CJl(~L) ~ CJl(~L) is called a non­ monotonic consequence operation for L iff for some exten­ sion operation Ext for L, for all r ~ ~L Cn(r) = rlExt(r).

Notice the explicit reference to the underlying standard logic in definition 4.1. For nonmonotonic logics formulated without an underlying standard logic, one can assume L to be trivial in the sense that for all r, CnL(r) = r. In that case, L-invariance trivially holds. We do not claim that L­ invariance is reasonable for all nonmonotonic logics, but the condition seems inevitable for nonmonotonic reasoning of ideally rational agents, since they are able to draw all stan­ dard consequences of the premises.

Extension operations will be called equivalent iff they in­ duce the same consequence operation. It is easy to see that for every extension operation Ext there exists an equivalent Ext' such that for all r ~ ~L Ext'(r) "* 0. (Just replace all values 0 with {~Ll .) We will not distinguish between hav­ ing no extensions and having only the inconsistent exten­ sion, and we simply assume from now on that only non­ empty sets are in the range of extension operations.

Proposition 4.3 Cn is a nonmonotonic consequence op­ eration for L iff Cn satisfies: (for all r.~ ~ ~L)

```
(i) r ~ Cn(r) (inclusion) (ii) r ~ ~ ~ Cn(r), then Cn(~) ~ Cn(r) (cumulative transitivity) (iii) Cn(r) = Cn(CnL(r)) (L-invariance)
```

Some properties that can be derived from those mentioned above are Cn(Cn(r)) = Cn(r) (idempotency), CnL(Cn(r)) = Cn(r) and CnL(r) ~ Cn(r). Moreover, if Cn is L-invariant, and CnL is L'-invariant, then Cn is L'-invariant.

Completely analogous to the representation theorems for cumulative consequence relations obtained in [Kraus et al., 1990] and [Makinson, 1989]. we have the following result for nonmonotonic consequence operations:

Proposition 4.4 Cn is a nonmonotonic consequence op­ eration for L iff Cn = Cn>, for some epistemic preference model (WDL,> ,r- ).

It follows from this result that the nonmonotonic modal logics introduced in [McDermott, 1982] have a preferential semantics, and it is shown in [Shvarts, 1990] that Moore's autoepistemic logic is a special case of the nonmonotonic modal framework. Proposition 4.4 is also valid for L-faith­ ful Makinson models.

## 5 Cumulativity and rationality

Gabbay [1985] introduces the notion of weakly monotonic, or cumulative, consequence, which is characterized in [Kraus et al., 1990] and [Makinson, 1989] in terms of preferential models. Below we show that the characterization in terms of Makinson models can be restricted to epistemic preference models.

Definition 5.1 An extension operation Ext for L is called cumulative iff it satisfies the following condition: If 11 E Ext(r), 11' E Ext(r') and r <;;;; r· <;;;; 11, then 11' E Ext(r). A cumulative consequence operation for L is a nonmonotonic consequence operation induced by a cumulative extension operation for L.

Proposition 5.2 Cumulative consequence operations are characterized by inclusion, cumulative transitivity, L-invari­ ance, and cumulative monotonicity (r <;;;; 11 <;;;; Cn(r) ~ Cn(f) <;;;; Cn(l1).)

Definition 5.3 A Makinson model (IDe,> ,F) is called stoppered iff for all r <;;;; ~L and for all .M. E ID'l, .M. F r im­ plies .N F > r, for some .N ~ .M. .

The following result is essentially already obtained in [Makinson, 1989]. but without the reference to Land with­ out requiring the models to beL-faithful.

Proposition 5.4 Cn is a cumulative consequence opera­ tion for L iff Cn = Cn>, for some stoppered L-faithful Makinson model (IDe,> ,F).

In the above proposition, the L-faithful Makinson models can be restricted to epistemic preference models for L:

Proposition 5.5 Cn is a cumulative consequence opera­ tion for L iff Cn = Cn>. for some stoppered epistemic pref­ erence model (WDL,> ,F).

Cumulative monotonicity is considered to be a rationality requirement, and in the literature there is a tendency to dis­ qualify non-cumulative nonmonotonic logics, such as Default Logic. For example, in [Brewka, 1990], Default Logic is modified to satisfy cumulative monotonicity.

However, we are not prepared to conclude that the conse­ quence operation of a nonmonotonic logic has to be cumula­ tive. First of all, nonmonotonic logics might be used to formalize the reasoning of agents or systems which are not ideally rational and which, for example, reason nonmonoton­ ically by "firing" default rules in appropriate circumstances.

Further, it cannot be inferred from the rationality of cumu­ lative monotonicity that any nonmonotonic logic formaliz­ ing the nonmonotonic reasoning of an ideally rational agent has to be cumulative. There is an analogy here with consis­ tency: Although an ideally rational agent only believes a consistent set of formulas, we do not have to require that the logic L under which the beliefs are closed is consistent in the sense that for all l: c ~L , CnL(l:) i:- ~L· (In fact, this requirement is inconsistent with the inclusion property, satisfied by standard logics.) ·

An inconsistent set l: will be revised before it will be­ come accepted by a rational agent, and this revision process is not described by L, but by operations as studied in Gfu"denfors [9]. Similarly, a rational agent will revise his de­ fault beliefs if they do not give rise to rational preferences, and this revision process does not have to be described by the nonmonotonic consequence operation.

In addition to cumulativity, there is another obvious ra­ tionality requirement on default beliefs and their induced nonmonotonic consequence operations, namely that Cn(f) is inconsistent only if r is. In other words, if CnL(r) i:- ~L. then Cn(r) i:- ~L· Let us call such consequence operation consistent. (The corresponding condition for Ext is: if CnL(r) i:- ~L. then Ext(f) i:- {~L}.)

In general, it is of course not easy to guarantee that a set of default beliefs induces a consistent consequence operation. However, there exist interesting special cases for which simple sufficient conditions can be formulated. For example, it is known that a default theory (D,r) has an inconsistent extension iff the set r of facts is inconsistent. Hence every set D of defaults which guarantees the existence of exten­ sions, such as a set of normal defaults, induces a consistent consequence operation.

Not every set of normal defaults induces a cumulative consequence operation. For example, the set{ : pIp, p v q : -,p I -,p}, which is used by Makinson (1989) to show that default logic is not cumulative, consists of normal defaults. But it is quite simple to revise a set of normal defaults into a set that yields a cumulative consequence operation. Besnard (1989) proposes the following translation of normal defaults into free defaults, i.e., defaults without prerequisites: Trses(a : ~ I~) = : a ::::> ~I a ::::> ~· Sets of. thus obtained defaults induce a cumulative consequence operation. However, since Trses lacks a proper justification and gives rise to some counterintuitive results, we propose an alterna­ tive, more general translation Trrree of arbitrary default into default without prerequisites. Trfree is defined by means of Trrree(a : ~1·· ..· ~n I ro) =ctef: a11.~l·· .. ,a11.~n I a=> ro.

Unfortunately, Trrree does not necessarily revise a set of (normal) defaults into a set that induces a cumulative conse­ quence operation, but Trfree can be motivated by a famous rationality property of preference relations that thus far has received little or no attention in the literature on preferential semantics: the sure-thing principle of [Savage, 1972]. which is informally stated thus:

If the person would not prefer f tog, either knowing that the event B obtained, or knowing that the event - B obtained, then he does not pre­ fer f to g. [Savage, 1972, p. 21]

The sure-thing principle is closely related to the ability to reason by cases, and if one does not allow (defaults with) prerequisites, then it is indeed possible to reason by cases in Default Logic.

An obvious objection against the translation of defaults into free defaults is that a rule like bird(Tweety) : fly(Tweety) I fly(Tweety) is supposed to "fire" only when­ ever it has become known that Tweety is a bird and it is supposed to be ignored in all other cases. But this objection implicitly interprets Default Logic as the logic of some agent or system for which computational issues might mat­ ter, and not as the logic of an ideally rational agent.

## 6 Conclusion

Default logic can be given a preferential semantics, provided Shoham's original requirement that the semantics has to be based on a strict partial order on the set of standard models is dropped. Default logic can be captured by epistemic prefer­ ence models (for a some standard logic L), in which a (not necessarily transitive) preference relation on the set of (partial) world descriptions is defined. These epistemic pref­ erence models for L characterize the class of nonmonotonic consequence operations for L, which satisfy inclusion, cu­ mulative transitivity, and CnL -invariance.

Cumulative monotonicity can be considered to be a ratio­ nality requirement on consequence operations, but this does not imply that noncumulative logics are necessarily inade­ quate formalizations of the (nonmonotonic) reasoning of an ideally rational agent. Instead, cumulative monotonicity can be seen as a constraint on the set of defaults a rational agent might believe, and in the context of Default Logic this con­ straint is for example satisfied sets of normal defaults with­ out prerequisites.

## References

1. [Besnard, 1989] P. Besnard, An Introduction to Default Logic Springer, Berlin, 1989.
2. [Brewka, 1990] G. Brewka, Cumulative Default Logic: in defense of nonmonotonic inference rules. Artificial Intelligence 50:183-205, 1990.
3. [Dix and Makinson, 1992] J. Dix and D. Makinson, The relationship between KLM and MAK models for nonmonotonic inference operations, Journal of Logic, Language and Information 1:131-140,1992.
4. [Etherington, 1988] D. Etherington, Reasoning with Incomplete Information. Pitman, London, 1988.
5. [Gabbay, 1985] D. Gabbay, Theoretical foundations for non- monotonic reasoning in expert systems. In Logics and Models of Concurrent Systems, pages 439-457, K.R. Apt (ed.), Springer, Berlin, 1985.
6. [Gardenfors, 1988] P. Gardenfors, Knowledge in Flux: Modeling the Dynamics of Epistemic States. MIT Press, Cambridge Mass., 1988. Halpern and Moses, 1985]
7. Y. Halpern and Y. Moses, Towards a theory of knowledge and ignorance: preliminary report. In Logics and Models of Concurrent Systems, pages 459-476, K.R. Apt (ed.), Springer, Berlin, 1985.
8. [Kraus eta/., 1990] S. Kraus, D. Lehmann and M. Magidor, Nonmonotonic reasoning, preferential models and cumulative logic. Artificial Intelligence 44 :167-207, 1990.
9. [Levesque, 1990] H.J. Levesque, All I know: A study in autoepistemic logic. Artificial Intelligence 42:263-309, 1990.
10. [Lin and Shoham, 1992] F. Lin andY. Shoham, A logic of knowledge and justified assumptions. Artificial Intelligence 57:271-289, 1992.
11. [Makinson, 1989] D. Makinson, General Theory of Cumulative Inference. In Non-Monotonic Reasoning, pages 1-18, M. Reinfrank eta/. (eds.). Springer, Berlin, 1989.
12. [McCarthy, 1980] J. McCarthy, Circumscription-a form of nonmonotonic reasoning. Artificial Intelligence 13:27-39, 1980.
13. [McDermott, 1982] D. McDermott, Nonmonotonic logic II: nonmonotonic modal theories. Journal of the ACM 29:33-57, 1982
14. [Reiter, 1980] R. Reiter, A logic for default reasoning . Artificial Intelligence 13:81-132, 1980.
15. [Savage, 1972] L.J. Savage, The Foundations of Statistics Dover, New York, 1972 (2nd ed.; 1st ed. John Wiley, 1954)
16. [Shoham, 1987] Y . Shoham, A semantical approach to nonmonotonic logics, in: M. Ginsberg, ed., Readings in Nonmonotonic Reasoning (Morgan Kaufmann, Los Altos CA, 1987) 227-250.
17. [Shoham, 1988] Y. Shoham, Reasoning about Change . MIT Press, Cambridge MA, 1988.
18. [Shvarts, 1990] G. Shvarts, Autoepistemic modal logic. In Theoretical Aspects of Reasoning About Knowledge: Proceedings of the Fourth Conference,, pages 97-109, R. Parikh (ed.), San Mateo CA, Morgan Kaufmann.
19. [Voorbraak, 1991] F. Voorbraak, A preferential model semantics for default logic. In Symbolic and Quantitative Approaches to Uncertainty, pages 344-351, R. Kruse and P. Siegel (eds.), Springer, Berlin, 1991.
20. [Voorbraak, 1992] F. V oorbraak, Generalized Kripke models for epistemic logic. In Theoretical Aspects of Reasoning About Knowledge: Proceedings of the Fourth Conference, pages 214-228, Y. Moses (ed.), Morgan Kaufmann, San Mateo CA ,1992 [Voorbraak, 1993]
21. F. Voorbraak,Preference-based semantics for nonmonotonic logics. Logic Group Preprint Series, Dept. of Philosophy, Utrecht University.