GERHARD BREWKA AND THOMAS EITER

PRIORITIZING DEFAULT LOGIC

1. INTRODUCTION

In nonmonotonic reasoning con�icts among defaults are ubiquitous. For instance, more speci�c rules may be in con�ict with more general ones, a problem which has been studied intensively in the context of inheritance networks (Poole, 1985; Touretzky, 1986; Touretzky et al., 1991). When defaults are used for representing design goals in con�guration tasks con�icts naturally arise. The same is true in model based diagnosis where defaults are used to represent the assumption that components typically are ok. In legal reasoning con�icts among rules are very common (Prakken, 1993) and keep many lawyers busy (and rich).

The standard nonmontonic formalisms handle such con�icts by generating multiple belief sets. In default logic (Reiter, 1980) and autoepistemic logic (Moore, 1985) these sets are called extensions or expansions, respectively. In circumscription (McCarthy, 1980) the belief sets correspond to different classes of preferred models.

Usually, not all of the belief sets are plausible. We often tend to prefer some of the con�icting rules and are interested in the belief sets generated by the preferred rules only. One way to achieve this is to re-represent the defaults in such a way that the unwanted belief sets are not generated, for instance by adding new consistency conditions to a default. This approach has the advantage that the logical machinery of the underlying nonmonotonic logic does not have to be changed. On the other hand, re-representing the defaults in this way is a very clumsy business. The resulting new defaults tend to be rather complex. Moreover, the addition of new information to the knowledge base may lead to further re-representations. In other words, elaboration tolerance is violated.

For this reason we prefer an approach where preferences among defaults can be represented via an explicit preference relation and where the logical machinery is extended accordingly. Indeed, for all major nonmonotonic formalisms, such prioritized versions have been proposed in the past. Among them are prioritized circumscription (Gelfond et al., 1989), hierarchic autoepistemic logic (Konolige, 1988), prioritized theory revision (Benferhat et al., 1993; Nebel, 1998), prioritized logic programming (Sakama and Inoue, 1996; Zhang and Foo, 1997), or prioritized abduction (Eiter and Gottlob, 1995).

Also several prioritized versions of Reiter’s default logic, the logic we are dealing with in this paper, have been described in the literature (Marek and Truszczy� nski, 1993; Brewka, 1994a; Baader and Hollunder, 1995; Delgrande and Schaub, 1997), as well as of defeasible logics beyond default logic (Nute, 1994; Gelfond and Son, 1998). However, as we will show in Section 3., these approaches are not fully satisfactory. It turns out that some of them implicitly recast Reiter’s default logic to a logic of graded beliefs, while others do overly enforce the application of rules with high priority, which leads to counterintuitive behavior.

Our approach takes a different perspective, which is dominated by the following two main ideas. The �rst is that the application of a default rule means to jump to a conclusion, and this conclusion is yet another assumption which has to be used globally in the program for the issue of deciding whether a rule is applicable or not. The second is that the rules must be applied in an order compatible with the priority information. We take this to mean that a rule is applied unless it is defeated via its assumptions by rules of higher priorities. This view is new and avoids the unpleasant behavior which is present with the other approaches. Our formalization of these ideas involves a dual of the standard Gelfond-Lifschitz reduction and a certain operator used to check satisfaction of priorities. In order to base our approach on �rmer grounds, we set forth some abstract principles that, as we believe, any formalization of prioritized default logic should satisfy. We demonstrate that our approach satis�es these principles, while other approaches violate them.

The remainder of this paper is organized as follows. The next section recalls the basic de�nitions of default logic and introduces the notion of a prioritized default theory. Section 3. introduces two basic principles for preference handling, reviews some approaches to prioritized default logic and demonstrates that they fail to satisfy the principles. In Section 4., we then present our approach, by introducing the concept of preferred extensions. We will introduce this notion in a stepwise manner, starting with the simplest case, namely prerequisite-free normal defaults, which are also called supernormal defaults. We then extend our de�nition to prerequisite-free default theories, showing that an additional �xed point condition is needed to get the de�nition of preferred extensions right. Finally, we handle arbitrary default theories by reducing them to the prerequisite-free case. The reduction can be viewed as dual to the famous Gelfond/Lifschitz reduction for extended logic programs. In Section 5. we show how preference information can be expressed in the logical language. This makes it possible to reason not only with, but also about preferences among rules. Section 6. discusses related work, and concludes the paper by considering possible extensions and outlining further work.

The work reported here generalizes the approach presented in (Brewka and Eiter, 1998), which covers the fragment of default logic equivalent to extended logic programs, and extends the results.

PRIORITIZING DEFAULT LOGIC

2. PRIORITIZED DEFAULT THEORIES

We �rst recall the basic de�nitions underlying Reiter’s default logic. A default theory is a pair Δ = (D, W) of a theory W containing �rst-order sentences and a set of defaults D. Each default is of the form a : b_{1}, …, b_{n}/c, n ≥ 1, where a, b_{i}, and c are �rst-order formulas. The intuitive meaning of the default is: if a is derived and the b_{i} are separately consistent with what is derived, then infer c. Formula a is called the prerequisite, each b_{i} a justi�cation, and c the consequent of the default. For a default d we use pre(d), just(d), and cons(d) to denote the prerequisite, the set of justi�cations, and the consequent of d, respectively; ¬just(d) denotes {¬a | a ∈ just(d)}. As usual, we assume that W and D are in skolemized form and that open defaults, i.e., defaults with free variables, represent the sets of their ground instances over the Herbrand universe (Reiter, 1980); a default theory with open defaults is closed by replacing open defaults with their ground instances. In what follows, we implicitly assume that default theories are closed before extensions etc are considered.

A (closed) default theory generates extensions which represent acceptable sets of beliefs which a reasoner might adopt based on the given default theory (D, W). Extensions are de�ned in (Reiter, 1980) as �xed points of an operator Γ_{Δ}. This operator Γ_{Δ} maps an arbitrary set of formulas S to the smallest deductively closed set S′ that contains W and satis�es the condition: if a : b_{1}, …, b_{n}/c ∈ D, a ∈ S′ and ¬b_{i} ∉ S then c ∈ S′. Intuitively, an extension is a set of beliefs containing W such that

1. as many defaults as consistently possible have been applied, and

2. only formulas possessing a non-circular derivation from W using defaults in D are contained.

Extensions can be characterized as follows (Marek and Truszczy� nski, 1993): Let D^{E} = {a/c | a : b_{1}, …, b_{n}/c ∈ D, ¬b_{i} ∉ E, i = 1, …, n} denote the reduct of D by E. Then E is an extension of T, if and only if E = T h_{D^{E}}(W ∪ D^{E}), where T h_{A}(S) is the deductive closure of S in the monotonic rule system F OL + A, i.e., �rst-order logic augmented with the rules in A.

A default theory Δ may have zero, one or multiple extensions. The (skeptical) conclusions of Δ is the set of formulas contained in all extensions of Δ. Default theories possessing at least one extension will be called coherent. We say a default a : b_{1}, …, b_{n}/c is defeated by a set of formulas S, iff ¬b_{i} ∈ S for some i ∈ {1, …, n}.

A default d = a : b/c is called normal, if b is logically equivalent to c; it is called prerequisite-free, if a is a logical truth, which is denoted by ⊤ . Defaults which are both prerequisite-free and normal are called supernormal. A default theory is called normal (prerequisite-free, supernormal), if all of its defaults are normal (prerequisitefree, supernormal), respectively.

A default d is called generating in a set of formulas S, if pre(d) ∈ S and ¬just(d)∩ S = ∅; denote by GD(E, D) the set of all defaults from D which are generating in E. It is well-known (Reiter, 1980) that every extension of a default theory Δ = (D, W) is characterized through GD(D, E), i.e.,

E = T h(W ∪ cons(GD(D, E)))  (1)

where cons(D′) = {cons(d) | d ∈ D′} for any set D′. Moreover, if Δ is prerequisitefree, then every E which satis�es (1) is an extension, cf. (Marek and Truszczy� nski, 1993).

We now introduce the notion of a prioritized default theory. Basically, we extend default theories with a strict partial order < (i.e., d ≮ d and d < d′, d′ < d′′ implies d < d′′) on the default rules. A default d will be considered preferred over default d′, whenever d < d′ holds.

De�nition 1. A prioritized default theory is a triple Δ = (D, W, <) where (D, W) is a default theory and < is a strict partial order on D.

Partially ordered default theories have the advantage that the preference ordering among certain defaults can be left unspeci�ed. This is important because in many cases there is no natural way of assigning preferences. However, the case of arbitrary partial orders can be reduced to particular re�nements, namely well-orderings, in a canonical way. Recall that a partial order is a well-ordering, iff every subset of the elements has the least element; observe that any well-ordering is a total ordering.

De�nition 2. A fully prioritized default theory is a prioritized default theory Δ = (D, W, <) where < is a well-ordering.

Conclusions of prioritized default theories are de�ned in terms of preferred extensions, which are a subset of the classical extensions of Δ, i.e., the extensions of (D, W) according to (Reiter, 1980). The de�nition of preferred extension for fully prioritized default theories will be given in the next section. The general case of arbitrary prioritized default theories can then be reduced to this case as follows.

De�nition 3. Let Δ = (D, W, <) be a closed prioritized default theory. E is a prioritized extension of Δ iff E is a prioritized extension of a fully prioritized default theory Δ′ = (D, W, <′) such that d < d′ implies d <′ d′.

The preferred extensions of an open prioritized default theory Δ are the preferred extensions of Δ^{∗} obtained by closing Δ. The partial order < is inherited from D to the ground set of instances D^{∗} in the obvious way. We assume here that no con�ict arises, i.e., d < d does not result for any d ∈ D^{∗}; otherwise, no preferred extensions are de�ned.

In the remainder of this paper, we will restrict our discussion to fully prioritized default theories. Unless stated otherwise, all default theories are tacitly assumed to be closed.

3. PROBLEMS WITH EXISTING APPROACHES

Different prioritized versions of default logic have been proposed in the literature, e.g. (Marek and Truszczy� nski, 1993; Brewka, 1994a; Baader and Hollunder, 1995; Rintanen, 1995; Delgrande and Schaub, 1997). They do not behave as desired in certain situations, and we show that some of them fail to satisfy natural principles for preference handling in default logic.

3.1. Principles for priorities

The �rst principle can be viewed as a meaning postulate for the term �preference� and states what we consider a minimal requirement for preference handling in rule based systems:

Principle I. Let B_{1} and B_{2} be two extensions of a prioritized default theory Δ generated by the defaults R∪{d_{1}} and R∪{d_{2}}, where d_{1}, d_{2} ∉ R, respectively. If d_{1} is preferred over d_{2}, then B_{2} is not a preferred extension of T.

We �nd it hard to see how the use of the term �preference among rules� could be justi�ed in cases where Principle I is violated.

The second principle is related to relevance. It tries to capture the idea that the decision whether to believe a formula p or not should depend on the priorities of defaults contributing to the derivation of p only, not on the priorities of defaults which become applicable when p is believed:

Principle II. Let E be a preferred extension of a prioritized default theory Δ = (D, W, <), and let d be a (closed) default such that the prerequisite of d is not in E. Then E is a preferred extension of Δ′ = (D ∪ {d}, W, <′) whenever <′ agrees with < on priorities among defaults in D.

Thus, adding a rule which is not applicable in a preferred belief set can never render this belief set non-preferred unless new preference information changes preferences among some of the old rules (e.g. via transitivity). In other words, a belief set is not blamed for not applying rules which are not applicable.

We will see that each of the existing treatments of preferences for default logic, described in (Marek and Truszczy� nski, 1993; Brewka, 1994a; Baader and Hollunder, 1995; Rintanen, 1995), violates one of these principles.

3.2. Control of Reiter’s quasi-inductive de�nition

The �rst group of proposals (Marek and Truszczy� nski, 1993; Brewka, 1994a; Baader and Hollunder, 1995) uses preferences to control the quasi-inductive de�nition of extensions (Reiter, 1980): in each step of the generation of extensions the defaults with highest priority whose prerequisites have already been derived are applied. Now what is wrong with this idea? The answer is: the preferred extensions do not take seriously what they believe. It may be the case that a less preferred default is applied although the prerequisite of a con�icting, more preferred default is believed in a preferred extension. As we will see, this can lead to situations where Principle I is violated.

The mentioned approaches differ in technical detail. We do not want to present the exact de�nitions here. Instead, we will illustrate the dif�culties using an example for which all these approaches obtain the same result.

Example 4. Assume we are given the following default theory:

\begin{matrix}(1) & a : b/b \\ (2) & ⊤ : ¬b/¬b \\ (3) & ⊤ : a/a \end{matrix}

Assume further that (1) is preferred over (2) and (2) over (3). This default theory has two classical extensions, namely E_{1} = T h({a, b}), which is generated by rules (1) and (3), and E_{2} = T h({a, ¬b}), which is generated by rules (2) and (3). The single preferred extension in the approaches mentioned above is E_{2}. The reason is that the prerequisite of (2) is derived before the prerequisite of (1) in the construction of the extension. The approaches thus violate Principle I. □

The selection of E_{2} in the previous example was already observed in (Brewka, 1994a). In that paper, the �rst author tried to defend his approach arguing that there is only weak evidence for the literal a in our example. We revise our view, however, and do not support this argument any longer. After all, default logic is not a logic of graded belief where degrees of evidence should play a role. Default logic models acceptance of belief based on defeasible arguments. Since a is an accepted belief, we believe rule (1) should be applied and E_{1} should be the preferred extension in the example.

3.3. Rintanen’s approach

An entirely different approach was proposed in (Rintanen, 1995). Rintanen uses a total order on (normal) defaults to induce a lexicographic order on extensions.

Call a normal default rule r = a:b/b applied in a set of formulas E (denoted r ∈ appl(E)), if a and b are in E. An extension E is then preferred over extension E′, if and only if there is a default r ∈ appl(E) \ appl(E′) satisfying the following condition: if r′ is preferred over r and r′ ∈ appl(E′), then r′ ∈ appl(E).

Unfortunately, also this approach leads to counterintuitive results and to a violation of our principles.

Example 5. Consider the following default theory:

\begin{matrix}(1) & a : b/b \\ (2) & ⊤ : ¬a/¬a \\ (3) & ⊤ : a/a \end{matrix}

Again (1) is preferred over (2), and (2) over (3). The default theory has two classical extensions, namely E_{1} = T h({¬a}) and E_{2} = T h({a, b}). Intuitively, since the decision whether to believe a or not depends on (2) and (3) only, and since (2) is preferred over (3), we would expect to conclude ¬a, in other words, to prefer E_{1}.

However, the approach of Rintanen prefers E_{2}. The reason is that in E_{2} default (1) is applied. Belief in a is thus accepted on the grounds that this allows us to apply a default of high priority. This is far from being plausible and amounts to wishful thinking. It is also easy to see that Principle II is violated: E_{1} clearly is the single preferred extension of rules (2) and (3) in Rintanen’s approach. Adding rule (1) which is not applicable in E_{1} makes E_{1} a non-preferred extension. □

The approach in (Rintanen, 1995) has been extended from normal to full default logic in (Rintanen, 1998). Moreover, variants of this approach are described in (Rintanen, 1998), which do not behave intuitively in certain situations either.

Since all the approaches discussed above suffer from drawbacks, we develop our new approach in the following section.

4. PREFERRED EXTENSIONS

In this section, we introduce our new notion of preferred extensions for fully prioritized default theories. As mentioned before, arbitrary prioritized default theories can be reduced to that case in a canonical manner.

We will consider the simplest case �rst, namely supernormal default theories. We then proceed to prerequisite-free default theories and, �nally, to arbitrary default theories.

4.1. Supernormal default theories

Preference handling in prioritized supernormal default theories is rather easy. The obvious idea is to check the applicability of defaults in the order of preference. We �rst introduce an operator C which, given a fully prioritized prerequisite-free default theory Δ (which is not necessarily supernormal), produces tentative conclusions of Δ.

Call a default d active in a set of formulas S, if pre(d) ∈ S, ¬just(d) ∩ S = ∅ and cons(d) ∉ S all hold. Intuitively, a default is active in S if it is applicable with respect to S and has not yet been applied.

De�nition 6. Let Δ = (D, W, <) be a fully prioritized prerequisite-free default theory. The operator C is de�ned as follows: C(Δ) = ⋃_{α≥0} E_{α}, where E_{0} = T h(W), and for every ordinal α > 0,

E_{α} = \{ \begin{matrix}\underline{E}_{α}, & if no default from D is active in \underline{E}_{α}; \\ T h(\underline{E}_{α} ∪ \{cons(d)\}) & otherwise, where \\ & d = min_{<}\{d′ ∈ D | d′ is active in \underline{E}_{α}\}, \end{matrix} where \underline{E}_{α} = ⋃_{β<α} E_{β}. (Note that for each successor ordinal α = β + 1, \underline{E}_{α} = E_{β}.)

In the case of supernormal default theories, the operator C always produces an extension in the sense of Reiter and thus can directly be used to de�ne preferred extensions:

De�nition 7. Let Δ = (D, W, <) be a fully prioritized supernormal default theory. E is the preferred extension of Δ if and only if E = C(Δ).

It is obvious that there is always exactly one preferred extension. Note that the de�nition of this extension is fully constructive. It extends the notion of preferred subtheories as developed in (Brewka, 1989) to the in�nite case.

4.2. Prerequisite-free default theories

Can we simply extend the de�nition for supernormal defaults to this case? The answer is obviously no. It may be the case that defaults are applied during the construction which are defeated later through the application of defaults of lower priority.

So, can we simply say: if the construction gives us an extension, then that extension is preferred? Unfortunately, the answer is again no.

Example 8. Consider the following default theory:

\begin{matrix}(1) & ⊤ : ¬b/a & (3) & ⊤ : a/a \\ (2) & ⊤ : ¬a/¬a & (4) & ⊤ : b/b \end{matrix}

Assume (1) < (2) < (3) < (4). Applying operator C to this default theory yields E = T h({a, b}). As easily seen, this is a classical extension. Nonetheless, one would certainly not say that this extension preserves priorities. What went wrong? Default (2) is defeated in E by applying a default which is less preferred than (2), namely default (3). In the construction of C(Δ) this remains unnoticed, since rule (1), although defeated in E, blocks the applicability of (2). In other words, without a special treatment of such cases, a rule (e.g. (3)) may inherit a high preference from a rule with the same consequent (namely (1)), even if that latter rule is not applicable in the extension. □

To avoid this, we have to impose an additional condition on an extension: in the construction of the tentative conclusions, we have to discard each rule whose consequent is in E, but which is defeated in E. Since we have to take E as the result of the construction into account, this amounts to adding a �xed point condition. What we will do is check whether we arrive at the same set of formulas after eliminating rules which are defeated in E and whose head is in E.

De�nition 9. Let Δ = (D, W, <) be a fully prioritized prerequisite-free default theory. Then, a set E of formulas is a prioritized extension of Δ, if and only if

E = C(Δ^{⋆E}),

where Δ^{⋆E} is obtained from Δ by deleting all defaults whose consequents are in E and which are defeated in E.

This de�nition is coherent with the intuition that preferred extensions are distinguished classical extensions. Moreover, as in the case of supernormal theories, the preferred extension (if it exists) is unique.

Proposition 10. Let Δ = (D, W, <) be a fully prioritized prerequisite-free default theory. Then, every preferred extension E of Δ is a classical extension, and Δ has at most one preferred extension.

Proof: To show the �rst part, assume that E is a preferred extension of Δ. We show that

E = T h(W ∪ cons(GD(D, E)))  (2)

holds; since all defaults are prerequisite-free, this implies that E is a classical extension of Δ, cf. paragraph after Equation (1).

Since E = C(Δ^{⋆E}), no default from D \ GD(D, E) is applied in the construction of E; hence, E ⊆ T h(W ∪ cons(GD(D, E))) follows. On the other hand, since each E_{α} is included in E and E does not defeat d, for every d ∈ GD(D, E), it follows cons(d) ∈ C(Δ^{⋆E}); hence, T h(W ∪ cons(GD(D, E))) ⊆ E follows. This implies Equation (2), and proves that E is a classical extension of Δ.

For the second part, assume that different preferred extensions E ≠ E′ exist. We derive a contradiction. Let d be the least default in D such that either (i) d ∈ GD(D, E) and cons(d) ∉ E′, or (ii) d ∈ GD(D, E′) and cons(d) ∉ E. Since E ≠ E′, d must exist. Consider �rst the case (i). It follows that d ∈ D^{⋆E′}; for, otherwise cons(d) ∈ E′ holds, which is a contradiction. The default d must be defeated by E′; from the de�nition of C(Δ^{⋆E}), it follows that d is defeated by T h(W ∪ cons(K)) for K = {d′ ∈ GD(D, E′) | d′ < d}. From the minimality of d, it follows that for every d′ ∈ K it holds that cons(d′) ∈ E. Hence, T h(W ∪ cons(K)) ⊆ E, which means E defeats d. This is a contradiction to d ∈ GD(D, E), however. The case (ii), i.e., d ∈ GD(D, E′) and cons(d) ∉ E is analogous. This proves the result.

4.3. General default theories

We will now reduce the general case to the prerequisite-free case. The basic idea is the following: in order to check whether an extension E of a fully prioritized default theory Δ is preferred, we evaluate the prerequisites of the default rules according to the extension E. Evaluating prerequisites means (1) eliminating prerequisites which are contained in the extension E from the corresponding rules, and (2) eliminating rules whose prerequisites are not contained in E. Observe that this operation can be viewed as a dual of the standard Gelfond/Lifschitz reduction from logic programming (Gelfond and Lifschitz, 1988), in which the justi�cations rather than the prerequisites are used to eliminate and simplify rules.

Finally, we check whether the resulting prerequisite-free theory Δ_{E} has E as its preferred extension.

De�nition 11. Let Δ = (D, W, <) be a fully prioritized default theory and E a set of formulas. The default theory Δ_{E} = (D_{E}, W, <_{E}) is obtained from Δ as follows: D_{E} results from D by

1. eliminating every default d ∈ D such that pre(d) ∉ E, and

2. replacing pre(d) by ⊤ in all remaining defaults;

<_{E} is inherited from < as follows: for any rules d and d′ in D_{E}, d <_{E} d′ holds if and only if d1 < d1′ holds for the <-least rules d1 and d1′ in D which give rise to d and d′ (i.e., d1_{E} = d and d1′_{E} = d′), respectively.

The resulting default theory is clearly prerequisite-free. We thus can de�ne preferred extensions for general default theories as follows:

De�nition 12. Let Δ = (D, W, <) be a fully prioritized default theory. Then, E is a prioritized extension of Δ, if (i) E is a classical extension of Δ, and (ii) E is a prioritized extension of Δ_{E}.

Let us show that the problematic examples discussed in Section 3. are handled correctly in our approach:

Example 13. Consider the default theory Δ:

\begin{matrix}(1) & a : b/b \\ (2) & ⊤ : ¬b/¬b \\ (3) & ⊤ : a/a \end{matrix}

Again we assume that (1) is preferred over (2) and (2) over (3). This default theory has two classical extensions, namely E_{1} = T h({a, b}) and E_{2} = T h({a, ¬b}). Δ_{E_{1}} consists of the rules

\begin{matrix}(1) & ⊤ : b/b \\ (2) & ⊤ : ¬b/¬b \\ (3) & ⊤ : a/a \end{matrix}

It is not dif�cult to see that C(Δ_{E_{1}}) = E_{1}. Since there are no rules whose head is in E_{1} but which are defeated in E_{1}, E_{1} is a preferred extension. On the contrary, E_{2} is not preferred. Note that the dual E_{2}-reduct of Δ is the same as the dual E_{1}-reduct, and that C(·) applied to the reduct does not reproduce E_{2}. □

Example 14. Consider the following default theory Δ′:

\begin{matrix}(1) & a : b/b \\ (2) & ⊤ : ¬a/¬a \\ (3) & ⊤ : a/a \end{matrix}

Again (1) is preferred over (2), and (2) over (3). The default theory has two classical extensions, namely E_{1} = T h({¬a}) and E_{2} = T h({a, b}). We argued in Section 3. that E_{1} should be preferred. Consider Δ′_{E_{1}}:

\begin{matrix}(2) & ⊤ : ¬a/¬a \\ (3) & ⊤ : a/a \end{matrix}

Clearly, C(Δ′_{E_{1}}) = E_{1}, and since again there are no rules defeated in E_{1} whose head is in E_{1}, we have that E_{1} is preferred.

E_{2} is not preferred since C(Δ′_{E_{2}}) = T h({b, ¬a}) which differs from E_{2}. □

The following proposition tells us that all rules which are not generating in a preferred extension must be defeated by some appropriate generating rules, which must have higher priority.

Proposition 15. Let Δ = (W, D, <) be a fully prioritized ground default theory, and let E be a classical extension of Δ. Then, E is a preferred extension of Δ, if and only if for each default d ∈ D such that pre(d) ∈ E and cons(d) ∉ E, there exists a set of defaults K_{d} ⊆ {d′ ∈ GD(D, E) | d′ < d} such that d is defeated in T h(W ∪ cons(K_{d})).

Proof: (⇐) Suppose that for every default d such that pre(d) ∈ E and cons(d) ∉ E a set K_{d} ⊆ {d′ ∈ GD(D, E) | d′ < d} exists such that T h(W ∪ cons(K_{d})) defeats d. By (trans�nite) induction on the sets E_{α}, α ≥ 1, we show that the least active default d_{E} from D_{E}^{⋆E} in \underline{E}_{α}, provided one exists, stems from some d ∈ GD(D, E) and cons(d) ∈ E_{α} holds.

For α = 1, the statement holds. Indeed, the least rule d_{E} of D_{E}^{⋆E} is active. Let d be the least parent of d_{E} in D, i.e., d = min_{<}{d′ | d′_{E} = d_{E}}. Assuming that d ∈ D \ GD(D, E), we obtain K_{d} = ∅, and hence d is defeated by E_{0} = T h(W). This contradicts that d_{E} is active in \underline{E}_{1} = E_{0}, however. Thus, d ∈ GD(D, E) holds, and cons(d) ∈ E_{α} follows.

Let then α > 1 and assume the statement holds for all 1 ≤ β < α. Suppose the least default d_{E} from D_{E}^{⋆E} active in \underline{E}_{α} exists, and that its least parent in D is not in GD(D, E). The induction hypothesis implies that for each d′ ∈ GD(D, E) such that d′ < d it holds that cons(d′) ∈ \underline{E}_{α}. Hence, T h(W ∪ cons(K_{d})) ⊆ \underline{E}_{α}, which implies that d is defeated by \underline{E}_{α}. This contradicts that d_{E} is active. Thus, if d_{E} exists, then d ∈ GD(D, E) holds; clearly, cons(d) ∈ E_{α}. This concludes the induction, from which C(Δ_{E}^{⋆E}) = T h(W ∪ cons(GD(D, E))) follows. By Equation (1), it follows E = C(Δ_{E}^{⋆E}), which means that E is a preferred extension.

(⇒) Suppose E is a preferred extension, but some d ∈ D such that pre(d) ∈ E and cons(d) ∉ E is not defeated by any T h(W ∪ cons(K)), where K ⊆ {d′ ∈ GD(D, E) | d′ < d}. Let d be the least such rule in D. Since E is a preferred extension, for every d′ ∈ GD(D, E) we have cons(d′) ∈ C(Δ_{E}^{⋆E}). By the minimality of d, it follows that d_{E} becomes the least active rule in D_{E}^{⋆E} at some step α, and up to this point, only consequents of active reducts d′_{E} of d′ ∈ K have been added, i.e., \underline{E}_{α} = T h(W ∪ cons(K)) holds. Since \underline{E}_{α} does not defeat d_{E}, the rule is applied, which implies C(Δ_{E}^{⋆E}) ≠ E. Consequently, E is not a preferred extension, which is a contradiction.

Exploiting this proposition, we can establish that the principles for a prioritization approach from above are both satis�ed by our approach.

Proposition 16. The approach to preferred extensions satis�es both Principles I and II as described in Section 3..

Proof: Principle I. Let Δ = (W, D, <) be a prioritized default theory, and let E, E′ be classical extensions of Δ such that GD(D, E) = R∪{d} and GD(D, E′) = R∪{d′}, where d_{1}, d_{2} ∉ R and d < d′. We have to show that E′ is not a preferred extension of Δ.

Towards a contradiction, suppose E′ is a preferred extension. Let Δ′ = (W, D, <′) be a full prioritization of Δ. Since d ∈ GD(D, E), it holds that pre(d) ∈ T h(W ∪ cons(R)); hence, d survives the dual GL-reduction with rspect E′, and d, d′ give rise to defaults d_{E′}, d′_{E′} ∈ D_{E′}, respectively.

Since d ∉ GD(D, E′), it follows that pre(d) ∈ E′ but cons(d) ∉ E′. Hence, by Proposition 15. , it follows that d is defeated by T h(W ∪ cons(K)) for some K ⊆ {d′′ ∈ GD(D, E′) | d′′ < d}. It follows that K ⊆ R holds. Since d is defeated by T h(W ∪ cons(K)) and T h(W ∪ cons(K)) ⊆ E, it follows that d is defeated by E. This contradicts d ∈ GD(D, E); satisfaction of Principle I follows. Principle II. Let E be a preferred extension of Δ = (W, D, <), and let d be a (closed) default such that pre(d) ∉ E. We have to show that E is a preferred extension of Δ′ = (D ∪ {d}, W, <′) where <′ is compatible with <.

Consider the dual reduct of Δ′ with respect E, i.e., Δ′_{E} = ((D ∪ {d})_{E}, W, <′_{E}). Then, the default d is eliminated in the dual reduct, and we have Δ′_{E} = Δ_{E}. Since E is a preferred extension of Δ_{E}, it follows immediately that E is a preferred extension of Δ′. Thus, Principle II is satis�ed. (Remark: the proof can be easily adapted for an open default d, if closing d does not lead to inconsistency of <′.)

Thus, our approach satis�es these general benchmarks for a prioritization logic. On the other hand, a less desirable property of the approach is that in some cases no

preferred extension may exist. This is what happens in Example 8. ; it is easily checked that neither of the two classical extensions E = T h({a, b}) and E′ = T h({¬a, b}) is a preferred extension.

Another example shows that in general, normal prioritized default theories may have no preferred extension. Thus, the property that supernormal default theories always have extensions is lost if prerequisites are allowed in the defaults.

Example 17. Consider the following defaults:

\begin{matrix}(1) & a : ¬b/¬b \\ (2) & ⊤ : b/b \\ (3) & b : a/a \end{matrix}

This default theory has the unique classical extension E = T h({a, b}). However, assuming (1) < (2) < (3), E is not preferred, since preference of (1) requires to conclude ¬b. □

Intuitively, if no preferred extension exists, then the priorities as speci�ed by the user are incompatible with the way in which defaults must be executed to generate an extension. In the preceding example, this is clearly the case.

There are different possibilities to react to such an inconsistency, and some of them have been discussed in (Brewka and Eiter, 1998). There are two main directions for handling such inconsistencies. One direction is to stop on occurrence of such an inconsistency and notify the user that there is an inconsistency in the priorities. The other would be trying to overcome this inconsistency, by reconciling the priority information and the logical entrenchment of default application by relaxing or modifying the priority information in a way such that preferred extensions become possible.

We believe that in general, the �rst direction is preferable to the second one since the user becomes explicitly aware that there is something wrong with his preferences, which cannot be satis�ed. However, we could require that an approach to priorities should be consistent in the sense that if classical extensions exist, then some of them should always be selected by the prioritization method. In this case, a relaxation of our preferred extension approach would be desirable, which selects the preferred extensions if some exist and some classical extensions, according to some rationale, if no preferred extensions exist.

There are different possibilities for generalizing the preferred extensions to such �weakly� preferred extensions. One such possibility is to allow a minimal reordering of the defaults in D, i.e., E becomes a preferred extension after switching as few neighbored defaults in < as possible, cf. (Brewka and Eiter, 1998). Another approach would be to remove preferences between defaults, e.g., to relax the ordering < as little as possible such that preferred extensions exist. We do not pursue these possibilities any further here. However, we observe some limitations of such weakly preferred extensions.

We call a function χ which selects a subset χ(Δ) from the classical extensions of a prioritized default theory D a consistent preference relaxation (CPR) of preferred extensions, if χ(Δ) selects all and only preferred extensions if preferred extensions exist, and selects some (arbitrary) classical extensions provided some classical extension exists. Then, the following holds.

Proposition 18. Every consistent preference relaxation χ of preferred extensions must violate both Principle I and Principle II.

Proof: (Sketch) To show that no CPR χ can satisfy Principle I in general, we consider a prioritized default theory Δ = (W, D, <) such that Δ has classical extensions but no preferred extensions, and such that χ can not select any of the classical extensions without violating Principle I. De�ne

W = {b_{i} → (b_{i+1} ∧ c), a_{i} ↔ ¬b_{i} | i ≥ 0},
D = {⊤ : a_{i}/a_{i}, ⊤ : b_{i}/b_{i} | i ≥ 0} ∪ {⊤ : ¬c/⊥},

where all a_{i}, b_{i} and c are propositional atoms, and let < be the well-ordering such that

\begin{matrix}⊤ : a_{i}/a_{i} < ⊤ : b_{i}/b_{i} < ⊤ : a_{i+1}/a_{i+1}, \\ ⊤ : a_{i}/a_{i} < ⊤ : ¬c/⊥, ⊤ : b_{i}/b_{i} < ⊤ : ¬c/⊥ \end{matrix} \} i ≥ 0,

where ⊥ denotes falsity. It can be seen that the classical extensions of Δ are of the form

E^{i} = T h(W ∪ cons({⊤ : a_{k}/a_{k}, ⊤ : b_{j}/b_{j} | 0 ≤ k < i, j ≥ i})), i ≥ 0.

Moreover, for each i ≥ 0, it holds that GD^{i} = GD(D, E^{i}) and GD^{i+1} = GD(D, E^{i+1}) are of the form GD^{i} = R ∪ {d′} and GD^{i+1} = R ∪ {d} such that d < d′, where R = GD^{i} ∩ GD^{i+1}, d = ⊤ : a_{i}/a_{i}, and d′ = ⊤ : b_{i}/b_{i}.

Hence, if χ satis�es Principle I, then it must not select E^{i}. Since this holds for all i ≥ 0, χ cannot select any classical extension. Observe that no preferred extensions exist (cf. Proposition 16. ). This proves unsatis�ability of Principle I.

That also Principle II is unsatis�able for any CPR χ is exempli�ed by the following prioritized default theory Δ = (∅, D, {1 < 2}), which is rephrased from (Brewka and Eiter, 1998):

\begin{matrix}(1) & ⊤ : ¬b/c \\ (2) & ⊤ : a/b \end{matrix}

The unique classical extension of Δ is E = T h({b}), which must be selected by χ. Augment Δ by a default (0) c : ⊤/¬a, such that 0 < 1 and 0 < 2; let Δ′ be the resulting default theory. Clearly, pre(0) ∉ E. However, E cannot be selected by χ, since Δ′ has the unique preferred extension E′ = T h({¬a, c}). Hence, χ violates Principle II.

This result tells us that we have to sacri�ce the principles if we want to have a �weakly� preferred extension for each coherent default theory. We take this as additional support for our view that the preferences should be reconsidered in situations where no preferred extension exists.

Observe that the prioritized default theory Δ showing the failure of Principle I is in�nite. It turns out that this is essential. In fact, over a �nite (closed) Δ, the following CPR χ satisfying Principle I is possible. In the case in which Δ has a preferred extension, χ just returns hat collection. In the case in which no preferred extension exists, �x a well-ordering <′ compatible with < in Δ = (D, W, <), and de�ne a relation ≺ on the classical extensions of Δ by E ≺ E′ iff GD(D, E) = R ∪ {d}, GD(D, E′) = R ∪ {d′} where d, d′ ∉ R and d <′ d′. Let then χ select the minimal elements of ≺, i.e., the classical extensions E such that E′ ⊀ E for all other classical extensions E′. It can be shown that ≺ is irre�exive, and moreover that ≺ has some minimal element. Hence, χ(Δ, <′) selects some classical extension(s), if some exist. Moreover, by construction of ≺ it is easily seen that χ satis�es Principle I.

5. EXPRESSING PREFERENCES IN THE LANGUAGE

For several applications like legal reasoning it is important to reason not only with, but also about the preferences among default rules. Such preferences often depend on the particular context at hand, and it is not possible to assign preferences independently of a particular context.

To make reasoning about default priorities possible, we must be able to refer to defaults explicitly, and we must introduce a special predicate symbol representing default preferences. We thus extend our logical language in two respects.

1. We introduce a distinct set of rule names N. A naming function assigns a unique name to default rules. Formally, default names are simply ground terms in the underlying language.

2. We use the reserved two-place in�x predicate symbol ≺ to represent default priority. For instance, if d_{1} and d_{2} are default names, then d_{1} ≺ d_{2} is a formula with the intended meaning: d_{1} has priority over d_{2}.

De�nition 19. A preferential default theory is a triple Δ = (D, W, name) where

1. (D, W) is a default theory,

2. name : D → N is an injective function, and

3. W contains axioms guaranteeing that ≺ is a strict partial order.

Note that we do not restrict the appearance of ≺ to W. It is possible (and useful) to have defaults which derive priority relations among other defaults.

An extension of a preferential default theory Δ = (D, W, name) is just a classical extension of (D, W). The question now is how to de�ne preferred extensions for preferential default theories.

All the derived preference information now is contained in the extensions of Δ. What we need is a way to eliminate an extension if it contains priority information which is in con�ict with the way the extension was generated.

Given the techniques developed for prioritized default theories, it is not dif�cult to see how this can be done. Basically, an extension E of a preferential default theory is preferred iff E is a preferred extension of a fully prioritized default theory (D, W, <) such that < is compatible with the preference information in E. Compatibility is tested by generating a syntactic description of < in terms of ≺ and checking whether this description is consistent with E.

De�nition 20. Let Δ = (D, W, name) be a preferential default theory, and let E be a classical extension of Δ. We say < is compatible with E if and only if

E ∪ {d_{i} ≺ d_{k} | r_{i} < r_{k}, name(r_{i}) = d_{i}, name(r_{k}) = d_{k}}

is consistent.

De�nition 21. Let Δ = (D, W, name) be a preferential default theory. Then, a set of formulas E is a preferred extension of Δ if and only if E is a preferred extension of some fully prioritized default theory (D, W, <) such that < is compatible with E.

Example 22. Let’s consider the following scenario. Your mother expects you to visit her on Sundays. Your wife likes the opera and expects you to join her whenever Mozart is played. Unfortunately, visiting your mother and simultaneously going to the opera is impossible. Normally, the rules representing your mother’s wishes must have preference over those representing your wife’s wishes. However, on your wife’s birthday, you de�nitely should give preference to her.

This scenario can be modeled as the following preferential default theory.^{1} The set of defaults D contains the following three rules:

(d_{1})  sunday : visit(mother)/visit(mother)
(d_{2})  play(mozart) : go(opera)/go(opera)
(d_{3}[d, d′]) mother rule(d) ∧ wife rule(d′) : d ≺ d′/d ≺ d′

The following formulas are in the background theory W:

birthday(wife) ∧ wife rule(d) ∧ mother rule(d′) → d ≺ d′,

mother rule(d_{1} ), wife rule(d_{2} ),

¬(visit(mother) ∧ go(opera)).

Now assume the following facts hold in addition (i.e., are in W):

sunday, play(mozart).

We obtain two classical extensions. Note that both extensions contain the preference information d_{1} ≺ d_{2}. It is easy to see that there is no total preference relation < compatible with this information such that E_{2} is a preferred extension of (D, W, <). Only the �rst extension is preferred and you should visit your mother.

Now consider what happens if we add birthday(wife). Again we obtain two extensions, E′_{1} containing visit(mother), and E′_{2} containing go(opera). In this case the preference information in both extensions is d_{2} ≺ d_{1}. Note that the applicability of default d_{3}[d_{1}, d_{2}] is blocked. Now E′_{1} cannot be reconstructed as preferred extension of a fully prioritized theory (D, W, <) such that < is compatible with E′_{1}. The extension E′_{2}, on the other hand, can be reconstructed in such a way: just use an ordering with r_{2} < r_{1} where name(r_{1}) = d_{1} and name(r_{2}) = d_{2}. That is, you should join your wife and go to the opera. □

6. RELATED WORK AND CONCLUSION

In this paper, we have presented an approach, based on the ideas of (Brewka and Eiter, 1998), to incorporating priority information into default logic. This approach overcomes problems of previous approaches with respect to general principles which, as we argue, any prioritized variant of default logic should satisfy. For space reasons, a detailed comparison of our approach to the many other variants of prioritized default logic is necessarily super�cial.

Rintanen’s approach and the approaches in (Marek and Truszczy� nski, 1993; Brewka, 1994b; Baader and Hollunder, 1995; Brewka, 1996) have already been brie�y mentioned. The latter handle priorities such that in the (re)construction of an extension, only some of the applicable defaults can be �red in each step.

In (Delgrande and Schaub, 1997) priorities are handled by encoding them into the object-level rather than constraining the construction of extensions at the meta-level. It turns out that in this approach some reasonable default theories do not possess any preferred extensions at all. For instance, no preferred extension exists for Example 4. .

Other approaches, somewhat less related to our work, are concerned with handling speci�city by respecting logical entrenchment of rules. In (Delgrande and Schaub, 1994), an approach to handling speci�city is developed which rewrites the defaults, based on their logical entrenchment, such that more speci�c rules are preferred. This is in the spirit of early versions of Nute’s defeasible logic, cf. (Nute, 1994). Nute distinguishes defeasible and certain rules and presents a semantics with strong proof theoretic �avor for answering queries to the system.

Further related work is present in the context of logic programming, where different proposals to enhance extended logic programs with priorities have been made, cf. (Sakama and Inoue, 1996; Zhang and Foo, 1997; Gelfond and Son, 1998). Possible extensions of these approaches to full default logic remain to be explored; however, on the common fragment of extended logic programs, these approaches differ from ours. For an extended discussion of these approaches and the ones mentioned above, see (Brewka and Eiter, 1999). For a discussion of further approaches to priorities and speci�city in default logic, see (Delgrande and Schaub, 1994; Baader and Hollunder, 1995; Brewka, 1996).

Several issues remain for future work. First of all, procedures for reasoning from prioritized default theories need to be investigated. In the �nite propositional case, brave and cautious reasoning in prioritized and classical default logic are polynomial time equivalent, and thus, by the results in (Gottlob, 1992), Σ_{2}^{p} and Π_{2}^{p}-complete, respectively. In fact, a suitable full prioritization of Δ = (W, D, <) such that E is a preferred extension of Δ′ = (W, D, <′) can be guessed, and the condition E = C(Δ_{E}^{⋆E}) can be checked in polynomial time with an NP oracle. As a consequence, theorem provers for Reiter’s default logic can be used after a polynomial transformation for solving reasoning tasks in prioritized default logic. The design of genuine algorithms for prioritized default logic remains to be explored.

Another issue are approximations of preferred extensions. As we have shown, consistent preference relaxations (CPRs) of preferred extensions are subject to certain limitations. It would be interesting to see to what extent relaxations satisfying Principle I and II are possible, as well as for which weakenings of the principles CPRs do exist.

ACKNOWLEDGMENTS

This work was partially supported by the Austrian Science Fund in the context of the Ludwig Wittgenstein Labor f� ur Informationssysteme (Project N Z29-INF) and by Deutsche Forschungsgemeinschaft (Forschergruppe Kommunikatives Verstehen).

Gerhard Brewka University of Leipzig Leipzig, Germany

Thomas Eiter Technische Universit� at Wien Vienna, Austria

NOTES

1. We de�ne name implicitly by putting the name of a default in front of the default.

REFERENCES

Baader, F. and Hollunder, B. (1995). Priorities on Defaults with Prerequisite and their Application in Treating

Speci�city in Terminological Default Logic. Journal of Automated Reasoning, 15:41�68. Benferhat, S., Cayrol, C., Dubois, D., Lang, J., and Prade, H. (1993). Inconsistency Management and

Prioritized Syntax-Based Entailment. In Bajcsy, R., editor, Proceedings of the Thirteenth International Joint Conference on Arti�cial Intelligence (IJCAI-93), pages 640�645. Morgan Kaufman.

Brewka, G. (1989). Preferred Subtheories: An Extended Logical Framework for Default Reasoning. In

Proceedings IJCAI ’89, pages 1043�1048. Brewka, G. (1994a). Adding Priorities and Speci�city to Default Logic. In Proceedings JELIA ’94, LNAI

838, pages 247�260. Springer. Brewka, G. (1994b). Reasoning About Priorities in Default Logic. In Proceedings AAAI ’94, pages 940�945. Brewka, G. (1996). Well-Founded Semantics for Extended Logic Programs with Dynamic Preferences.

Journal of Arti�cial Intelligence Research, 4:19�36. Brewka, G. and Eiter, T. (1998). Preferred Answer Sets for Extended Logic Programs. In Cohn, A., Schubert,

L., and Shapiro, S., editors, Proceedings Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR-98), pages 86�97.

Brewka, G. and Eiter, T. (1999). Preferred Answer Sets for Extended Logic Programs. Arti�cial Intelligence,

to appear. Delgrande, J. and Schaub, T. (1994). A General Approach to Speci�city in Default Reasoning. In Proceedings

Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR-94), pages 146�157.

Delgrande, J. and Schaub, T. (1997). Compiling Reasoning With and About Preferences into Default Logic. In Proceedings IJCAI ’97, pages 168�174.

Eiter, T. and Gottlob, G. (1995). The Complexity of Logic-Based Abduction. Journal of the ACM, 42(1):3�

42. Gelfond, M. and Lifschitz, V. (1988). The Stable Model Semantics for Logic Programming. In Logic

Programming: Proceedings Fifth Intl Conference and Symposium, pages 1070�1080, Cambridge, Mass. MIT Press.

Gelfond, M., Przymusinska, H., and Przymusinski, T. (1989). On the Relationship Between Circumscription

and Negation as Failure. Arti�cial Intelligence, 38:75�94. Gelfond, M. and Son, T. (1998). Reasoning with Prioritized Defaults. In Selected Papers presented at the

Workshop on Logic Programming and Knowledge Representation (LPKR ’97), Port Jefferson, volume 1471 of LNAI, pages 164�223. Springer.

Gottlob, G. (1992). Complexity Results for Nonmonotonic Logics. Journal of Logic and Computation,

2(3):397�425. Konolige, K. (1988). Hierarchic Autoepistemic Theories for Nonmonotonic Reasoning. In Proceedings

AAAI ’88, pages 439�443. Marek, W. and Truszczy� nski, M. (1993). Nonmonotonic Logics � Context-Dependent Reasoning. Springer. McCarthy, J. (1980). Circumscription � A Form of Non-Monotonic Reasoning. Arti�cial Intelligence,

13:27�39. Moore, R. (1985). Semantical Considerations on Nonmonotonic Logics. Arti�cial Intelligence, 25:75�94. Nebel, B. (1998). How Hard is it to Revise a Belief Base ? In Dubois, D. and Prade, H., editors, Handbook on

Defeasible Reasoning and Uncertainty Management Systems, volume III: Belief Change, pages 77�145. Kluwer Academic.

Nute, D. (1994). Defeasible Logic. In Gabbay, D., Hogger, C., and Robinson, J., editors, Handbook of Logic

in Arti�cial Intelligence and Logic Programming, volume III, pages 353�395. Clarendon Press, Oxford. Poole, D. (1985). On the Comparison of Theories: Preferring the Most Speci�c Explanation. In Proceedings

IJCAI ’85, pages 144�147. Prakken, H. (1993). Logical Tools for Modelling Legal Argument. Dissertation, Vrije Universiteit Amster-

dam. Reiter, R. (1980). A Logic for Default Reasoning. Arti�cial Intelligence, 13:81�132. Rintanen, J. (1995). On Speci�city in Default Logic. In Mellish, C., editor, Proceedings IJCAI ’95, pages

1474�1479. AAAI Press. Rintanen, J. (1998). Lexicographic Priorities in Default Logic. Arti�cial Intelligence, 106:221�265. Sakama, C. and Inoue, K. (1996). Representing Priorities in Logic Programs. In Proceedings IJCSLP-96,

pages 82�96, Bonn, Germany. MIT-Press. Touretzky, D. (1986). The Mathematics of Inheritance. Pitman Research Notes in Arti�cial Intelligence,

London. Touretzky, D., Thomason, R., and Horty, J. (1991). A Skeptic’s Menagerie: Con�ictors, Preemptors, Rein-

staters, and Zombies in Nonmonotonic Inheritance. In Proceedings IJCAI ’91, pages 478�485. Zhang, Y. and Foo, N. (1997). Answer Sets for Prioritized Logic Programs. In Proceedings ILPS 97, pages

69�83.