=Paper=
{{Paper
|id=Vol-3835/paper17
|storemode=property
|title=Ranking-based Defeasible Reasoning for Restricted First-Order Conditionals Applied to Description Logics
|pdfUrl=https://ceur-ws.org/Vol-3835/paper17.pdf
|volume=Vol-3835
|authors=Alexander Hahn,Gabriele Kern-Isberner,Thomas Meyer
|dblpUrl=https://dblp.org/rec/conf/nmr/HahnKM24
}}
==Ranking-based Defeasible Reasoning for Restricted First-Order Conditionals Applied to Description Logics==
https://ceur-ws.org/Vol-3835/paper17.pdf
Ranking-based Defeasible Reasoning for Restricted First-Order
Conditionals Applied to Description Logics
Alexander Hahn1 , Gabriele Kern-Isberner1 and Thomas Meyer2
1
Dept. of Computer Science, TU Dortmund University, Dortmund, Germany
2
University of Cape Town and CAIR, Cape Town, South Africa
Abstract
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 efficient 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.
Keywords
first-order logic, description logic, conditional reasoning, non-monotonic reasoning, ranking functions, c-representations
1. Introduction DL version of these postulates, lifting the KLM approach to
defeasible description logics.
Rules in the form of conditional statements โIf A then (usu- The goal of this paper is to propose first steps towards
ally) Bโ (sometimes equipped with a quantitative degree) an interpretation of defeasible subsumptions in description
are basic to human reasoning and also to logics in Artificial logics (DL) which is thoroughly based on conditionals and
Intelligence, and have been explored in the area of non- ranking functions. To this end, we lift the notion of inductive
monotonic reasoning since the 80s of the past century. They inference operators defined in [7] to first-order conditional
can be formalized as conditionals (๐ต|๐ด), allowing for a non- knowledge bases. Additionally, we adapt the KLM postu-
classical, three-valued interpretation of conditional state- lates from [4], as well as additional rationality postulates for
ments. Semantics for knowledge bases consisting of condi- the KLM approach from [3] and show that they are fulfilled
tionals are provided by epistemic states, often equipped with by our approach. Moreover, we illustrate the application
total preorders on possible worlds. Using total preorders of ranking-based first-order conditional semantics to a DL
ensures a high quality of nonmonotonic reasoning in terms example well-known from the literature and compare it to
of broadly accepted axioms. Ordinal conditional functions concept-wise multipreference (cwm ) semantics from [5].
[1, 2], often called ranking functions, can be considered an The rest of this paper is organized as follows. In Section 2,
implementation of such epistemic states that assign to each the basics on first-order conditionals and defeasible ๐โ๐
possible world ๐ an implausibility rank ๐
(๐) such that the are summarized. In Section 3, we describe inductive infer-
higher ๐
(๐), the less plausible ๐ is, and with the normal- ence operators for first-order (conditional) knowledge bases.
ization constraint that there are worlds that are maximally In Section 4, postulates from [4] and [8] are adapted and
plausible. evaluated for the use with first-order conditional logic. In
Similar to conditionals for propositional logic, statements Section 5, we compare the OCF-based semantics for first-
of the form โUsually, As are Bsโ encoded as defeasible con- order knowledge bases with cwm -semantics [5] for defeasi-
cept inclusions ๐ด โ โผ ๐ต, also called defeasible subsumptions, ble ๐โ๐ knowledge bases. In Section 6, we conclude this
are a natural extension for description logics (DLs) in or- paper with summarizing its main contributions and some
der to introduce conditional reasoning. Recently, different pointers for future work.
semantics for defeasible DL knowledge bases have been
proposed [3, 4, 5].
In order to compare and contrast different approaches to 2. Preliminaries
non-monotonic reasoning, as well as to provide unifying
frameworks, postulates are necessary. A popular approach This section recalls some formal basics on conditional first-
for non-monotonic reasoning, preferential models, is char- order logic and defeasible description logics. For a more
acterized by the so-called KLM postulates [6]. However, thorough introduction to description logics, we recommend
preferential models have been mostly considered for propo- [9].
sitional logics. Recently, Britz et al. [4] have proposed a
2.1. Conditionals in First-Order Logic
22nd International Workshop on Nonmonotonic Reasoning, November 2-4,
2024, Hanoi, Vietnam In this section, we recall relevant parts of the first-order
$ alexander.hahn@tu-dortmund.de (A. Hahn); conditional logic introduced in [10]. We start with syntac-
gabriele.kern-isberner@tu-dortmund.de (G. Kern-Isberner); tical details. Let ฮฃ = โจ๐ฮฃ , ๐ฮฃ โฉ be a first-order signature
tommie.meyer@uct.ac.za (T. Meyer)
0009-0008-6114-2594 (A. Hahn); 0000-0001-8689-5391
consisting of a finite set of predicates ๐ฮฃ and a finite set
(G. Kern-Isberner); 0000-0003-2204-6969 (T. Meyer) of constant symbols ๐ฮฃ but without function symbols of
ยฉ 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribu-
tion 4.0 International (CC BY 4.0).
arity > 0. An atom is a predicate of arity ๐ together with a
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
list of ๐ constants and/or variables. A literal is an atom or a Definition 1. An ordinal conditional function (OCF) ๐
on
negated atom. Formulas are built on atoms using conjunc- โฆฮฃ is a function ๐
: โฆฮฃ โ N โช {โ} with ๐
โ1 (0) ฬธ= โ
.
tion (โง), disjunction (โจ), negation (ยฌ), material implication
(โ), and quantification (โ, โ). We abbreviate conjunctions We can now make use of the possible world semantics
by juxtaposition and negations usually by overlining, e. g. to assign degrees of disbelief also to formulas and (non-
๐ด๐ต means ๐ด โง ๐ต and ๐ด means ยฌ๐ด. The symbol โค denotes quantified) conditionals. In the following, let ๐ด, ๐ต โ โฮฃ
an arbitrary tautology, and โฅ denotes an arbitrary contra- denote closed formulas, and let ๐ด(๐ฅ โ ) โ โฮฃ denote
โ ), ๐ต(๐ฅ
diction. A ground formula contains no variables. In a closed open formulas.
formula, all variables (if they occur) are bound by quanti- Definition 2 (๐
-ranks of closed formulas [10]). Let ๐
be
fiers, otherwise, the formula is open, and the variables that an OCF. The ๐
-ranks of closed formulas are defined (as in the
occur outside of the range of quantifiers are called free. If a propositional case) via
formula ๐ด contains free variables we also use the notation
๐ด(๐ฅ โ ) where โ๐ฅ = (๐ฅ1 , . . . , ๐ฅ๐ ) contains all free variables in ๐
(๐ด) = min ๐
(๐) and ๐
(๐ต | ๐ด) = ๐
(๐ด๐ต) โ ๐
(๐ด).
๐|=๐ด
๐ด. If โ๐ is a vector of the same length as โ๐ฅ then ๐ด(๐ โ) is meant
to denote the instantiation of ๐ด with โ. ๐ A formula โ๐ฅ โ ๐ด(๐ฅโ) By convention, ๐
(โฅ) = โ, because ranks are supposed
(โ๐ฅโ ๐ด(๐ฅโ )) is universal (existential) if ๐ด involves no further to reflect plausibility.
quantification. Let โฮฃ be the first-order language that al- The ranks of first-order formulas are coherently based on
lows no nested quantification, i.e., all quantified formulas the usage of OCFs for propositional formulas. These degrees
are either universal or existential formulas. โฮฃ contains of beliefs are used to specify when a formula from (โฮฃ |โฮฃ )
both open and closed formulas. is accepted by a ranking function ๐
(where acceptance is
โฮฃ is extended by a conditional operator โ|โ to a condi- denoted by |=). We will first consider the acceptance of
tional language (โฮฃ |โฮฃ ) containing first-order condition- closed (conditional) formulas.
als (๐ต|๐ด) with ๐ด, ๐ต โ โฮฃ . We write (๐ต(๐ฅ โ )) to
โ )|๐ด(๐ฅ
highlight free variables. Then we assume โ๐ฅ to mention Definition 3 (Acceptance of closed formulas [10]). Let ๐
all free variables occurring in ๐ด or ๐ต where the positions be an OCF. The acceptance relation between ๐
and closed
of the variables are suitably adapted. Note that ๐ด and ๐ต formulas from โฮฃ and (โฮฃ |โฮฃ ) is defined as follows:
usually will have free variables in common but may also โข ๐
|= ๐ด iff for all ๐ โ โฆ with ๐
(๐) = 0, it holds that
mention free variables which do not occur in the respec- ๐ |= ๐ด.
tive other formula. E.g., the conditional (๐น ๐๐๐๐๐๐ (๐ฆ, ๐ฅ) โง โข ๐
|= (๐ต | ๐ด) iff ๐
(๐ด๐ต) < ๐
(๐ด๐ต).
๐น ๐๐๐๐๐๐ (๐ฅ, ๐ง)|๐น ๐๐๐๐๐๐ (๐ฅ, ๐ฆ)) (if ๐ฅ is a friend of ๐ฆ then
usually ๐ฆ is also a friend of ๐ฅ and ๐ฅ has also a(nother) Acceptance of a sentence by a ranking function is the
friend ๐ง) would be represented by (๐ต(๐ฅ, ๐ฆ, ๐ง)|๐ด(๐ฅ, ๐ฆ, ๐ง)) same as in the propositional case for ground sentences, and
with ๐ต(๐ฅ, ๐ฆ, ๐ง) = ๐น ๐๐๐๐๐๐ (๐ฆ, ๐ฅ) โง ๐น ๐๐๐๐๐๐ (๐ฅ, ๐ง) and interprets the classical quantifiers in a straightforward way.
๐ด(๐ฅ, ๐ฆ, ๐ง) = ๐น ๐๐๐๐๐๐ (๐ฅ, ๐ฆ). Note that conditionals cannot The treatment of acceptance of open formulas is more
be nested, and that conditionals with tautological antecedent intricate, as such formulas will be used to express default
are identified with the corresponding non-conditional state- statements, like in โ๐ด is plausibleโ, or in โusually, if ๐ด holds,
ment, i.e., (๐ด|โค) โก ๐ด. Nevertheless, we distinguish be- then ๐ต also holdsโ.
tween such plausible statements (๐ด|โค) โก ๐ด and strict
Definition 4 (๐
-ranks of open formulas [10]). We define the
facts. Let โ๐ฮฃ = โฮฃ โช (โฮฃ |โฮฃ ) be the language contain-
ranks of open formulas and open conditionals by evaluating
ing both first-order formulas and conditionals as specified
most plausible instances:
above.
A first-order conditional knowledge base โ is a finite set ๐
(๐ด(๐ฅ
โ )) = min ๐
(๐ด(๐
โ ))
of conditional formulas. A first-order knowledge base ๐ฆโฌ = ๐โโ๐ด(๐ฅ
โ โ)
โจโฑ, โโฉ consists of a first-order conditional knowledge base ๐
(๐ต(๐ฅ
โ )|๐ด(๐ฅ
โ )) = min ๐
(๐ด(๐ โ )) โ ๐
(๐ด(๐
โ )๐ต(๐ โ )).
โ, together with a set โฑ of closed formulas from โฮฃ , called ๐โโ(๐ต(๐ฅ
โ โ )|๐ด(๐ฅ
โ ))
facts. The open formulas and conditionals in โ are meant Generalizing the notion of acceptance of a first-order for-
to represent defeasible plausible beliefs. mula or conditional is straightforward for closed formulas
Regarding semantics, we base our first-order conditional and conditionals. The basic idea here is that such (condi-
semantics on the Herbrand semantics. A possible world tional) open statements hold if there are individuals called
๐ is a subset of the Herbrand base โฮฃ , which contains all representatives that provide most convincing instances of
ground atoms of the first-order signature ฮฃ. Possible worlds the respective conditional.
can be concisely represented as complete conjunctions or
minterms, i.e. conjunctions of literals where every atom Definition 5 (representative [10]). Let ๐ = (๐ต(๐ฅ โ )|๐ด(๐ฅ โ ))
of โฮฃ appears either in positive or in negated form. The be an open conditional. We call โ๐ โ โ๐ a weak representa-
set of all possible worlds is denoted by โฆฮฃ . For an open tive of ๐ iff both of the following conditions are satisfied:
conditional ๐ = (๐ต(๐ฅ โ )|๐ด(๐ฅโ )), the set โ๐ denotes the set
of all vectors from the Herbrand universe that appear in ๐
(๐ด(๐
โ )๐ต(๐
โ )) = ๐
(๐ด(๐ฅ
โ )๐ต(๐ฅ
โ )) (1)
groundings of ๐, i.e. ๐
(๐ด(๐
โ )๐ต(๐
โ )) < ๐
(๐ด(๐
โ )๐ต(๐
โ )) (2)
โ(๐ต(๐ฅโ)|๐ด(๐ฅโ)) = {๐
โ โ ๐ฮฃ | |๐
โ | = |๐ฅ
โ |}. The set of weak representatives of ๐ is denoted by wRep(๐).
Further, โ๐ โ wRep(๐) is a (strong) representative of ๐ iff
Ordinal conditional functions [1], usually called rank- (๏ธ )๏ธ
โ )๐ต(๐
โ) . (3)
(๏ธ )๏ธ
ing functions, can be defined just as in the propositional ๐
๐ด(๐ โ )๐ต(๐
โ ) = min ๐
๐ด(๐
โ
๐โwRep(๐)
case. They associate degrees of (im)plausibility with possi-
ble worlds. The set of strong representatives of ๐ is denoted by Rep(๐).
(Strong) Representatives of a conditional are character- ๐
(๐ด(๐)๐ต(๐)) and ๐
(๐ด(๐)๐ต(๐)) = โ = ๐
(๐ด(๐)๐ต(๐)).
ized by being most general (1) and least exceptional (3). And Moreover, we must have ๐
|= (๐ต(๐ฅ)|๐ด(๐ฅ)) and ๐
|=
of course, their instantiation should be accepted by ๐
(2). (๐ต(๐)|๐ด(๐)). For the second closed conditional, this simply
Note that Rep(๐) ฬธ= โ
iff wRep(๐) ฬธ= โ
. Now we can base means ๐
(๐ด(๐)๐ต(๐)) < ๐
(๐ด(๐)๐ต(๐)), which clearly holds.
our definition of acceptance of open conditionals on the For the open conditional (๐ต(๐ฅ)|๐ด(๐ฅ)), we must apply Def-
notion of representatives as follows. inition 6. In particular, we must consider representatives of
this conditional. Since ๐
(๐ด(๐)๐ต(๐)) = 0 = ๐
(๐ด(๐)๐ต(๐)),
Definition 6 (acceptance of open conditionals [10]). Let ๐
we also have ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) = 0 = ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) by
be an OCF and ๐ = (๐ต(๐ฅ โ )|๐ด(๐ฅโ )). Then ๐
|= ๐ iff Rep(๐) ฬธ= Definition 4. Hence the more complicated option (B) of
โ
and either of the two following conditions holds. Definition 6 applies, and we must also consider represen-
(A) It holds that tatives of (๐ต(๐ฅ)|๐ด(๐ฅ)). Natural candidates of representa-
tives for (๐ต(๐ฅ)|๐ด(๐ฅ)) resp. (๐ต(๐ฅ)|๐ด(๐ฅ)) would be ๐ resp.
๐
(๐ด(๐ฅ
โ )๐ต(๐ฅ
โ )) < ๐
(๐ด(๐ฅ
โ )๐ต(๐ฅ
โ )). (4) ๐, but let us go into more details here. For both, we have
๐
(๐ด(๐)๐ต(๐)) = โ = ๐
(๐ด(๐)๐ต(๐)), so they are defi-
(B) ๐
(๐ด(๐ฅ โ )๐ต(๐ฅโ )) = ๐
(๐ด(๐ฅ โ )) and either
โ )๐ต(๐ฅ nitely weak representatives of the respective conditional. How-
Rep((๐ต(๐ฅ โ ))) = โ
, or for all ๐โ1 โ
โ )|๐ด(๐ฅ ever, for strong representatives, their rank of falsification
Rep((๐ต(๐ฅ โ ))), ๐โ2 โ Rep((๐ต(๐ฅ
โ )|๐ด(๐ฅ โ )|๐ด(๐ฅ
โ ))) must also be minimal among all weak representatives, ac-
it holds that cording to (3). For ๐ and ๐, this rank is maximal due to
๐
(๐ด(๐)๐ต(๐)) = โ = ๐
(๐ด(๐)๐ต(๐)), and at least prima fa-
๐
(๐ด(๐โ1 )๐ต(๐โ1 )) < ๐
(๐ด(๐โ2 )๐ต(๐โ2 )). (5)
cie, it is well imaginable that there are other constants ๐ โ ๐ฮฃ
We also have to ensure that strict knowledge (facts) are with lower, i.e., finite falsification ranks. So, at this point we
interpreted suitably by ranking functions. An OCF can stop our investigations here and will come back later to this
enforce factual knowledge by setting the ranks of all worlds example when we can use more detailed information about
which violate facts to infinity. the structure of ranking models of ๐ฆโฌ in the next section.
Definition 7 (enforcement of facts). Let ๐
be an OCF and let Now we have set up the formal framework of our ranking-
๐ด โ โฮฃ be a closed formula. Then we define that ๐
enforces based approach that we need for reasoning from first-order
the fact ๐ด, denoted by ๐
||โ ๐ด, iff ๐
(๐ด) = โ. knowledge bases. Before dealing with inference from such
knowledge bases in the next section, we briefly summarize
Observe the difference between acceptance and enforce- the syntactic basics of a description logics with defeasible
ment: while ๐
|= ๐ด is the same as ๐
|= (๐ด|โค) and subsumptions.
only means that ๐ด has to hold in the ๐
-minimal worlds,
๐
||โ ๐ด means that ๐ด holds in all feasible (i.e. finitely-
ranked) worlds. Nevertheless, enforcement is downward- 2.2. Defeasible ๐โ๐
compatible to plausible acceptance, as the next proposition Let ๐๐ถ be a set of atomic concept names, ๐๐
be a set of
shows. role names and ๐๐ผ be a set of individual names. The set of
๐โ๐-concepts is defined by the rule
Proposition 1. Let ๐
be an OCF and let ๐ด โ โฮฃ be a closed
formula. ๐
||โ ๐ด implies ๐
|= ๐ด. ๐ถ ::= ๐ด|โค|โฅ|ยฌ๐ถ|๐ถ โ ๐ถ|๐ถ โ ๐ถ|โ๐.๐ถ|โ๐.๐ถ ,
Proof. If ๐
||โ ๐ด, then ๐ |= ๐ด for all ๐ โ โฆ such that
where ๐ด โ ๐๐ถ and ๐ โ ๐๐
.
๐
(๐) < โ. This implies particularly that ๐ |= ๐ด for all
An ๐โ๐-interpretation is a tuple ๐ผ = โจโโ , ยทโ โฉ, where
๐ โ โฆ such that ๐
(๐) = 0, i.e., ๐
|= ๐ด.
โ is a domain and ยทโ is an interpretation function which
โ
With the necessary notation for the treatment of both un- maps ๐ด โ ๐๐ถ , ๐ โ ๐๐
, ๐ โ ๐๐ผ to ๐ดโ โ โโ , ๐โ โ
certain and factual knowledge in place, we are now ready to โโ ร โโ , ๐โ โ โโ , respectively. For complex concepts:
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 rank-
ing models in the following example. Classical (strict) subsumptions ๐ถ โ ๐ท (where ๐ถ, ๐ท are
Example 1. We consider a signature ฮฃ = โจ๐ฮฃ , ๐ฮฃ โฉ con- concepts) hold in an interpretation ๐ผ (short: ๐ผ |= ๐ถ โ ๐ท)
sisting of two unary predicates ๐ฮฃ = {๐ด, ๐ต} and at least iff ๐ถ โ โ ๐ทโ . Assertions of the form ๐ถ(๐) or ๐(๐, ๐) (where
two constants {๐, ๐} โ ๐ฮฃ . Let the knowledge base ๐ฆโฌ = ๐ถ is a concept, ๐ is a role and ๐, ๐ are individuals) hold if
โจโฑ, โโฉ be specified by โฑ = {๐ด(๐)๐ต(๐), ๐ด(๐)๐ต(๐)} and ๐ โ ๐ถ โ or (๐, ๐) โ ๐โ , respectively.
โ = {(๐ต(๐ฅ)|๐ด(๐ฅ)), (๐ต(๐)|๐ด(๐))}. Any model ๐
of ๐ฆโฌ Beyond classical logics and similar to first-order condi-
must assign rank โ to all ๐ ฬธ|= โฑ, i.e., can have finite ranks tionals, defeasible subsumptions ๐ถ โโผ ๐ท encode information
only for worlds ๐ satisfying ๐ |= ๐ด(๐)๐ต(๐)๐ด(๐)๐ต(๐). This of the form โUsually, instances of ๐ถ are instances of ๐ทโ or
implies, also by Proposition 1, that ๐
(๐ด(๐)๐ต(๐)) = 0 = โTypical ๐ถs are ๐ทsโ.
A defeasible (๐โ๐) knowledge base ๐ฆโฌ = โจ๐ฏ , ๐, ๐โฉ 3.2. Inductive FO-Inference Based on
consists of a TBox ๐ฏ (containing strict subsumptions), a c-Representations
DBox ๐ (containing defeasible subsumptions) and an ABox
๐ (containing assertions). c-Representations, originally defined for the propositional
A popular approach to provide semantics for defeasible setting [11, 12], are a special kind of ranking models which
subsumptions (e.g. used in [4, 5]) is to introduce some order- assign ranks to possible worlds in a regular way by adhering
ing over the domain elements โโ and require the minimal to the conditional structures of knowledge bases. A (simpli-
instances of ๐ถ (with respect to said ordering) to be instances fied) version of c-representations for first-order conditinal
of ๐ท in order for ๐ถ โ knowledge bases was proposed in [10].
โผ ๐ท to hold.
In this paper, we understand defeasible subsumptions as Definition 9 (c-Representation [10]). Let ๐ฆโฌ = โจโฑ, โโฉ
open conditionals and interpret them via ranking functions. with โ = {(๐ต1 (๐ฅ โ 1 )|๐ด1 (๐ฅ
โ 1 )), . . . , (๐ต๐ (๐ฅโ ๐ )|๐ด๐ (๐ฅ
โ ๐ ))} be
a first-order knowledge base. An OCF ๐
is a c-representation
3. Reasoning from First-Order of ๐ฆโฌ if ๐
(๐) = โ for all ๐ ฬธ|= โฑ and ๐
|= ๐ for every
๐ โ โ, and for all ๐ |= โฑ, ๐
(๐) is of the form
Knowledge Bases โ๏ธ
๐
(๐) = ๐
0 + ๐๐ (๐)๐๐ , (7)
In this section, we consider inference relations induced by 1โค๐โค๐
first-order (FO) knowledge bases, similar to the ones con-
sidered for the propositional case in [7]. where ๐๐ (๐) = #{๐ ๐๐
โ ๐ โ โ | ๐๐ = (๐ต๐ (๐ฅ โ ๐ ) | ๐ด๐ (๐ฅ
โ ๐ )) โ
โ, ๐ |= ๐ด๐ (๐ โ ๐ )๐ต๐ (๐
โ ๐ )} is the number of possible grounding
3.1. Inductive FO-Inference Relations vectors that appear in falsifications of ๐๐ in ๐, and ๐
0 , ๐๐ โ N
with ๐๐ โฅ 0 are suitably chosen to ensure that ๐
is an OCF
Let ๐ฆโฌ = โจโฑ, โโฉ be a first-order knowledge base. We and ๐
|= โ.
are interested in defeasible inferences that we can draw
from ๐ฆโฌ, i.e., we consider (nonmonotonic) inferences of The value ๐
0 is a normalizing factor for ensuring that
the form ๐ฆโฌ |โผ ๐ with ๐ โ โ๐ฮฃ being a first-order formula min๐โฮฉ ๐
(๐) = 0, and the values ๐๐ are called impact fac-
or conditional. More precisely, we study inductive inference tors. Observe that the value of ๐๐ does not depend on the
relations |โผโ โ๐ฮฃ ร โ๐ฮฃ similar to the ones presented in [7]. specific world ๐ under consideration, but on the other condi-
Two fundamental postulates for such inference relations pre- tionals in โ, and can be determined via a set of inequalities
supposed in [7] are that formulas from the knowledge base between the different ๐๐ . Therefore, c-representations exist
can be inferred (this is called Direct Inference (DI)), and that iff this system of inequalities is solvable. This allows for
without conditionals in the knowledge base, conditionals deriving sufficient conditions for the satisfiability of knowl-
can be inferred only trivially (Trivial Vacuity (TV)). edge bases in terms of solutions of inequalities. However, in
the first-order case, this system of inequalities is much more
(DI) ๐ โ โฑ โช โ implies โจโฑ, โโฉ |โผ ๐. complex than in the propositional case because conditionals
can be both verified and falsified by different constants in
(TV) โจโฑ, โ
โฉ |โผ (๐ต(๐ฅ โ )|๐ด(๐ฅโ )) only if there is a constant
the same world, and due to the interactions between facts
vector โ๐ such that โฑ |= ๐ด(๐ โ ) โ ๐ต(๐โ ).
and conditionals. Therefore, it is hardly possible to give a
Note that (DI) is a bit basic concerning the treatments of generic representation of these inequalities for first-order
facts. Actually, we would expect facts from โฑ to be enforced. knowledge bases. We illustrate c-representations by contin-
We will see that our approach can guarantee this. uing our Example 1.
One natural way to construct an inductive inference re-
Example 2 (Example 1 contโd). We consider the knowledge
lation is to choose a model ๐
for each knowledge base and
base ๐ฆโฌ = โจโฑ, โโฉ with โฑ = {๐ด(๐)๐ต(๐), ๐ด(๐)๐ต(๐)} and
consider the inferences induced by ๐
via
โ = {๐1 = (๐ต(๐ฅ)|๐ด(๐ฅ)), ๐2 = (๐ต(๐)|๐ด(๐))} from Exam-
โจโฑ, โโฉ |โ๐
๐ iff ๐
|= ๐, (6) A c-representation ๐
of ๐ฆโฌ has the form ๐
(๐) =
ple 1. โ๏ธ
๐
0 + 1โค๐โค2 ๐๐ (๐)๐๐ for ๐ |= ๐ด(๐)๐ต(๐)๐ด(๐)๐ต(๐),
where ๐ โ โ๐ฮฃ , and โจโฑ, โโฉ |โ๐
๐ means that ๐ can be and ๐
(๐) = โ for ๐ ฬธ|= ๐ด(๐)๐ต(๐)๐ด(๐)๐ต(๐). Since
inferred from โจโฑ, โโฉ via its ranking model ๐
. ๐ด(๐)๐ต(๐) โ โฑ , conditional ๐2 cannot be falsified by finitely-
However in general, it is not easy to decide on the ex- ranked worlds, so the impact factor ๐2 is ineffective, and we
istence of models of a first-order knowledge base, i.e., on just have
the satisfiability of such knowledge bases in our ranking- ๐
(๐) = ๐
0 + ๐1 (๐)๐1 (8)
based semantics, as we saw in Example 1. In particular,
for ๐ |= ๐ด(๐)๐ต(๐)๐ด(๐)๐ต(๐). For any such ๐, ๐
(๐) โฅ
knowledge given by facts in โฑ may interact with plausi-
๐
0 + ๐1 because of the falsification of ๐1 by ๐, and if no
ble beliefs specified by conditionals in โ. For example, if
other constant falsifies ๐1 , we obtain ๐
(๐) = ๐
0 + ๐1 as the
โฑ |= โ๐ฅ โ ) โ ๐ต(๐ฅ
โ .๐ด(๐ฅ โ ), the conditional (๐ต(๐ฅ โ )) โ โ
โ )|๐ด(๐ฅ
minimum rank which must be 0. This yields ๐
0 = โ๐1 .
cannot be accepted by a ranking function ๐
. In this case,
The impact factor ๐1 โฅ 0 has to be chosen in such a
the ๐ฆโฌ = โจโฑ, โโฉ would be not satisfiable.
way that ๐1 is accepted by ๐
. As for any model of ๐ฆโฌ,
In the next subsection, we recall a class of ranking models
it holds that 0 = ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) = ๐
(๐ด(๐)๐ต(๐)) <
of first-order knowledge bases that allow for more trans-
๐
(๐ด(๐)๐ต(๐)) = โ and 0 = ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) =
parent investigations into the satisfiability of first-order
๐
(๐ด(๐)๐ต(๐)) < ๐
(๐ด(๐)๐ต(๐)) = โ, so ๐ โ wRep(๐1 )
knowledge bases and usually provide a basis for quite well-
and ๐ โ wRep((๐ต(๐ฅ)|๐ด(๐ฅ))), and Definition 6 (B) applies.
behaved inductive inference.
Consider any constant ๐ ฬธโ {๐, ๐}. Since ๐ |= ๐ด(๐)๐ต(๐)
can be chosen in such a way that ๐ |= ๐ด(๐) for any fur-
ther constant ๐ ฬธโ {๐, ๐, ๐}, we obtain ๐
(๐ด(๐)๐ต(๐)) =
๐
(๐ด(๐)๐ต(๐)๐ด(๐)๐ต(๐)๐ด(๐)๐ต(๐)) = 0 = ๐
(๐ด(๐ฅ)๐ต(๐ฅ)), Proof. Any c-representation ๐
of โจโฑ, โ
โฉ has the form (7)
and analogously, ๐
(๐ด(๐)๐ต(๐)) = ๐1 . for ๐ |= โฑ and satisfies ๐
(๐) = โ for ๐ ฬธ|= โฑ. Since
Consider the case ๐1 = 0. Then we would have there are no conditionals in the rule base, we simply have
๐
(๐ด(๐)๐ต(๐)) = 0 = ๐
(๐ด(๐)๐ต(๐)), so ๐ ฬธโ wRep(๐1 ) and ๐
(๐) = ๐
0 for ๐ |= โฑ, hence the normalization constant
๐ ฬธโ wRep((๐ต(๐ฅ)|๐ด(๐ฅ))). Hence wRep(๐1 ) = {๐} and must satisfy ๐
0 = 0. If ๐
|= (๐ต(๐ฅ โ )) holds, there
โ )|๐ด(๐ฅ
wRep((๐ต(๐ฅ)|๐ด(๐ฅ))) = {๐}, and therefore Rep(๐1 ) = {๐} must be weak representative for (๐ต(๐ฅ โ )), hence there
โ )|๐ด(๐ฅ
and Rep((๐ต(๐ฅ)|๐ด(๐ฅ))) = {๐}. So finally, we have to check must be a constant vector โ๐ such that ๐
(๐ด(๐ โ )๐ต(๐ โ )) <
the last condition (5) from Definition 6 (B) for ๐ and ๐, and ๐
(๐ด(๐โ )๐ต(๐โ )). This is possible only if ๐
(๐ด(๐ โ )๐ต(๐โ )) = 0
find that ๐
(๐ด(๐)๐ต(๐)) = โ = ๐
(๐ด(๐)๐ต(๐)), hence (5) is and ๐
(๐ด(๐ โ )๐ต(๐ โ )) = โ, since ๐
has only these two ranks.
violated. Therefore, ๐1 = 0 cannot ensure the acceptance of This implies ๐
(๐) = โ for all ๐ |= ๐ด(๐ โ )๐ต(๐โ ), i.e., for
๐1 . all ๐ |= ๐ด(๐ โ )๐ต(๐ โ ), ๐ ฬธ|= โฑ. Via contraposition, โฑ |=
On the other hand, for any (finite) ๐1 > 0 and for any ยฌ(๐ด(๐ โ )) โก ๐ด(๐
โ )๐ต(๐ โ ) โ ๐ต(๐โ ). This was to be shown.
constant ๐ ฬธโ {๐, ๐}, we then calculate ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) =
๐
(๐ด(๐)๐ต(๐)) = 0 < ๐1 = ๐
(๐ด(๐)๐ต(๐)). Hence each
such ๐ is a weak representative satisfying ๐
(๐ด(๐)๐ต(๐)) = 3.3. c-Representations for Defeasible ๐โ๐
๐1 < โ = ๐
(๐ด(๐)๐ต(๐)). So in this case, ๐ cannot be
a strong representative of ๐1 , and we obtain Rep(๐1 ) = The basic idea of our approach is to understand defeasi-
๐ฮฃ โ {๐, ๐}. Obviously, any ๐ โ ๐ฮฃ โ {๐} cannot be a ble subsumptions as open first-order conditionals. This
(weak) representative of (๐ต(๐ฅ)|๐ด(๐ฅ)), and therefore we have allows for considering defeasible ๐โ๐ knowledge bases
wRep((๐ต(๐ฅ)|๐ด(๐ฅ))) = Rep((๐ต(๐ฅ)|๐ด(๐ฅ))) = {๐}. Fi- as first-order (conditional) knowledge bases and make use
nally, since for any ๐ โ Rep(๐1 ), ๐
(๐ด(๐)๐ต(๐)) = ๐1 < of ranking functions to provide semantics for defeasible
โ = ๐
(๐ด(๐)๐ต(๐)), also (5) can be satisfied. Therefore, any ๐โ๐ knowledge bases. Even more, we are then able to
finite ๐1 > 0 in (8) yields a c-representation of ๐ฆโฌ. reason inductively from defeasible ๐โ๐ knowledge bases
via c-representations. We will investigate both the general
Nevertheless, if c-representations of a first-order knowl- ranking-based semantics of defeasible ๐โ๐ reasoning and
edge base exist at all, then there are usually infinitely many its more sophisticated version based on c-representations
of them. E.g., in Example 2 above, infinitely many ๐1 > 0 in the following to show the potential of this semantics for
define infinitely many c-representations. Therefore, some description logics. Since this paper only takes first steps in
kind of selection procedure is needed in order to formal- this direction, we want to focus on main techniques of our
ize which c-representations an inductive inference operator approach to not burden the general line of thought with
should choose. too many technical details. Therefore, the following three
prerequisites apply for the rest of this paper:
Definition 10 (selection strategy ๐). A selection strategy
(for c-representations) is a function ๐ assigning to each first- 1. Both components โฑ and โ of first-order conditional
order conditional knowledge base ๐ฆโฌ = โจโฑ, โโฉ an impact knowledge bases do not mention any constant. For
vector โ๐ โ N|โ| defeasible ๐โ๐ knowledge bases, this means that
๐ : ๐ฆโฌ โฆโ โ๐ the ABox is empty.
such that the OCF obtained by using โ๐ as impacts in Defini- 2. The ranking-based semantics for open first-order
tion 9 is a c-representation of โ. conditionals is restricted to option (A) of Definition 6,
i.e., in the following, ๐
|= ๐ = (๐ต(๐ฅ โ )) iff
โ )|๐ด(๐ฅ
With the help of selection strategies, we are now able to Rep(๐) ฬธ= โ
and
define inductive inference operators specifically for infer-
ences obtained from c-representations of a given knowledge ๐
(๐ด(๐ฅ
โ )๐ต(๐ฅ
โ )) < ๐
(๐ด(๐ฅ โ )).
โ )๐ต(๐ฅ
base.
3. Moreover, we also presuppose that there are
c-rep
Definition 11 (C๐ ). An inductive inference operator for โenoughโ constants available in ๐ฮฃ to ensure that
c-representations with selection strategy ๐ is a function for every conditional there is some constant vector
that can serve as a strong representative, and that
Cc-rep
๐ : ๐ฆโฌ โฆโ ๐
๐(๐ฆโฌ) non-acceptance of conditionals is not due to |๐ฮฃ |
being too small. E.g., one may assume that for every
where ๐ is a selection strategy for c -representations. As before, conditional ๐ = (๐ต(๐ฅ โ )|๐ด(๐ฅโ )) there exists a special
a corresponding inductive inference relation can be obtained constant vector โ๐๐ with โ๐๐ โ โ๐ the components of
via Equation (6). which do not occur anywhere else in the knowledge
It can easily be checked that the postulates (DI) and base.
(TV) are satisfied by all inference relations induced from The first prerequisite is not uncommon for description logics
c-representations. (DI) is ensured by the fact that each c- and is an intuitive justification for the second prerequisite.
representation is a model of the knowledge base, and (TV) Although the ranking-based conditional semantics for first-
is immediate from Equation (7), as the following lemma order knowledge bases from Section 2.1 is able very well
shows. to deal with information about individuals and even allows
for having a defeasible ABox, as Examples 1 and 2 illustrate,
Lemma 1. Let โจโฑ, โ
โฉ be a first-order knowledge base, let
these examples also show how intricate investigations can
๐
be a c-representation of โจโฑ, โ
โฉ. Then for any conditional
be when option (B) of Definition 6 must be applied. This
(๐ต(๐ฅโ )|๐ด(๐ฅโ )), ๐
|= (๐ต(๐ฅ
โ )|๐ด(๐ฅ โ )) only if there is a constant
option is typically relevant only in cases where knowledge
vector โ๐ such that โฑ |= ๐ด(๐ โ ) โ ๐ต(๐ โ ).
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 (CMโ ) If โ๐.๐ด โ
โผ ๐ถ and โ๐.๐ด โผ โ๐.๐ต, then โ๐.(๐ดโ๐ต) โผ
โ โ
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 (CMโ ) If โ๐.๐ด โ
โผ ๐ถ and โ๐.๐ด โผ โ๐.๐ต, then โ๐.(๐ดโ๐ต) โผ
โ โ
of a conditional, as the following proposition shows. ๐ถ.
(RMโ ) If โ๐.๐ด โ
โผ ๐ถ and โ๐.๐ด โผ โ๐.ยฌ๐ต, then โ๐.(๐ด โ
โ
โงธ๏ธ
Proposition 2. Let ๐
be an OCF and let (๐ต(๐ฅโ )|๐ด(๐ฅ
โ )) be an
open conditional. If ๐
(๐ด(๐ฅ โ )๐ต(๐ฅ
โ )) < ๐
(๐ด(๐ฅ
โ )๐ต(๐ฅ
โ )) holds, ๐ต) โโผ ๐ถ.
then ๐
|= (๐ต(๐ฅ
โ )|๐ด(๐ฅ โ )). (RMโ ) If โ๐.๐ด โ
โผ ๐ถ and โ๐.๐ด โผ โ๐.ยฌ๐ต, then โ๐.(๐ด โ
โ
โงธ๏ธ
๐ต) โโผ ๐ถ.
Proof. We have to show that (4) ensures that the con-
ditional has strong representatives. Let โ๐ be such that We now present a version of the KLM-style postulates
๐
(๐ด(๐ฅ โ )๐ต(๐ฅ โ )) = ๐
(๐ด(๐ โ )๐ต(๐ โ )). Since ๐
(๐ด(๐ฅ โ )๐ต(๐ฅ
โ )) < using first-order conditionals. Since concepts and roles in
๐
(๐ด(๐ฅ โ )๐ต(๐ฅ โ )) โค ๐
(๐ด(๐ โ )๐ต(๐ โ )), we have ๐
(๐ด(๐ โ )๐ต(๐
โ )) < description logics are unary and binary predicates, respec-
๐
(๐ด(๐ โ )๐ต(๐ โ )). Therefore, โ๐ is at least a weak representative tively, we use single variables ๐ฅ, ๐ฆ instead of vectors โ๐ฅ here
of (๐ต(๐ฅ โ )|๐ด(๐ฅ โ )), which means that Rep((๐ต(๐ฅ โ ))) ฬธ=
โ )|๐ด(๐ฅ in order to simplify notation. However, none of the proofs
โ
. Because (A) holds by definition, it follows that ๐
|= 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
To motivate prerequisite (3), consider Example 2 again. If
symbol, i.e. ๐ฮฃ ฬธ= โ
.
๐ฮฃ would consist only of the constants ๐ and ๐, conditional
๐1 could not be accepted for the only reason that neither ๐ (Ref) ๐
|= (๐ด(๐ฅ)|๐ด(๐ฅ)).
nor ๐ can be a strong representative for ๐1 (please see the
argumentation for case ๐1 = 0 in the example). At least a (LLE) If ๐
||โ โ๐ฅ.[๐ด(๐ฅ) โ ๐ต(๐ฅ)] and ๐
|= (๐ถ(๐ฅ)|๐ด(๐ฅ)),
third constant ๐ ฬธโ {๐, ๐} is needed to ensure the acceptance then ๐
|= (๐ถ(๐ฅ)|๐ต(๐ฅ)).
of ๐1 .
(RW) If ๐
||โ โ๐ฅ.[๐ต(๐ฅ) โ ๐ถ(๐ฅ)] and ๐
|= (๐ต(๐ฅ)|๐ด(๐ฅ)),
However, even under all three prerequisites from above,
then ๐
|= (๐ถ(๐ฅ)|๐ด(๐ฅ)).
it is hard to make general statements about the consistency
of a first-order knowledge base, or the system of inequalities (And) If ๐
|= (๐ต(๐ฅ)|๐ด(๐ฅ)), (๐ถ(๐ฅ)|๐ด(๐ฅ)), then ๐
|=
that impact factors in c-representations have to solve. The (๐ต(๐ฅ) โง ๐ถ(๐ฅ)|๐ด(๐ฅ)).
papers [13, 14] present a sufficient condition for the consis-
tency of a first-order knowledge base by lifting the concept (Or) If ๐
|= (๐ถ(๐ฅ)|๐ด(๐ฅ)), (๐ถ(๐ฅ)|๐ต(๐ฅ)), then ๐
|=
of a tolerance partition (on which the propositional system (๐ถ(๐ฅ)|๐ด(๐ฅ) โจ ๐ต(๐ฅ)).
Z [15] is based) to the first-order case. However, it is still an
(CM) If ๐
|= (๐ต(๐ฅ)|๐ด(๐ฅ)), (๐ถ(๐ฅ)|๐ด(๐ฅ)), then ๐
|=
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 (RM) If ๐
|= (๐ถ(๐ฅ)|๐ด(๐ฅ)) and ๐
ฬธ|= (๐ต(๐ฅ)|๐ด(๐ฅ)), then
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 rea- The translation of the quantified postulates using first-order
soning based on c-representations for defeasible description conditionals is given below.
logics in the following.
(CMโ ) If ๐
|= (๐ถ(๐ฅ) | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โง ๐ด(๐ฆ)]) and ๐
|=
(โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ต(๐ฆ)] | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โง ๐ด(๐ฆ)]), then
4. KLM-style Postulates and Beyond ๐
|= (๐ถ(๐ฅ)|โ๐ฆ.๐
(๐ฅ, ๐ฆ) โง ๐ด(๐ฆ) โง ๐ต(๐ฆ)).
In [4], the well-known KLM postulates for non-monotonic (CMโ ) If ๐
|= (๐ถ(๐ฅ) | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ด(๐ฆ)]) and ๐
|=
reasoning were translated for use with defeasible description (โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ต(๐ฆ)] | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ด(๐ฆ)]),
logics, and also the postulate of rational monotonicity was then ๐
|= (๐ถ(๐ฅ) | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ (๐ด(๐ฆ) โง ๐ต(๐ฆ))]).
considered. Let ๐ด, ๐ต, ๐ถ be concepts. (RMโ ) If ๐
|= (๐ถ(๐ฅ) | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โง ๐ด(๐ฆ)]) and ๐
ฬธ|=
(Ref) ๐ด โ (โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ต(๐ฆ)] | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โง ๐ด(๐ฆ)]), then
โผ ๐ด.
๐
|= (๐ถ(๐ฅ) | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โง ๐ด(๐ฆ) โง ๐ต(๐ฆ)]).
(LLE) If ๐ด โก ๐ต and ๐ด โ
โผ ๐ถ, then ๐ต โผ ๐ถ.
โ
(RMโ ) If ๐
|= (๐ถ(๐ฅ) | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ด(๐ฆ)]) and ๐
ฬธ|=
(RW) If ๐ด โ
โผ ๐ต and ๐ต โ ๐ถ, then ๐ด โผ ๐ถ.
โ (โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ต(๐ฆ)] | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ด(๐ฆ)]),
then ๐
|= (๐ถ(๐ฅ) | โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ (๐ด(๐ฆ) โง ๐ต(๐ฆ))]).
(And) If ๐ด โ
โผ ๐ต and ๐ด โผ ๐ถ, then ๐ด โผ (๐ต โ ๐ถ).
โ โ
Proposition 3. All of the postulates given above hold for
โผ ๐ถ and ๐ต โผ ๐ถ, then (๐ด โ ๐ต) โผ ๐ถ.
(Or) If ๐ด โ โ โ
every OCF ๐
.
(CM) If ๐ด โ
โผ ๐ต and ๐ด โผ ๐ถ, then (๐ด โ ๐ต) โผ ๐ถ.
โ โ
Proof. In the following proofs for the individual postulates,
(RM) If ๐ด โ we implicitly use Proposition 2 and prove the acceptance
โผ ๐ถ and ๐ด โผ ยฌ๐ต, then (๐ด โ ๐ต) โผ ๐ถ.
โ โ
โงธ๏ธ
of desired conditionals by proving that their verification is
Moreover, in [4], quantified versions of (CM) and (RM) more plausible than their falsification.
which are adapted to the specific form of DL concepts have (Ref): This postulate is straightforward as ๐
(๐ด(๐ฅ)) <
been presented. ๐
(โฅ) by definition.
(LLE): Let ๐ด(๐ฅ) be equivalent to ๐ต(๐ฅ) for all ๐ฅ in all Postulate (CLA) claims that each ranking model of a con-
feasible possible worlds, and let ๐
|= (๐ถ(๐ฅ)|๐ด(๐ฅ)). Be- ditional knowledge base respects all classical consequences
cause of the equivalence of ๐ด(๐ฅ) and ๐ต(๐ฅ), we have of the facts. Postulate (SUB) reveals a compatibility between
๐
(๐ด(๐)๐ถ(๐)) = ๐
(๐ต(๐)๐ถ(๐)) and ๐
(๐ด(๐)๐ถ(๐)) = a conditional and its counterpart as material implication.
๐
(๐ต(๐)๐ถ(๐)) for every ๐. Therefore, if ๐ is a represen- But note that this counterpart is only plausible.
tative of (๐ถ(๐ฅ)|๐ด(๐ฅ)), it has to be a representative of The next proposition shows that both these postulates
(๐ถ(๐ฅ)|๐ต(๐ฅ)) as well. Hence, if condition (A) or (B) from are also satisfied by our approach.
Definition 6 holds for (๐ถ(๐ฅ)|๐ด(๐ฅ)), the respective condi-
tion has to hold for (๐ถ(๐ฅ)|๐ต(๐ฅ)), too. Proposition 4. Let ๐
be an OCF. If ๐
is a model of โจโฑ, โโฉ
(RW): We have ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) < ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) and then ๐
||โ ๐ผ for all ๐ผ โ โฮฃ with โฑ |= ๐ผ. If ๐
is a model of
the fact โ๐ฅ.[๐ต(๐ฅ) โ ๐ถ(๐ฅ)]. Therefore, we have โจโ
, {(๐ต(๐ฅ โ ))}โฉ then ๐
|= (๐ด(๐ฅ
โ )|๐ด(๐ฅ โ ) โ ๐ต(๐ฅโ )|โค).
๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) โค ๐
(๐ด(๐ฅ)๐ต(๐ฅ)๐ถ(๐ฅ)) = ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) and
Proof. Let ๐
be a model of โจโฑ, โโฉ, let ๐ผ โ โฮฃ with
๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) = ๐
(๐ด(๐ฅ)๐ต(๐ฅ)๐ถ(๐ฅ)) โฅ ๐
(๐ด(๐ฅ)๐ต(๐ฅ)).
โฑ |= ๐ผ. Then ๐
(๐) = โ for all ๐ ฬธ|= โฑ and hence
Hence, ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) < ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)).
also for all ๐ ฬธ|= ๐ด. Therefore, ๐
||โ ๐ผ. If ๐
is a
(And): Because of ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) < ๐
(๐ด(๐ฅ)๐ต(๐ฅ))
model of โจโ
, {(๐ต(๐ฅ โ ))}โฉ then ๐
|= (๐ต(๐ฅ
โ )|๐ด(๐ฅ โ )|๐ด(๐ฅโ )),
and ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) < ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)), the minimal worlds
i.e., ๐
(๐ด(๐ฅ
โ )๐ต(๐ฅ
โ )) < ๐
(๐ด(๐ฅ โ )). Since ๐
(๐ด(๐ฅ
โ )๐ต(๐ฅ โ) โ
๐ in ๐
with ๐ |= ๐ด(๐) for some ๐ have to sat-
๐ต(๐ฅ โ )) = ๐
(ยฌ๐ด(๐ฅ โ ) โจ ๐ต(๐ฅโ )) โค ๐
(๐ด(๐ฅ โ )), the state-
โ )๐ต(๐ฅ
isfy both ๐ต(๐) and ๐ถ(๐) as well. Therefore, we
ment follows.
can conclude that ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) = ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) =
๐
(๐ด(๐ฅ)๐ต(๐ฅ)๐ถ(๐ฅ)). It follows that ๐
(๐ด(๐ฅ)๐ต(๐ฅ)๐ถ(๐ฅ)) < The next postulate deals with obviously irrelevant vari-
min{๐ด(๐ฅ)๐ต(๐ฅ), ๐ด(๐ฅ)๐ถ(๐ฅ)} = ๐
(๐ด(๐ฅ)(๐ต(๐ฅ) โจ ๐ถ(๐ฅ))). ables in an open conditional, i.e., variables that do not occur
(Or): It holds that ๐
(๐ด(๐ฅ)๐ถ(๐ฅ) โจ ๐ต(๐ฅ)๐ถ(๐ฅ)) = in both the antecedent and the consequent of the conditional.
min{๐
(๐ด(๐ฅ)๐ถ(๐ฅ)), ๐
(๐ต(๐ฅ)๐ถ(๐ฅ))} < It adapts the postulate (IRR) from [8].
min{๐
(๐ด(๐ฅ)๐ถ(๐ฅ)), ๐
(๐ต(๐ฅ)๐ถ(๐ฅ))} = ๐
(๐ด(๐ฅ)๐ถ(๐ฅ) โจ
๐ต(๐ฅ)๐ถ(๐ฅ)). (IRR) Let โ๐ฅ, โ๐ฆ , โ๐ง mention variables from pairwise dis-
(CM): Because of ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) < ๐
(๐ด(๐ฅ)๐ต(๐ฅ)) and joint sets. Then โจโ
, {(๐ต(๐ฅ โ , โ๐ง ))}โฉ |โผ
โ , โ๐ฆ )|๐ด(๐ฅ
๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) < ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)), the minimal worlds ๐ (๐ต(๐ฅ โ , โ๐)|๐ด(๐ฅโ , โ๐)) for all proper groundings โ๐, โ๐ of
in ๐
with ๐ |= ๐ด(๐) for some ๐ have to satisfy both โ๐ง resp. โ๐ฆ in ๐ด resp. ๐ต.
๐ต(๐) and ๐ถ(๐) as well. Therefore, we can conclude that
๐
(๐ด(๐ฅ)๐ต(๐ฅ)) = ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) = ๐
(๐ด(๐ฅ)๐ต(๐ฅ)๐ถ(๐ฅ)). This postulate does not hold in general for our ranking
It follows that ๐
(๐ด(๐ฅ)๐ต(๐ฅ)๐ถ(๐ฅ)) < ๐
(๐ด(๐ฅ)๐ถ(๐ฅ)) โค semantics but we can show that it holds for ranking models
๐
(๐ด(๐ฅ)๐ต(๐ฅ)๐ถ(๐ฅ)). which are c-representations.
(CMโ ): Let ๐ be a minimal world in ๐
such that ๐ฅ, ๐ฆ ex-
ist with ๐ |= ๐
(๐ฅ, ๐ฆ)๐ด(๐ฆ). Since (A) holds, for every ๐ โฒ Proposition 5. Let โ๐ฅ, โ๐ฆ , โ๐ง mention variables from pairwise
with ๐
(๐ โฒ ) = ๐
(๐) we have ๐ โฒ |= โ๐ฅ.โ๐ฆ.[๐
(๐ฅ, ๐ฆ)๐ด(๐ฆ) โ disjoint sets, and let ๐ฆโฌ = โจโ
, {(๐ต(๐ฅ โ , โ๐ฆ )|๐ด(๐ฅ
โ , โ๐ง ))}โฉ. Let
๐ถ(๐ฅ)๐ต(๐ฆ)], and for every ๐ โฒโฒ with ๐
(๐ โฒโฒ ) < ๐
(๐) ๐
= ๐
๐(๐ฆโฌ) be a strategic c-representation of ๐ฆโฌ. Then
we have ๐ โฒโฒ |= โ๐ฅ.โ๐ฆ.๐
(๐ฅ, ๐ฆ) โจ ๐ด(๐ฆ). Therefore, ๐
|= (๐ต(๐ฅ โ , โ๐)|๐ด(๐ฅ
โ , โ๐)) for all proper groundings โ๐, โ๐ of โ๐ง
๐
(๐) = ๐
(๐ถ(๐ฅ) โง โ๐ฆ.[๐
(๐ฅ, ๐ฆ)๐ด(๐ฆ)๐ต(๐ฆ)]) < ๐
(๐ถ(๐ฅ) โง resp. โ๐ฆ in ๐ด resp. ๐ต.
โ๐ฆ.[๐
(๐ฅ, ๐ฆ)๐ด(๐ฆ)๐ต(๐ฆ)]).
(CMโ ): Let ๐ be a minimal world in ๐
such that ๐ฅ ex- Proof. Let โ๐ฅ, โ๐ฆ , โ๐ง mention variables from pairwise disjoint
ists with ๐ |= โ๐ฆ.๐
(๐ฅ, ๐ฆ) โ ๐ด(๐ฆ). Since (A) holds, for sets, and let ๐ฆโฌ = โจโ
, {(๐ต(๐ฅ โ , โ๐ง ))}โฉ. Each c-
โ , โ๐ฆ )|๐ด(๐ฅ
every ๐ โฒ with ๐
(๐ โฒ ) = ๐
(๐) it holds for all ๐ฅ that ๐ โฒ |= representation ๐
of ๐ฆโฌ has the form
โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ด(๐ฆ)] implies ๐ โฒ |= ๐ถ(๐ฅ)โงโ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ
๐
(๐) = ๐
0 + ๐1 (๐)๐1 ,
๐ต(๐ฆ)]. And for every ๐ โฒโฒ with ๐
(๐ โฒโฒ ) < ๐
(๐) we have
๐ โฒโฒ |= โ๐ฅ.โ๐ฆ.๐
(๐ฅ, ๐ฆ)๐ด(๐ฆ). Therefore, ๐
(๐) = ๐
(๐ถ(๐ฅ) โง where ๐1 (๐) = #{(๐ โ , โ๐, โ)|(๐
๐ โ , โ๐, โ)
๐ are proper groundings
โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ ๐ด(๐ฆ)๐ต(๐ฆ)]) < ๐
(๐ถ(๐ฅ) โง โ๐ฆ.[๐
(๐ฅ, ๐ฆ) โ of โ๐ง , โ๐ฆ , โ๐ฅ in (๐ต(๐ฅ
โ , โ๐ฆ )|๐ด(๐ฅ โ , โ๐ง ))} and ๐
0 , ๐1 โ N with ๐1
๐ด(๐ฆ)๐ต(๐ฆ)]). suitably chosen to ensure that ๐
|= (๐ต(๐ฅ โ , โ๐ง )). This
โ , โ๐ฆ )|๐ด(๐ฅ
For the case (A), (RM), (RMโ ), and (RMโ ) are implied by latter condition enforces that
(CM), (CMโ ), and (CMโ ), respectively.
In [8], the authors present an approach to defeasible rea- min ๐
(๐ด(๐ โ, โ๐) < min ๐
(๐ด(๐
โ, โ๐)๐ต(๐ โ, โ๐).
โ, โ๐)๐ต(๐
โ โ ,๐
๐,๐ โ โ โ ,๐
๐,๐ โ
soning for a restricted first-order logic which they evaluate
according to postulates that are inspired by rational closure The left hand side here is 0 (all instantiations verifying the
[16]. Beyond the KLM-postulates the satisfaction of which conditional), and the right hand side here is ๐1 (just one
we proved above, they also propose further postulates. E.g., falsification of the conditional), so we obtain ๐1 > 0 from
the postulate (INCL) in that paper corresponds to our (DI). In that.
the following, we adapt and extend three of those properties Now, if we take any proper groundings โ๐, โ๐ of โ๐ง resp. โ๐ฆ
that deal with relations to classical logic and irrelevance to in ๐ด resp. ๐ต and check whether
the framework here. First, we consider relations to classical
logic resp. implication: min ๐
(๐ด(๐
โ
๐
โ, โ๐ง )๐ต(๐
โ, โ๐ฆ ) < min ๐
(๐ด(๐
โ, โ๐ง )๐ต(๐
โ
๐
โ, โ๐ฆ ),
(CLA) Let ๐ฆโฌ = โจโฑ, โโฉ be a first-order conditional we find again that the left hand side is 0 and the right hand
knowledge base, and let ๐
be a model of ๐ฆโฌ. If side is ๐1 . Since ๐1 > 0 must hold, we conclude that ๐
|=
โฑ |= ๐ผ โ โฮฃ , then ๐
||โ ๐ผ.
(๐ต(๐ฅโ , โ๐)|๐ด(๐ฅ
โ , โ๐)) for all proper groundings โ๐, โ๐ of โ๐ง resp. โ๐ฆ
(SUB) โจโ
, {(๐ต(๐ฅ โ ))}โฉ |โผ (๐ด(๐ฅ
โ )|๐ด(๐ฅ โ ) โ ๐ต(๐ฅ
โ )|โค). in ๐ด resp. ๐ต.
5. Application of OCF-based A cwm -model โณ satisfies a defeasible subsumption ๐ถ โโผ
๐ท iff the <โณ -minimal instances of ๐ถ are instances of ๐ท:
Reasoning to a DL Knowledge
โณ โ โ
Base โผ ๐ท iff min(< , ๐ถ ) โ ๐ท ,
โณ |= ๐ถ โ
The goal of this section is to provide an example for how where min(<, ๐) = {๐ โ ๐ | โ๐ โฒ โ ๐ : ๐ โฒ < ๐ } as usual.
a DL knowledge base can be translated into a first-order Now we move towards defining ๐๐คm -entailment from
knowledge base, so that OCF-based inductive reasoning can defeasible knowledge bases. Let ๐ฎ๐ฆโฌ be the set that contains
be applied. Further, we point out some commonalities and ๐ถ and ยฌ๐ถ for all concepts ๐ถ that occur in a knowledge base
differences between the OCF-based semantics and the cwm - ๐ฆโฌ = โจ๐ฏ , ๐, ๐โฉ. We say that {๐ท1 , . . . , ๐ท๐ } โ ๐ฎ๐ฆโฌ is
semantics introduced by Giordano and Theseider Duprรฉ in consistent with ๐ฆโฌ if
[5] which we consider first.
๐ฏ ฬธ|= (๐ท1 โ ยท ยท ยท โ ๐ท๐ ) โ โฅ ,
5.1. Concept-Wise Multipreference i.e. if the intersection of ๐ท1 to ๐ท๐ does not have to be
Semantics empty.
In [5], a concept-wise multipreference (cwm ) semantics for Definition 14 (canonical interpretation [5]). A cwm -model
ranked defeasible knowledge bases was presented, which โณ = โจโโ , ยทโ , <โณ โฉ is canonical for a knowledge base
makes use of a typicality operator T on concepts used for ๐ฆโฌ = โจ๐ฏ , ๐, ๐โฉ if โจโโ , ยทโ โฉ satisfies ๐ฏ , and for any set of
the construction of typicality inclusions of the form T(๐ถ) โ concepts {๐ท1 , . . . , ๐ท๐ } โ ๐ฎ๐ฆโฌ consistent with ๐ฆโฌ, there
๐ท (where ๐ถ, ๐ท are concepts). We provide an equivalent exists ๐ฅ โ (๐ท1 โ ยท ยท ยท โ ๐ท๐ )โ .
definition using the notation ๐ถ โ โผ ๐ท here. Note that our
definition here is a simplified version of the one given in In other words, an interpretation is canonical if there is
[5], because we only consider non-ranked knowledge bases at least one domain element ๐ฅ โ โโ in every intersection
in this paper. of concepts that occur in ๐ฆโฌ.
In order to define a preference relation over individuals, Definition 15 (T-compliant interpretation [5]). A cwm -
the DBox ๐ is partitioned based on the left-hand side of the model โณ = โจโโ , ยทโ , <โณ โฉ is T-compliant for a knowledge
defeasible inclusions. Let ๐ = {๐ถ | (๐ถ โ โผ ๐ท) โ ๐}. For base ๐ฆโฌ = โจ๐ฏ , ๐, ๐โฉ if โจโโ , ยทโ โฉ satisfies ๐ฏ and for all ๐ถ โ
each concept ๐ถ โ ๐, let ๐๐ถ be the set that contains all de- ๐ with ๐ถ โ ฬธ= โ
, there exists ๐ฅ โ ๐ถ โ such that ๐๐ถ
โ
(๐ฅ) = ๐๐ถ .
feasible inclusions (๐ถ โโผ ๐ท) โ ๐, and for an interpretation
โ = โจโโ , ยทโ โฉ, let ๐๐ถ
โ
(๐ฅ) be the set of defeasible inclusions The definition above means that for all non-empty con-
from ๐๐ถ which are not violated by ๐ฅ, i.e. cepts ๐ถ, there is at least one instance of ๐ถ which does not
violate any defeasible subsumptions in with ๐ถ on the left-
โ โ
๐๐ถ (๐ฅ) = {(๐ถ โ
โผ ๐ท) โ ๐๐ถ | ๐ฅ โ (ยฌ๐ถ โ ๐ท) }. hand side.
Based on the amount of non-violated defeasible subsump- Definition 16 (cwm -entailment [5]). A defeasible subsump-
tion ๐ = ๐ถ โโผ ๐ท is cw -entailed by a knowledge base ๐ฆโฌ
m
tions, for each concept ๐ถ โ ๐ a preference relation โค๐ถ is
defined via (short: ๐ฆโฌ |โcwm ๐) if all canonical and T-compliant cwm -
models of ๐ฆโฌ satisfy ๐.
โ โ
๐ฅ โค๐ถ ๐ฆ iff |๐๐ถ (๐ฅ)| โฅ |๐๐ถ (๐ฆ)|. (9)
It was proven in [5] that cwm -entailment fulfills the prop-
Before we can define cwm -models, we need one more erties (Ref), (LLE), (And), (Or), and (CM).
definition: If a concept ๐ถ is a (potentially) strict subset of
another concept ๐ท, the subset ๐ถ can be viewed as more 5.2. Translation of a DL Knowledge Base
specific then ๐ท.
In order to allow for a comparison between the approach
Definition 12 (specificity of concepts [5]). Given a defea- of [5] and the OCF-based semantics in the next part of this
sible knowledge base ๐ฆโฌ = โจ๐ฏ , ๐, ๐โฉ and two concepts section, we now give an example for how a defeasible knowl-
๐ถ, ๐ท โ ๐, we call ๐ถ more specific than ๐ท (short: ๐ถ โป ๐ท) edge base can be transformed into a first-order knowledge
iff ๐ฏ |= ๐ถ โ ๐ท and ๐ฏ ฬธ|= ๐ท โ ๐ถ. base.
In cwm -models of defeasible knowledge bases, the prefer- Example 3. We consider the following example DL knowl-
ence relations for the specific concepts defined in Equation 9 edge base, which is very similar to the running example pre-
are combined into a global preference relation based on the sented in [5].
conceptsโ specificity.
๐ฏ = {Employee โ Adult, PhdStudent โ Student,
Definition 13 (cwm -model [5]). A cwm -model of a defea- (โhas_funding.โค โ ยฌFunded) โ โฅ},
sible knowledge base ๐ฆโฌ = โจ๐ฏ , ๐, ๐โฉ is a tuple โณ =
โจโโ , ยทโ , <โณ โฉ, where โโ ฬธ= โ
, โจโโ , ยทโ โฉ is an ๐โ๐- ๐Employee = { ๐1 : Employee โ
โผ ยฌYoung,
interpretation satisfying ๐ฏ and ๐, and <โณ is an ordering ๐2 : Employee โ
โผ โhas_boss.Employee },
over โโ such that ๐ฅ <โณ ๐ฆ iff ๐Student = { ๐3 : Student โ
โผ โhas_classes.โค,
1. ๐ฅ <๐ถ ๐ฆ for some ๐ถ โ ๐, and ๐4 : Student โ
โผ Young,
2. for all ๐ถ โ ๐: ๐ฅ โค๐ถ ๐ฆ, or there exists ๐ถ โฒ such that ๐5 : Student โ
โผ ยฌFunded },
๐ถ โฒ โป ๐ถ and ๐ฅ <๐ถ โฒ ๐ฆ.
๐PhdStudent = { ๐6 : PhdStudent โ
โผ โhas_funding.Money,
๐7 : PhdStudent โ
โผ Bright }.
As description logics are fragments of first-order logic, the In the following, we present an example which shows that
knowledge base above can easily be translated into a first- the desirable properties of cwm -semantics w.r.t. inheritance
order knowledge base. We start by translating the strict sub- of properties are fulfilled by the OCF-based semantics as
sumptions in the TBox as facts. well. A full axiomatization of โproper inheritance of proper-
tiesโ is out of the scope of this paper, and will be addressed
โฑ = {โ๐ฅ.[Employee(๐ฅ) โ Adult(๐ฅ)], in future work.
โ๐ฅ.[PhdStudent(๐ฅ) โ Student(๐ฅ)],
Example 4. We consider again the knowledge base from
โ๐ฅ.[โ๐ฆ.has_funding(๐ฅ, ๐ฆ) โ Funded(๐ฅ)]} .
Example 3. In [5], several possible queries and desirable re-
The defeasible subsumptions can be translated as open con- sults are mentioned. Formulated as queries for the first-order
ditionals. From now on, all predicates are shortened to their knowledge base defined above, they read as follows.
initial letters. 1. โจโฑ, โโฉ |โ๐
โ๐ฆ.hb(๐ฅ, ๐ฆ) | ๐(๐ฅ) โง ๐ธ(๐ฅ) ?
(๏ธ )๏ธ
โ = { ๐1 : (ยฌ๐ (๐ฅ) | ๐ธ(๐ฅ)), หโ should be(๏ธyes (inheritance)
2. โจโฑ, โโฉ |โ๐
โ๐ฆ.hc(๐ฅ, ๐ฆ) | ๐(๐ฅ) โง ๐ธ(๐ฅ) ?
)๏ธ
๐2 : (โ๐ฆ.[hb(๐ฅ, ๐ฆ) โง ๐ธ(๐ฆ)] | ๐ธ(๐ฅ)),
หโ should be(๏ธyes )๏ธ (inheritance)
๐3 : (โ๐ฆ.hc(๐ฅ, ๐ฆ) | ๐(๐ฅ)),
3. โจโฑ, โโฉ |โ๐
ยฌ๐น (๐ฅ) | ๐(๐ฅ) โง ๐ธ(๐ฅ) ?
๐4 : (๐ (๐ฅ) | ๐(๐ฅ)), หโ should be(๏ธyes )๏ธ (inheritance)
๐5 : (ยฌ๐น (๐ฅ) | ๐(๐ฅ)), 4. โจโฑ, โโฉ |โ๐
๐ (๐ฅ) | ๐(๐ฅ) โง ๐ธ(๐ฅ) ?
๐6 : (โ๐ฆ.[hf (๐ฅ, ๐ฆ) โง ๐ (๐ฆ)] | ๐ (๐ฅ)), หโ should be(๏ธno (conflict)
5. โจโฑ, โโฉ |โ๐
ยฌ๐ (๐ฅ) | ๐(๐ฅ) โง ๐ธ(๐ฅ) ?
)๏ธ
๐7 : (๐ต(๐ฅ) | ๐ (๐ฅ)) }
หโ should be(๏ธno )๏ธ (conflict)
We demonstrate below how the inequality for the acceptance 6. โจโฑ, โโฉ |โ๐
ยฌ๐ (๐ฅ) | ๐(๐ฅ) โง Italian(๐ฅ) ?
of ๐6 by a c-representation ๐
can be computed. In order to หโ should be(๏ธno (irrelevance)
7. โจโฑ, โโฉ |โ๐
ยฌ๐น (๐ฅ) | ๐ (๐ฅ) ?
)๏ธ
keep formulas compact and readable, we indicate by a dot
ฬ (๐)) that the literal may be either positive
over a literal (e.g. ๐ด หโ should be no (override)
or negative (๐ด(๐) or ยฌ๐ด(๐)) and an underscore serves as a
When the OCF ๐
used for answering the queries above is a
wildcard that may be filled by all suitable constants ๐ โ ๐ฮฃ .
(minimal) c-representation, all of the queries are answered
For roles, i.e., binary predicates, the constants ๐๐๐ are the ones
correctly. As an example, we will compute the answer for
used together with a constant ๐ in order to form a candidate
query 7 below. The conditional mentioned in the query is
for a strong representative for the rule ๐๐ .
accepted by ๐
iff ๐
(๐น (๐ฅ)๐ (๐ฅ)) < ๐
(๐น (๐ฅ)๐ (๐ฅ). Hence, we
(4) need to compute these two ranks.
๐
|= ๐6 โ ๐
(๐ (๐ฅ)hf (๐ฅ, ๐ฆ)๐ (๐ฆ))
< ๐
(๐ (๐ฅ) โง โ๐ฆ.hf (๐ฅ, ๐ฆ)๐ (๐ฆ)) ๐
(๐ (๐ฅ)๐น (๐ฅ)) = min ๐
(๐ (๐)๐น (๐))
๐โ๐ฮฃ
โ min ๐
(๐ (๐)hf (๐, ๐๐6 )๐ (๐๐6 )) (๏ธ
๐โ๐ฮฃ = min ๐
๐ (๐)๐น (๐)๐(๐)hf (๐, _)
๐โ๐ฮฃ
โ๏ธ
< min ๐
(๐ (๐) hf (๐, ๐)๐ (๐)) ๐ธ(๐))hbฬ (๐, _)hc(๐, ๐๐3 )๐ (๐)
๐โ๐ฮฃ
๐โ๐ฮฃ
ฬ (๐)๐ฬ (๐)
)๏ธ
(๏ธ ๐ต(๐)๐ด
โ min ๐
๐ (๐)hf (๐, ๐๐6 )๐ (๐๐6 ) = ๐6
๐โ๐ฮฃ
๐นฬ (๐)๐(๐)๐ธ(๐)hc(๐, ๐๐3 )๐ (๐) ๐
(๐ (๐ฅ)๐น (๐ฅ)) = min ๐
(๐ (๐)๐น (๐))
๐โ๐ฮฃ
)๏ธ
ฬ (๐)๐ต(๐)๐ ฬ (๐, _)
ฬ (๐)hb min ๐
๐ (๐)๐น (๐)๐(๐)hf (๐, ๐๐6 )
(๏ธ
๐ด =
๐โ๐ฮฃ
(๏ธ โ๏ธ (๏ธ
๐ (๐๐6 )๐ธ(๐))hbฬ (๐, _)hc(๐, ๐๐3 )
)๏ธ
< min ๐
๐ (๐) hf (๐, ๐) โจ ๐ (๐)
๐โ๐ฮฃ
ฬ (๐)๐ ฬ (๐)
๐โ๐ฮฃ
)๏ธ
๐ (๐)๐ต(๐)๐ด
๐นฬ (๐)๐(๐)๐ธ(๐)hc(๐, ๐๐3 )๐ (๐) = ๐5
)๏ธ
๐ดฬ (๐)๐ต(๐)๐ ฬ (๐, _)
ฬ (๐)hb
The computation above shows that the conditional
โ ๐5 < ๐6 (๐น (๐ฅ)|๐ (๐ฅ)) is accepted by ๐
if ๐6 < ๐5 . However, we know
from Example 3 that ๐5 < ๐6 . Hence, the answer to the query
The other inequalities can be computed in a similar way. The
is no.
resulting system of inequalities can be solved, i.e. the knowl-
edge base โจโฑ, โโฉ is consistent for the OCF-based semantics The example above shows that the OCF-based semantics,
as well. just like cwm -semantics, allows subclasses to appropriately
inherit and override information specified for their respec-
5.3. Inheritance of Properties and tive superclass.
Observe another interesting feature of c-representations
Conflicting Information
that comes to light in the example above: We did not have
One particular advantage of the cwm -semantics is that it sup- to compute the ranks for all possible worlds or even just the
ports sub-concepts to both inherit and override properties values of the ๐๐ , but could answer the query based on the
defined for their parent-concepts, depending on whether underlying conditional structures of the knowledge base,
there is a conflict of information. This is not the case for e.g. captured by the inequalities between the ๐๐ .
Rational Closure [4], which suffers from the well-known There are some key differences between our approach and
drowning problem. the semantics proposed for defeasible description logics in
the literature. While most of these approaches are based on More advanced properties like syntax splitting [7] could
an ordering over individuals and uses some notion of typical be considered for the first-order case as well. Our results
individuals for specific concepts, our approach uses an order- concerning the property (IRR) dealing with splitting of vari-
ing over possible worlds and makes use of representatives ables can be considered as first steps in this direction.
for conditionals. Even if canonical models look very similar
to orderings over possible worlds, only considering typi-
cality between domain elements (even on a concept-level) References
when constructing the global ordering < seems to be less
[1] W. Spohn, Ordinal conditional functions: A dynamic
restrictive than considering representatives for conditionals,
theory of epistemic states, in: W. L. Harper, B. Skyrms
as it allows knowledge bases to have models that would be
(Eds.), Causation in Decision, Belief Change, and
considered inconsistent under our semantics. However, this
Statistics, Springer Netherlands, 1988, pp. 105โ134.
breaks (DI), as the following example shows.
doi:10.1007/978-94-009-2865-7_6.
Example 5. Consider the following knowledge base. [2] W. Spohn, The Laws of Belief - Ranking Theory and Its
Philosophical Applications, Oxford University Press,
๐ฏ = {๐ด โ ๐ต} Oxford, 2014.
๐๐ด = {๐ด โ
โผ ยฌ๐ถ} [3] G. Casini, T. Meyer, K. Moodley, R. Nortjรฉ, Relevant
๐๐ต = {๐ต โ โ
โผ ๐ด, ๐ต โผ ๐ถ}
closure: A new form of defeasible reasoning for de-
scription logics, in: E. Fermรฉ, J. Leite (Eds.), Log-
A canonical and T-compliant model โณ for this knowledge ics in Artificial Intelligence - 14th European Confer-
base is given by the orderings below. The individuals are ence, JELIA 2014, Funchal, Madeira, Portugal, Septem-
named after the concepts that they are interpreted in, with ber 24-26, 2014. Proceedings, volume 8761 of Lecture
overlines indicating negation, i.e. for the individual ๐๐๐ we Notes in Computer Science, Springer, 2014, pp. 92โ106.
have ๐๐๐ โ (ยฌ๐ด โ ยฌ๐ต โ ๐ถ)โ . doi:10.1007/978-3-319-11558-0_7.
๐๐๐, ๐๐๐, ๐๐๐, ๐๐๐, ๐๐๐ <๐ด ๐๐๐ [4] K. Britz, G. Casini, T. Meyer, K. Moodley, U. Sattler,
I. Varzinczak, Principles of KLM-style defeasible de-
๐๐๐, ๐๐๐, ๐๐๐ <๐ต ๐๐๐, ๐๐๐ <๐ต ๐๐๐ scription logics, ACM Transactions on Computational
๐๐๐, ๐๐๐ <โณ ๐๐๐, ๐๐๐ <โณ ๐๐๐ <โณ ๐๐๐ Logic 22 (2020) 1โ46. doi:10.1145/3420258.
[5] L. Giordano, D. Theseider Duprรฉ, An ASP ap-
We have min< (๐ต โ ) = {๐๐๐, ๐๐๐}, i.e. min< (๐ต โ ) โ ๐ดโ proach for reasoning in a concept-aware multipref-
and min< (๐ต โ ) โ ๐ถ โ . Therefore, ๐ฆโฌ ฬธ|โcwm ๐ต โ
โผ ๐ด and erential lightweight DL, Theory and Practice of
๐ฆโฌ ฬธ|โcwm ๐ต โ
โผ ๐ถ. Logic Programming 20 (2020) 751โ766. doi:10.1017/
s1471068420000381.
[6] S. Kraus, D. Lehmann, M. Magidor, Nonmonotonic
6. Conclusions reasoning, preferential models and cumulative logics,
Artificial Intelligence 44 (1990) 167โ207. doi:10.1016/
In this paper, we have presented an approach for first-order
0004-3702(90)90101-5.
conditional logic from [10], and added a definition of in-
[7] G. Kern-Isberner, C. Beierle, G. Brewka, Syntax split-
ductive inference operators for first-order knowledge bases.
ting = relevance + independence: New postulates for
Moreover, we have shown that an inductive inference op-
nonmonotonic reasoning from conditional belief bases,
erator based on strategic c-representations fulfills the DL-
in: Proceedings of the Seventeenth International Con-
version of the KLM postulates defined in [4], as well as
ference on Principles of Knowledge Representation
additional postulates from [8]. Additionally, we have shown
and Reasoning, KR-2020, International Joint Confer-
how to apply our approach to defeasible DL knowledge
ences on Artificial Intelligence Organization, 2020.
bases, while pointing out some commonalities and differ-
doi:10.24963/kr.2020/56.
ences with cwm -semantics for defeasible description logics
[8] G. Casini, T. Meyer, G. Paterson-Jones, I. Varzinczak,
[5].
KLM-style defeasibility for restricted first-order logic,
The work done in this paper lays the foundation for future
in: Lecture Notes in Computer Science, Springer In-
research on the capabilities of OCF-based semantics for
ternational Publishing, 2022, pp. 81โ94. doi:10.1007/
first-order conditional knowledge bases and, in particular,
978-3-031-21541-4_6.
for more in-depth comparisons between c-representation-
[9] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduc-
based inductive inference operators and different entailment
tion to Description Logic, Cambridge University Press,
relations proposed for defeasible DL knowledge bases like
2017. doi:10.1017/9781139025355.
rational entailment [17, 4], relevant entailment [3], and cwm -
[10] G. Kern-Isberner, M. Thimm, A ranking semantics for
entailment [5]. There is some recent work on connections
first-order conditionals, in: L. De Raedt, C. Bessiere,
between defeasible DL semantics and OCF-based semantics
D. Dubois, P. Doherty, P. Frasconi, F. Heintz, P. J. F.
[18], albeit only using propositional conditional logic.
Lucas (Eds.), ECAI 2012 - 20th European Conference
Additionally, most work done so far on first-order condi-
on Artificial Intelligence. Including Prestigious Appli-
tional knowledge bases and defeasible DL knowledge bases
cations of Artificial Intelligence (PAIS-2012) System
focus on the general case where no facts or no ABox, respec-
Demonstrations Track, Montpellier, France, August
tively, are present. Our approach is basically also capable
27-31 , 2012, volume 242 of Frontiers in Artificial Intel-
of dealing with information from an ABox, but for this, we
ligence and Applications, IOS Press, 2012, pp. 456โ461.
must also include option (B) from Definition 6 into our con-
doi:10.3233/978-1-61499-098-7-456.
siderations. We will work this out in future work. Moreover,
[11] G. Kern-Isberner, Conditionals in Nonmonotonic Rea-
also more postulates describing how different approaches
soning and Belief Revision, volume 2087 of Lecture
deal specifically with facts are needed.
Notes in Computer Science, Springer, 2001. doi:10.
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 rank-
ing 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 Reason-
ing 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 In-
telligence 226 (2015) 1โ33. doi:10.1016/J.ARTINT.
2015.05.001.
[18] J. Haldimann, C. Beierle, Characterizing multipref-
erence closure with system W, in: F. D. de Saint-
Cyr, M. รztรผrk-Escoffier, N. Potyka (Eds.), Scalable
Uncertainty Management - 15th International Confer-
ence, SUM 2022, Paris, France, October 17-19, 2022,
Proceedings, volume 13562 of Lecture Notes in Com-
puter Science, Springer, 2022, pp. 79โ91. doi:10.1007/
978-3-031-18843-5\_6.