Nonmonotonic reasoning based on ordinal conditional functions (OCFs), often called ranking functions, and description logics are both well-established methodologies in knowledge representation and reasoning. However, nonmonotonic reasoning mainly focuses on propositional logic as a base logic, while description logics investigate fragments of first-order logic for eficient reasoning with terminological knowledge. In this paper, we investigate how OCFs can be employed to define inference relations induced from first-order conditional knowledge bases. The goal of this work is to present first steps towards an interpretation of defeasible subsumptions in description logics (DL) which is thoroughly based on conditionals and ranking functions. In the process, we adapt a recently proposed DL version of the KLM postulates, a popular framework for non-monotonic reasoning from propositional knowledge bases, for the use with conditional first-order logic. Moreover, we consider some additional recently proposed rationality postulates for a KLM approach based on (restricted) first-order logic. Concrete examples are provided for reasoning with strategic c-representations, a special type of ranking functions based on the underlying conditional structures of a knowledge base, yielding high-quality non-monotonic inferences without the need to specify external relations, e.g., expressing typicality among individuals.
Rules in the form of conditional statements “If A then
(usually) B” (sometimes equipped with a quantitative degree)
are basic to human reasoning and also to logics in Artificial
Intelligence, and have been explored in the area of
nonmonotonic reasoning since the 80s of the past century. They
can be formalized as conditionals (|), allowing for a
nonclassical, three-valued interpretation of conditional
statements. Semantics for knowledge bases consisting of
conditionals are provided by epistemic states, often equipped with
total preorders on possible worlds. Using total preorders
ensures a high quality of nonmonotonic reasoning in terms
of broadly accepted axioms. Ordinal conditional functions
[
Similar to conditionals for propositional logic, statements
of the form “Usually, As are Bs” encoded as defeasible
concept inclusions ⊏∼ , also called defeasible subsumptions,
are a natural extension for description logics (DLs) in
order to introduce conditional reasoning. Recently, diferent
semantics for defeasible DL knowledge bases have been
proposed [
In order to compare and contrast diferent approaches to
non-monotonic reasoning, as well as to provide unifying
frameworks, postulates are necessary. A popular approach
for non-monotonic reasoning, preferential models, is
characterized by the so-called KLM postulates [
0009-0008-6114-2594 (A. Hahn); 0000-0001-8689-5391 (G. Kern-Isberner); 0000-0003-2204-6969 (T. Meyer) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
DL version of these postulates, lifting the KLM approach to defeasible description logics.
The goal of this paper is to propose first steps towards
an interpretation of defeasible subsumptions in description
logics (DL) which is thoroughly based on conditionals and
ranking functions. To this end, we lift the notion of inductive
inference operators defined in [
The rest of this paper is organized as follows. In Section 2,
the basics on first-order conditionals and defeasible ℒ
are summarized. In Section 3, we describe inductive
inference operators for first-order (conditional) knowledge bases.
In Section 4, postulates from [
This section recalls some formal basics on conditional
firstorder logic and defeasible description logics. For a more
thorough introduction to description logics, we recommend
[
In this section, we recall relevant parts of the first-order
conditional logic introduced in [
ℒΣ be the first-order language that alboth open and closed formulas. lows no nested quantification, i.e., all quantified formulas are either universal or existential formulas. ℒΣ contains ℒΣ is extended by a conditional operator “|” to a conditional language (ℒΣ|ℒΣ) containing first-order conditionals (|) with , ∈ ℒΣ. We write ((⃗)|(⃗)) to highlight free variables. Then we assume ⃗ to mention all free variables occurring in or where the positions of the variables are suitably adapted. Note that and usually will have free variables in common but may also mention free variables which do not occur in the respective other formula. E.g., the conditional ( (, ) ∧ (, )| (, )) (if is a friend of then usually is also a friend of and has also a(nother) friend ) would be represented by ((, , )|(, , )) with (, , ) = (, ) ∧ (, ) and (, , ) = (, ). Note that conditionals cannot be nested, and that conditionals with tautological antecedent are identified with the corresponding non-conditional statement, i.e., (|⊤) ≡ tween such plausible statements (|⊤) ≡ facts. Let ℒΣ = ℒΣ ∪ (ℒΣ|ℒΣ) be the language containing both first-order formulas and conditionals as specified and strict above. ℛ is a finite set
to represent defeasible plausible beliefs. ⟨ℱ , ℛ⟩ consists of a first-order conditional knowledge base ℛ, together with a set ℱ of closed formulas from ℒΣ, called facts. The open formulas and conditionals in ℛ are meant
Regarding semantics, we base our first-order conditional of ℋ semantics on the Herbrand semantics. A possible world is a subset of the Herbrand base ℋΣ, which contains all ground atoms of the first-order signature Σ . Possible worlds can be concisely represented as complete conjunctions or minterms, i.e. conjunctions of literals where every atom Σ appears either in positive or in negated form. The set of all possible worlds is denoted by Ω Σ. For an open conditional = ((⃗)|(⃗)), the set ℋ of all vectors from the Herbrand universe that appear in denotes the set ℬ = groundings of , i.e.
ℋ
((⃗)|(⃗)) = {⃗ ∈ Σ | |⃗| = |⃗|}.
Ordinal conditional functions [
. Nevertheless, we distinguish bethen also holds”.
Definition 1.
An ordinal conditional function (OCF) on Ω Σ is a function : Ω Σ → N ∪ {∞} with − 1(0) ̸= ∅. open formulas.
We can now make use of the possible world semantics to assign degrees of disbelief also to formulas and (nonquantified) conditionals. In the following, let , ∈ ℒΣ denote closed formulas, and let (⃗), (⃗) ∈ ℒΣ denote Definition 2
( -ranks of closed formulas [
|= () = min () and ( | ) = () − ().
By convention, (⊥) = ∞, because ranks are supposed to reflect plausibility. closed (conditional) formulas.
The ranks of first-order formulas are coherently based on
the usage of OCFs for propositional formulas. These degrees
of beliefs are used to specify when a formula from (ℒΣ|ℒΣ)
is accepted by a ranking function (where acceptance is
denoted by |=). We will first consider the acceptance of
Definition 3 (Acceptance of closed formulas [
• |= ( | ) if () < ().
Acceptance of a sentence by a ranking function is the same as in the propositional case for ground sentences, and interprets the classical quantifiers in a straightforward way.
The treatment of acceptance of open formulas is more
intricate, as such formulas will be used to express default
statements, like in “ is plausible”, or in “usually, if holds,
Definition 4 ( -ranks of open formulas [
((⃗)) = ((⃗)|(⃗)) =
min ⃗∈ℋ(⃗)
min ⃗∈ℋ((⃗)|(⃗)) ((⃗)) ((⃗)(⃗)) − ((⃗)).
Generalizing the notion of acceptance of a first-order formula or conditional is straightforward for closed formulas and conditionals. The basic idea here is that such (conditional) open statements hold if there are individuals called representatives that provide most convincing instances of the respective conditional.
Definition 5 (representative [
Further, ⃗ ∈ wRep() is a (strong) representative of if (︀ (⃗)(⃗))︀ =
min ⃗∈wRep() ︁( (⃗)(⃗))︁ .
The set of strong representatives of is denoted by Rep(). (1) (2) (3) (Strong) Representatives of a conditional are characterized by being most general (1) and least exceptional (3). And of course, their instantiation should be accepted by (2). Note that Rep() ̸= ∅ if wRep() ̸= ∅. Now we can base our definition of acceptance of open conditionals on the notion of representatives as follows.
Definition 6 (acceptance of open conditionals [
Observe the diference between acceptance and enforcement: while |= is the same as |= (|⊤) and only means that has to hold in the -minimal worlds, ||− means that holds in all feasible (i.e. finitelyranked) worlds. Nevertheless, enforcement is downwardcompatible to plausible acceptance, as the next proposition shows.
Proposition 1. Let be an OCF and let ∈ ℒΣ be a closed formula. ||− implies |= .
Proof. If ||− , then |= for all ∈ Ω such that () < ∞. This implies particularly that |= for all ∈ Ω such that () = 0, i.e., |= .
With the necessary notation for the treatment of both uncertain and factual knowledge in place, we are now ready to define the conditions for whether an OCF can be considered a model of a first-order knowledge base.
Definition 8 ((ranking) model of a first-order KB [
• ||− for every fact ∈ ℱ .
• |= for every rule ∈ ℛ.
We illustrate first-order knowledge bases and their ranking models in the following example.
Example 1. We consider a signature Σ = ⟨Σ, Σ⟩ consisting of two unary predicates Σ = {, } and at least two constants {, } ⊆ Σ. Let the knowledge base ℬ = ⟨ℱ , ℛ⟩ be specified by ℱ = {()(), ()()} and ℛ = {(()|()), (()|())}. Any model of ℬ must assign rank ∞ to all ̸|= ℱ , i.e., can have finite ranks only for worlds satisfying |= ()()()(). This implies, also by Proposition 1, that (()()) = 0 = (()()) and (()()) = ∞ = (()()). Moreover, we must have |= (()|()) and |= (()|()). For the second closed conditional, this simply means (()()) < (()()), which clearly holds. For the open conditional (()|()), we must apply Definition 6. In particular, we must consider representatives of this conditional. Since (()()) = 0 = (()()), we also have (()()) = 0 = (()()) by
Definition 6 applies, and we must also consider representatives of (()|()). Natural candidates of representatives for (()|()) resp. (()|()) would be resp. , but let us go into more details here. For both, we have (()()) = ∞ = (()()), so they are definitely weak representatives of the respective conditional. However, for strong representatives, their rank of falsification must also be minimal among all weak representatives, according to (3). For and , this rank is maximal due to (()()) = ∞ = (()()), and at least prima facie, it is well imaginable that there are other constants ∈ Σ with lower, i.e., finite falsification ranks. So, at this point we stop our investigations here and will come back later to this example when we can use more detailed information about the structure of ranking models of ℬ in the next section.
Now we have set up the formal framework of our rankingbased approach that we need for reasoning from first-order knowledge bases. Before dealing with inference from such knowledge bases in the next section, we briefly summarize the syntactic basics of a description logics with defeasible subsumptions. 2.2. Defeasible ℒ Let be a set of atomic concept names, be a set of role names and be a set of individual names. The set of ℒ-concepts is defined by the rule
::= |⊤|⊥|¬| ⊓ | ⊔ |∃.|∀. , where ∈ and ∈ .
An ℒ-interpretation is a tuple = ⟨∆ ℐ , · ℐ ⟩, where ∆ ℐ is a domain and · ℐ is an interpretation function which maps ∈ , ∈ , ∈ to ℐ ⊆ ∆ ℐ , ℐ ⊆ ∆ ℐ × ∆ ℐ , ℐ ∈ ∆ ℐ , respectively. For complex concepts: ⊤ℐ = ∆ ℐ ⊥ℐ = ∅ ¬ℐ = ∆ ℐ ∖ ℐ ( ⊓ )ℐ = ℐ ∩ ℐ ( ⊔ )ℐ = ℐ ∪ ℐ (∃.)ℐ = { ∈ ∆ ℐ | ∃.(, ) ∈ ℐ ∧ ∈ ℐ } (∀.)ℐ = { ∈ ∆ ℐ | ∀.(, ) ∈ ℐ ⇒ ∈ ℐ } Classical (strict) subsumptions ⊑ (where , are concepts) hold in an interpretation (short: |= ⊑ ) if ℐ ⊆ ℐ . Assertions of the form () or (, ) (where is a concept, is a role and , are individuals) hold if ∈ ℐ or (, ) ∈ ℐ , respectively.
Beyond classical logics and similar to first-order conditionals, defeasible subsumptions ⊏∼ encode information of the form “Usually, instances of are instances of ” or “Typical s are s”.
A defeasible (ℒ) knowledge base ℬ = ⟨ , , ⟩ consists of a TBox (containing strict subsumptions), a DBox (containing defeasible subsumptions) and an ABox (containing assertions).
A popular approach to provide semantics for defeasible
subsumptions (e.g. used in [
In this paper, we understand defeasible subsumptions as open conditionals and interpret them via ranking functions.
In this section, we consider inference relations induced by
ifrst-order (FO) knowledge bases, similar to the ones
considered for the propositional case in [
Let ℬ = ⟨ℱ , ℛ⟩ be a first-order knowledge base. We
are interested in defeasible inferences that we can draw
from ℬ, i.e., we consider (nonmonotonic) inferences of
the form ℬ |∼ with ∈ ℒΣ being a first-order formula
or conditional. More precisely, we study inductive inference
relations |∼⊆ℒ Σ × ℒ Σ similar to the ones presented in [
Note that (DI) is a bit basic concerning the treatments of facts. Actually, we would expect facts from ℱ to be enforced. We will see that our approach can guarantee this.
One natural way to construct an inductive inference relation is to choose a model for each knowledge base and consider the inferences induced by via ⟨ℱ , ℛ⟩ |≈ if |= , (6) where ∈ ℒΣ, and ⟨ℱ , ℛ⟩ |≈ means that can be inferred from ⟨ℱ , ℛ⟩ via its ranking model .
However in general, it is not easy to decide on the existence of models of a first-order knowledge base, i.e., on the satisfiability of such knowledge bases in our rankingbased semantics, as we saw in Example 1. In particular, knowledge given by facts in ℱ may interact with plausible beliefs specified by conditionals in ℛ. For example, if ℱ |= ∀⃗.(⃗) ⇒ (⃗), the conditional ((⃗)|(⃗)) ∈ ℛ cannot be accepted by a ranking function . In this case, the ℬ = ⟨ℱ , ℛ⟩ would be not satisfiable.
In the next subsection, we recall a class of ranking models
of first-order knowledge bases that allow for more
transparent investigations into the satisfiability of first-order
knowledge bases and usually provide a basis for quite
wellbehaved inductive inference.
3.2. Inductive FO-Inference Based on
c-Representations
c-Representations, originally defined for the propositional
setting [
Definition 9 (c-Representation [
(7) 1≤ ≤ where () = #{⃗ ∈ ℋ | = ((⃗) | (⃗)) ∈ ℛ, |= (⃗)(⃗)} is the number of possible grounding vectors that appear in falsifications of in , and 0, ∈ N with ≥ 0 are suitably chosen to ensure that is an OCF and |= ℛ.
The value 0 is a normalizing factor for ensuring that min∈Ω () = 0, and the values are called impact factors. Observe that the value of does not depend on the specific world under consideration, but on the other conditionals in ℛ, and can be determined via a set of inequalities between the diferent . Therefore, c-representations exist if this system of inequalities is solvable. This allows for deriving suficient conditions for the satisfiability of knowledge bases in terms of solutions of inequalities. However, in the first-order case, this system of inequalities is much more complex than in the propositional case because conditionals can be both verified and falsified by diferent constants in the same world, and due to the interactions between facts and conditionals. Therefore, it is hardly possible to give a generic representation of these inequalities for first-order knowledge bases. We illustrate c-representations by continuing our Example 1.
Example 2 (Example 1 cont’d). We consider the knowledge base ℬ = ⟨ℱ , ℛ⟩ with ℱ = {()(), ()()} and ℛ = {1 = (()|()), 2 = (()|())} from Example 1. A c-representation of ℬ has the form () = 0 + ∑︀1≤ ≤ 2 () for |= ()()()(), and () = ∞ for ̸|= ()()()(). Since ()() ∈ ℱ , conditional 2 cannot be falsified by finitelyranked worlds, so the impact factor 2 is inefective, and we just have () = 0 + 1() 1 (8) for |= ()()()(). For any such , () ≥ 0 + 1 because of the falsification of 1 by , and if no other constant falsifies 1, we obtain () = 0 + 1 as the minimum rank which must be 0. This yields 0 = − 1.
The impact factor 1 ≥ 0 has to be chosen in such a way that 1 is accepted by . As for any model of ℬ, it holds that 0 = (()()) = (()()) < (()()) = ∞ and 0 = (()()) = (()()) < (()()) = ∞, so ∈ wRep(1) and ∈ wRep((()|())), and Definition 6 (B) applies. Consider any constant ̸∈ {, }. Since |= ()() can be chosen in such a way that |= () for any further constant ̸∈ {, , }, we obtain (()()) = (()()()()()()) = 0 = (()()), and analogously, (()()) = 1.
= 0.
Then we would have ̸∈ (()()) = 0 = (()()), so ̸∈ wRep(1) and wRep((()|())). Hence wRep(1) = {} and wRep((()|())) = {}, and therefore Rep(1) = {} and Rep((()|())) = {}. So finally, we have to check the last condition (5) from Definition 6 (B) for and , and ifnd that (()()) = ∞ = (()()), hence (5) is violated. Therefore, 1 = 0 cannot ensure the acceptance of 1.
On the other hand, for any (finite) 1 > 0 and for any constant ̸∈ {, }, we then calculate (()()) = (()()) = 0 < 1
= (()()). Hence each such is a weak representative satisfying (()()) = 1 < ∞
= (()()). So in this case, cannot be a strong representative of 1, and we obtain Rep(1) = Σ ∖ {, }. Obviously, any ∈ Σ ∖ {} cannot be a (weak) representative of (()|()), and therefore we have wRep((()|())) = Rep((()|())) = {}. Finally, since for any ∈ Rep(1), (()()) = 1 < ∞ = (()()), also (5) can be satisfied. Therefore, any ifnite 1 > 0 in (8) yields a c-representation of ℬ.
Nevertheless, if c-representations of a first-order knowledge base exist at all, then there are usually infinitely many of them. E.g., in Example 2 above, infinitely many 1 > 0 define infinitely many c-representations. Therefore, some kind of selection procedure is needed in order to formalize which c-representations an inductive inference operator should choose. vector⃗ ∈ N|ℛ| Definition 10 (selection strategy ). A selection strategy (for c-representations) is a function assigning to each firstorder conditional knowledge base ℬ = ⟨ℱ , ℛ⟩ an impact : ℬ ↦→⃗ such that the OCF obtained by using⃗ as impacts in Definition 9 is a c-representation of ℛ.
With the help of selection strategies, we are now able to define inductive inference operators specifically for inferences obtained from c-representations of a given knowledge base.
Definition 11 (Cc-rep). An inductive inference operator for c-representations with selection strategy is a function Cc-rep : ℬ ↦→ (ℬ)
where is a selection strategy for c -representations. As before, a corresponding inductive inference relation can be obtained via Equation (6).
It can easily be checked that the postulates (DI) and (TV) are satisfied by all inference relations induced from c-representations. (DI) is ensured by the fact that each crepresentation is a model of the knowledge base, and (TV) is immediate from Equation (7), as the following lemma shows. vector ⃗ such that ℱ |= (⃗) ⇒ (⃗).
Lemma 1. Let ⟨ℱ , ∅⟩ be a first-order knowledge base, let be a c-representation of ⟨ℱ , ∅⟩. Then for any conditional ((⃗)|(⃗)), | = ((⃗)|(⃗)) only if there is a constant Proof. Any c-representation of ⟨ℱ , ∅⟩ has the form (7) for |= ℱ and satisfies () = ∞ for ̸|= ℱ there are no conditionals in the rule base, we simply have . Since () = 0 for |= ℱ must satisfy 0 = 0. If , hence the normalization constant
|= ((⃗)|(⃗)) holds, there must be weak representative for ((⃗)|(⃗)), hence there must be a constant vector ⃗ such that ((⃗)(⃗)) < ((⃗)(⃗)). This is possible only if ((⃗)(⃗)) = 0 and ((⃗)(⃗)) = ∞, since has only these two ranks. This implies () =
∞ for all |= (⃗)(⃗), i.e., for all |= (⃗)(⃗), ̸|= ℱ . Via contraposition, ℱ | = ¬((⃗)(⃗)) ≡
(⃗) ⇒ (⃗). This was to be shown. 3.3. c-Representations for Defeasible ℒ The basic idea of our approach is to understand defeasible subsumptions as open first-order conditionals. This allows for considering defeasible ℒ knowledge bases as first-order (conditional) knowledge bases and make use of ranking functions to provide semantics for defeasible ℒ knowledge bases. Even more, we are then able to reason inductively from defeasible ℒ knowledge bases via c-representations. We will investigate both the general ranking-based semantics of defeasible ℒ reasoning and its more sophisticated version based on c-representations in the following to show the potential of this semantics for description logics. Since this paper only takes first steps in this direction, we want to focus on main techniques of our approach to not burden the general line of thought with too many technical details. Therefore, the following three prerequisites apply for the rest of this paper:
Rep() ̸= ∅ and 1. Both components ℱ and ℛ of first-order conditional knowledge bases do not mention any constant. For the ABox is empty.
defeasible ℒ knowledge bases, this means that 2. The ranking-based semantics for open first-order conditionals is restricted to option (A) of Definition 6, i.e., in the following, |
= = ((⃗)|(⃗)) if 3. Moreover, we also presuppose that there are “enough” constants available in Σ to ensure that for every conditional there is some constant vector that can serve as a strong representative, and that non-acceptance of conditionals is not due to |Σ| being too small. E.g., one may assume that for every conditional = ((⃗)|(⃗)) there exists a special constant vector ⃗ with ⃗ ∈ ℋ the components of which do not occur anywhere else in the knowledge base.
The first prerequisite is not uncommon for description logics and is an intuitive justification for the second prerequisite. Although the ranking-based conditional semantics for firstorder knowledge bases from Section 2.1 is able very well to deal with information about individuals and even allows for having a defeasible ABox, as Examples 1 and 2 illustrate, these examples also show how intricate investigations can be when option (B) of Definition 6 must be applied. This option is typically relevant only in cases where knowledge or beliefs about individuals are present. Since we focus on generic (conditional) beliefs in this paper, i.e., our knowledge bases consist of quantified first-order sentences and open conditionals representing defeasible subsumptions, we use only option (A) of Definition 6 in this paper.
In fact, condition (4) is enough to ensure the acceptance of a conditional, as the following proposition shows. Proposition 2. Let be an OCF and let ((⃗)|(⃗)) be an open conditional. If ((⃗)(⃗)) < ((⃗)(⃗)) holds, then |= ((⃗)|(⃗)).
Proof. We have to show that (4) ensures that the conditional has strong representatives. Let ⃗ be such that ((⃗)(⃗)) = ((⃗)(⃗)). Since ((⃗)(⃗)) < ((⃗)(⃗)) ≤ ((⃗)(⃗)), we have ((⃗)(⃗)) < ((⃗)(⃗)). Therefore, ⃗ is at least a weak representative of ((⃗)|(⃗)), which means that Rep(((⃗)|(⃗))) ̸= ∅. Because (A) holds by definition, it follows that |= ((⃗)|(⃗)).
To motivate prerequisite (3), consider Example 2 again. If Σ would consist only of the constants and , conditional 1 could not be accepted for the only reason that neither nor can be a strong representative for 1 (please see the argumentation for case 1 = 0 in the example). At least a third constant ̸∈ {, } is needed to ensure the acceptance of 1.
However, even under all three prerequisites from above, it is hard to make general statements about the consistency of a first-order knowledge base, or the system of inequalities that impact factors in c-representations have to solve. The papers [13, 14] present a suficient condition for the consistency of a first-order knowledge base by lifting the concept of a tolerance partition (on which the propositional system Z [15] is based) to the first-order case. However, it is still an open question under which conditions c-representations for a first-order knowledge base exist. Our conjecture here is that they exist if the knowledge base is consistent, i.e., if it has a ranking model at all, just as in the propositional case. We leave further investigations into this research question for future work and focus on the quality of inductive reasoning based on c-representations for defeasible description logics in the following.
In [
We now present a version of the KLM-style postulates using first-order conditionals. Since concepts and roles in description logics are unary and binary predicates, respectively, we use single variables , instead of vectors ⃗ here in order to simplify notation. However, none of the proofs in this paper rely on the arity of the predicates. Moreover, in compliance with the prerequisites stated in the previous section, we can assume that there is at least one constant symbol, i.e. Σ ̸= ∅. (Ref) |= (()|()). (LLE) If ||− ∀ .[() ⇔ ()] and |= (()|()), then |= (()|()). (RW) If ||− ∀ .[() ⇒ ()] and |= (()|()), then |= (()|()). (And) If |= (()|()), (()|()), then (() ∧ ()|()). (Or) If |= (()|()), (()|()), then (()|() ∨ ()). (CM) If |= (()|()), (()|()), then (()|() ∧ ()). |= |= |= (RM) If |= (()|()) and ̸|= (()|()), then |= (()|() ∧ ()).
The translation of the quantified postulates using first-order conditionals is given below. (CM∃) If |= (() | ∃.[(, ) ∧ ()]) and |= (∀.[(, ) ⇒ ()] | ∃.[(, ) ∧ ()]), then |= (()|∃.(, ) ∧ () ∧ ()). (CM∀) If |= (() | ∀.[(, ) ⇒ ()]) and |= (∀.[(, ) ⇒ ()] | ∀.[(, ) ⇒ ()]), then |= (() | ∀.[(, ) ⇒ (() ∧ ())]). (RM∃) If |= (() | ∃.[(, ) ∧ ()]) and ̸|= (∀.[(, ) ⇒ ()] | ∃.[(, ) ∧ ()]), then |= (() | ∃.[(, ) ∧ () ∧ ()]). (RM∀) If |= (() | ∀.[(, ) ⇒ ()]) and ̸|= (∀.[(, ) ⇒ ()] | ∀.[(, ) ⇒ ()]), then |= (() | ∀.[(, ) ⇒ (() ∧ ())]).
Proof. In the following proofs for the individual postulates, we implicitly use Proposition 2 and prove the acceptance of desired conditionals by proving that their verification is more plausible than their falsification.
(Ref): This postulate is straightforward as (()) < (⊥) by definition.
(LLE): Let () be equivalent to () for all in all feasible possible worlds, and let | = (()|()). Because of the equivalence of () and (), we have (()()) = (()()) and (()()) = (()()) for every . Therefore, if is a representative of (()|()), it has to be a representative of (()|()) as well. Hence, if condition (A) or (B) from (()|()), the respective condiDefinition 6 holds for tion has to hold for (()|()), too.
(RW): We have (()()) the fact ∀.[() ⇒ ()].
< (()()) and Therefore, we have (()())
= (()()()) ≥ Hence, (()()) < (()()). (()()) ≤ (()()()) = (()()) and (()()). | = (And):
Because of (()()) < (()()) and (()()) < (()()), the minimal worlds in with
() for some have to satisfy both () and () as well.
Therefore, we can conclude that (()()) = (()()) = (()()()). It follows that (()()()) < min{()(), ()()} = (()(() ∨ ())).
(Or): It holds that (()() ∨ ()()) ()()). min{ (()()), (()())} min{ (()()), (()())} = (()() ∨ = < (CM): Because of (()()) < (()()) and (()()) < (()()), the minimal worlds ∃ ∀ in with |
= () for some have to satisfy both (()()()). () and () as well. Therefore, we can conclude that (()())
= (()()) = (()()()).
It follows that (()()()) < (()()) ≤ (CM ): Let be a minimal world in such that , ex()()], and for every ′′ with (′′) ist with |= (, )(). Since (A) holds, for every ′ with (′) = () we have ′ |= ∀.∀.[(, )() ⇒ () < we have ′′ | =
∀.∀.(, ) ∨ (). () = (() ∧ ∃.[(, )()()]) < (() ∧ Therefore, ()()]). ∃.[(, )()()]).
(CM ): Let be a minimal world in such that exists with |= ∀.(, ) ⇒ (). Since (A) holds, for every ′ with (′) = () it holds for all that ′ |= ∀.[(, ) ⇒ ()] implies ′ |= () ∧ ∀.[(, ) ⇒ ()]. And for every ′′ with (′′) < () we have ′′ |= ∀.∃.(, )(). Therefore, () = (() ∧ ∀.[(, ) ⇒ ()()]) < (() ∧ ∀.[(, ) ⇒ For the case (A), (RM), (RM∃), and (RM∀) are implied by ∃
∀ (CM), (CM ), and (CM ), respectively.
In [
= ⟨ℱ , ℛ⟩ be a first-order conditional knowledge base, and let be a model of ℬ. If ℱ |= ∈ ℒΣ, then ||− . (SUB) ⟨∅, {((⃗)|(⃗))}⟩ |∼ ((⃗) ⇒ (⃗)|⊤).
Postulate (CLA) claims that each ranking model of a conditional knowledge base respects all classical consequences of the facts. Postulate (SUB) reveals a compatibility between a conditional and its counterpart as material implication. But note that this counterpart is only plausible.
The next proposition shows that both these postulates are also satisfied by our approach.
Proposition 4. Let be an OCF. If is a model of ⟨ℱ , ℛ⟩ then ||− for all
∈ ℒΣ with ℱ |= . If is a model of ⟨∅, {((⃗)|(⃗))}⟩ then |= ((⃗) ⇒ (⃗)|⊤). Proof. Let be a model of ⟨ℱ , ℛ⟩, let ℱ | also for all ̸|
= = . Then () = .
Therefore,
∞ for all ̸|= ment follows. model of ⟨∅, {((⃗)|(⃗))}⟩ then i.e., ((⃗)(⃗)) < ((⃗)(⃗)). Since ((⃗) (⃗)) = (¬(⃗) ∨ (⃗)) ≤ ((⃗)(⃗)), the state⇒ ||− | = ∈ ℒΣ with ℱ and hence . If is a ((⃗)|(⃗)),
The next postulate deals with obviously irrelevant
variables in an open conditional, i.e., variables that do not occur
in both the antecedent and the consequent of the conditional.
It adapts the postulate (IRR) from [
Then ⟨∅, {((⃗, ⃗)|(⃗, ⃗))}⟩ |∼ ⃗ resp. ⃗ in resp. .
((⃗, ⃗)|(⃗, ⃗)) for all proper groundings ⃗, ⃗ of This postulate does not hold in general for our ranking semantics but we can show that it holds for ranking models which are c-representations. resp. ⃗ in resp. .
Proposition 5. Let ⃗, ⃗, ⃗ mention variables from pairwise disjoint sets, and let ℬ
= ⟨∅, {((⃗, ⃗)|(⃗, ⃗))}⟩. Let | = (ℬ) be a strategic c-representation of ℬ. Then = ((⃗, ⃗)|(⃗, ⃗)) for all proper groundings ⃗, ⃗ of ⃗ representation of ℬ has the form Proof. Let ⃗, ⃗, ⃗ mention variables from pairwise disjoint sets, and let ℬ
= ⟨∅, {((⃗, ⃗)|(⃗, ⃗))}⟩. Each c () = 0 + 1() 1, latter condition enforces that where 1() = #{(⃗, ⃗, ⃗)|(⃗, ⃗, ⃗) are proper groundings of ⃗, ⃗, ⃗ in ((⃗, ⃗)|(⃗, ⃗))} and 0, 1 ∈ suitably chosen to ensure that |= ((⃗, ⃗)|(⃗, ⃗)). This N with 1 ⃗,⃗,⃗ min ((⃗, ⃗)(⃗, ⃗) < min ((⃗, ⃗)(⃗, ⃗). ⃗,⃗,⃗ The left hand side here is 0 (all instantiations verifying the conditional), and the right hand side here is 1 (just one falsification of the conditional), so we obtain 1 > 0 from that.
Now, if we take any proper groundings ⃗, ⃗ of ⃗ resp. ⃗ in resp. and check whether ⃗
⃗
min ((⃗, ⃗)(⃗, ⃗) < min ((⃗, ⃗)(⃗, ⃗),
in resp. .
we find again that the left hand side is 0 and the right hand
side is 1. Since 1 > 0 must hold, we conclude that |
((⃗, ⃗)|(⃗, ⃗)) for all proper groundings ⃗, ⃗ of ⃗ resp. ⃗
=
The goal of this section is to provide an example for how
a DL knowledge base can be translated into a first-order
knowledge base, so that OCF-based inductive reasoning can
be applied. Further, we point out some commonalities and
diferences between the OCF-based semantics and the cw
msemantics introduced by Giordano and Theseider Dupré in
[
In [
In order to define a preference relation over individuals, the DBox is partitioned based on the left-hand side of the defeasible inclusions. Let = { | ( ⊏∼ ) ∈ }. For each concept ∈ , let be the set that contains all defeasible inclusions ( ⊏∼ ) ∈ , and for an interpretation ℐ = ⟨∆ ℐ , · ℐ ⟩, let ℐ () be the set of defeasible inclusions from which are not violated by , i.e.
ℐ () = {( ⊏∼ ) ∈ | ∈ (¬ ⊔ )ℐ }. Based on the amount of non-violated defeasible subsumptions, for each concept ∈ a preference relation ≤ is defined via ≤ if |ℐ ()| ≥ | ℐ ()|. (9)
Before we can define cw m-models, we need one more definition: If a concept is a (potentially) strict subset of another concept , the subset can be viewed as more specific then .
Definition 12 (specificity of concepts [
In cwm-models of defeasible knowledge bases, the preference relations for the specific concepts defined in Equation 9 are combined into a global preference relation based on the concepts’ specificity.
Definition 13 (cwm-model [
A cwm-model ℳ satisfies a defeasible subsumption ⊏∼ if the <ℳ-minimal instances of are instances of : ℳ |= ⊏∼ if min(<ℳ, ℐ ) ⊆ ℐ , where min(<, ) = { ∈ | ∄′ ∈ : ′ < } as usual.
Now we move towards defining m-entailment from defeasible knowledge bases. Let ℬ be the set that contains and ¬ for all concepts that occur in a knowledge base ℬ = ⟨ , , ⟩. We say that {1, . . . , } ⊆ ℬ is consistent with ℬ if ̸|= (1 ⊓ · · · ⊓ ) ⊑ ⊥ , i.e. if the intersection of 1 to does not have to be empty.
Definition 14 (canonical interpretation [
In other words, an interpretation is canonical if there is at least one domain element ∈ ∆ ℐ in every intersection of concepts that occur in ℬ.
Definition 15 (T-compliant interpretation [
The definition above means that for all non-empty concepts , there is at least one instance of which does not violate any defeasible subsumptions in with on the lefthand side.
Definition 16 (cwm-entailment [
It was proven in [
In order to allow for a comparison between the approach
of [
Example 3. We consider the following example DL
knowledge base, which is very similar to the running example
presented in [
= {Employee ⊑ Adult, PhdStudent ⊑ Student, (∃has_funding.⊤ ⊓ ¬Funded) ⊑ ⊥}, Employee = { 1 : Employee ⊏∼ ¬Young,
2 : Employee ⊏∼ ∃has_boss.Employee }, Student = { 3 : Student ⊏∼ ∃has_classes.⊤, 4 : Student ⊏∼ Young, 5 : Student ⊏∼ ¬Funded }, PhdStudent = { 6 : PhdStudent ⊏∼ ∃has_funding.Money, 7 : PhdStudent ⊏∼ Bright }.
As description logics are fragments of first-order logic, the knowledge base above can easily be translated into a firstorder knowledge base. We start by translating the strict subsumptions in the TBox as facts.
ℱ = {∀.[Employee() ⇒ Adult()], ∀.[PhdStudent() ⇒ Student()], ∀.[∃.has_funding(, ) ⇒ Funded()]} .
The defeasible subsumptions can be translated as open conditionals. From now on, all predicates are shortened to their initial letters.
ℛ = { 1 : (¬ () | ()), 2 : (∃.[hb(, ) ∧ ()] | ()), 3 : (∃.hc(, ) | ()), 4 : ( () | ()), 5 : (¬ () | ()), 6 : (∃.[hf (, ) ∧ ()] | ()), 7 : (() | ()) }
of 6 by a c-representation can be computed. In order to keep formulas compact and readable, we indicate by a dot over a literal (e.g. ̇()) that the literal may be either positive or negative (() or ¬()) and an underscore serves as a wildcard that may be filled by all suitable constants ∈ Σ. For roles, i.e., binary predicates, the constants are the ones used together with a constant in order to form a candidate for a strong representative for the rule . |= 6 (4) ⇔ ⇔ ⇔ ( ()hf (, ) ()) ∈Σ < ( () ∧ ∀.hf (, ) ()) min ( ()hf (, 6) (6)) < min ( () ⋀︁ hf (, ) ())
∈Σ ()hf (, 6) (6) ∈Σ
︁( min ∈Σ < min ∈Σ ̇ ()()()hc(, 3) () ̇()()̇ ()ḣb(, _)
︁) ︁( () ⋀︁ (︀ hf (, ) ∨ ())︀
∈Σ ̇ ()()()hc(, 3) () ̇()()̇ ()ḣb(, _) ︁)
In the following, we present an example which shows that the desirable properties of cwm-semantics w.r.t. inheritance of properties are fulfilled by the OCF-based semantics as well. A full axiomatization of “proper inheritance of properties” is out of the scope of this paper, and will be addressed in future work.
Example 3. In [
˓→ should be yes 4. ⟨ℱ , ℛ⟩ |≈ 5. ⟨ℱ , ℛ⟩ |≈ ˓→ should be no ˓→ should be no 6. ⟨ℱ , ℛ⟩ |≈ 7. ⟨ℱ , ℛ⟩ |≈ ˓→ should be no ˓→ should be no ︀( ︀( ︀( ︀( ︀( ︀( ∃.hb(, ) | () ∧ ())︀ ? ︀( ∃.hc(, ) | () ∧ ())︀ ? ¬ () | () ∧ ())︀ ?
() | () ∧ ())︀ ? ¬ () | () ∧ ())︀ ? ¬ () | () ∧ Italian())︀ ? ¬ () | ())︀ ? (inheritance) (inheritance) (inheritance) (conflict) (conflict) (irrelevance) (override) When the OCF used for answering the queries above is a (minimal) c-representation, all of the queries are answered correctly. As an example, we will compute the answer for query 7 below. The conditional mentioned in the query is accepted by if ( () ()) < ( () (). Hence, we need to compute these two ranks. ( () ())
min ( () ()) = = = = = = ∈Σ ∈Σ 6 ∈Σ ∈Σ 5 min (︀ () ()()hf (, _) ())ḣb(, _)hc(, 3) () ()̇()̇ ())︀ min (︀ () ()()hf (, 6 ) (6)())ḣb(, _)hc(, 3 )
()()̇()̇ ())︀ ( () ()) min ( () ()) ⇔
5 < 6 as well.
resulting system of inequalities can be solved, i.e. the knowledge base ⟨ℱ , ℛ⟩ is consistent for the OCF-based semantics
One particular advantage of the cwm-semantics is that it
supports sub-concepts to both inherit and override properties
defined for their parent-concepts, depending on whether
there is a conflict of information. This is not the case for e.g.
Rational Closure [
above shows that the conditional ( ()| ()) is accepted by if 6 < 5. However, we know from Example 3 that 5 < 6. Hence, the answer to the query is no.
The example above shows that the OCF-based semantics, just like cwm-semantics, allows subclasses to appropriately inherit and override information specified for their respective superclass.
Observe another interesting feature of c-representations that comes to light in the example above: We did not have to compute the ranks for all possible worlds or even just the values of the , but could answer the query based on the underlying conditional structures of the knowledge base, captured by the inequalities between the .
There are some key diferences between our approach and the semantics proposed for defeasible description logics in the literature. While most of these approaches are based on an ordering over individuals and uses some notion of typical individuals for specific concepts, our approach uses an ordering over possible worlds and makes use of representatives for conditionals. Even if canonical models look very similar to orderings over possible worlds, only considering typicality between domain elements (even on a concept-level) when constructing the global ordering < seems to be less restrictive than considering representatives for conditionals, as it allows knowledge bases to have models that would be considered inconsistent under our semantics. However, this breaks (DI), as the following example shows.
= { ⊑ } = { ⊏∼ ¬} = { ⊏∼ , ⊏∼ } A canonical and T-compliant model ℳ for this knowledge base is given by the orderings below. The individuals are named after the concepts that they are interpreted in, with overlines indicating negation, i.e. for the individual we have ∈ (¬ ⊓ ¬ ⊓ )ℐ .
, , , , < , , < , < , <ℳ , <ℳ <ℳ We have min<(ℐ ) = {, }, i.e. min<(ℐ ) ⊈ ℐ and min<(ℐ ) ⊈ ℐ . Therefore, ℬ ̸|≈ cwm ⊏∼ and ℬ ̸|≈ cwm ⊏∼ .
In this paper, we have presented an approach for first-order
conditional logic from [
The work done in this paper lays the foundation for future
research on the capabilities of OCF-based semantics for
ifrst-order conditional knowledge bases and, in particular,
for more in-depth comparisons between
c-representationbased inductive inference operators and diferent entailment
relations proposed for defeasible DL knowledge bases like
rational entailment [
Additionally, most work done so far on first-order conditional knowledge bases and defeasible DL knowledge bases focus on the general case where no facts or no ABox, respectively, are present. Our approach is basically also capable of dealing with information from an ABox, but for this, we must also include option (B) from Definition 6 into our considerations. We will work this out in future work. Moreover, also more postulates describing how diferent approaches deal specifically with facts are needed.
More advanced properties like syntax splitting [
1007/3-540-44600-1. [12] G. Kern-Isberner, A thorough axiomatization of a principle of conditional preservation in belief revision, Annals of Mathematics and Artificial Intelligence 40 (2004) 127–164. doi:10.1023/a:1026110129951. [13] C. Beierle, T. Falke, S. Kutsch, G. Kern-Isberner, Minimal tolerance pairs for system Z-like ranking functions for first-order conditional knowledge bases, in: Z. Markov, I. Russell (Eds.), Proceedings of the Twenty-Ninth International Florida Artificial Intelligence Research Society Conference, FLAIRS 2016, AAAI Press, Menlo Park, CA, 2016, pp. 626– 631. URL: http://www.aaai.org/ocs/index.php/FLAIRS/ FLAIRS16/paper/view/12868. [14] C. Beierle, T. Falke, S. Kutsch, G. Kern-Isberner, System ZFO: Default reasoning with system Z-like ranking functions for unary first-order conditional knowledge bases, International Journal of Approximate Reasoning 90 (2017) 120–143. [15] J. Pearl, System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning, in: Proc. of the 3rd conf. on Theor. asp. of reasoning about knowledge, TARK ’90, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1990, pp. 121–135. [16] D. Lehmann, M. Magidor, What does a conditional knowledge base entail?, Artificial Intelligence 55 (1992) 1–60. doi:10.1016/0004-3702(92)90041-u. [17] L. Giordano, V. Gliozzi, N. Olivetti, G. L. Pozzato, Semantic characterization of rational closure: From propositional logic to description logics, Artificial Intelligence 226 (2015) 1–33. doi:10.1016/J.ARTINT. 2015.05.001. [18] J. Haldimann, C. Beierle, Characterizing multipreference closure with system W, in: F. D. de SaintCyr, M. Öztürk-Escofier, N. Potyka (Eds.), Scalable Uncertainty Management - 15th International Conference, SUM 2022, Paris, France, October 17-19, 2022, Proceedings, volume 13562 of Lecture Notes in Computer Science, Springer, 2022, pp. 79–91. doi:10.1007/ 978-3-031-18843-5\_6.