Defeasible Inheritance-Based Description Logics

1 Introduction

The notion of rational closure [Lehmann and Magidor, 1992] is acknowledged as a landmark for non-monotonic reasoning due to its logical properties, but has limited inference capabilities; e.g. an exceptional class will not inherit any of the typical properties from its superclass: penguins are atypical non-flying birds, but still have wings, a typical property of the birds, but under rational closure we may not infer that penguins have wings. On the other hand, Defeasible Inheritance Networks (INs, for short, see e.g. [Horty, 1994]) are a nonmonotonic framework appropriate for hierarchical knowledge that does not have this limitation, but exhibit questionable logical properties (see Section 6).

We combine these two approaches and define a new nonmonotonic closure operation for propositional knowledge bases that combines the advantages of both and we apply such a method to Description Logics [Baader et al., 2003] (DLs), a formalism well-suited to model structured information.

Contributions and Roadmap. (i) We propose a newmethod to reason on INs relying on a procedure for rational closure, and we use it to propose a boolean extension of them, called Boolean defeasible Inheritance Networks (BINs, Section 3); (ii) using BINs, we develop a defeasible inheritance-based propositional logic (Section 4); and (iii) we apply the latter to the case of defeasible inheritance-based description logics (Section 5). Amajor feature is that (iv) for propositional logic and DLs we still maintain all desired logical properties of rational closure; and (v) our method does uniquely require the Umberto Straccia ISTI - CNR Pisa, ITALY straccia@isti.cnr.it existence of a decision procedure of classical entailment and, thus, can be implemented on top of exiting propositional SAT solvers and DL reasoners.

Related Work. Several non-monotonic DLs exists, e.g. [Baader and Hollunder, 1993; Bonatti et al., 2009; Brewka, 1987; Britz et al., 2008; Casini and Straccia, 2010; Donini et al., 2002; Giordano et al., 2009a; 2009b; Grimm and Hitzler, 2009; Quantz and Royer, 1992; Straccia, 1993], which integrate several kind of non-monotonic reasoning mechanism into DLs. Somewhat related to our proposal are [Britz et al., 2008; Giordano et al., 2009a; Casini and Straccia, 2010; Straccia, 1993], as they address the application of the preferential methods into the DL framework, but, they do not refer to rational closure (except [Casini and Straccia, 2010]), and do not modify it in order to increase its inferential power.

2 Preliminaries

For completeness, we start with some basic notions of INs and propositional rational closure we will rely on.

Defeasible inheritance networks. In INs ([Horty, 1994; Sandewall, 2010]), there are classes, a strict subsumption relation among classes and a defeasible subsumption relation. The method used to define the inferences that are permitted is based on the notion of preemption that allows to identify paths, i.e. sequences of subsumption relationships, that are valid in the given inheritance network. Sceptical approaches define one single extension of valid paths, while credulous approaches define a set of permitted extensions. We recap that preemption is a procedure that, given two conflicting paths, allows to choose the one resting on more specific information, invalidating the other. Using the notions of path and preemption, [Horty, 1994] defines an iterative construction of a sceptical extension of a net, which we do not present here (see [Horty, 1994], Sections 2 and 3). Instead, we will introduce the notions strictly required for our purpose only.

An IN is a pair N = 〈S,D〉, where S is a set of strict links, while D is a set of defeasible links. Every link in N is said a direct link, and it can be strict or defeasible, positive or negative: specifically (i) p ⇒ q: class p is subsumed by class q [positive strict link]; (ii) p ̸⇔ q: class p and class q are disjoint [negative strict link]; (iii) p → q: an element of the class p is usually an element of the class q [positive defeasible link]; (iv) p ̸→ q: an element of the class p is usually not an element of the class q [negative defeasible link].

The non-monotone entailment relation establishing which links are entailed by a network N, indicated with p ⋆N q, for ⋆ ∈ {⇒, ̸⇔,→, ̸→}, is defined as whether p ⋆N q is in the sceptical extension of N according to [Horty, 1994, Definition 3.3.2].

Example 2.1 The 'penguin' example can be represented e.g. as 1 N = 〈{p ⇒ b}, {p ̸→ f, b → f, b → w}〉. Now, following Horty's approach, p ⇒N b, p ̸→N f, p →N w, b →N f, b →N w hold.

Propositional Rational Closure. INs do not satisfy some fundamental logical properties, presented below, such as (CM) and (CT) [Makinson, 1994], that are desirable structural properties for nonmonotonic consequence relations, and that are satisfied by rational closure. We recap here the reasoning algorithm of rational closure described in [Casini and Straccia, 2010], since our method will rely on it.

So, consider a classical propositional language. 2 We represent consequential information by means of ⊢ and |∼; Γ ⊢ C and Γ|∼C will be called, respectively, strict and defeasible sequents (Γ is a finite set of propositions), that have to be read as 'If Γ, then necessarily C' and 'If Γ, then typically C'. A conditional knowledge base is a pair 〈T , B〉, where T is a set of strict sequents C ⊢ D, and B is a set of defeasible sequents C|∼D.

Example 2.2 Example 2.1 can be encoded as: K = 〈T , B〉 with T = {p ⊢ b} and B = {p|∼¬f, b|∼f, b|∼w}.

Another way to formalize defeasible information may be based on the default-assumption approach, where a default knowledge base is a pair 〈Φ,Δ〉, where Φ and Δ are sets of formulae representing respectively what the agent considers as necessarily true and as typically true.

Example 2.3 Example 2.1 could be encoded, for example, as: K = 〈Φ, Δ〉 with Φ = {p ⊃ b} and Δ = {b ⊃ f, p ⊃ ¬f, b ⊃ w}.

A consequence relation |∼ is rational iff it satisfies the properties below (see e.g. [Makinson, 1994]):

Now, consider B = {C1|∼E1, . . . ,Cn|∼En}. We say that a sequent C|∼D is in the rational closure R(B) iff it is included in a particular rational consequence relation containing B and defined as in [Lehmann and Magidor, 1992] (as the rule (RM) has a non-Horn form, there could be more than one rational consequence relations containing B). For a set of formulae Γ, we will write Γ|∼rc B D iff ∧ Γ|∼D ∈ R(B).

1 Read b as 'Bird', p as 'Penguin', f as 'Flying' and w as 'Wings' 2 With connectives ¬, ∧, ∨, ⊃, sentences C, D, E . . ., set of sentences Γ, Δ, . . ., ⊤ and ⊥ with usual meaning of "true" and "false"

and classical consequence relation ⊨.

We recap now briefly the procedure in [Casini and Straccia, 2010] that decides defeasible consequence via a mapping of a conditional knowledge base into a default knowledge base (we transform a KB of the kind of the one in Example 2.2 into a KB of the kind in Example 2.3).

Step 3. Define an exceptionality ranking of the formulae and the sequents with respect to B′ as follows.

Step 3.1. Given a set of sequents D, define a formula C as exceptional w.r.t.D iff ΓD ⊨ ¬C. Consider E(AD) = {C ∈ AD | ΓD ⊨ ¬C} and E(D) = {C|∼D ∈ D | C ∈ E(AD)}. Obviously, for every D, E(D) ⊆ D.

• Step 3.2. Construct iteratively a sequence E0, E1 . . .: E0 = B′ , Ei+1 = E(Ei) (as B′ is a finite set, the construction always terminates with En = ∅ or a fixed point of E, a totally exceptional set of sequents, such that all its antecedents are negated).

Step 3.3. Define now a ranking function r that associates to every sequent in B′ its level of exceptionality:

Step 4. Now,

Step 4.1. Define B′ inconsistent iff ΓB′ |= ⊥.

Step 4.2. If B′ is consistent, define the background theory ˜ T as ˜ T = {⊤ ⊢ ¬C | C|∼D ∈ B′ and r(C|∼D) = ∞} (one may verify that, modulo logical equivalence, T ⊆ ˜ T ).

• Step 4.3. Define ˜ B = {C|∼D ∈ B′ | r(C|∼D) < ∞} (one may verify that ˜ B ⊆ B). 3

Step 5. Now build the default-assumption characterization 〈 ˜Φ, ˜Δ〉 of the rational closure of 〈 ˜ T , ˜ B〉 as ˜Φ = {C | ⊤ ⊢ C ∈ ˜ T } and ˜Δ = {δ0, . . . , δn}, with δi = ∧{C ⊃ D | C|∼D ∈ ˜ B and r(C|∼D) ≥ i}. Note that δi |= δi+1, for 0 ≤ i < n.

Step 6. Now, it has been proven (see [Casini and Straccia, 2010]) that using the following knowledge base transformations

we can characterize the rational closure of 〈T , B〉 via 〈 ˜Φ, ˜Δ〉 as Γ|∼rc 〈T ,B〉D iff Γ∪ ˜Φ∪{δi} ⊨ D, with δi being the first (Γ∪

˜Φ)-consistent formula of the ordered sequence 〈δ0, . . . , δn〉.

So, we have a simple method to decide defeasible consequence under rational closure. Given a defeasible knowledge base 〈T , B〉, certain facts Γ and a formula D,

3 We recap: we have started with 〈T , B〉 and now we have an equivalent characterization 〈 ˜ T , ˜ B〉, that differs from the former one because the background theory and the defeasible information are correctly distinguished. Moreover, we have a rank value for every sequent in ˜ B.

1. Once for all, apply to 〈T , B〉 the transformations (∗∗) to obtain the defeasible knowledge base 〈 ˜Φ, ˜Δ〉;
2. Given Γ, determine δi as the first (Γ ∪ ˜Φ)-consistent formula of the sequence 〈δ0, . . . , δn〉.
3. Then decide if D follows under rational closure from Γ w.r.t. 〈T , B〉 by determining whether Γ ∪ ˜Φ ∪ {δi} ⊨ D.

Example 2.4 Consider Example 2.2. It can be verified that, under rational closure, penguins are non-flying birds and birds fly and have wings.

Remark 1 Consider Example 2.4. It would be intuitive also to conclude that penguins have wings. But the main problem with every preferential approach is that a class that is recognized as atypical (penguins are birds, but they don't fly), loses the 'right' to inherit all the other typical characteristics of their superclasses and, thus, we are not allowed to conclude that penguins have wings. On the other hand, note that INs manage successfully this kind of problems.

3 Boolean defeasible inheritance networks

3.1 Exceptionality levels in inheritance nets

Our first aim is to apply a modified version of our decision procedure for rational closure to inheritance nets.

For whole Section 3 we will assume that the strict part of a net N = 〈S,D〉 is closed, that is, if p ⇒N q then p ⇒ q ∈ S. 4 In what follows, paths containing repetitions of links are disallowed. The omission of repetitions is to have finite paths even if the net contains "cycles". Now, p ⇒N q if there is a valid strict path from p to q, whose definition is as follows: 5 (i) every strict positive (negative) link in S is a valid positive (negative) path; (ii) if π = 〈t, σ, p〉 is a valid positive path, then for p ⇒ q ∈ S, 〈π, q〉 is a valid strict positive path, while for p ̸⇔ q ∈ S, 〈π, q〉 is a valid strict negative path; (iii) if π = 〈t, σ, p〉 is a valid negative path, then for q ⇒ p ∈ S, 〈π, q〉 is a valid strict negative path.

Now, we define courses. Roughly, courses are simply routes on the net following the direction of the arrows, without considering if each of them is a positive or a negative arrow. Courses are defined as follows (where ⋆ ∈ {⇒, ̸⇔,→ , ̸→}): (i) every link p ⋆ q in N is a course π = 〈p, q〉 in N; and (ii) if π = 〈σ, q〉 is a course and q ⋆ r is a link in N that does not already appear in π, then π′ = 〈π, r〉 is a course in N. Note that there is only a finite set C N of courses, and every course is a finite sequence of nodes. We denote with C N p,q the set of all the courses in N going from node p to the node q, i.e. C N p,q = {σ ∈ C N | σ = 〈p, σ′ , q〉 for some σ′ }.

We next provide a procedure that defines the validity of a defeasible link p ⋆ q via a mapping to propositional logic. So, given a net N = 〈S,D〉, we define a correspondent knowledge base KN = 〈ΦN,ΔN〉, where ΦN = {p ⊃ q | p ⇒ q ∈ S} ∪ {p ⊃ ¬q | p ̸⇔ q ∈ S} and ΔN = {p ⊃ q | p → q ∈ D} ∪ {p ⊃ ¬q | p ̸→ q ∈ D}. In the following, we may omit N if clear from context. We define an 'exceptionality ranking' of the nodes, that depends on the decision problem of the validity of p⋆q only. 6 So, let 7

4 The assumption is made only for the simplicity of the exposition. It becomes unnecessary once we work with the procedure we are going to define for propositional logic.

5 We use Greek letters to denote paths, which are denoted as a tuple of nodes: e.g., π = 〈p, σ, q〉 indicates that the path π starts from the node p, passes through the path σ, and ends with node q.

and consider the set of relative antecedents (l literal)

⊨Φ will denote the classical entailment relation obtained adding to ⊨ the set of propositional formulae Φ as extra axioms, while |∼N will indicate the consequence relation for the defeasible part, that is, 'p|∼N q' has to be read as 'a member of the class p is typically also a member of the class q' in N. Analogously for 'p|∼N ¬q' in the negative case.

Now, we define the notions of strict (⊢N) and defeasible (|∼N ) consequence in N. At first, consider case Δp,q = ∅: if p ⊨Φ q (p ⊨Φ ¬q), then we say p ⊢N q (p ⊢N ¬q), i.e. q (¬q) follows strictly from p in N. Now, consider the case Δp,q ̸= ∅. We use now Φ and Δp,q to determine the 'exceptionality level' (compare with Step 3.2. of previous section):

Therefore, like Step 3.3. of Section 2, we build a sequence α0 = Ap,q, αi = E(αi-1), and the corresponding sequence E0 = Δp,q, Ei = E(Ei-1). 8 Define now a ranking function r (like Step 3.3) that associates to every node and implication in Δp,q a number, representing its level of exceptionality:

We now consider the set ̂Δp,q of the implications a ⊃ b ∈ Δp,q that are at least as exceptional as p,

and eventually define

So, given N = 〈S,D〉 and a pair of nodes 〈p, q〉, our inference procedure for INs can be summarised as follows:

1. Determine the set Cp,q of the courses in N connecting p to q, map the links in S and Cp,q into the sets of implications Φ and Δp,q, define the set Ap,q of the antecedents of the implications in Φ ∪ Δp,q .
2. Determine the ranking value of every proposition in Ap,q and every implication in Δp,q. Define the set ̂Δp,q of the implications that are at least as exceptional as p.

6 A main difference w.r.t. the procedure for rational closure. While there we rank all the information in the KB at once, here we rank only the information related to the connection we are interested in, between p and q.

7 Here, e.g.r → t ∈ σ means that r → t occurs in the course.

8 Since Ap,q, Δp,q are finite, and αi+1 ⊆ αi and Ei+1 ⊆ Ei for every i, the sequences can terminate either with an empty set or with a stable set (a fixed point of the function E), as in Section 2.

1. Then decide p|∼N q (p|∼N ¬q) by determining whether ̂Δp,q ⊨Φ p ⊃ q ( ̂Δp,q ⊨Φ p ⊃ ¬q).

Note that we rely on a decision procedure for ⊨ only.

The example below illustrates the behaviour of our method.

Example 3.1 Consider Example 2.1 with additional links t ⇒ b and t ⇒ p (read t as 'tweety'). We translate the net into the following knowledge base K = 〈Φ, Δ〉, where Φ = {t ⊃ b, t ⊃ p, p ⊃ b} and Δ = {p ⊃ ¬f, b ⊃ f, b ⊃ w}. Suppose now, we want to decide if t is connected to f (i.e., Tweety flies). We have Δt,f = {p ⊃ ¬f, b ⊃ f}, At,f = {t, b, p}, Δt,f ⊨Φ ¬p and Δt,f ⊨Φ ¬t; thus, r(b ⊃ f) = 0 and r(p ⊃ ¬f) = 1 = r(t) follow. So, ̂Δt,f = {p ⊃ ¬f} and, as ̂Δt,f ⊨Φ t ⊃ ¬f, we have t|∼N ¬f, as expected. As next, we ask if t is connected to w (i.e., Tweety has wings). Now, we have to consider Δt,w = {b ⊃ w}, with At,w = {t, b, p}. As Δt,w does not imply the negation of any of the members of At,w, we have r(b ⊃ w) = 0 = r(t) and ̂Δt,w = Δt,w. As ̂Δt,w ⊨Φ t ⊃ w, we have t|∼N w, as expected.

3.2 Boolean inheritance nets

We next extend INs by allowing any classical propositional connective in them. Despite such an extension has been felt as desirable, we are aware of just an attempt in this direction [Horty and Thomason, 1990].

So far, p ̸⇔ q has logical meaning p ⊃ ¬q. We change the notation and indicate with p ⇔¬ q that 'class p and class q are complementary'. With p we indicate the complementary class of a class p, and assume that for any node p, we have p ⇔¬ ¯ p in the net as well. Hence, we can substitute p ̸⇔ q with the four links p ⇔¬ p, q ⇔¬ q, p ⇒ q, and q ⇒ p, and analogously, we can substitute p ̸→ q with p → q. So, we can transform an IN into an equivalent net using only the arrows →, ⇒, and ⇔¬. We shall continue to use ̸⇔ as a macro indicating negative strict valid connections obtained from the composition of ⇔¬ and ⇒ (and, since we assume that the strict part S of a net to be closed, we shall have in it also ̸⇔-links).

Next, we extend inheritance nets to support conjunction and disjunction as well, by allowing links a, b ⇔∧ c (conjunction of a and b is equivalent to c) and a, b ⇔∨ c (disjunction of a and b is equivalent to c). We will assume that inheritance nets containing such kind of links are closed according to the following rule: if there is a, b ⇔∧ c (resp. a, b ⇔∨ c) in a net, then there are also c ⇒ a and c ⇒ b (resp. a ⇒ c and b ⇒ c) in the net. We call these nets Boolean Defeasible Inheritance Networks (BINs). We denote with a ⊗ b (a ⊕ b) a node representing the conjunction (disjunction) of a and b.

We extend now our reasoning method to BINs. To do so, we introduce the notion of duct, that is a generalization of the notion of course. Roughly, π = 〈s, σ σ′ , t〉 will indicate a duct π that starts at node s and develops through the ducts σ and σ′ , both reaching the node t. Formally, ducts are defined as follows (where ⋆ ∈ {⇒,⇔¬, ̸⇔,→}): (i) every link p ⋆ q in N is a duct π = 〈p, q〉 in N; (ii) if π = 〈σ, q〉 is a duct and q ⋆ r is a link in N that does not already appear in π, then π′ = 〈π, r〉 is a duct in N; (iii) if 〈t, σ, p〉 and 〈r, σ′ , p〉 are ducts, then for s ⇔∨ t, r ∈ S, 〈s, t,σ r,σ′ , p〉 is a duct; and (iv) if 〈p, σ, t〉 and 〈p, σ′ , r〉 are ducts, then for t, r ⇔∧ s ∈ S, 〈p, σ,t σ′ ,r , s〉 is a duct.

Now our reasoning method for BINs is as follows. Consider N = 〈S,D〉, define a correspondent knowledge base K = 〈Φ,Δ〉, where Φ = {p ⊃ q | p ⇒ q ∈ S} ∪ {p ≡ ¬q | p ⇔¬ q ∈ S} ∪ {p ≡ q ∧ r | q, r ⇔∧ p ∈ S} ∪ {p ≡ q ∨ r | p ⇔∨ q, r ∈ S} and Δ = {p ⊃ q | p → q ∈ D} and proceed for the definition of |∼N as for Section 3.1 in which CN is now defined as the set of the ducts, and CN p,q (or simply Cp,q) is defined as the set of the ducts from p to q.

Example 3.2 Consider a net N that has been mapped into the KB K = 〈Φ, Δ〉, where Φ = {c ∧ d ≡ g, f ≡ ¬g} 9 and Δ = {a ⊃ b, b ⊃ c, b ⊃ d, a ⊃ f}. Is a connected to c? It can be verified that Δa,c = {a ⊃ b, b ⊃ c, b ⊃ d, a ⊃ f}. Note that b ⊃ d ∈ Δa,c, as there is a duct from a to c that passes through c and d in order to reach g, and then back towards c. Now, the only negated antecedent is a (Δa,c ⊨ ¬a) and, thus, ̂Δa,c = {a ⊃ b, a ⊃ f}. Since ̂Δa,c ̸⊨Φ a ⊃ c and ̂Δa,c ̸⊨Φ a ⊃ ¬c, we have a̸|∼N c and a̸|∼N ¬c. In a similar way, we may show that a̸|∼N d and a̸|∼N ¬d. This is the desirable result: since a → f is a direct link, we have that a|∼N f (a|∼N ¬(c ∧ d)), from which we can concluded neither a|∼N c nor a|∼N d. The result of our 'sceptical' approach is then that a̸|∼N c, a̸|∼N ¬c, a̸|∼N d, and a̸|∼N ¬d.

4 Defeasible inheritance in propositional logic

Now, we depart from BINs and apply a similar reasoning procedure using the full expressivity of propositional logic and show how to obtain a form of closure of a knowledge base that corresponds to a rational consequence relation that refines the classical rational closure, as defined in [Lehmann and Magidor, 1992]. So, consider a conditional KB K = 〈T , B〉 (see Section 2). We proceed as follows:

Step 1. construct a BIN from K, i.e. we define a net NK = 〈SK,DK〉, modeling the information in K: (i) for every formula C that appears as antecedent or as succedent in the sequents in K we create a correspondent node C representing the class of the formulas that are logically equivalent to C. For every such node we add also, if not already present, the complementary node, linking them by ⇔¬ . We add the other links: if C ⊢ D ∈ T we add the strict link C ⇒ D to the net, and we also add to SK all the strict links that correspond to the logical dependencies between the formulae represented by the nodes (considering also the information contained in T , that is, the arrow ⇒ will represent in the net the monotonic consequence relation obtained adding to ⊨ the sequents in T as extra-axioms); and (ii) for C|∼D ∈ B, we add a defeasible link → from node C to node D. 10

Step 2. apply the reasoning procedure for BINs toNK (Section 3.2) to identify all valid defeasible connections C|∼N D and add them as C|∼D to the conditional base K to obtain a new conditional base K′ = 〈T , B〉 11 .

9 To easy the reading, we have omitted the redundant implications such as g ⊃ c, obtained from c, d ⇔∧ g, g ⇒ c ∈ N .

10 For ⊤ we add to the net a correspondent node ⊤, and, for every other node n in the net, we add a strict node n ⇒ ⊤. Analogously, for ⊥ we add ⊥ ⇒ n for every node n in the net.

11 We do not modify T , since all the strict connections valid in the net are classically derivable from T . Also, nodes that are compound boolean formulae are represented as formulae in the obvious way, e.g. c ⊕ ( ¯ d ⊗ ¯ e) becomes c ∨ (¬d ∧ ¬e)

Step 3. Finally, apply to K′ its rational closure (see Section 2): we consider that C|∼D is derivable from K, denoted C|∼KD, iff C|∼D ∈ R(K′ ).

We can show that

Proposition 4.1 |∼K is a rational consequence relation.

Example 4.1 Consider Example 2.4. We have seen that p|∼w ̸∈ R(K) (see Remark 1). According to our procedure, it can be verified that B = {b|∼f, b|∼w, p|∼w, p|∼¬f}. Now, we have p|∼Kw, and, using the rational closure, we can derive also sequents as b∧f |∼Kw, that could not be considered using only the BIN.

Example 4.2 Consider a red fish (r). It is both a fish (f) and a pet (p). Typically, a fish has gills (g) and scales (s), while pets are docile (d) and play with kids (k). Red fishes are not typical pets, since they do not play with kids. So, consider K = 〈T , B〉 with T = {r ⊢ f, r ⊢ p} and B = {r|∼¬k, p|∼k, p|∼d, f|∼g, f|∼s}. In a standard preferential approach red fishes, since they are atypical pets (they do not play with kids), result atypical in general, and they cannot inherit any of the typical properties of all their superclasses. Instead, we infer that red fishes do inherit, besides the properties of pets that are compatible with them (d), also all the typical properties of fishes (g and s), since we consider them as typical fishes.

Hence, we have defined a new rational consequence relation for K that extends K, as K ⊂ R(K′ ), and that contains intuitive sequents not derivable in the rational closure of K.

5 Defeasible inheritance in DLs

We next apply our method to ALC, a significant DL representative (see e.g. [Baader et al., 2003]). ALC has monadic predicates, called concepts, and dyadic ones, called roles: from the set C of concept names A, the set R of roles R, the set L of concepts is inductively defined as follows: (i) C ⊂ L; (ii) ⊤,⊥ ∈ L; (iii) C,D ∈ L ⇒ C ⊓ D,C ⊔ D, ¬C ∈ L; and (iii) C ∈ L,R ∈ R ⇒ ∃R.C, ∀R.C ∈ L. Concept C ⊃ D is used as a shortcut of ¬C ⊔ D. A General Concept Inclusion (GCI) axiom is of the form C ⊑ D (C, D ∈ L) and indicates that any instance of C is also an instance of D. We use C = D as a shortcut of the pair of C ⊑ D and D ⊑ C.

From a FOL point of view, concepts, roles and GCIs, may be seen as formulae obtained by the following transformation

τ(C ⊑ D) = ∀x.τ(x,C) ⊃ τ(x,D), τ(x,⊤) = ⊤(x), τ(x,⊥) = ⊥(x) τ(x,A) = A(x), τ(x, ¬C) = ¬τ(x,C) τ(x,C ⊓D) = τ(x,C) ∧ τ(x,D), τ(x,C ⊔D) = τ(x,C) ∨ τ(x,D) τ(x, ∃R.C) = ∃y.R(x, y) ∧ τ(y,C), τ(x, ∀R.C) = ∀y.R(x, y) ⊃ τ(y,C)

A defeasible knowledge base is K = 〈T , B〉, where T is a finite set of GCIs (a TBox) and B is a finite set of conditionals C ⊏∼ D ('an instance of a concept C is typically an instance of a concept D' ), with C,D ∈ L. 12 Next we show that by using our method, we overcome to the limits of classical rational closure, in a similar way as for the propositional case: concepts will play the same role as propositions, while inclusion axioms C ⊑ D and C ⊏∼ D play the same role of, respectively, C ⊢ D and C|∼D. Our procedure is as in [Casini and Straccia, 2010], except that now we inject the DL analogue of Steps 1-3 from Section 4 into it. Specifically, Steps

12 We do not deal here with individuals and so-called Aboxes, which will be addressed in an extend work, as the development is essentially the same as in [Casini and Straccia, 2010].

1-2 are the DL analogue as from Section 4, while Steps 38, are the same as the rational closure construction for DLs in [Casini and Straccia, 2010].

• Step 1. Construct a BINNK fromK. The process is similar to the one in Section 4: nodes in NK represent the concepts present as antecedents or consequents of the inclusion axioms in T and B (modulo logical equivalence); for every node we add its complementary node, if not already present, and we connect them by ⇔¬ ; every GCI C ⊑ D ∈ T becomes a strict link C ⇒ D; and every defeasible inclusion axiom C ⊏∼ D ∈ B becomes a defeasible link C → D. Moreover, consider the consequence relation ⊨T as the monotonic consequence relation obtained adding the GCIs in T to ⊨, and add to the net the strict links representing all the logical dependencies between nodes with respect to ⊨T .
• Step 2. Apply the reasoning procedure for BINs to NK (Section 3.2) to identify all valid defeasible connections C|∼N D, and add them as C ⊏∼ D to the conditional base K to obtain a new conditional base K′ = 〈T , B〉.
• Step 3. Define B′ = B ∪ {C ⊓¬D ⊏∼ ⊥ | C ⊑D ∈ T }.
• Step 4. Define ΓB′ = {⊤ ⊑ C ⊃ D | C ⊏∼ D ∈ B′ } and let AB′ = {C | C ⊏∼ D ∈ B′ }.
• Step 5. Determine the exceptionality ranking of the sequents in B′ using the sets AB′ and ΓB′ , where a concept C is exceptional w.r.t. a set of sequents D iff ΓD |= ⊤ ⊑ ¬C. The steps are the same of the propositional case (Steps 3.1 - 3.4, Section 2) by replacing the expression ΓD |= ¬C with the expression ΓD |= ⊤ ⊑ ¬C. In this way define a ranking function r.
• Step 6. As in Step 4.1 in Section 2 verify if the KB is consistent, by checking the consistency of ΓB′ . Then (Steps 4.2-4.3, Section 2), define the sets ˜ T = {⊤ ⊑ ¬C | C ⊏∼ D ∈ B′ and r(C ⊏∼ D) = ∞} and ˜ B = {C ⊏∼ D | C ⊏∼ D ∈ B′ and r(C ⊏∼ D) < ∞}.
• Step 7. Define (similarly to Step 5, Section 2) ˜Δ = {δ0, . . . , δn}, where

As for Section 2, for every δi, 0 ≤ i < n, |= δi ⊑ δi+1.

• Step 8. Consider ˜ T = {⊤ ⊑ C1, . . . ,⊤ ⊑ Cm}, ˜Δ = {δ0, . . . , δn}, and define ˜Φ = {C1, . . . ,Cm}. Now, decide whether C ⊏∼ D holds in K, denoted C|∼KD, by checking whether |= C⊓ bigsqcap ˜Φ⊓δi ⊑ D, where δi is the first ({C}∪ ˜Φ)- consistent formula 13 of the sequence 〈δ0, . . . , δn〉. This is the DL analogue as Step 6, Section 2.

Again, all steps require a decision procedure for the classical entailment relation |= of DLs. As in [Casini and Straccia, 2010], we can show that

Proposition 5.1 |∼K is a rational consequence relation.

Example 5.1 Consider Example 2.2. Consider propositional letters as concept names, add a role Prey (Prey(a, b) is read as 'a preys on b') and a role Born (Born(a, b) is read as 'a is born from b'), and add concepts I (Insect), Fi (Fish) and E (Egg). Consider K = 〈T , B〉 with T = {P ⊑ B, I ⊑ ¬Fi}, B = {P ⊏∼ ∀Prey.Fi ⊓ ∃Prey.⊤,B ⊏∼ ∀Prey.I ⊓ ∃Prey.⊤,B ⊏∼ ∃Born.E}. Now, it can be shown that B = {P ⊏∼ ∀Prey.Fi ⊓ ∃Prey.⊤,B ⊏∼ ∀Prey.I ⊓ ∃Prey.⊤,B ⊏∼ ∃Born.E, P ⊏∼

13 That is, ̸|= C ⊓ bigsqcap ˜Φ ⊑ ¬δi .

∃Born.E}. Then we move to the rational closure. The pair 〈T , B〉 is changed into B′ = {P ⊓ ¬B ⊏∼ ⊥, I ⊓ Fi ⊏∼ ⊥, P ⊏∼ ∀Prey.Fi ⊓ ∃Prey.⊤,B ⊏∼ ∀Prey.I ⊓ ∃Prey.⊤,B ⊏∼ ∃Born.E, P ⊏∼ ∃Born.E}. We obtain ΓB′ = {⊤ ⊑ P ∧ ¬B ⊃ ⊥, ⊤ ⊑ I ⊓ F i ⊃ ⊥, ⊤ ⊑ P ⊃ ∀P rey.F i ⊓ ∃P rey.⊤, ⊤ ⊑ B ⊃ ∀P rey.I ⊓∃P rey.⊤, ⊤ ⊑ B ⊃ ∃Born.E, ⊤ ⊑ P ⊃ ∃Born.E}, and AB′ = {P ⊓ ¬B, I ⊓ F i, P, B}. The exceptionality ranking of the sequents is: E0 = {P⊓¬B ⊏∼ ⊥, I⊓F i ⊏∼ ⊥, P ⊏∼ ∀P rey.F i⊓ ∃Prey.⊤,B ⊏∼ ∀Prey.I ⊓ ∃Prey.⊤,B ⊏∼ ∃Born.E, P ⊏ ∼ ∃Born.E}; E1 = {P ⊓ ¬B ⊏∼ ⊥, I ⊓ Fi ⊏∼ ⊥, P ⊏∼ ∀Prey.Fi ⊓ ∃Prey.⊤, P ⊏∼ ∃Born.E}; E2 = {P ⊓ ¬B ⊏∼ ⊥, I ⊓ Fi ⊏∼ ⊥} and E3 = {P ⊓ ¬B ⊏∼ ⊥, I ⊓ Fi ⊏∼ ⊥}. Automatically, we have the ranking values of every sequent in B′ : namely, r(B ⊏∼ ∀Prey.I ⊓ ∃Prey.⊤) = r(B ⊏∼ ∃Born.E) = 0; r(P ⊏∼ ∀Prey.Fi ⊓ ∃Prey.⊤) = r(P ⊏∼ ∃Born.E) = 1 and r(P ⊓¬B|∼⊥) = r(I ⊓F i|∼⊥) = ∞. From such a ranking, we obtain a background theory ˜ T = {⊤ ⊑ ¬(P ∧¬B), ⊤ ⊑ ¬(I ⊓F i)}, and a default-assumption set ˜Δ = {δ0, δ1}, with

δ1 = (P ⊃ ∀Prey.Fi ⊓ ∃Prey.⊤) ⊓ (P ⊃ ∃Born.E) .

to be used in Step 8. for our decision problem at hand. For instance, unlike [Casini and Straccia, 2010], we can conclude now that penguins are born from eggs.

6 Conclusion

By combining the classical rational closure with the ideas from defeasible inheritance networks, we have proposed a new rational consequence relation that overcomes the limits of both formalisms. By doing so, we have extended the defeasible inference capabilities of rational closure by allowing an atypical class still to inherit some properties from its superclass while maintaining the desired logical properties, as summarized in the table below 14 :

As we can see, our proposal for defeasible inheritance-based propositional logic and Description Logics still satisfy all axioms of classical rational closure. Another feature is that our method requires uniquely the existence of a decision procedure of classical entailment and, thus, can be implemented on top of exiting propositional SAT solvers and DL reasoners.

As a further exercise, we have applied also our method to all examples exhibited in [Sandewall, 2010, Appendix B], and verified that our method behaves as desired.

A point we want to address is the computational complexity of our method, especially for low complexity DL languages such as OWL QL, EL and RL, for which we conjecture to have the same reasoning complexity.