Introduction

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 [1,2], often called ranking functions, can be considered an implementation of such epistemic states that assign to each possible world 𝜔 an implausibility rank 𝜅(𝜔) such that the higher 𝜅(𝜔), the less plausible 𝜔 is, and with the normalization constraint that there are worlds that are maximally plausible.

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, different semantics for defeasible DL knowledge bases have been proposed [3,4,5].

In order to compare and contrast different 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 [6]. However, preferential models have been mostly considered for propositional logics. Recently, Britz et al. [4] have proposed a 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 [7] to first-order conditional knowledge bases. Additionally, we adapt the KLM postulates from [4], as well as additional rationality postulates for the KLM approach from [3] and show that they are fulfilled by our approach. Moreover, we illustrate the application of ranking-based first-order conditional semantics to a DL example well-known from the literature and compare it to concept-wise multipreference (cw m ) semantics from [5].

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 [4] and [8] are adapted and evaluated for the use with first-order conditional logic. In Section 5, we compare the OCF-based semantics for firstorder knowledge bases with cw m -semantics [5] for defeasible 𝒜ℒ𝒞 knowledge bases. In Section 6, we conclude this paper with summarizing its main contributions and some pointers for future work.

Preliminaries

This section recalls some formal basics on conditional firstorder logic and defeasible description logics. For a more thorough introduction to description logics, we recommend [9].

Conditionals in First-Order Logic

In this section, we recall relevant parts of the first-order conditional logic introduced in [10]. We start with syntactical details. Let Σ = ⟨𝑃Σ, 𝑈Σ⟩ be a first-order signature consisting of a finite set of predicates 𝑃Σ and a finite set of constant symbols 𝑈Σ but without function symbols of arity > 0. An atom is a predicate of arity 𝑛 together with a list of 𝑛 constants and/or variables. A literal is an atom or a negated atom. Formulas are built on atoms using conjunction (∧), disjunction (∨), negation (¬), material implication (⇒), and quantification (∀, ∃). We abbreviate conjunctions by juxtaposition and negations usually by overlining, e. g. 𝐴𝐵 means 𝐴 ∧ 𝐵 and 𝐴 means ¬𝐴. The symbol ⊤ denotes an arbitrary tautology, and ⊥ denotes an arbitrary contradiction. A ground formula contains no variables. In a closed formula, all variables (if they occur) are bound by quantifiers, otherwise, the formula is open, and the variables that occur outside of the range of quantifiers are called free. If a formula 𝐴 contains free variables we also use the notation 𝐴(𝑥 ⃗ ) where 𝑥 ⃗ = (𝑥1, . . . , 𝑥𝑛) contains all free variables in 𝐴. If 𝑐 ⃗ is a vector of the same length as 𝑥 ⃗ then 𝐴(𝑐 ⃗) is meant to denote the instantiation of 𝐴 with 𝑐 ⃗. A formula ∀𝑥 ⃗ 𝐴(𝑥 ⃗ ) (∃𝑥 ⃗ 𝐴(𝑥 ⃗ )) is universal (existential) if 𝐴 involves no further quantification. Let ℒΣ be the first-order language that allows no nested quantification, i.e., all quantified formulas are either universal or existential formulas. ℒΣ contains both open and closed formulas.

ℒΣ 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., (𝐴|⊤) ≡ 𝐴. Nevertheless, we distinguish between such plausible statements (𝐴|⊤) ≡ 𝐴 and strict facts. Let ℒ 𝑐 Σ = ℒΣ ∪ (ℒΣ|ℒΣ) be the language containing both first-order formulas and conditionals as specified above.

A first-order conditional knowledge base ℛ is a finite set of conditional formulas. A first-order knowledge base 𝒦ℬ = ⟨ℱ, ℛ⟩ 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 to represent defeasible plausible beliefs.

Regarding semantics, we base our first-order conditional 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 of ℋ Σ appears either in positive or in negated form. The set of all possible worlds is denoted by ΩΣ. For an open conditional 𝑟 = (𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ )), the set ℋ 𝑟 denotes the set of all vectors from the Herbrand universe that appear in groundings of 𝑟, i.e.

ℋ (𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ )) = {𝑎 ⃗ ∈ 𝑈Σ | |𝑎 ⃗| = |𝑥 ⃗ |}.

Ordinal conditional functions [1], usually called ranking functions, can be defined just as in the propositional case. They associate degrees of (im)plausibility with possible worlds.

Definition 1. An ordinal conditional function (OCF) 𝜅 on ΩΣ is a function 𝜅 : ΩΣ → N ∪ {∞} with 𝜅 −1 (0) ̸ = ∅.

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 open formulas.

Definition 2 (𝜅-ranks of closed formulas [10]). Let 𝜅 be an OCF. The 𝜅-ranks of closed formulas are defined (as in the propositional case) via

𝜅(𝐴) = min 𝜔|=𝐴 𝜅(𝜔) and 𝜅(𝐵 | 𝐴) = 𝜅(𝐴𝐵) − 𝜅(𝐴).

By convention, 𝜅(⊥) = ∞, because ranks are supposed to reflect plausibility.

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 closed (conditional) formulas.

Definition 3 (Acceptance of closed formulas [10]). Let 𝜅 be an OCF. The acceptance relation between 𝜅 and closed formulas from ℒΣ and (ℒΣ|ℒΣ) is defined as follows:

• 𝜅 |= 𝐴 iff for all 𝜔 ∈ Ω with 𝜅(𝜔) = 0, it holds that 𝜔 |= 𝐴. • 𝜅 |= (𝐵 | 𝐴) iff 𝜅(𝐴𝐵) < 𝜅(𝐴𝐵).

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, then 𝐵 also holds".

Definition 4 (𝜅-ranks of open formulas [10]). We define the ranks of open formulas and open conditionals by evaluating most plausible instances:𝜅(𝐴(𝑥 ⃗ )) = 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 [10]). Let 𝑟 = (𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ )) be an open conditional. We call 𝑎 ⃗ ∈ ℋ 𝑟 a weak representative of 𝑟 iff both of the following conditions are satisfied:

𝜅(𝐴(𝑎 ⃗)𝐵(𝑎 ⃗)) = 𝜅(𝐴(𝑥 ⃗ )𝐵(𝑥 ⃗ ))(1)𝜅(𝐴(𝑎 ⃗)𝐵(𝑎 ⃗)) < 𝜅(𝐴(𝑎 ⃗)𝐵(𝑎 ⃗))(2)

The set of weak representatives of 𝑟 is denoted by wRep(𝑟).

Further, 𝑎 ⃗ ∈ wRep(𝑟) is a (strong) representative of 𝑟 iff 𝜅 (︀ 𝐴(𝑎 ⃗)𝐵(𝑎 ⃗) )︀ = min 𝑏 ⃗ ∈wRep(𝑟) 𝜅 (︁ 𝐴(𝑏 ⃗ )𝐵(𝑏 ⃗ ) )︁ . (3)

The set of strong representatives of 𝑟 is denoted by Rep(𝑟). (

) (B) 𝜅(𝐴(𝑥 ⃗ )𝐵(𝑥 ⃗ )) = 𝜅(𝐴(𝑥 ⃗ )𝐵(𝑥 ⃗ )) and either Rep((𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ ))) = ∅, or for all 𝑎1 ⃗ ∈ Rep((𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ ))), 𝑎2 ⃗ ∈ Rep((𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ ))) it holds that 𝜅(𝐴(𝑎1 ⃗ )𝐵(𝑎1 ⃗ )) < 𝜅(𝐴(𝑎2 ⃗ )𝐵(𝑎2 ⃗ )).4

We also have to ensure that strict knowledge (facts) are interpreted suitably by ranking functions. An OCF can enforce factual knowledge by setting the ranks of all worlds which violate facts to infinity. Definition 7 (enforcement of facts). Let 𝜅 be an OCF and let 𝐴 ∈ ℒΣ be a closed formula. Then we define that 𝜅 enforces the fact 𝐴, denoted by

𝜅 || − 𝐴, iff 𝜅(𝐴) = ∞.

Observe the difference 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 [10]). Let 𝜅 be an OCF and let 𝒦ℬ = ⟨ℱ, ℛ⟩ be a first-order knowledge base. We say that 𝜅 is a (ranking) model of 𝒦ℬ if both of the following conditions hold.

• 𝜅 || − 𝐴 for every fact 𝐴 ∈ ℱ.

• 𝜅 |= 𝑟 for every rule 𝑟 ∈ ℛ.

We illustrate first-order knowledge bases and their ranking models in the following example. 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 4. Hence the more complicated option (B) of 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.

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: 𝐼 |= 𝐶 ⊑ 𝐷) iff 𝐶 ℐ ⊆ 𝐷 ℐ . 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 [4,5]) is to introduce some ordering over the domain elements ∆ ℐ and require the minimal instances of 𝐶 (with respect to said ordering) to be instances of 𝐷 in order for 𝐶 ⊏ ∼ 𝐷 to hold.

In this paper, we understand defeasible subsumptions as open conditionals and interpret them via ranking functions.

Reasoning from First-Order Knowledge Bases

In this section, we consider inference relations induced by first-order (FO) knowledge bases, similar to the ones considered for the propositional case in [7].

Inductive FO-Inference Relations

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 [7]. Two fundamental postulates for such inference relations presupposed in [7] are that formulas from the knowledge base can be inferred (this is called Direct Inference (DI)), and that without conditionals in the knowledge base, conditionals can be inferred only trivially (Trivial Vacuity (TV)).

(DI) 𝜙 ∈ ℱ ∪ ℛ implies ⟨ℱ, ℛ⟩ | ∼ 𝜙. (TV) ⟨ℱ, ∅⟩ | ∼ (𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ )) only if there is a constant vector 𝑎 ⃗ such that ℱ |= 𝐴(𝑎 ⃗) ⇒ 𝐵(𝑎 ⃗).

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

⟨ℱ, ℛ⟩ | ≈ 𝜅 𝜙 iff 𝜅 |= 𝜙,(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.

Inductive FO-Inference Based on c-Representations

c-Representations, originally defined for the propositional setting [11,12], are a special kind of ranking models which assign ranks to possible worlds in a regular way by adhering to the conditional structures of knowledge bases. A (simplified) version of c-representations for first-order conditinal knowledge bases was proposed in [10].

𝜅(𝜔) = 𝜅0 + ∑︁ 1≤𝑖≤𝑛 𝑓𝑖(𝜔)𝜂𝑖,(7)

where 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 different 𝜂𝑖. Therefore, c-representations exist iff this system of inequalities is solvable. This allows for deriving sufficient 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 different 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. 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. 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 (C c-rep 𝜎

). An inductive inference operator for c-representations with selection strategy 𝜎 is a function

C c-rep 𝜎 : 𝒦ℬ ↦ → 𝜅 𝜎(𝒦ℬ)

where 𝜎 is a selection strategy for c -representations. As before, a corresponding inductive inference relation can be obtained via Equation (6).

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: 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. 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 sufficient 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.

KLM-style Postulates and Beyond

In [4], the well-known KLM postulates for non-monotonic reasoning were translated for use with defeasible description logics, and also the postulate of rational monotonicity was considered. Let 𝐴, 𝐵, 𝐶 be concepts. Moreover, in [4], quantified versions of (CM) and (RM) which are adapted to the specific form of DL concepts have been presented. 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. 𝑈Σ ̸ = ∅. (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 [8], the authors present an approach to defeasible reasoning for a restricted first-order logic which they evaluate according to postulates that are inspired by rational closure [16]. Beyond the KLM-postulates the satisfaction of which we proved above, they also propose further postulates. E.g., the postulate (INCL) in that paper corresponds to our (DI). In the following, we adapt and extend three of those properties that deal with relations to classical logic and irrelevance to the framework here. First, we consider relations to classical logic resp. implication: 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 𝛼 ∈ ℒΣ with ℱ |= 𝛼. Then 𝜅(𝜔) = ∞ for all 𝜔 ̸ |= ℱ and hence also for all 𝜔 ̸ |= 𝐴. Therefore,

𝜅 || − 𝛼. If 𝜅 is a model of ⟨∅, {(𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ ))}⟩ then 𝜅 |= (𝐵(𝑥 ⃗ )|𝐴(𝑥 ⃗ )), i.e., 𝜅(𝐴(𝑥 ⃗ )𝐵(𝑥 ⃗ )) < 𝜅(𝐴(𝑥 ⃗ )𝐵(𝑥 ⃗ )). Since 𝜅(𝐴(𝑥 ⃗ ) ⇒ 𝐵(𝑥 ⃗ )) = 𝜅(¬𝐴(𝑥 ⃗ ) ∨ 𝐵(𝑥 ⃗ )) ≤ 𝜅(𝐴(𝑥 ⃗ )𝐵(𝑥 ⃗ )), the state- ment follows.

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 [8].

(IRR) Let 𝑥 ⃗ , 𝑦 ⃗, 𝑧 ⃗ mention variables from pairwise dis- joint sets. Then ⟨∅, {(𝐵(𝑥 ⃗ , 𝑦 ⃗)|𝐴(𝑥 ⃗ , 𝑧 ⃗))}⟩ | ∼ (𝐵(𝑥 ⃗ , 𝑏 ⃗ )|𝐴(𝑥 ⃗ , 𝑎 ⃗)) for all proper groundings 𝑎 ⃗, 𝑏 ⃗ of 𝑧 ⃗ resp. 𝑦 ⃗ in 𝐴 resp. 𝐵.

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. 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 𝑐 ⃗ 𝜅(𝐴(𝑐 ⃗, 𝑧 ⃗)𝐵(𝑐 ⃗, 𝑦 ⃗),

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. 𝑦 ⃗ in 𝐴 resp. 𝐵.

Application of OCF-based Reasoning to a DL Knowledge Base

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 differences between the OCF-based semantics and the cw msemantics introduced by Giordano and Theseider Dupré in [5] which we consider first.

Concept-Wise Multipreference Semantics

In [5], a concept-wise multipreference (cw m ) semantics for ranked defeasible knowledge bases was presented, which makes use of a typicality operator T on concepts used for the construction of typicality inclusions of the form T(𝐶) ⊑ 𝐷 (where 𝐶, 𝐷 are concepts). We provide an equivalent definition using the notation 𝐶 ⊏ ∼ 𝐷 here. Note that our definition here is a simplified version of the one given in [5], because we only consider non-ranked knowledge bases in this paper.

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

𝑥 ≤𝐶 𝑦 iff |𝒟 ℐ 𝐶 (𝑥)| ≥ |𝒟 ℐ 𝐶 (𝑦)|.(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 [5]). Given a defeasible knowledge base 𝒦ℬ = ⟨𝒯 , 𝒟, 𝒜⟩ and two concepts 𝐶, 𝐷 ∈ 𝒞, we call 𝐶 more specific than 𝐷 (short: 𝐶 ≻ 𝐷) iff 𝒯 |= 𝐶 ⊑ 𝐷 and 𝒯 ̸ |= 𝐷 ⊑ 𝐶.

In cw m -models of defeasible knowledge bases, the preference relations for the specific concepts defined in Equation 9are combined into a global preference relation based on the concepts' specificity.

Definition 13 (cw m -model [5]). A cw m -model of a defeasible knowledge base 𝒦ℬ = ⟨𝒯 , 𝒟, 𝒜⟩ is a tuple ℳ = ⟨∆ ℐ , • ℐ , < ℳ ⟩, where ∆ ℐ ̸ = ∅, ⟨∆ ℐ , • ℐ ⟩ is an 𝒜ℒ𝒞interpretation satisfying 𝒯 and 𝒜, and < ℳ is an ordering over ∆ ℐ such that 𝑥 < ℳ 𝑦 iff 1. 𝑥 <𝐶 𝑦 for some 𝐶 ∈ 𝒞, and 2. for all 𝐶 ∈ 𝒞: 𝑥 ≤𝐶 𝑦, or there exists 𝐶 ′ such that 𝐶 ′ ≻ 𝐶 and 𝑥 < 𝐶 ′ 𝑦.

A cw m -model ℳ satisfies a defeasible subsumption 𝐶 ⊏ ∼ 𝐷 iff the < ℳ -minimal instances of 𝐶 are instances of 𝐷:

ℳ |= 𝐶 ⊏ ∼ 𝐷 iff 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 [5]). A cw m -model In other words, an interpretation is canonical if there is at least one domain element 𝑥 ∈ ∆ ℐ in every intersection of concepts that occur in 𝒦ℬ.

ℳ = ⟨∆ ℐ , • ℐ , < ℳ ⟩ is canonical for a knowledge base 𝒦ℬ = ⟨𝒯 , 𝒟, 𝒜⟩ if ⟨∆ ℐ , • ℐ ⟩ satisfies 𝒯 ,

Definition 15 (T-compliant interpretation [5]). A cw mmodelℳ = ⟨∆ ℐ , • ℐ , < ℳ ⟩ is T-compliant for a knowledge base 𝒦ℬ = ⟨𝒯 , 𝒟, 𝒜⟩ if ⟨∆ ℐ , • ℐ ⟩ satisfies 𝒯

and for all 𝐶 ∈ 𝒞 with 𝐶 ℐ ̸ = ∅, there exists 𝑥 ∈ 𝐶 ℐ such that 𝒟 ℐ 𝐶 (𝑥) = 𝒟𝐶 . 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 (cw m -entailment [5]). A defeasible subsumption 𝑑 = 𝐶 ⊏ ∼ 𝐷 is cw m -entailed by a knowledge base 𝒦ℬ (short: 𝒦ℬ | ≈ cw m 𝑑) if all canonical and T-compliant cw mmodels of 𝒦ℬ satisfy 𝑑.

It was proven in [5] that cw m -entailment fulfills the properties (Ref), (LLE), (And), (Or), and (CM).

Translation of a DL Knowledge Base

In order to allow for a comparison between the approach of [5] and the OCF-based semantics in the next part of this section, we now give an example for how a defeasible knowledge base can be transformed into a first-order knowledge base.

Example 3. We consider the following example DL knowledge base, which is very similar to the running example presented in [5].

𝒯 = {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. We demonstrate below how the inequality for the acceptance 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 𝑟𝑖. 𝐹 ̇(𝑎)𝑆(𝑎)𝐸(𝑎)hc(𝑎,

𝜅 |= 𝑟6𝑏 𝑎 3 )𝑌 (𝑎) 𝐴 ̇(𝑎)𝐵(𝑎)𝑀 ̇(𝑎)hb ̇(𝑎, _) )︁ < min 𝑎∈𝑈 Σ 𝜅 (︁ 𝑃 (𝑎) ⋀︁ 𝑏∈𝑈 Σ (︀ hf (𝑎, 𝑏) ∨ 𝑀 (𝑏) )︀ 𝐹 ̇(𝑎)𝑆(𝑎)𝐸(𝑎)hc(𝑎, 𝑏 𝑎 3 )𝑌 (𝑎) 𝐴 ̇(𝑎)𝐵(𝑎)𝑀 ̇(𝑎)hb ̇(𝑎, _) )︁ ⇔ 𝜂5 < 𝜂6

The other inequalities can be computed in a similar way. The resulting system of inequalities can be solved, i.e. the knowledge base ⟨ℱ, ℛ⟩ is consistent for the OCF-based semantics as well.

Inheritance of Properties and Conflicting Information

One particular advantage of the cw m -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 [4], which suffers from the well-known drowning problem.

In the following, we present an example which shows that the desirable properties of cw m -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 4. We consider again the knowledge base from Example 3. In [5], several possible queries and desirable results are mentioned. Formulated as queries for the first-order knowledge base defined above, they read as follows. )︀

= 𝜂5

The computation 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 cw m -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 differences 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.

Conclusions

In this paper, we have presented an approach for first-order conditional logic from [10], and added a definition of inductive inference operators for first-order knowledge bases. Moreover, we have shown that an inductive inference operator based on strategic c-representations fulfills the DLversion of the KLM postulates defined in [4], as well as additional postulates from [8]. Additionally, we have shown how to apply our approach to defeasible DL knowledge bases, while pointing out some commonalities and differences with cw m -semantics for defeasible description logics [5].

The work done in this paper lays the foundation for future research on the capabilities of OCF-based semantics for first-order conditional knowledge bases and, in particular, for more in-depth comparisons between c-representationbased inductive inference operators and different entailment relations proposed for defeasible DL knowledge bases like rational entailment [17,4], relevant entailment [3], and cw mentailment [5]. There is some recent work on connections between defeasible DL semantics and OCF-based semantics [18], albeit only using propositional conditional logic.

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 different approaches deal specifically with facts are needed.

More advanced properties like syntax splitting [7] could be considered for the first-order case as well. Our results concerning the property (IRR) dealing with splitting of variables can be considered as first steps in this direction.