Extensions of Description Logics (DLs) to reason about typicality and defeasible inheritance have been largely investigated. In this paper, we consider two such extensions, namely (i) the extension of DLs with a typicality operator T, having the properties of Preferential nonmonotonic entailment P, and (ii) its variant with a typicality operator having the properties of the stronger Rational entailment R. The first one has been proposed in [1, 2]. Here, we investigate the second one and we show, by a representation theorem, that it is equivalent to the approach to preferential subsumption proposed in [3]. We compare the two extensions, preferential and rational, and argue that the first one is more suitable than the second one to reason about typicality, as the latter leads to unintuitive inferences.
Description logics (DLs) represents one of the most important formalisms of knowledge representation. Their success can be explained by two key advantages characterizing them. On the one hand, DLs have a well-defined semantics based on first-order logic; on the other hand, they offer a good trade-off between expressivity and complexity. DLs have been successfully implemented by a range of systems and they are at the base of languages for the semantic web such as OWL.
In a DL framework, a knowledge base (KB) comprises two components: an intensional part, called the TBox, containing the definition of concepts (and possibly roles) as well as a specification of inclusion relations among them, and an extensional part, called the ABox, containing instances of concepts and roles. Since the very objective of the TBox is to build a taxonomy of concepts, the need of representing prototypical properties and of reasoning about defeasible inheritance of such properties naturally arises.
The traditional approach is to handle defeasible inheritance by integrating some
kind of nonmonotonic reasoning mechanism. This has led to study nonmonotonic
extensions of DLs [
Here, we consider an alternative approach, based on nonmonotonic entailment as
defined by Kraus, Lehmann and Magidor (KLM) in [
We start by considering the logic ALC + T proposed in [
“typical writers are brillant” is represented by
An ALC + T TBox can consistently contain the above inclusion together with
(typical depressed writers are not brillant). It is worth noticing that, if the same properties were expressed by ordinary inclusions, such as Writer ⊑ Brillant , we would simply get that there are not depressed writers, thus the KB would collapse. This collapse is avoided in ALC + T, as it is not assumed that T is monotonic, that is to say C ⊑ D does not imply T(C) ⊑ T(D).
The semantics of the T operator is defined by a set of postulates that are essentially a restatement of axioms and rules of nonmonotonic entailment in preferential logic P, as defined by KLM. The logic P introduces a nonmonotonic entailment |∼ in order to formalize conditional assertions of the form A |∼ B, whose intuitive meaning is that “normally the As are Bs”. The semantics of T is given by means of a preference relation < on individuals, so that typical instances of a concept C can be defined as the instances of C that are minimal with respect to <. In this modal logic, < works as an accessibility relation R with R(x, y) ≡ y < x, so that T(C) can be defined as C ⊓ 2¬C. The preference relation < does not have infinite descending chains as the so-called Smoothness condition is assumed. As a consequence, the corresponding modal operator 2 has the same properties as in Go¨ del-Lo¨ b modal logic G of arithmetic provability.
The family of KLM logics contains other interesting members, notably the stronger
logic R, known as Rational Preferential Logic [
RM. ((A |∼ B) ∧ ¬(A |∼ ¬C)) → ((A ∧ C) |∼ B)
The intuitive meaning of rational monotonicity is as follows: if A |∼ B and ¬(A |∼ ¬C)
hold, then one can infer A ∧ C |∼ B. This rule allows a conditional to be inferred from
a set of conditionals in absence of other information. More precisely, “it says that an
agent should not have to retract any previous defeasible conclusion when learning about
a new fact the negation of which was not previously derivable” [
In this paper, we consider whether the properties of T in ALC + T are the correct ones, by comparing them with the properties that would result for T if we adopted the stronger logic of nonmonotonic entailment R. We call ALC + TR the resulting Description Logic. We provide some examples to show that P is better suited than R since R would force some inferences that we consider counterintuitive. Using R, for instance, we would be forced to conclude that typical writers are not brillant from the simple fact that there is a certain Mr. John who is a typical brillant person (he has, for instance, a lot of social success), who is a writer but who is not a typical writer (since he has never succeeded in publishing anything). We consider this as an unwanted inference, and therefore argue that the properties of R are too strong for T, and that P must be preferred.
In section 4.2 we also show that the logic ALC + TR is equivalent to the logic
for defeasible subsumptions in DLs proposed by [
In this section we briefly recall the description logic ALC + T introduced in [
The language L of the logic ALC + T is defined by distinguishing concepts and extended concepts as follows: – Concepts: A ∈ C and ⊤ are concepts of L; if C, D ∈ L and R ∈ R, then C ⊓
D, C ⊔ D, ¬C, ∀R.C, ∃R.C are concepts of L; – Extended concepts: if C is a concept, then C and T(C) are extended concepts, and all the boolean combinations of extended concepts are extended concepts of L.
A knowledge base is a pair (TBox,ABox). TBox contains subsumptions C ⊑ D, where C ∈ L is an extended concept of the form either C′ or T(C′), and D ∈ L is a concept. ABox contains expressions of the form C(a) and aRb where C ∈ L is an extended concept, R ∈ R, and a, b ∈ O.
In order to provide a semantics to the operator T, we extend the definition of a model used in “standard” terminological logic ALC:
where: – Δ is the domain; – I is the extension function that maps each extended concept C to CI ⊆ Δ, and each role R to a RI ⊆ Δ × Δ. I assigns to each atomic concept A ∈ C a set AI ⊆ Δ and it is extended as follows: • ⊤I = Δ • ⊥I = ∅ • (¬C)I = Δ\CI • (C ⊓ D)I = CI ∩ DI • (C ⊔ D)I = CI ∪ DI • (∀R.C)I = {a ∈ Δ | ∀b.(a, b) ∈ RI → b ∈ CI } • (∃R.C)I = {a ∈ Δ | ∃b.(a, b) ∈ RI } • (T(C))I = fT(CI ) – Given S ⊆ Δ, fT is a function fT : P ow(Δ) → P ow(Δ) satisfying the following properties: • (fT − 1) fT(S) ⊆ S; • (fT − 2) if S 6= ∅, then also fT(S) 6= ∅; • (fT − 3) if fT(S) ⊆ R, then fT(S) = fT(S ∩ R); • (fT − 4) fT(S Si) ⊆ S fT(Si); • (fT − 5) T fT(Si) ⊆ fT(S Si).
Intuitively, given the extension of some concept C, fT selects the typical instances of C. (fT − 1) requests that typical elements of S belong to S. (fT − 2) requests that if there are elements in S, then there are also typical such elements. The next properties constraint the behavior of fT wrt ∩ and ∪ in such a way that they do not entail monotonicity. According to (fT − 3), if the typical elements of S are in R, then they coincide with the typical elements of S ∩ R, thus expressing a weak form of monotonicity (namely cautious monotonicity). (fT − 4) corresponds to one direction of the equivalence fT(S Si) = S fT(Si), so that it does not entail monotonicity. Similar considerations apply to the equation fT(T Si) = T fT(Si), of which only the inclusion T fT(Si) ⊆ fT(T Si) is derivable. (fT − 5) is a further constraint on the behavior of fT wrt arbitrary unions and intersections; it would be derivable if fT were monotonic.
In [
Let us first define the concept of minimal elements of a given set S ⊆ Δ wrt a relation <: Definition 2 (Minimal elements of S). Given a relation < over a domain Δ, and given any S ⊆ Δ, we define:
M in<(S) = {x : x ∈ S and ∄y ∈ S s.t. y < x}
Moreover, we say that a relation < over a set Δ satisfies the Smoothness Condition iff for all S ⊆ Δ, for all x ∈ S, either x ∈ M in<(S) or ∃y ∈ M in<(S) such that y < x.
In [
The above representation theorem allows to use the following semantics for ALC + T, which is similar to the one of Preferential logic P as defined by KLM. Definition 3 (Semantics of ALC + T). A model M of ALC + T is any structure hΔ, I , <i where: • (∃R.C)I = {a ∈ Δ | ∃b.(a, b) ∈ RI } • (T(C))I = M in<(CI )
As mentioned before, the intuitive idea is as follows: typical elements of a concept C, i.e. instances of the extended concept T(C) (thus, belonging to (T(C))I ) correspond to minimal elements of C, i.e. to elements in M in<(CI ). An inclusion relation T(C) ⊑ D is satisfied in a model M if M in<(CI ) ⊆ DI . This is stated in a rigorous manner by the following definition: Definition 4 (Model satisfying a Knowledge Base). Consider a model M, as defined in Definition 3. We extend I so that it assigns to each individual a of O an element aI of the domain Δ. Given a KB (TBox,ABox), we say that: – –
M satisfies TBox if for all inclusions C ⊑ D in TBox, and all elements x ∈ Δ, if x ∈ CI then x ∈ DI .
M satisfies ABox if: (i) for all C(a) in ABox, we have that aI ∈ CI , (ii) for all aRb in ABox, we have that (aI , bI ) ∈ RI .
M satisfies a knowledge base if it satisfies both its TBox and its ABox.
If a model does not satisfy an inclusion C ⊑ D, we will say that C 6⊑ D holds in the model.
The following equation between the typicality operator T and the nonmonotonic entailment operator |∼ in KLM logic P (describing what can be typically derived from a given premise) holds:
C |∼ D iff T(C) ⊑ D 3
In the Introduction we have recalled that the family of KLM logics contains other
interesting members, notably the stronger logic R, known as Rational Preferential Logic
[
RM. ((A |∼ B) ∧ ¬(A |∼ ¬C)) → ((A ∧ C) |∼ B) Let us now consider the properties that would result for T if we adopted the stronger logic of nonmonotonic entailment R. If we added to the conditions above for fT the following condition of Rational Monotonicity:
(fT − R) if fT(S) ∩ R 6= ∅, then fT(S ∩ R) ⊆ fT(S)
we would obtain a stronger DL based on Rational Entailment, as described in [
model with selection function is any structure hΔ, I, fTi, defined as in Definition 1, in which fT satisfies (fT − R).
As for the logic ALC + T, the semantics of ALC + TR can be formulated in terms of possible world structures hΔ, I, <i in which < is modular, i.e. for each x, y, z, if x < y, then either z < y or x < z.
hΔ, I, <i, defined as in Definition 3, in which < is further assumed to be modular.
The equivalence between this semantics and the one formulated with fT is proven by
the representation theorem below (Theorem 6). First of all, we need to recall Lemma
2.1 in [
Now we are able to prove the representation theorem:
described in Definition 6 iff it is satisfiable in a model hΔ, I, fTi where fT satisfies (fT − 1) − (fT − 5) plus (fT − R), and (T(C))I = fT(CI ).
Proof. Here we only consider the property (fT − R). For the other properties, we refer
to the proof of the Representation Theorem for ALC + T, as presented in [
Notice that given (fT − R), this condition is equivalent to the simplified condition that only contains (a). Indeed, if (a) holds, it follows that also (b) holds. To be convinced, take any S such that y ∈ fT(S), and x 6∈ S. We show that x ∈ fT(S ∪ {x}), hence (b) holds. For a contradiction, suppose x 6∈ fT(S ∪ {x}), then by (fT − 1) and (fT − 2), fT(S ∪ {x}) ∩ S 6= ∅, and by (fT − R), fT(S) = fT((S ∪ {x}) ∩ S) ⊆ fT(S ∪ {x}). Hence, y ∈ fT(S ∪ {x}), which contradicts (a), given that x ∈ S ∪ {x}. Therefore, we will consider the simplified definition of <:
– for all x, y ∈ Δ, we let x < y if ∀S ⊆ Δ, if y ∈ fT(S), then x 6∈ S. We then show that if fT satisfies (fT − R), then < is modular. Let x < y. Consider z and suppose z 6< y. This means that there is R such that y ∈ fT(R), and z ∈ R We reason as follows. First, notice that by Lemma 1, y ∈ fT({y, z}) (given that y, z ∈ R, y ∈ fT(R∪{y, z})∩{y, z}, hence y ∈ fT({y, z})). In order to show that < is modular, we want to show that x < z. For a contradiction, suppose that x 6< z. Then there is Z such that z ∈ fT(Z) and x ∈ Z. Consider Z ∪ {y, z}, by (fT − 1), fT(Z ∪ {y, z}) ⊆ Z ∪ {y, z}, and by (fT − 2), fT(Z ∪ {y, z}) 6= ∅. Hence, either fT(Z ∪ {y, z}) ∩ Z 6= ∅ or fT(Z ∪{y, z})∩Z = ∅, and fT(Z ∪{y, z})∩{y, z} 6= ∅. In the last case, y ∈ fT(Z ∪ {y, z}). In the first case, by (fT−R), fT(Z) = fT((Z ∪{y, z})∩Z) ⊆ fT(Z ∪{y, z}), hence z ∈ fT(Z ∪ {y, z}). From this, we derive that fT(Z ∪ {y, z}) ∩ {y, z} 6= ∅, hence, by (fT − R), fT({y, z}) = fT((Z ∪ {y, z}) ∩ {y, z}) ⊆ fT(Z ∪ {y, z}), and y ∈ fT(Z ∪ {y, z}). In both cases, we have that y ∈ fT(Z ∪ {y, z}), however this is impossible, given that x ∈ Z ∪ {y, z} and x < y. We therefore conclude that if z 6< y, then x < z, hence modularity holds.
The following facts hold in ALC + TR: (R) (T(A) ⊓ B 6⊑ ⊥) implies T(A ⊓ B) ⊑ T(A) (*) (T(A) ⊓ B 6⊑ ⊥) implies T(B) ⊓ A ⊑ T(A) Proof. For simplicity, we consider here the semantics of ALC + TR with selection function (Definition 5). By the Representation Theorem above, this is equivalent to considering the semantics of ALC + TR with < (Definition 6). It is immediate to see that (R) holds in an ALC + TR model with selection function satisfying (fT − R). For (*): If (T(A) ⊓ B 6⊑ ⊥) holds in a model, then fT(AI ) ∩ BI 6= ∅, hence by (fT − R), fT((A ∩ B)I ) ⊆ fT(AI ). On the other hand, from Lemma 1, we have that fT(BI ) ∩ AI ⊆ fT((A ∩ BI ). Hence, fT(BI ) ∩ AI ⊆ fT((A ∩ B)I ) ⊆ fT(AI ), and T(B) ⊓ A ⊑ T(A) holds.
Both properties allow us to draw conclusions from the simple fact that there is one individual that (i) is a typical instance of the concept A and that (ii) has the property B. From (R), we derive that all typical A and Bs are typical As. From (∗) we derive something about typical Bs, even if A and B are unrelated properties. In particular, we derive that typical Bs that also have the property A are typical As.
From (*) we derive the counterintuitive example of the Introduction, where from an empty TBox and an ABox containing the following facts: (a) T(Brillant )(john ) (b) Writer (john ) (c) ¬T(Writer )(john ) we can then conclude that
(d) T(Writer ) ⊑ ¬Brillant Indeed, from the ABox we can first obtain that T(Brillant ) ⊓ Writer 6⊑ T(Writer ), then, by making the contrapositive of (∗), we get T(Writer ) ⊓ Brillant ⊑ ⊥, from which we can immediately conclude (d) T(Writer ) ⊑ ¬Brillant .
As a further example, given the following ABox:
and an empty TBox, we can get that:
which does not make sense given that lilian is a different person not related to andras, hence we do not want to use lilian ’s properties to make inferences about andras.
In our opinion, the inferences that hold in ALC + TR are rather arbitrary and counterintuitive. In conclusion, we believe that the logic R is too strong and unsuitable to reason about typicality. 4
In [
We show that the logic ALC⊏ is equivalent to the logic ALC + TR, namely we
show that the logic ALC⊏ of prefeerential subsumption can be translated into ALC + TR
by replacing C ⊏ D witeh T(C) ⊑ D. Therefore we conclude that the approach in [
A knowledge base is a pair (TBox,ABox). TBox contains subsumptions C ⊑ D as well as preferential (or defeasible) subsumptions C ⊏ D, where C, D ∈ L. ABox contains expressions of the form C(a) and aRb where Ce∈ L is a concept, R ∈ R, and a, b ∈ O.
The basic idea of the semantics for preferential subsumption is that it is assumed that some objects of the domain Δ are viewed as more typical than others. Before giving a formal description of a model for ALC⊏, we introduce the following definition of maximal elements of a given S ⊆ Δ. As uesual, given a partial order ≤, we have that x = y if and only if x ≤ y and y ≤ x, so that x 6= y if and only if either x 6≤ y or y 6≤ x.
given any S ⊆ Δ, we define:
S− = {x : x ∈ S | ∄y ∈ S s.t. x ≤ y and x 6= y}
Intuitively, given a concept C, the set CI− represents the maximally preferred (or
typical) elements of C. A preferential subsumption C ⊏ D is then satisfied in a model M
if CI− ⊆ DI . e
Furthermore, we remember that a relation ≤ over a set Δ is Noetherian (or bounded)
iff there is no infinite strictly ascending chain of objects of Δ. As the same authors have
pointed out in [
We also remember that a relation ≤ is modular iff, for each x, y, z such that x 6= y, y 6= z, x 6= z, if x ≤ y, then either z ≤ y or x ≤ z. In order to provide a semantics for ALC⊏, we extend the definition of model of ALC as follows:
e Definition 8 (Semantics of ALC⊏). A model M (ordered interpretation) is any structure hΔ, ≤, I i, where Δ and I aree defined as in Definition 1, and ≤ is a Noetherian, modular, reflexive, transitive, anti-symmetric relation over Δ. For any concept C, CI is defined in the usual way.
Definition 9 (Model satisfying a Knowledge Base). Consider a model M, as defined in Definition 8. We extend I so that it assigns to each individual a of O an element aI of the domain Δ. Given a KB (TBox,ABox), we say that: – M satisfies TBox if: • for all subsumptions C ⊑ D in TBox, and all elements x ∈ Δ, if x ∈ CI then x ∈ DI • for all preferential subsumptions C ⊏ D in TBox, and all elements x ∈ Δ, if x ∈ CI− then x ∈ DI . e – M satisfies ABox if: (i) for all C(a) in ABox, we have that aI ∈ CI , (ii) for all aRb in ABox, we have that (aI , bI ) ∈ RI .
M satisfies a knowledge base if it satisfies both its TBox and its ABox.
In this section we show that the semantics of ALC + TR proposed in Section 3
corresponds to the semantics of preferential subsumption of [
we define an ALC⊏ TBox T ′ as follows: – for all inclusioens C ⊑ D ∈ T , where C is a concept, then C ⊑ D ∈ T ′; – for all inclusions T(C) ⊑ D ∈ T , then C ⊏ D ∈ T ′. e
an ALC + TR TBox T as follows: e e – for all subsumptions C ⊑ D ∈ T ′, then C ⊑ D ∈ T ; – for all preferential subsumptions C ⊏ D ∈ T ′, then T(C) ⊑ D ∈ T .
e
Let us first prove that: Theorem 3. Given an ALC + TR TBox T , if it satisfiable in an ALC + TR model M, then the ALC⊏ TBox T ′, obtained by the translation of T as in Definition 10, is also satisfiable in aen ALC⊏ model M′.
e Proof. Let M = hΔ, <, Ii be the ALC + TR model satisfying T . We first define a model M∗ = hΔ′, ≤, I′i as follows: – Δ′ = Δ; – we let x ≤′ y iff y < x; – we let CI = CI for any ALC4 concept C.
We then define a model M′ = hΔ′, ≤′, I′i, where ≤′ is defined as follows: x ≤′ y if x ≤ y; for all x ∈ Δ, we let x ≤′ x.
We first show that M′ is an ALC⊏ model. To this aim, we just need to prove that the relation ≤′ is Noetherian (i.e. it satisfiees the property (N)), modular, reflexive, transitive, and anti-symmetric.
Reflexivity follows from the definition of ≤′.
To show that ≤′ is transitive, suppose (1) x ≤′ y and (2) y ≤′ z. We have to show that also x ≤′ z. If x = y, then (2) x ≤′ z and we are done. The case in which y = z is symmetric. In case x 6= y and y 6= z, by definition of ≤′ we have that x ≤ y and y ≤ z. By definition of ≤, we have that y < x and z < y. Since < is transitive, we have that z < x and, by definition of ≤, x ≤ z. We conclude by definition of ≤′ that x ≤′ z.
The relation ≤′ is modular. Consider x ≤′ y and a given z ∈ Δ such that x 6= y, z 6= y, and x 6= z. We have to show that either (∗) x ≤′ z or (∗∗) z ≤′ y. Since x 6= y, it can be observed that x ≤ y, then y < x. Since < is modular, we have that either z < x or y < z. By definitions of ≤ and ≤′, if z < x then (∗) x ≤′ z, whereas if y < z, then (∗∗) z ≤′ y. In both cases, we are done.
The relation ≤′ is anti-symmetric. Suppose, by absurd, that x ≤′ y and y ≤′ x, but x 6= y. By definition of ≤′, this means that x ≤ y and y ≤ x and, by definition of ≤, that x < y and y < x in M. By transitivity of <, we have that x < x, against the fact that M is an ALC + TR model and, then, < is irreflexive. The relation ≤′ is then also anti-symmetric, since it is obtained from ≤ by adding only relations x ≤′ x.
In order to prove that the relation ≤′ satisfies (N) we need the following fact: Fact 1 Given the models M and M′ above, we have that S− = M in<(S). 4 In other words, the interpretation I′ corresponds to I with the exception of the extension of extended concepts T(C), not belonging to the language of the logic ALC⊏ . e Proof of Fact 1. First, we prove that S− ⊆ M in<(S). Let x ∈ S−, thus x ∈ S. This means that, for all y ∈ S, y 6= x, we have that x 6≤′ y. By definition of ≤′, also x 6≤ y and, by definition of ≤, y 6< x. Therefore, x ∈ S and, for all y ∈ S, we have y 6< x, that is to say x ∈ M in<(S).
In order to prove that M in<(S) ⊆ S−, consider x ∈ M in<(S), thus x ∈ S. This means that, for all y ∈ S, y 6= x, we have that y 6< x. Again, by definitions of ≤ and ≤′, we conclude that x 6≤′ y, that is to say x ∈ S−. ( proof of Fact 1) Let us now prove that ≤′ satisfies the property (N). Suppose, on the contrary, that there exist S ⊆ Δ and x ∈ S such that x 6∈ S− and (⋆) ∄y ∈ S− such that x ≤′ y. Since S 6= ∅ (x ∈ S), also M in<(S) 6= ∅ since < satisfies the smoothness condition. Therefore, (⋆) means that, for all y ∈ S−, x 6= y, we have x 6≤′ y. From Fact 1, we have that x 6∈ M in<(S). Moreover, for all y ∈ M in<, we have that y 6< x by definition of ≤′ and ≤. This contradicts the fact that the relation < satisfies the smoothness condition. fTa′cttsFh:ien(iap)lrloMyo,fwiiess sashtromawiogdthhetalftooMrfwTa′r,idst,haesminnocCdeIeCl⊆fo⊑rDTDI′., F(∈ioi)rTsCuaIbnsd=umCCpIt′Ii′o⊆nasnDdofI(ti′hiibe)yfDotrhIme=CfolD⊑loIwD′i(nC∈g and D are ALC concepts). For preferential subsumptions of the form C ⊏ D ∈ T ′, we observe that T(C) ⊑ D ∈ T and, since M is a model of T , we have thaet (T(C))I = taMhlsaiotnCo<bI(s′Ce−rIv=)e ⊆tMhaDitnD<.IM(C=oIrD)eo⊆Iv′ .eDrB,Iysi=FnacceDt DI1′,,iwsaneadnhatAhveeLptChraoctooCfnicIse′−opvt=e(nr.Mot mine<n(tiConIi)n.gWTe )c,owncelucadne
I
Let us now prove that: Theorem 4. Given an ALC⊏ TBox T ′, if it satisfiable in an ALC⊏ model M′, then the ALC + TR TBox T , obteained by the translation of T ′ as in Deefinition 11, is also satisfiable in an ALC + TR model M.
Proof. Let M′ = hΔ′, ≤′, I′i be the ALC⊏ model satisfying T ′. We define a model M = hΔ, <, Ii as follows: e – Δ = Δ′; – we let x < y iff y ≤′ x and y 6= x; – we define I as follows: • CI = CI′ for all ALC concepts C; • (T(C))I = M in<(CI ).
We prove that M is an ALC + TR model satisfying T . First, we prove that < is irreflexive, transitive and satisfies the smoothness condition.
By definition of <, x < y if and only if x 6= y, therefore < is irreflexive.
For transitivity, consider x < y and y < z. By definition, we have that x 6= y, y 6= z, y ≤′ x, and z ≤′ y. Since M′ is an ALC⊏ model, the relation ≤′ is transitive, therefore z ≤′ x and, by definition of <, we concelude that x < z.
As we have done for Fact 1, we can prove the following fact: Fact 2 Given the models M′ and M above, we have that S− = M in<(S). Let us now prove that the relation < satisfies the smoothness condition. By absurd, suppose that that this does not hold, that is to say there are a set S ⊆ Δ and an element x ∈ S such that (i) x 6∈ M in<(S) and (ii) ∄y ∈ M in<(S) such that y < x. First, observe that, since M′ is an ALC⊏ model, the relation ≤′ satisfies condition (N), therefore S− 6= ∅. Therefore, (i) and (iie) imply that, for all y ∈ M in<(S), y 6< x. We can also observe that x 6≤′ y, since otherwise we would have y < x. By (i) and Fact 2, we have that x 6∈ S−. This is in contrast with the fact that ≤′ satisfies condition (N), since there are S ⊆ Δ and x ∈ S such that x 6∈ S− and, for all y ∈ S− (again, by Fact 2, y ∈ S− if and only if y ∈ M in<(S)), x 6= y, we have that x 6≤′ y.
Finally, we prove that the model M satisfies the Tbox T . First of all, by definition of M, we have that CI = CI′ for all ALC concepts C, that is to say for all concepts not mentioning T. Therefore, we have that M satisifies inclusions of the form C ⊑′ D ∈ T where C is an ALC concept, since C ⊑ D ∈ T ′ and M′ satisfies T ′, then CI ⊆ DI′ , thus CI ⊆ DI .
For inclusions of the form T(C) ⊑ D ∈ T , we have that C ⊏ D ∈ T ′ and, since aMre′ AisLaCmcoodnecleopftsT, w′,ewceanhacvoentchlautdCetIh′ −at ⊆M DinI<′ .(CByI)F=actC2Ia′−nd⊆teheDfIa′ct=thDatI C,aannddwDe are done.
By Theorems 3 and 4 above, we can conclude that the semantics of preferential subsumption is equivalent to the one of preferential (rational) description logics, therefore it inherits the criticisms for extensions of DLs that use R discussed in Section 3.
From a knowledge representation point of view, it can be observed that the language of ALC + T, as well as of ALC + TR, is more general than the one of ALC⊏. In the logics ALC + T and ALC + TR, it is also possible to use the T operator in thee ABox, in order to express that individuals are typical members of a concept. For instance, an ABox can contain the following facts:
representing that sophie is a typical writer and that mick is a typical depressed writer, respectively. Moreover, it is possible to reason about prototypical properties of those individuals; in the above example, from the KB of the Introduction, one can infer that sophie is brillant, whereas mick is not, i.e.:
It is not obvious how such typical properties of individuals occurring in the ABox can be encoded in the logic ALC⊏ with preferential subsumptions. Moreover, although we have considered only TBoxesecontaining inclusions of the form
T(C) ⊑ D where C and D are concepts not mentioning T, nothing prevents us a more general use of the T operator in the definition of the TBox, for instance to formalize inclusions of the form
T(C) ⊑ T(D). In this work we have investigated the role of rational monotonicity in the context of nonmonotonic extensions of DLs.
We have first compared two approaches based on the semantics of KLM rational
preferential entailment, namely:
1. the logic ALC + T, extending standard ALC by means of a typicality operator T,
which allows to express inclusion relations of the form T(C) ⊑ D, representing the
fact that “typical” elements of concept C have the property D/are also members of
D; the semantics of the operator T is based on a set of postulates that are essentially
a reformulation of the axioms and rules of KLM logic P;
2. the logic ALC + TR, which is equivalent to the approach by [
We have provided some examples to show that the former is more appropriate than
the latter when reasoning about typicality. Of course, both ALC + T and ALC + TR
are monotonic, so they must be completed by some kind of nonmonotonic mechanism.
For ALC + T, some work has been done in [
we get for instance that:
KB ∪ {Writer (mick), Depressed (mick)} 6|= ¬Brillant (mick)
KB 6|= T(Writer ⊓ Fat ) ⊑ Brillant In order to derive the conclusion about mick we should know (or assume) that mick is a typical depressed writer, but we do not dispose of this information. Similarly, in order to derive that also a typical fat writer is brillant, we must be able to infer or assume that a “typical fat writer” is also a “typical writer”, since there is no reason why it should not be the case; this cannot be derived by the logic itself given the nonmonotonic nature of T. The basic monotonic logic ALC + T is then too weak to enforce these extra assumptions, so that an additional mechanism to perform defeasible inferences is needed.
In [
The work has been partially supported by the Project “MIUR PRIN 2008 - LoDeN
- Logiche Descrittive Nonmonotone: Complessita` e implementazioni”. This paper
extends the results presented in [