Ordering Default Theories

1 Introduction

In knowledge representation based on logic, the relative value of a given theory is formally assessed by comparing the amount of information between theories. In first-order logic, a theory T1 is considered stronger than another theory T2 if every formula derived from T2 is also derived from T1 but not vice-versa (i.e., T1 f= T2 and T2 ~ T1). For instance, the theory

is stronger than the theory

In the context of default logic [Reiter, 1980], however, the problem is not so simple. For instance, consider the default theory:

In this case, both T1 and T3 imply flies, but the fact flies from T1 is a conclusion from definite information, while the same fact from T3 is a conclusion from default infor­ mation. Introducing another fact -.flies to each theory, the conclusion flies is still derived from the inconsistent theory T1 U {-.flies}, while it is withdrawn from T3 U {-.flies}. Thus, two theories T1 and T3 have the same extension, but conclusions derived from T1 are stronger than those ofT3 .

To compare and order default theories, it is necessary to distinguish different sorts of information derived from a the­ ory. Such consideration is meaningful and important with the following reasons.

• Studies in nonmonotonic logics have been centered on answering the question: "What information is concluded from a theory (with common-sense)?" On the other hand, few studies answer the question: "What sort of information is concluded from a theory?" Since default theories contain definite and default information, distin­ guishing different sorts of information is meaningful to assess the information content of a theory. Default the­ ories contain incomplete information, so that the assess­ ment provides a theoretical ground to measure the de­ gree of "incompleteness" of a theory. These arguments are also effective in the field of nonmonotonic logic pro­ gramming [Baral and Gelfand, 1994].
• It is important to know relative value between theories. A theory is considered more valuable than another the­ ory if the former contains more information than the I at­ ter. Comparison of theories is especially important when there exist multiple sources of information as in multi­ agent systems. In first-order logic, theories are ordered by logical entailment. In default logic, however, exten­ sions of theories are not necessarily helpful for judging relative strength between theories (as presented above). To order default theories, it is necessary to provide a bet­ ter ability of comparing default theories beyond their ex­ tensions. It should distinguish different sorts of informa­ tion in a default theory, and order theories according to their information contents.
• In first-order logic, a theory is called more general than another theory if the former is stronger than the latter. Generality relations over first-order clauses have been extensively studied in the fields of machine learning and inductive logic programming [Nienhuys-Cheng and de Wolf, 1997]. In these fields, generalization is used as a basic operation for inductive learning, but it is un­ known how to extend the notion to nonmonotonic the-

ories. To construct induction systems that learn non­ monotonic theories, it is necessary to extend the gen­ eralization operation and to build a theory for ordering nonmonotonic theories. Ordering default theories thus has potential application to the theory of induction in nonmonotonic logics and nonmonotonic inductive logic programming.

With these background and motivation, this paper studies a method for ordering default theories. To this end, we first pro­ vide a multi-valued interpretation for default theories based on a nine-valued bilattice. It can distinguish different sorts of information derived from default theories. We then intro­ duce ordering over default theories, which orders different default theories based on the multi-valued interpretations of formulas. The techniques are also applied to order nonmono­ tonic logic programs under the answer set semantics. The rest of this paper is organized as follows. Section 2 reviews the framework of default logic. Section 3 develops a theory of ordering default theories. Section 4 applies the technique to nonmonotonic logic programming. Section 5 discusses re­ lated issues and Section 6 summarizes the paper.

2 Default Logic

A default theory is defined as a pair D. = (D, W) where D is a set of default rules and W is a set of first-order formulas (called facts) . A default rule (or simply default) is of the form:

where o:, (31 , .. . , f3n and 1 are first-order formulas and re­ spectively called the prerequisite, the justifications and the consequent. In this paper, any default is assumed to have at least one justification (n ~ 1). A default theory is called super-normal if every default is of the form :f· As defaults and facts are syntactically distinguishable, we often write a default theory D. as a set W U D as far as no confusion arises. Any variable appearing in D and W is free and any default/fact with variables represents the set of its ground in­ stances over the Herbrand universe of D.. Throughout this paper we assume a default theory which is already ground­ instantiated, i.e., for any default theory (D, W), D and W contain no variable. Also, a formula means a propositional formula unless stated otherwise.

A set E of formulas is an extension of (D, W) if it co­ incides with the smallest deductively closed set E' of for­ mulas satisfying the conditions: (i) W ~ E', and (ii) for any ground default o: : (31 , ... , f3n/l from D, o: E E' and ·f3i !/. E ( i = 1, ... , n) imply 1 E E'. A default theory may have none, one or multiple extensions in general. The set of all extensions of D. is written as £XT(D.). Given a default theory D., a formula is a credulous conclusion of D. if it be­ longs to some (but not all) extensions. By contrast, a formula is a skeptical conclusion of D. if it belongs to all extensions. An extension E is inconsistent if it is the set of all formulas in the language.

Proposition 2.1 [Reiter, 1980] 1 A default theory D. = (D, W) has the inconsistent extension iffW is inconsistent.

1 This property holds for defaults with non-empty justifications.

3 Ordering Default Theories

In classical logic, a formula F is interpreted true/false if FI·F is a logical consequence of a theory; otherwise it is undefined. In default logic, on the other hand, a formula is either a definite consequence by W or a default consequence by D. Moreover, default consequences are brought by two different modes of inferences - skeptical or credulous reason­ ing. To characterize these different types of inferences, we first introduce a multi-valued logic for default reasoning.

Definition 3.1 The logic I X has the nine truth values t, f, T, ..l, dts, dfs, dtc, dfc, *· which respectively mean true, false, contradictory, undefined, skeptically true by de­ fault, skeptically false by default, credulously true by default, credulously false by default, and contradictory by default.

The truth values of I X constitute a bilattice under the knowledge ordering '5:. k and the truth ordering '5:. t (Figure I). Here, it holds that ..l 'S.k dtc 'S.k * ':5:k dts ':5:k t ':5:k T ; ..l ':5:k dfc ':5:k * ':5:k dfs ':5:k f ':5:k T; f ':5:t T ':5:t t ; and f ':5:t dfs ':5:t dfc ':5:t { *, ..l} ':5:t dtc ':5:t dts ':5:t t.

In logic I X, negation -, is defined as: -, T = T, ·t = f , -,f = t, -,dts = dfs, ·dfs = dts, ·dtc · = dfc, ·dfc = dtc, '* = *· and -,..1_ = ..l. On the other hand, the dis­ junction V and the conjunction A are respectively defined by the join operation and the meet operation with respect to the truth ordering in the bilattice. That is, t V x = t for x E I X , * V ..l = dtc, T A dfc = f, and so on. It is easily verified that V and A are associative, commutative, idempotent and absorptive. 2 Note that the truth-functional operations V and A have their meaning supplied by the -:5, t ordering, while we later order default theories by the -:5, k ordering.

Under I X the interpretation of a formula in a default the­ ory is defined as follows.

Definition 3.2 Given a default theory D. = (D, W), the mapping¢~ associates a propositional formula F with a truth value of I X as follows :

2 They are not distributive, e.g.,* V (T A ..l) I= ( * V T) A ( * V ..l).

t if EXT(~) =1- 0 and W f= F;

f if EXT(~) =1- 0 and W f= -.F;

dts if EXT(~) =j:. 0, W ~ F and \IE E EXT(~) FEE;

dfs if EXT(~) =j:. 0, W ~ -.F and \IE E EXT(~) -.FEE;

dtc if3 E E EXT(~) s.t. FEE and ::J E' E EXT(~) s.t. F (j. E';

dfc if3 E E EXT(~) s.t. -.FEE and ::J E' E EXT(~) s.t. -.F (j. E';

.l otherwise.

In particular, we write

Remark that formulas F and -.F are included in every ex­ tension of ~ iff W is inconsistent (Proposition 2.1). So it does not happen that both <Pt:..(F) = dts and <Pt:..(F) = dfs for any F .

The mapping <Pt:.. provides multi-valued interpretations of formulas in a default theory. Intuitively, ¢ t:.. (F) E { t, f} means that For -.F is a definite conclusion from W. When <Pt:..(F) = T for some formula F, <Pt:..(G) = T for any formula G. This is because in this case W is inconsis­ tent and entails every formula. 3 On the other hand, when <Pt:.. (F) E { dts, dfs} (resp. <Pt:.. (F) E { dtc, dfc} ), For -.F is a default conclusion inferred skeptically (resp. credulously) from ~. When ¢ t:.. (F) = *, a formula F belongs to some ex­ tension and its negation -.F belongs to another extension. In this case, the truth value ofF is contradictory by default. ¢ t:.. maps a formula into .l if it is included in no extension. In par­ ticular, every formula has the value .l if~ has no extension.

Example 3.1 Let ~ be the theory:

which has the single extension Th( {bird, flies}). Then <Pt:..(bird) = t, <Pt:..(flies) = dts, and <Pt:..(bird--+ flies)= dts, etc.

Example 3.2 Let ~ be the theory:

: -.rh-broken 1\ lh-broken : -.lh-broken 1\ rh-broken

lh-broken rh-broken which has two extensions Th( { lh-broken}) and Th( {rh-broken} ). Then <Pt:.. (lh-broken) = <Pt:..(rh-broken) = dtc, <Pt:..(lh-broken Vrh-broken) = dts and <Pt:..(lh-broken 1\ rh-broken) = .l.

Example 3.3 Let ~ be the theory:

quaker 1\ republican,

which has two extensions Th( {quaker 1\ republican, pacifist}) and Th({quaker 1\ republican, -.pacifist}). Then <Pt:.. (quaker 1\ republican) = t and <Pt:.. (pacifist) = *·

3 In this sense, our logic is not "paraconsistent".

¢t:..(F) =

The followings are some properties of ¢ t:...

Proposition 3.1 Given two formulas F and G, F = G im­ plies <Pt:..(F) = <Pt:..(G).

Proposition 3.2 For formulas F and G,

• <Pt:.. (-.F) = -.¢t:.. (F).
• <Pt:..(F) "2k <Pt:..(G) i.ff¢t:..(-.F) "2k <Pt:..(-.G).
• <Pt:..(F) "2t <Pt:..(G) i.ff¢t:..(-.G) "2t <Pt:..(-.F).
• -.(¢t:..(F) V ¢t:..(G)) = -.¢t:..(F) 1\ -.¢t:..(G).
• -.(¢t:..(F) 1\ <Pt:..(G)) = -.¢t:..(F) v -.¢t:..(G) .

Proposition 3.3 For formulas F and G,

• <Pt:..(F v G) "2t <Pt:..(F) v ¢t:..(G).
• <Pt:..(F 1\ G) ~t <Pt:..(F) 1\ <Pt:..(G).
• <Pt:..(F--+ G) "2t <Pt:..(-.F) V <Pt:..(G) .

Proof" By <Pt:.. (FvG) "2t <Pt:.. (F) and ¢t:.. (FVG) "2t <Pt:.. (G), <Pt:.. (F V G) "2t <Pt:.. (F) V ¢t:.. (G) holds. Also, <Pt:.. (F 1\ G) ~t <Pt:..(F) and <Pt:..(F 1\ G) ~t <Pt:..(G) imply <Pt:..(F 1\ G) ~t <Pt:..(F) 1\ <Pt:..(G). The result for implication follows by the relation <Pt:..(F--+ G)= <Pt:..(-.F V G). D

Example 3.4 In Example 3.2, <Pt:..(lh-broken V rh-broken) "2t <Pt:..(lh-broken) V <Pt:..(rh-broken) and <Pt:..(lh-broken 1\ rh-broken) ~t <Pt:..(lh-broken) 1\ <Pt:..(rh-broken).

Thus, the degree of truth of an internal disjunction (resp. conjunction) is generally higher (resp. lower) than that of an external one. By contrast, there are no general relations be­ tween ¢ t:.. ( F V G) and ¢ t:.. (F) V ¢ t:.. (G); and ¢ t:.. ( F 1\ G) and <Pt:..(F) 1\ ¢1J.(G) under the ~k ordering.

Next we introduce ordering between default theories.

Definition 3.3 Let ~ 1 and ~2 be two default theories which have the same underlying language. Then, ~ 1 is stronger than ~2 (written as ~2 ~DL ~1) if ¢t:.. 2 (F) ~k <Pt:.., (F) for any formula F in the language. We write ~ 1 -::::.nL ~2 if ~1 ~DL ~2 and ~2 ~DL ~1·

The relation ~ DL is a pre-order, i.e., a reflexive and transi­ tive relation on the set of all default theories in the language. Throughout the paper, when we compare different default theories, we assume that they have the same underlying lan­ guage.

Intuitively, a default theory ~ 1 is stronger than another de­ fault theory ~2 if ~1 entails more certain information than ~2· In other words, when ~2 ~DL ~1 , conclusions derived from ~1 are relatively more stable and reliable than those de­ rived from ~2 . The 'stronger' relation reduces to the relation between (propositional) first-order theories when default the­ ories have no defaults.

Proposition 3.4 Let ~ 1 = (0, W1 ) and ~2 = (0, W2 ) be two default theories. Then, ~2 ~DL ~1 i.ffW1 f= W2.

Thus, the relation ~DL is a natural extension of the one for (propositional) first-order theories.

Proposition 3.5 Given two default theories ~ 1 and ~2 , ~1 -::::.nL ~2 implies EXT(~l) = EXT(~2 ), but not vice­ versa.

The above proposition presents that the order-equivalence relation '::::.D£ provides an equivalence relation which is stronger than the equivalence based on extensions.

Example 3.5 (introductory example) Let 6. 1 and 6.2 be two default theories:

where ¢e:., (bird) = ¢e:. 2 (bird) = t, ¢e:., (flies) t, ¢e:. 2 (flies) = dts. Then, 6.2 'S.DL 6.1. On the other hand, given

6.2 '::::.D£ 6.3. Note that all 6.1, 6.2 and 6.3 have the same extension Th( {bird, flies}).

The order 'S.DL is nonmonotonic with respect to the in­ crease of information.

Proposition 3.6 Let 6.1 and 6.2 be two default theories and Fa formula. Then, 6.1 'S.DL 6.2 implies neither 6.1 'S.DL 6.2 U {F} nor 6.1 U {F} 'S.DL 6.2 U {F}. In particular, 6.1 i:.DL 6.1 U {F} in general.

Example 3.6 Let 6.1 and 6.2 be two default theories:

where ¢e:., (p) = ¢e:. 2 (p) = dts, ¢e:., (q) = ¢e:. 2 (q) = ..l, ¢e:., (r) = ..land ¢e:. 2 (r) = t. Then, 6. 1 'S.DL 6.2 holds. Let F = (r--+ q). Then, 6.1 'f:.DL 6.2U{F} and 6.1U{F} 'f:.DL 6.2 U {F} by ¢e:.,u{F}(P) = dts and ¢e:. 2 u{F}(P) = ..l.

The introduction of new information may block the appli­ cation of some default rules, which would cause the with­ drawal of some default conclusions in a theory. This is a typ­ ical feature of default reasoning.

We finally provide a connection between the order relation 'S.DL and default extensions.

Theorem 3.7 Let 6.1 = (D1, WI) and 6.2 = (D2, W2) be two default theories. Then, 6.1 'S.DL 6.2 if the following conditions are satisfied:

1. w2 F= w1.
2. VE2 E £XT(6.2) :JE1 E £XT(6.1) s.t. E1 ~ E2,

Proof' Let F be a formula. By w2 F wl' t 'S.k ¢e:., (F) im­ plies t 'S.k ¢e:. 2 (F), and f 'S.k ¢e:., (F) impliesf 'S.k ¢e:.. 2 (F). Suppose ¢e:., (F) = dts. In this case, £XT(6.I) -::J. 0, W p!: F and F is included in every extension of 6. 1 . By the second condition, F is included in every extension of 6. 2 · Then, dts S.k ¢e:. 2 (F). Similarly, it is shown that ¢e:., (F) = dfs implies dfs 'S.k ¢e:. 2 (F). Next, suppose ¢e:., (F) = dtc. In this case, F is included in some (but not every) extension of 6. 1 . By the third condition, F is included in some extension of 6.2. Then, dtc S.k ¢e:. 2 (F). Similarly, it is shown that ¢e:., (F) = dfc implies dfc 'S.k ¢e:. 2 (F). Finally, suppose ¢e:. 1 (F) = ..l. Since ¢e:. 2 (F) = x with ..l 'S.k x, ..l 'S.k ¢e:. 2 (F) holds. D

Theorem 3.7 provides a sufficient condition to judge 6.1 'S.DL 6.2 using extensions of default theories.

4 Ordering Nonmonotonic Logic Programs

In logic programming, default reasoning is realized by nega­ tion as failure (NAF). Logic programs containing NAF are called nonmonotonic logic programs.

Non monotonic logic programs considered in this paper are the class of extended logic programs (ELPs) [Gelfond and Lifschitz, 1991], which contain two kinds of negation; ex­ plicit (or classical) negation-, and NAF (or default negation) not. An extended logic program (or simply a program) is a set of rules of the form:

where each Li (0 '5. i '5. n) is a positive/negative literal and not represents NAF. The literal L0 is the head and the con­ junction L1, ... , Lm, not Lm+l, ... , not Ln is the body of the rule. A rule or a program is called not free if it contains no NAF (i.e., m = n). Given an ELP II, the set of not­ free rules from II is denoted by II+. A rule with the empty body L f- is identified with the literal L. The head of any rule is non-empty. 4 Like default theories, every variable in a program is interpreted as a free variable. A program II is semantically identified with its ground instantiation, i.e., the set of ground rules obtained from II by substituting variables with elements of the Herbrand universe of II in every possible way. We handle ground programs throughout the paper.

The semantics of ELPs is given by the answer set se­ mantics [Gel fond and Lifschitz, 1991 ]. Let Lit be the set of all ground literals in the language of a program (called the literal base). Suppose an ELP II and a set of literals S(~ Lit). Then, the reduct II 5 is the program which con­ tains the ground rule Lo f- L1, ... , Lm iff there is a rule Lo f- L1, ... , Lm, not Lm+l, ... , not Ln in the ground in­ stantiation of II such that { Lm+l, . .. , Ln } n S = 0. Given a not-free ELP II, Cn(II) denotes the smallest set of ground literals which is (i) closed under II, i.e., for every ground rule L0 f- L1, ... , Lm from the ground instantiation of II, {L1, ... , Lm} ~ Cn(II) implies Lo E Cn(II); and (ii) logi­ cally closed, i.e., it is either consistent or equal to Lit. Given an ELP II and a set S of literals, S is an answer set of II if S = Cn(II 5 ).

Answer sets represent possible beliefs of a program, and an ELP may have none, one, or multiple answer sets. In particu­ lar, every not-free ELP has the unique answer set. An answer set is consistent if it is not Lit. The set of all answer sets of an ELP II is written as AS(II).

Proposition 4.1 An ELP II has the unique answer set Lit iff Cn(II+) = Lit.

4 Under the answer set semantics which we consider in this paper, a rule with the empty head +--- F is expressed by the semantically equivalent rule L +--- F , not L with a literal L.

According to [GelfondandLifschitz, 1991], theruleL0 +­ Ll , ... , Lm, not Lm+ 1, .. . , not Ln is interpreted as the default rule:

where ··L = L for a positive literal L. In this case, there is a 1-1 correspondence between the answer sets of a program and the extensions of the corresponding default theory. 5

Proposition 4.2 [Gelfand and Lifschitz, 1991 I Let II be an ELP and lln its corresponding default theory. If Sis an an­ swer set of IT, then the deductive closure of S is an extension of lln. Conversely, every extension of lln is the deductive closure of exactly one answer set of IT.

Using the correspondence, a multi-valued interpretation for ELPs is defined under the logic I X.

Definition 4.1 Given an ELP II, the mapping ¢n associates a positive literal L E Lit with a truth value of I X as follows:

In particular, we write

Remark that literals L and ·L are included in every answer set of II iff they are in Cn(II+) (Proposition 4.1). So it does not happen that ¢>n(L) takes both dts and dfs for any L.

The intuitive meaning of ¢>n is analogous to that of ¢>c:..

Example 4.1 Let II be the program:

which has two answer sets {p, r} and { q, r}. Then ¢> n (p) = ¢>n(q) = dtc, ¢n(r) = dts, and ¢>n(s) = l_.

Example 4.2 Let II be the program:

which has two answer sets {p} and { ·P }. Then, ¢>n(p) = *·

¢>n has properties obtained from Proposition 3.2 by replac­ ing ¢>c:. with ¢n and formulas with literals.

Ordering between ELPs is defined as follows.

5 Precisely speaking, not-free rules in an ELP correspond to justification-free defaults. Although we supposed defaults with non­ empty justifications in the previous sections, the following discus­ sion is valid apart from the results of Section 3.

Definition 4.2 Let II1 and II2 be two ELPs which have the same literal base Lit. Then, II1 is stronger than II2 under the answer set semantics (written as II2 :SAs II1) if ¢n 2 (L) :Sk ¢n, (L) for any literal L E Lit. We write II1 ~AS II2 if II1 :SAs II2 and II2 :SAs II1 .

The relation :S AS is a pre-order on the set of all ELPs in the language. A program II 1 is stronger than II2 if the answer sets ofii1 entail more certain information than II 2 . Different from the case of default logic, we compare programs in terms of literals included in answer sets. This is because in non­ monotonic logic programs the meaning of a program is deter­ mined not by individual rules in a program, but by consequent literals included in selected models of a program. Thus, we capture the information content of a program as consequences brought by answer sets.

Proposition 4.3 Let IT1 and IT2 be two not-free ELPs which have the same literal base. Then, II1 :SAs II2 ijJCn(ITI) ~ Cn(II2).

Proposition 4.4 Given two ELPs II1 and IT2, II1 ~AS II2 implies AS(IT1) = AS(IT2), but not vice-versa.

Example 4.3 Let II1 and II2 be two programs:

where II1 and II2 have the same answer set { p, ·q }. Then, ¢n, (p) = t, ¢n, (q) = f, c/>n 2 (p) = dts, and c/>n 2 (q) = dfs. Thus, II2 :SAs II1.

It is easily verified that the order :S AS has nonmonotonic properties which correspond to Proposition 3.6 with respect to the introduction of new rules to a program.

A connection between the order relation :S AS and answer sets is given as follows (The proof is similar to Theorem 3.7).

Theorem 4.5 Let IT1 and IT2 be two ELPs which have the same literal base. Then, II1 :SAs II2 if the following condi­ tions are satisfied:

1. Cn(ITt) ~ Cn(ITt),
2. VS E AS(II2) 3T E AS(II1) s.t. T ~ S,
3. VT E AS(III) 3S E AS(II2) s.t. T ~ S.

5 Discussion

In the context of multi-valued logics, Ginsberg [1988] firstly introduces a bilattice for default logic. He distinguishes definite and default conclusions obtained from a (super­ normal) default theory using the bilattice of Figure 2. How­ ever, Ginsberg's bilattice is seven-valued and does not distin­ guish between skeptical and credulous default conclusions. For instance, suppose the super-normal default theory ll = { i~i, ~ } which has two default extensions T h( { p 1\ q}) and Th( { ·p} ). Then, ¢>c:. (p) = *, ¢>c:. (q) = dtc, and ¢>c:. ( ·p V q) = dts in our framework, while Ginsberg in­ terprets pas* but handles both q and ·p V q as dt. Thus, to distinguish skeptical/credulous default inference, additional truth values are necessary as introduced in this paper. Dion­ isio et al . [ 1998] distinguish skeptical/credulous default in­ ference in super-normal default theories using modal logic.

Their goal is reasoning about defaults and is not ordering de­ fault theories.

In logic programming, Fitting [ 1991] uses bilattices to characterize the semantics of normal logic programs. He uses a four-valued logic and does not distinguish definite and de­ fault information. Dix [1992] uses the knowledge ordering under a three-valued logic to compare information obtained from a single normal logic program under different seman­ tics. This is in contrast to our approach in which we com­ pare different programs under the single answer set seman­ tics. Lattice-valued logics are also used for characterizing the "paraconsistent" semantics of logic programs [Damasio and Pereira, 1998]. To our best knowledge, however, the 9valued bilattice used in this paper never appears in the litera­ ture. Moreover, existing studies all use multi-valued logics to provide a semantics of a single program, while we use them to compare information between different programs. The order­ equivalence provides a stronger relation than the usual model­ based equivalence (Proposition 4.4). On the other hand, it is known another strong equivalence relation between logic programs [Lifschitz et al., 2001]. At the moment, we have an evidence that there is no stronger/weaker relation between the strong equivalence and the order-equivalence in general.

From the computational viewpoint, there is a difficulty for directly computing ¢Ll for an arbitrary formula F. This is due to the fact that the interpretation ¢ Ll of a formula F is generally not constructive by those of the sub-formulas ofF (Proposition 3.3). The same problem happens in the restricted class of super-normal default theories [Ginsberg, 1988]. For checking an order between default theories, however, Theo­ rem 3.7 provides a sufficient condition to judge the relation .6. 1 ~DL .6.2 using default extensions. In the context of logic programming, II 1 ~AS II2 is checked by Theorem 4.5 using the existing procedures for computing answer sets.

In the fields of machine learning and inductive logic pro­ gramming, a theory of generalization has been extensively studied in the context of first-order logic [Nienhuys-Cheng and de Wolf, 1997]. However, generalization under logi­ cal entailment f= is not directly applicable to default theo­ ries and nonrnonotonic logic programs. A default ordering introduced in this paper can order default theories and non­ monotonic logic programs, thereby could give a theoretical ground for inductive generalization in nonrnonotonic logic programs. For instance, for the programs II= { fl ies(x) +­ bird(x) , bird(tweety) +-} and II' = { fl ies(x) +­ bird(x), not abnormal(x), bird(tweety) +- }, the rela­ tion II' ~AS II holds (flies(tweety) has the value t in II, while it has the value dts in II'). Thus, if we read the order ~AS as "more general", II is considered a generalization of II'. This coincides with the view in the ILP literature [Bain and Muggleton, 1992] in which II' is a specialization of II.

6 Conclusion

In this paper, we introduced a multi-valued interpretation of default theories, which can distinguish definite and skepti­ cal/credulous default consequences. Based on this, we devel­ oped a theory for ordering default theories and applied the technique to ordering nonmonotonic logic programs. The 9valued bilattice is used for characterizing other non monotonic formalisms which have the same inference modes as default logic. The results of this paper provide a method of com­ paring default theories or nonrnonotonic logic programs in a manner different from the conventional extension-based or model-based standpoint. The proposed framework is consid­ ered to have potential application to inductive learning in non­ monotonic logics, which we will investigate in future study.