=Paper=
{{Paper
|id=Vol-3197/paper6
|storemode=property
|title=Conditional Syntax Splitting, Lexicographic Entailment and the Drowning Effect
|pdfUrl=https://ceur-ws.org/Vol-3197/paper6.pdf
|volume=Vol-3197
|authors=Jesse Heyninck,Gabriele Kern-Isberner,Thomas Meyer
|dblpUrl=https://dblp.org/rec/conf/nmr/HeyninckKM22
}}
==Conditional Syntax Splitting, Lexicographic Entailment and the Drowning Effect==
https://ceur-ws.org/Vol-3197/paper6.pdf
Conditional Syntax Splitting, Lexicographic Entailment and the
Drowning Effect
Jesse Heyninck1,2,3,* , Gabriele Kern-Isberner4 and Thomas Meyer2
1
Vrije Universiteit Brussel, Belgium
2
University of Cape Town and CAIR, South-Africa
3
Open Universiteit Heerlen, the Netherlands
4
Technische UniversitΓ€t Dortmund
Abstract
Lexicographic inference [1] is a well-behaved and popular approach to reasoning with non-monotonic conditionals. In recent work we have
shown that lexicographic inference satisfies syntax splitting, which means we can restrict our attention to parts of the belief base that share atoms
with a given query. In this paper, we introduce the concept of conditional syntax splitting, inspired by the notion of conditional independence
as known from probability theory. We show that lexicographic inference satisfies conditional syntax splitting, and connect conditional syntax
splitting to several known properties from the literature on non-monotonic reasoning, including the drowning effect.
Keywords
Non-monotonic Reasoning, lexicographic inference, defeasible reasoning, non-monotonic logic, syntax splitting
1. Introduction us from splitting the belief base into two independent parts.
Lexicographic inference [1] is a well-known and popular approach An intuitively related problem that was somewhat surprisingly
to reasoning with non-monotonic conditionals, which has been shown to be independent of syntax splitting in [7] is the so-called
applied in description logics [2], probabilistic description logics drowning problem. It consists in the fact that under some inductive
[3] and richer preferential languages [4]. It is seen as a logic of inference relations, abnormal individuals do not inherit any prop-
very high-quality, as it extends rational closure (also known as erties. It is best illustrated using the canonical Tweety-example:
system Z) [5] and avoids the so-called drowning problem. This
Example 2 (The Drowning Problem). The drowning problem
high quality seems to come at a cost, as reasoning on the basis of
is illustrated by using the following conditional belief base
lexicographic inference is PNP -complete, even when restricted to
β = {(π |π), (π|π), (Β¬π |π), (π|π)}, which represents the Tweety-
belief bases consisting of Horn-literal rules, i.e. rule bases where
example, i.e. that birds typically fly, penguins are typically birds,
every ruleβs antecedent is a conjunction of atoms and every ruleβs
and penguins typically donβt fly, together with the additional con-
consequent is a literal [6]. In previous work [7], we have shown
ditional βbirds typically have beaksβ. The drowning problem is
that lexicographic inference satisfies syntax splitting [8]. Syntax
constituted by the fact that some inductive inference operators,
splitting is a property of inference operators that requires that,
such as system π, do not allow to infer that penguins typically
for a belief base which can be split syntactically into two parts
have beaks (π |βΌ π
Ξ π), i.e. the fact that penguins are abnormal when
(i.e. there exists two sub-signatures such that every conditional in
it comes to flying drowns inferences about penguinsβ beaks. It is
the belief base is built up entirely one of the two sub-signatures),
well-known that lexicographic inference does not suffer from the
restricting attention to the sub-signature does not result in a loss
drowning problem.
or addition of inferences. In other words, syntax splitting ensures
we can safely restrict our attention to parts of the belief base The drowning problem seems to be related to syntax splitting.
that share atoms with a given query, thus seriously lessening the Intuitively, {(π|π)} is unrelated to the rest of the belief base, in the
computational strain for many concrete queries. However, this sense that having beaks has nothing to do with flying or having
presupposed that parts of a conditional belief base are syntactically wings, as long as we know we are talking about birds. However,
independent, meaning that no common atoms are allowed. This (unconditional) syntax splitting does not allow to capture this kind
might be an overly strong requirement, as the two parts of the of independence, since the atom π prohibits the belief base from
belief base might have common elements. Consider the following being split into information about flying and wings on the one
example: hand, and information about beaks on the other hand. It is exactly
this kind of conditional independencies between conditionals that
Example 1. Usually, bikes are chain-driven (π|π), usually chain-
we seek to formally capture and study in this paper. In more detail,
driven bikes have multiple gears (π|π), and usually a bike frame
the contributions of the paper are the following:
consists of four pipes (π |π). The form of the frame is independent
of whether a bike is chain driven and how many gears it has. 1. we introduce and study the notion of conditional splitting
However, syntax splitting as defined in [8] does not allow us to of a belief base, a property of conditional belief bases, and
restrict attention to {(π |π)} when we want to make inferences generalize the concept of syntax splitting, a property of
about the form of a bike frame, as the common atom π prevents inductive inference operators, to conditional syntax split-
ting, thus bringing the idea of conditional independence
NMR 2022: 20th International Workshop on Non-Monotonic Reasoning, Au- into the realm of inductive inference operators;
gust 07β09, 2022, Haifa, Israel
*
Corresponding author. 2. we show that lexicographic entailment satisfies conditional
jesse.heyninck@ou.nl (J. Heyninck); syntax splitting;
gabriele.kern-isberner@cs.tu-dortmund.de (G. Kern-Isberner);
tmeyer@cair.org.za (T. Meyer) 3. we argue that the drowning effect can be seen as a violation
0000-0002-3825-4052 (J. Heyninck)
Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 of conditional syntax splitting; and
International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
61
4. we show how Lehmannβs so-called desirable closure prop- both antecedent and conclusion ((π΅|π΄)(π) = 1); it falsifies, or
erties [1] can be derived from conditional syntax splitting. violates it iff it satisfies the antecedence but not the conclusion
Outline of this Paper: We first state all the necessary preliminar- ((π΅|π΄)(π) = 0); otherwise the conditional is not applicable, i. e.,
ies in Section 2 on propositional logic (Section 2.1), reasoning the interpretation does not satisfy the antecedent ((π΅|π΄)(π) =
with non-monotonic conditionals (Section 2.2), inductive infer- π’). We say that π satisfies a conditional (π΅|π΄) iff it does not
ence (Section 2.3), System Z (Section 2.4) and lexicographic falsify it, i.e., iff π satisfies its material counterpart π΄ β π΅.
inference (Section 2.5). In Section 3 we define and study the Given a total preorder (in short, TPO) βͺ― on possible β²
worlds,
concept of conditional syntax splitting. In Section 4, we show that representing relative plausibility, π΄ βͺ― π΅ iff π βͺ― π for some
β²
lexicographic inference satisfies conditional syntax splitting. In π β min βͺ― (Mod(π΄)) and some π β minβͺ― (Mod(π΅)). This
Sections 5 and 6, we show how properties of inductive inference allows for expressing the validity of defeasible inferences via
operators previously only discussed informally, namely the drown- stating that π΄ |βΌ β²
βͺ― π΅ iff (π΄β§π΅) βΊ (π΄β§Β¬π΅) [10]. As is usual, we
ing effect (Section 5) and the properties introduced by Lehmann denote π βͺ― π and π β² βͺ― π by π β π β² and π βͺ― π β² and π β² ΜΈβͺ― π
β²
1995 (Section 6) can be seen as special cases of conditional syn- by π βΊ π (and similarly for formulas). We can marginalize total
tax splitting. Finally, we discuss related work in Section 7 and preorders and even inference relations, i.e., restricting them to
conclude in Section 8. sublanguages, in a natural way: If Ξ β Ξ£ then any TPO βͺ― on
β¦(Ξ£) induces uniquely a marginalized TPO βͺ―|Ξ on β¦(Ξ) by
setting
2. Preliminaries π1Ξ βͺ―|Ξ π2Ξ iff π1Ξ βͺ― π2Ξ . (2)
In the following, we briefly recall some general preliminaries on Note that on the right hand side of the iff condition above π1Ξ , π2Ξ
propositional logic, and technical details on inductive inference. are considered as propositions in the superlanguage β(β¦), hence
π1Ξ βͺ― π2Ξ is well defined [11].
Similarly, any inference relation |βΌ on β(Ξ£) induces a
2.1. Propositional Logic marginalized inference relation |βΌ|Ξ on β(Ξ) by setting
For a set At of atoms let β(At) be the corresponding proposi-
tional language constructed using the usual connectives β§ (and), π΄ |βΌ|Ξ π΅ iff π΄ |βΌ π΅ (3)
β¨ (or), Β¬ (negation), β (material implication) and β (mate-
rial equivalence). A (classical) interpretation (also called pos- for any π΄, π΅ β β(Ξ).
sible world) π for a propositional language β(At) is a function An obvious implementation of total preorders are ordinal
π : At β {β€, β₯}. Let β¦(At) denote the set of all interpretations conditional functions (OCFs), (also called ranking functions)
for At. We simply write β¦ if the set of atoms is implicitly given. π
: β¦ β N βͺ {β} with π
β1 (0) ΜΈ= β
. [12]. They express degrees
An interpretation π satisfies (or is a model of) an atom π β At, of (im)plausibility of possible worlds and propositional formulas
denoted by π |= π, if and only if π(π) = β€. The satisfaction π΄ by setting π
(π΄) := min{π
(π) | π |= π΄}. A conditional
relation |= is extended to formulas as usual. As an abbrevia- (π΅|π΄) is accepted by π
iff π΄ |βΌπ
π΅ iff π
(π΄ β§ π΅) < π
(π΄ β§ Β¬π΅).
tion we sometimes identify an interpretation π with its complete
conjunction, i. e., if π1 , . . . , ππ β At are those atoms that are 2.3. Inductive Inference Operators
assigned β€ by π and ππ+1 , . . . , ππ β At are those propositions
that are assigned β₯ by π we identify π by π1 . . . ππ ππ+1 . . . ππ In this paper, we will be interested in inference relations |βΌ Ξ
(or any permutation of this). For π β β(At) we also define parametrized by a conditional belief base β. In more detail, such
π |= π if and only if π |= π΄ for every π΄ β π. Define the set of inference relations are induced by β, in the sense that β serves as
models Mod(π) = {π β β¦(At) | π |= π} for every formula a starting point for the inferences in |βΌ Ξ . We call such operators
or set of formulas π. A formula or set of formulas π1 entails inductive inference operators:
another formula or set of formulas π2 , denoted by π1 |= π2 , Definition 1 ([8]). An inductive inference operator (from condi-
if Mod(π1 ) β Mod(π2 ). Where π β Ξ£, and π β β¦(Ξ£), we tional belief bases) is a mapping C that assigns to each conditional
denote by π π the restriction of π to π, i.e. π π is the interpretation belief base β β (β|β) an inference relation |βΌ Ξ on β that satis-
over Ξ£π that agrees with π on all atoms in π. Where Ξ£π , Ξ£π β Ξ£, fies the following basic requirement of direct inference:
β¦(Ξ£π ) will also be denoted by β¦π for any π β N, and likewise
β¦π,π we denote β¦(Ξ£π βͺ Ξ£π ) (for π, π β N). Likewise, for some DI If β is a conditional belief base and |βΌ Ξ is an inference
π β β(Ξ£π ), we define Modπ (π) = {π β β¦π | π |= π}. relation that is induced by β, then (π΅|π΄) β β implies
π΄ |βΌ Ξ π΅.
2.2. Reasoning with Nonmonotonic Examples of inductive inference operators include system P
Conditionals [13], System Z ([5], see Section 2.4), lexicographic inference ([1],
Given a language β, conditionals are objects of the form (π΅|π΄) see Section 2.5) and c-representations ([14].
where π΄, π΅ β β. The set of all conditionals based on a language As already indicated in the previous subsection, inference rela-
β is defined as: (β|β) = {(π΅|π΄) | π΄, π΅ β β}. We follow tions can be obtained on the basis of TPOs respectively OCFs:
the approach of [9] who considered conditionals as generalized Definition 2. A model-based inductive inference operator for
indicator functions for possible worlds resp. propositional inter- total preorders (on β¦) is a mapping Cπ‘ππ that assigns to each
pretations π: conditional belief base β a total preorder βͺ―Ξ on β¦ s.t. π΄ |βΌ βͺ―Ξ π΅
β§
β¨ 1 : π |= π΄ β§ π΅ for every (π΅|π΄) β β (i.e. s.t. DI is ensured). A model-based
((π΅|π΄))(π) = 0 : π |= π΄ β§ Β¬π΅ (1) inductive inference operator for OCFs (on β¦) is a mapping Cπππ
π’ : π |= Β¬π΄ that assigns to each conditional belief base β an OCF π
Ξ on β¦
β©
s.t. β is accepted by π
Ξ (i.e. s.t. DI is ensured).
where π’ stands for unknown or indeterminate. In other words,
a possible world π verifies a conditional (π΅|π΄) iff it satisfies
62
Examples of inductive inference operators for OCFs System Example 3. Let β = {(π |π), (π|π), (Β¬π |π)} be a sub-base of
Z ([5], see Sec. 2.4) and c-representations ([14], whereas lexico- belief base used in Example 2. This conditional belief base
graphic inference ([1], see Sec. 2.5) is an example of an inductive has the following Z-partitioning: β0 = {(π |π)} and β1 =
inference operator for TPOs. {(π|π), (Β¬π |π)}. This gives rise to the following π
π
Ξ -ordering
To define the property of syntax splitting [8], we assume a over the worlds based on the signature {π, π, π}:
conditional belief base β that can be split into subbases β1 , β2
s.t. βπ β (βπ |βπ ) with βπ = β(Ξ£π ) for π = 1, 2 s.t. Ξ£1 β©Ξ£2 = β
and Ξ£1 βͺ Ξ£2 = Ξ£, writing: π π
π
Ξ π π
π
Ξ π π
π
Ξ π π
π
Ξ
βοΈ πππ 2 πππ 1 πππ 2 ππ π 2
β = β1 β2 πππ 0 πππ 1 πππ 0 ππ π 0
Ξ£1 ,Ξ£2
whenever this is the case. As an example of a (non-)inference, observe that e.g. β€ |βΌ π
Ξ Β¬π
and π β§ π ΜΈ|βΌ π
Ξ π.
Definition 3 (Independence (Ind), [8]). An inductive inference
operator C satisfies (Ind) if for any β = β1 Ξ£1 ,Ξ£2 β2 and for
βοΈ
any π΄, π΅ β βπ , πΆ β βπ (π, π β {1, 2}, π ΜΈ= π), 2.5. Lexicographic Entailment
We recall lexicographic inference as introduced by [1]. For some
π΄ |βΌ Ξ π΅ iff π΄πΆ |βΌ Ξ π΅ conditional belief base β, the order βͺ―lex Ξ is defined as follows:
Given π β β¦ and ββ² β β, π (π, ββ² ) = |({(π΅|π΄) β ββ² |
Definition 4 (Relevance (Rel), [8]). An inductive inference oper-
(π΅|π΄)(π) = 0}|. Given a set of conditionals β π-partitioned in
ator C satisfies (Rel) if for any β = β1 Ξ£1 ,Ξ£2 β2 and for any
βοΈ
(β0 , . . . , βπ ), the lexicographic vector for a world π β β¦ is the
π΄, π΅ β βπ (π β {1, 2}),
vector lex(π) = (π (π, β0 ), . . . , π (π, βπ )). Given two vectors
π΄ |βΌ Ξ π΅ iff π΄ |βΌ Ξπ π΅. (π₯1 , . . . , π₯π ) and (π¦1 , . . . , π¦π ), (π₯1 , . . . , π₯π ) βͺ―lex (π¦1 , . . . , π¦π )
iff there is some π β©½ π s.t. π₯π = π¦π for every π > π and
β²
Definition 5 (Syntax splitting (SynSplit), [8]). An inductive in- π₯π β©½ π¦π . π βͺ―lex Ξ π iff lex(π) βͺ―
lex
lex(π β² ). The resulting
π‘ππ
ference operator C satisfies (SynSplit) if it satisfies (Ind) and inductive inference operator πΆβͺ―lex will be denoted by πΆ lex to
(Rel). avoid clutter.
In [1], lexicographic inference was shown to be RC-extending
Thus, Ind requires that inferences from one sub-language are (for finite conditional belief bases):
independent from formulas over the other sublanguage, if the
belief base splits over the respective sublanguages. In other words, Proposition 1 ([1, Theorem 3]). For any π΄ β β s.t. π
π
Ξ (π΄) is
information on the basis of one sublanguage does not influences finite, then π΄ |βΌ π lex
Ξ π΅ implies π΄ |βΌ Ξ π΅.
inferences made in the other sublanguage. Rel, on the other hand,
restricts the scope of inferences, by requiring that inferences in Example 4 (Example 3 ctd.). For the Tweety belief base β as in
a sublanguage can be made on the basis of the conditionals in a Example 3 we obtain the following lex(π)-vectors:
conditional belief base formulated on the basis of that sublanguage.
SynSplit combines these two properties. π lex(π) π lex(π) π lex(π) π lex(π)
πππ (0,1) πππ (1,0) πππ (0,2) ππ π (0,1)
2.4. System Z πππ (0,0) πππ (1,0) πππ (0,0) ππ π (0,0)
We present system π defined in [5] as follows. A conditional
The lex-vectors are ordered as follows:
(π΅|π΄) is tolerated by a finite set of conditionals β if there is a
possible world π with (π΅|π΄)(π) = 1 and (π΅ β² |π΄β² )(π) ΜΈ= 0 for (0, 0) βΊlex (1, 0) βΊlex (0, 1) βΊlex (0, 2).
all (π΅ β² |π΄β² ) β β, i.e. π verifies (π΅|π΄) and does not falsify any
(other) conditional in β. The Z-partitioning (β0 , . . . , βπ ) of β Observe that e.g. β€ |βΌ lex
Ξ Β¬π (since lex(β€ β§ Β¬π) = (0, 0) βΊ
lex
is defined as: lex
lex(β€ β§ π) = (1, 0)) and π β§ π |βΌ Ξ π.
β’ β0 = {πΏ β β | β tolerates πΏ};
β’ β1 , . . . , βπ is the Z-partitioning of β β β0 . 3. Conditional Syntax Splitting
For πΏ β β we define: πΞ (πΏ) = π iff πΏ β βπ and (β0 , . . . , βπ ) We now introduce a conditional version of syntax splitting. A first
is the Z-partioning of β. Finally, the ranking function π
π Ξ is
central idea is the syntactical notion of conditional splitting, a
defined via: π
π Ξ (π) = max{π(πΏ) | πΏ(π) = 0, πΏ β β} + 1, with
property of belief bases.
max β
= β1. The resulting inductive inference operator πΆπ
πππ π is
Ξ Definition 6. We say a conditional belief base β can be split
denoted by πΆ π . into subbases β1 ,β2 conditional on a sub-alphabet Ξ£3 , if βπ β
In the literature, system π has also been called rational closure (β(Ξ£π βͺ Ξ£3 ) | β(Ξ£π βͺ Ξ£3 )) for π = 1, 2 s.t. Ξ£1 , Ξ£2 and Ξ£3 are
[15]. An inference relation |βΌ Ξ based on β s.t. π΄ |βΌ π Ξ π΅ implies pairwise disjoint and Ξ£ = Ξ£1 βͺ Ξ£2 βͺ Ξ£3 , writing:
π΄ |βΌ Ξ π΅ is called RC-extending [16]. An RC-extending inference βοΈ
relation has also been called a refinement of System π [17]. We β = β1 β2 | Ξ£3
call an inductive inference operator C RC-extending iff every Ξ£1 ,Ξ£2
C(β) is RC-extending.
We now illustrate OCFs in general and System π in particular Intuitively, a conditional belief base can be split into Ξ£1 and
with the well-known βTweety the penguinβ-example. Ξ£2 conditional on Ξ£3 , if every conditional is built up from atoms
in Ξ£1 βͺ Ξ£3 or atoms in Ξ£2 βͺ Ξ£3 .
63
The above notion of conditional syntax splitting, however, is Proposition 2. Let a conditional belief base β =
too strong, in the sense that it does not warrant satisfaction of β1 Ξ£1 ,Ξ£2 β2 | Ξ£3 be given. If there is a πΆ β β(Ξ£3 ) s.t.
βοΈ
conditional variants of relevance and independence (we will define for every conditional in (π΅|π΄) β β = β1 2
βοΈ
Ξ£1 ,Ξ£2 β | Ξ£3 :
them in formal detail below) for lexicographic inference. The
underlying problem is that toleration might not be respected by 1. π΅ β β(Ξ£1 ) βͺ β(Ξ£2 ), or π΅ β‘ πΆ.
conditional belief bases that conditionally split: 2. π΄ β β(Ξ£1 ) βͺ β(Ξ£2 ), or π΄ β‘ πΆ.
Example 5. Let β = {(π₯|π), (Β¬π₯|π), (π|π β§ π)}. Then 3. (πΊ|π»)βΞπ π» β πΊ ΜΈβ’ {Β¬πΉ | (πΉ |πΆ β² ) β βπ , πΆ β² β‘
βοΈ βοΈ
πΆ} for π = 1, 2.1
βοΈ
β = {(π₯|π), (Β¬π₯|π)} {(π|π β§ π)} | {π, π}
{π₯},{π} Then β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 .
βοΈ
However, this notion of purely syntactical conditional indepen-
dence is not reflected on the level of tolerance (and therefore Proof. Consider some π 3 β β¦(Ξ£3 ). If π 3 ΜΈ|= πΆ we are done.
3
entailment). Indeed, {(π|π β§ π)} (trivially) tolerates itself, i.e. Suppose
2 β²3 βοΈ π |= πΆ. With the third condition,
therefore
2 β²3
there is an
π{(π|πβ§π)} (π|π β§ π) = 0, yet β does not tolerate (π|π β§ π), i.e. π π β Mod( (πΊ|π»)βΞ 2 π» β πΊ) s.t. π π |= πΉ for every
πΞ (π|π β§ π) = 1. (πΉ |πΆ β² ) β β2 s.t. πΆ β² β‘ πΆ. Notice that, in view of the first two
π 2
This means that for system Z and lexicographic entaiment, conditions, for any (π΅|π΄) β β , either π |= π΄ β π΅ or π΅ β‘ πΆ
conditional relevance (now only introduced informally) is vio- or π΄ β‘ πΆ. Furthermore, in the case where π΄ β‘ πΆ, π 2 π β²3 |= π΅.
2 3
Since π΅ β βοΈ β(Ξ£2 ) or π΅ β‘ πΆ, also π π |= π΅. Altogether,
βοΈ base. In more detail, even though β =
lated for this belief
2 3 1 βοΈs 2
{(π₯|π), (Β¬π₯|π)} {π₯},{π} {(π|π β§ π)} | {π, π}, we have e.g. π π |= (πΊ|π»)βΞ2 π» β πΊ. Thus, β = β Ξ£1 ,Ξ£2 β |
β€ ΜΈ|βΌ lex lex
Β¬(π β§ π) whereas β€ |βΌ Β¬(π β§ π) (and likewise Ξ£ 3 .
{(π|πβ§π)} Ξ
for system π). A simpler case of this condition is a belief base where all
What happens here is that (π₯|π) and (Β¬π₯|π) act as βconstraintsβ antecedents derive from the common alphabet Ξ£3 and all conse-
on π and π being true together, which on its turn is needed for quents derive from either Ξ£1 or Ξ£2 .
(π|π β§ π) to be tolerated. In other words, pure syntactic conditional Notice that e.g. the conditional belief base from Example 2 has
splitting is not reflected on the semantic level (in contradistinction the form described in Proposition 2:
to unconditional splitting). We can exclude such cases by using Example 6. Consider again β from Example 2, and let Ξ£1 =
the following weaker notion of safe conditional syntax splitting: {π, π}, Ξ£2 = {π} and Ξ£3 = {π}. Observe that:
Definition 7. A conditional belief base β = β1 Ξ£1 ,Ξ£2 β2 |
βοΈ
βοΈ
Ξ£3 can be safely split into subbases β1 , β2 conditional on a β = {(π |π), (π|π), (Β¬π |π)} {(π|π)} | Ξ£3 .
Ξ£1 ,Ξ£2
sub-alphabet Ξ£3 , writing:
s
βοΈ Furthermore, the first two items in Proposition 2 are satisfied
β = β1 β2 | Ξ£3 , as every conditional is either completely on the basis of the al-
Ξ£1 ,Ξ£2 phabet {π, π} or has as an antecedent or a consequent π. Fi-
nally, the last condition is satisfied as {π β π} ΜΈ|= Β¬π and
if for every π β β¦(Ξ£π βͺΞ£3 ), there is a π π β β¦(Ξ£π ) s.t. π π π 3 ΜΈ|=
βοΈ
3
{π β π, π β π, π β Β¬πβοΈ} ΜΈ|= π β¨ Β¬π. We thus see that
(πΉ |πΈ)βΞπ πΈ β§ Β¬πΉ (for π, π = 1, 2 and π ΜΈ= π). β = {(π |π), (π|π), (Β¬π |π)} sΞ£1 ,Ξ£2 {(π|π)} | Ξ£3 .
The notion of safe splitting is explained as follows: β can be The bicycle example is also of this form:
safely split into β1 and β2 conditional on Ξ£3 if it can be split in
β1 and β2 conditional on Ξ£3 , and additionally, for every world Example 7. Consider again β from Example 1. We see that:
π π π 3 in the subsignature Ξ£π βͺ Ξ£3 , we can find a world π π in s
βοΈ
the subsignature Ξ£π (π, π = 1, 2 and π ΜΈ= π) s.t. no conditional {(π|π), (π|π)} {(π |π)} | {π}.
πΏ β βπ is falsified by π π π π π 3 (or, equivalently, by π π π 3 ). We {π,π},{π }
will show some more syntactical formulated conditions that ensure Remark 1. Note that a weaker prerequisite such as taking only
safe splitting below. the first two conditions in Proposition 2 does not work: in more de-
We argue here that safe splitting faithfully captures indepen-
dences of two conditional belief bases conditional on a sub- βοΈis a πΆ β β(Ξ£3 ) s.t. for every conditional
tail, requiring that there
in (π΅|π΄) β β = β1 Ξ£1 ,Ξ£2 β2 | Ξ£3 :
signature Ξ£3 . Indeed, safe splitting requires that (1) all condition-
1. π΅ β β(Ξ£1 ) βͺ β(Ξ£2 ),
βοΈ built up from the sub-signatures Ξ£1 βͺ Ξ£3 or Ξ£2 βͺ Ξ£3 (i.e.
als are
β1 Ξ£1 ,Ξ£2 β2 | Ξ£3 ), and (2) that any information on Ξ£π βͺ Ξ£3 is 2. π΄ β β(Ξ£1 ) βͺ β(Ξ£2 ), or π΄ β‘ πΆ.
compatible with βπ , i.e. no world π π π 3 causes a conditional in
βπ to be violated. In other words, toleration with respect to βπ is In other words, these two conditions say that conditionals are
independent of βπ . either fully from the language based on either Ξ£1 or Ξ£2 , or their
We now delineate some more syntactic conditions that ensure antecedent is fully based on Ξ£3 , and there is only a single formula
safe syntax splitting. These conditions are typically easier to allowed to occur as such. However, this notion is not consistent
check, and might reasonably be expected to hold for certain with toleration. Consider β = {(π¦|β€), (Β¬π¦|π), (π₯|π)}. Then
natural language scenarios. For example, if it holds that (1)
βοΈ
β = {(π¦|β€), (Β¬π¦|π)} {(π₯|π)} | {π}
β = β1 Ξ£1 ,Ξ£2 β2 | Ξ£3 , (2) all antecedents and consequents
βοΈ
{π¦},{π₯}
(of conditionals in β) using elements of the common sub-alphabet
Ξ£3 are equivalent, and (3) all material versions of the conditional and {(π₯|π)} tolerates itself (trivially), yet {(π¦|β€), (Β¬π¦|π), (π₯|π)}
sub-base βπ are consistent with the set of consequents of the does not tolerate (π₯|π). It is perhaps not surprising that such a
conditionals whose antecedent uses atoms in the common sub- purely syntactic condition is elusive.
alphabet Ξ£3 , then β can be safely split into β1 and β2 condi- 1
Or, equivalently, {π» β πΊ | (πΊ|π») β Ξπ }βͺ{πΉ | (πΉ |πΆ β² ) β Ξπ , πΆ β² β‘
tional on Ξ£3 . πΆ} ΜΈβ’ β₯.
64
Safe conditional splitting of a conditional belief
βοΈ base is consis- CIndπ‘ππ π΄π· βͺ―Ξ π΅π· iff π΄πΆπ· βͺ―Ξ π΅πΆπ·
tent with toleration, in the sense that β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3
CRelπ‘ππ π΄π· βͺ―Ξ π΅π· iff π΄π· βͺ―Ξπ π΅π·
implies that toleration of a conditional (π΅|π΄) by β is equiva-
π CIndπππ π
Ξ (π΄π·) β©½ π
Ξ (π΅π·) iff π
Ξ (π΄πΆπ·) β©½ π
Ξ (π΅πΆπ·)
lent to toleration of (π΅|π΄) by the conditional sub-base β in
which it occurs. This gives further evidence to the fact that safe CRelπππ π
Ξ (π΄π·) β©½ π
Ξ (π΅π·) iff π
Ξπ (π΄π·) β©½ π
Ξπ (π΅π·)
conditional splitting adequately captures the notion of indepen- We now connect CInd to the notion of conditional indepen-
dence of sub-bases: toleration of a conditional is independent of a dence of TPOs as known from belief revision. For this, we need
(conditionally) unrelated sub-base. the following notion taken from [18]:
Proposition 3. Let a conditional βοΈ belief base β = Definition 11 ([18]). Let βͺ― be a total preorder on β¦(Ξ£), and
β1 Ξ£1 ,Ξ£2 β2 | Ξ£3 be given. β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 implies
βοΈ
let Ξ£1 , Ξ£2 , Ξ£3 be three (disjoint) subsignatures of Ξ£. Then
(for any π = 1, 2) that βπ tolerates (π΅|π΄) β βπ iff β tolerates Ξ£1 and Ξ£2 are independent conditional on Ξ£3 , in symbols,
(π΅|π΄). 1 1 2 2
|=
Ξ£1 βͺ― Ξ£2 |Ξ£3 , if for all π1 , π2 β β¦(Ξ£1 ), π1 , π2 β β¦(Ξ£2 ),
and π 3 β β¦(Ξ£3 ) holds that for all π, π β {2, 3}, π ΜΈ= π,
Proof. Suppose β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 . Suppose βπ tolerates
βοΈ
(π΅|π΄) β βπ . Wlog let π = 1. This means there is an π 1 β β¦(Ξ£1 ) π1π π1π π 3 βͺ― π2π π1π π 3 iff π1π π 3 βͺ― π2π π 3 . (4)
and π 3 β β¦(Ξ£3 ) s.t. π 1 π 3 |= π΄ β§ π΅ and πβοΈ1 π 3 |= πΆ β π·
for every (π·|πΆ) β β1 . Since β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 , Independence of two subsignatures Ξ£π and Ξ£π conditional on
π 1 π 2 π 3 |= (πΉ |πΈ)βΞ2 πΈ β§ Β¬πΉ , i.e. π 1 π 2 π 3 |= πΈ β πΉ for
βοΈ Ξ£3 means that, in the context of fixed information about Ξ£3 ,
every (πΉ |πΈ) β βπ . Thus, β tolerates (π΅|π΄). The other direction information about Ξ£π is irrelevant for the ordering of worlds
is immediate. based on Ξ£π : π1π can be βcancelled outβ.
TPOs Cπ‘ππ :
Proposition 4. An inductive inference operator forβοΈ
We now move to the formulation of conditional syntax splitting,
β β¦ββͺ―Ξ on β satisfies (CInd) iff for any β = β1 sΞ£1 ,Ξ£2 β2 |
a property of inductive inference relations that expresses that the
|=
independencies between sub-bases of conditionals, as encoded in Ξ£3 , it holds that Ξ£1 βͺ― Ξ£2 |Ξ£3 .
safe splitting, are respected by an inductive inference relation.
Proof. For the βοΈβ-direction, suppose that Cπ‘ππ satisfies (CInd)
Conditional independence (CInd) and safe conditional rele- s
and β = β1 Ξ£1 ,Ξ£2 β2 | Ξ£3 . Consider some π11 , π21 β β¦(Ξ£1 ),
vance (CRel) are defined analogous to (Ind) and (Rel), but now
assuming that a conditional belief base can be safely split and π 2 β β¦(Ξ£2 ) and π 3 β β¦(Ξ£3 ) and suppose that π11 π 3 βΊ
taking into account we have full information on the βconditional π11 π 3 . Thus, π11 π 3 β¨ π21 π 3 |βΌ βͺ― Β¬π11 . Thus, with (CIndπ‘ππ ),
pivotβ Ξ£3 : π11 π 2 π 3 β¨ π21 π 2 π 3 |βΌ βͺ― Β¬π11 and thus π11 π 2 π 3 βΊ π21 π 2 π 3 . The
other direction of equation (4) is analogous.
Definition 8. An inductive inference operator C satisfies (CInd)
|=
For the βοΈβ-direction, suppose Ξ£1 βͺ― Ξ£2 |Ξ£3 and suppose
if for any β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 , and for any π΄, π΅ β β(Ξ£π ), β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 and π΄π· |βΌ Ξ π΅ for some π΄, π΅ β
βοΈ
πΆ β β(Ξ£π ) (for π, π β {1, 2}, π ΜΈ= π) and a complete conjunction β(Ξ£1 ) and some complete conjunction π· β β(Ξ£3 ). Notice
π· β β(Ξ£3 ), that since π· is a complete conjunction, there is a unique world
π΄π· |βΌ Ξ π΅ iff π΄π·πΆ |βΌ Ξ π΅ π 3 β β¦(Ξ£3 ) s.t. π 3 |= π·. Then π΄π΅π· βΊ π΄π΅π·. Consider
now some arbitrary πΆ β β(Ξ£2 ). Notice that π΄π΅π· βͺ― π΄π΅πΆπ·.
Thus, an inductive inference operator satisfies conditional in-
Take some π21 π22 π 3 β minβͺ― Mod(π΄π΅πΆπ·). For any π11 π12 π 3 β
dependence if, for any β that safely splits into β1 and β2 con-
minβͺ― Mod(π΄π΅π·), π31 π12 π 3 β Mod(π΄π΅π·) (as π΅ β β(Ξ£1 ),
ditional on Ξ£3 , whenever we have all the necessary information
and thus π11 π12 π 3 βΊ π31 π12 π 3 (since π΄π΅π· βΊ π΄π΅π·). With
about Ξ£3 , inferences from one sub-language are independent from
independence, π11 π 3 βΊ π21 π 3 . Again with independence,
formulas over the other sub-language.
π11 π22 π 3 βΊ π21 π22 π 3 . Since π22 |= πΆ, π11 π22 π 3 β Mod(π΄π΅πΆπ·)
Definition 9. An inductive inference operator C satisfies (CRel) and thus there is some π31 π32 π 3 β minβͺ― Mod(π΄π΅πΆπ·) with
if for any β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 , and for any π΄, π΅ β β(Ξ£π )
βοΈ π31 π32 π 3 βΊ π21 π22 π 3 . Since π21 π22 π 3 β minβͺ― Mod(π΄π΅πΆπ·),
(for π β {1, 2}) and a complete conjunction π· β β(Ξ£3 ), we have established that π΄πΆπ· |βΌ βͺ― π΅.
π΄π· |βΌ Ξ π΅ iff π΄π· |βΌ Ξπ π΅ Proposition 4 establishes a correspondence between the prop-
erty CInd of inductive inference operators, and the notion of
Thus, CRel restricts the scope of inference by requiring that conditional independence for TPOs, as already known from belief
inferences in the sub-language Ξ£1 βͺ Ξ£3 can be made on the basis revision.
of the conditionals on the basis of that sub-language.
TPOs Cπ‘ππ :
Proposition 5. An inductive inference operator forβοΈ
Syntax splitting (CSynSPlit) combines the two properties
β β¦ββͺ―Ξ on β satisfies (CRel) iff for any β = β1 sΞ£1 ,Ξ£2 β2 |
(CInd) and (CRel):
Ξ£3 , it holds that βͺ―Ξπ = βͺ―Ξ |Ξ£π .
Definition 10. An inductive inference operator C satisfies con-
ditional syntax splitting (CSynSPlit) if it satisfies (CInd) and Proof. π‘ππFor the β-direction, supposeβοΈ that Cπ‘ππ satisfies
(CInd). (CRel ) and consider some β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 . Sup-
pose π11 π13 βΊΞπ π21 π23 . Then π11 π13 β¨ π21 π23 |βΌ Ξ Β¬π21 π23 . With
We now proceed with the study of conditional syntax splitting. (CRel), π 1 π 3 β¨ π 1 π 3 |βΌ Β¬π 1 π 3 and thus π 1ππ 3 βΊ π 1 π 3 ,
1 1 2 2 Ξ 2 2 1 1 Ξ 2 2
We first analyse the properties of CInd and CRel for TPOs. We i.e. π 1 π 3 βͺ― 1 3
1 1 Ξ |Ξ£1 π2 π2 . The other direction is analogous.
first notice that CInd and CRel for inductive inference operators
For the β-direction, suppose that β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3
βοΈ
for TPOs respectively for OCFsβοΈis equivalent to the following two
properties (for any β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 and for π΄, π΅ β and βͺ―Ξπ = βͺ―Ξ |Ξ£π . Suppose now π΄ |βΌ Ξ π΅. Then π΄π΅ βΊΞ π΄π΅
β(Ξ£π ), complete conjunction π· β β(Ξ£3 ), πΆ β β(Ξ£π ), π, π = and thus π΄π΅ βΊΞπ π΄π΅, which implies π΄ |βΌ Ξπ π΅.
1, 2 and π ΜΈ= π):
65
We now analyze conditional syntax splitting for inductive infer- Lemma 9. Let a conditional belief base β1 sΞ£1 ,Ξ£2 β2 | Ξ£3
βοΈ
ence operators for OCFs. Thanks to the close relationship between with its corresponding Z-partition (β0 , . . . , βπ ) be given. Then
rankings and probabilities, there is a straightforward adaptation for every 0 β©½ π β©½ π2 :
of conditional independence for OCFs [19, Chapter 7].
π (π, βπ ) = π (π 1 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π )
Definition 12. Let Ξ£1 βͺΜ Ξ£2 βͺΜ Ξ£3 β Ξ£ and let π
be an OCF. = π (π 1 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β2π )
Ξ£2 , Ξ£3 are conditionally independent given Ξ£1 with respect to π
,
1 2
|=
π
Ξ£2 |Ξ£3 , if for all π β β¦(Ξ£1 ), π β β¦(Ξ£2 ), Proof. Take some 0 β©½ π β©½ π. Noice that β1
βοΈs
in symbols Ξ£1 2
3 1 1 3 1 3 Ξ£1 ,Ξ£2 β | Ξ£3 ,
and π β β¦(Ξ£3 ), π
(π |π π ) = π
(π |π ) holds. (π΅|π΄) β βπ iff (π΅|π΄) β βπ β βπ or (π΅|π΄) β βπ β β1π or
1 2 2
1 2
As for probabilities, conditional independence for OCFs ex- (π΅|π΄) β βπ β© βπ . Thus π (π, βπ )
presses that information on Ξ£3 is redundant for Ξ£2 if full infor-
= |{(π΅|π΄) β βπ | π |= π΄ β§ Β¬π΅}|
mation on Ξ£1 is available and used.
= |{(π΅|π΄) β β1π | π 1 π 3 |= π΄ β§ Β¬π΅}|
πππ
βοΈs for OCFs C
Proposition 6. An inductive inference operator : +|{(π΅|π΄) β β2π | π 2 π 3 |= π΄ β§ Β¬π΅}|
β β¦β π
Ξ satisfies CInd iff for any β = β1 Ξ£1 ,Ξ£2 β2 | Ξ£3 we
β|{(π΅|π΄) β β1π β© β2π | π 1 π 2 π 3 |= π΄ β§ Β¬π΅}|.
|=
have Ξ£1 π
Ξ£2 |Ξ£3 .
Since β1π β© β2π = βπ β© (β(Ξ£3 )|β(Ξ£3 )), and for any
Proof. We first recall the following Lemma from [18]
(π΅|π΄) β βπ β© (β(Ξ£3 )|β(Ξ£3 )), πΞ ((π΅|π΄)) = πΞ1 ((π΅|π΄)) =
Lemma 7. Let Ξ£1 , Ξ£2 , Ξ£3 be disjoint subsignatures of Ξ£, let π
πΞ2 ((π΅|π΄)) (with Fact 1) we have:
1 2
|=
be an OCF. Then Ξ£1 π
Ξ£2 |Ξ£3 iff for all π β β¦(Ξ£1 ), π β
1 3 1 2 3 2 3 1
β¦(Ξ£2 ), and π 3 β β¦(Ξ£3 ), we have π
(π 1 π 2 π 3 ) = π
(π 1 π 3 ) + π (π, βπ ) = π (π π , βπ ) + π (π π , βπ ) β π (π , βπ )
2 3 3 1 3 1 2 3 2 3 2
π
(π π ) β π
(π ). = π (π π , βπ ) + π (π π , βπ ) β π (π , βπ ).
We now show that: (β ) for any π΄ β β(Ξ£π ) and π 3 β β(Ξ£3 ),
π
(π΄π 3 ) = min{π
(π 1 π 3 ) | π π π 2 π 3 |= π΄}. Wlog let π = 1 and
π = 2. Observe that by definition, π
(π΄π 3 ) = min{π
(π 1 π 2 π 3 ) | Lemma 10. Where β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 , π β {1, 2}, π β
βοΈ
π 1 π 2 π 3 |= π΄}. Consider some π 1 π 2 π 3 β Mod1,2,3 (π΄π 3 ) β(Ξ£1 ) and π 3 β β¦(Ξ£3 ), π β minβͺ―lex (Mod(π 3 β§ π)) iff π 1 β
s.t. π
(π 1 π 2 π 3 ) = π
(π΄π 3 ). With Lemma 7, π
(π 1 π 2 π 3 ) = Ξ
minβͺ―lex (Mod1,3 (π 3 β§ π)) and π 2 β minβͺ―lex Mod2,3 (π 3 ).
π
(π 1 π 3 ) + π
(π 2 π 3 ) β π
(π 3 ). Suppose now towards a contra- Ξ1 Ξ2
diction that π
(π 1 π 3 ) > π
(π΄π 3 ), i.e. there is some πβ1 πβ2 π 3 s.t.
πβ1 π 3 |= π΄π 3 and π
(πβ1 π 3 ) + π
(πβ2 π 3 ) < π
(π 1 π 3 ) + π
(π 2 π 3 ). Proof. For the β-direction, suppose π β minβͺ―lex (Mod(π 3 )).
Ξ
Suppose first that π
(πβ2 π 3 ) > π
(π 2 π 3 ). Then π
(πβ1 π 3 ) < Suppose now towards a contradiction that either (a) π 2 π 3 ΜΈβ
π
(π 1 π 3 ) and thus π
(πβ1 π 2 π 3 ) < π
(π 1 π 2 π 3 ), contradiction. minβͺ―lex (Mod2,3 (π 3 )) or (b) π 1 ΜΈβ minβͺ―lex (Mod1,3 (π 3 β§ π)).
Ξ2 Ξ1
Suppose therefore that π
(πβ2 π 3 ) β©½ π
(π 2 π 3 ). Then we can derive
that π
(πβ1 π 2 π 3 ) < π
(π 1 π 2 π 3 ), contradiction. ad. (b) Suppose that π π β minβͺ―lex (Mod2,3 (π 3 )) (the case
2 3
Ξ2
From the β , it follows immediately that π
(π΄π΅π 3 ) < π
(π΄π΅π 3 ) where also π 2 π 3 ΜΈβ minβͺ―lex (Mod2,3 (π 3 )) is similar).
iff π
(π΄π΅πΆπ 3 ) < π
(π΄π΅πΆπ 3 ) for any π΄, π΅ β β(Ξ£π ), πΆ β Ξ2
β(Ξ£π ) and π 3 β β(Ξ£3 ) (for π, π = 1, 2 and π ΜΈ= π). π 1 ΜΈβ minβͺ―lex (Mod1,3 (π 3 β§ π)) implies that there is
Ξ1
πππ
some π β²1 π 3 β Mod1,3 (π 3 β§π) s.t. π β²1 π 3 βΊlex 1 3
Ξ1 π π , i.e.
βοΈ for OCFs C
Proposition 8. An inductive inference operator : there is some π β©Ύ 0 s.t. for every π > π, π (π β²1 π 3 , β1π ) =
β β¦β π
Ξ satisfies CRel iff for any β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 , it π (π 1 π 3 , β1π ) and π (π β²1 π 3 , β1π ) < π (π 1 π 3 , β1π ) (with
holds that π
Ξπ = π
Ξ |Ξ£1 βͺΞ£3 . Lemma 9) this implies:
Proof. Similar to the proof of Proposition 5. π (π β²1 π 2 π 3 , βπ )
= π (π β²1 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π )
4. Lexicographic Inference Satisfies = π (π 1 π 2 π 3 , βπ )
Conditional Syntax Splitting = π (π 1 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π )
In this section, we show that for any conditional belief base that and
safely splits conditionally, conditional syntax splitting is satisfied.
We first need to show some intermediate results. π (π β²1 π 2 π 3 , βπ )
= π (π β²1 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π )
Fact 1. Where β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 , π β {1, 2} and
βοΈ
< π (π 1 π 2 π 3 , βπ )
(π΅|π΄) β βπ , πΞ ((π΅|π΄)) = πΞπ ((π΅|π΄))
= π (π 1 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π )
Proof. Immediate from Proposition 3.
which (since π β²1 π 2 π 3 β Mod(π 3 )) contradicts π β
The following Lemma shows that the components of vectors minβͺ―lex (π 3 ).
lex(π) can be simply combined by summation over disjoint sub- Ξ
languages (taking into account double counting): ad. (a) Similar.
The β-direction is similar.
2
Notice that it follows from Fact 1 that, given the Z-partition (Ξ1 , . . . , Ξπ )
of Ξ and Ξ£π β Ξ£, Ξππ = Ξπ β© (βπ |βπ ) for any 0 β©½ π β©½ π.
66
Proposition 11. πΆ lex satisfies CInd. basis of examples such as the Tweety-example, but no generic
formal description has been given.
Proof. Suppose that β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 . We show that
βοΈ
In this paper, we have developed the necessary tools to talk
Ξ£1 and Ξ£2 are independent w.r.t. βͺ―lex Ξ conditional on Ξ£3 , i.e. for about the drowning effect in a formally precise manner. Indeed,
any π β {1, 2}, for any π1π , π2π β β¦π , π 3 β β¦3 , π β {1, 2}, π ΜΈ= π, the first crucial notion is that of unrelatedness of propositions.
π1π π 3 βͺ―lex π 3 π π 3
Ξ π2 π iff π1 π π βͺ―lex π π 3
Ξ π2 π π for all π
π
β β¦π . This notion is formally captured by safe splitting into subbases
With Proposition 4 this is sufficient to show the proposition. For (Definition 7): given a belief base β, a proposition π΄ is unrelated
simplicity, we let π = 1 and π = 2, the other case follows by to a proposition πΆ iff β can be safely split into βοΈ
subbases β1 , β2
symmetry. conditional on a sub-alphabet Ξ£3 , i.e. β = β1 sΞ£1 ,Ξ£2 β2 | Ξ£3 ,
For the β-direction, suppose that π11 π 3 βͺ―lex 1 3
Ξ π2 π . We show and π΄ β β(Ξ£2 ) and πΆ β β(Ξ£1 βͺ Ξ£3 ). This means that the
1 2 3 lex 1 2 3 2
that π1 π π βͺ―Ξ π2 π π for all π β β¦2 . We first make the abstract situation of the drowning problem can be precisely de-
following observation that follows in view of Lemma 10. For any scribed by conditional syntax splitting. We see that the drowning
πβ2 β minβͺ―lex (Mod2,3 (π 3 )) and π = 1, 2: effect is nothing else than a violation of the postulate of condi-
Ξ2
tional independence (CInd): if we know that a typical property
ππ1 π 3 βlex 1 2 3
Ξ ππ πβ π .
π΅ of π΄π·-individuals (π΄π· |βΌ Ξ π΅) is unrelated to an exceptional
subclass πΆ of π΄π·, then we can also derive that if something is
Thus, for any π 2 β minβͺ―lex (Mod2,3 (π 3 )): π΄π·πΆ is typically π΅ (π΄π·πΆ |βΌ Ξ π΅). We illustrate this with the
Ξ2
Tweety-example:
π11 π 2 π 3 βͺ―lex 1 2 3
Ξ π2 π π . Example 8 (Example 2 ctd.). We already established in Example
βοΈ
6 that β = {(π |π), (π|π), (Β¬π |π)} {π,π},{π} {(π|π)} | {π}. It is
This means (with Lemma 9) that there is some π β©Ύ 0
now not hard to see that any inductive inference operator C that
s.t. π (π11 π 3 , β1π ) = π (π21 π 3 , β1π ) for every π > π and
satisfies (DI) and (CInd) avoids the drowning effect. In more
π (π11 π 3 , β1π ) β©½ π (π21 π 3 , β1π ). Thus, for any π 2 β β¦2 , it
detail, we have:
holds that (for any π > π):
π |βΌ Ξ π by DI (5)
π (π11 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π )
π β§ π |βΌ Ξ π by CInd and (5) (6)
= π (π21 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π23 , β1π )
For any inductive inference operator that additionally satisfies
and: Cut (i.e. from π΄ |βΌ π΅ and π΄ β§ π΅ |βΌ πΆ derive π΄ |βΌ πΆ), a postulate
that holds for any inductive inference operator based on TPOs
π (π11 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π ) [13], we obtain:
β©½ π (π21 π 3 , β1π ) + π (π 2 π 3 , β2π ) β π (π 3 , β1π ).
π |βΌ Ξ π by DI (7)
With Lemma 9 we have that π (ππ1 π 2 π 3 , βπ ) = π (ππ1 π 3 , β1π ) + π |βΌ Ξ π by Cut, (6) and (7) (8)
π (π 2 π 3 , β2π ) β π (π 3 , β3π ) for π = 1, 2 and π β©½ π and thus
π11 π 2 π 3 βͺ―lex 2 2 3 2
Ξ π1 π π (for any π β β¦2 ).
Summarizing, we can express our findings as follows:
The β-direction is similar. Proposition 13. Any inductive inference operator that satis-
Proposition 12. πΆ lex satisfies Rel. fies (CInd) does not βοΈ show the drowning problem (for β =
{(π |π), (π|π), (Β¬π |π)} {π,π},{π} {(π|π)} | {π}).
Proof. This follows immediately from Lemma 10. Indeed, we
We note that the drowning effect has not been defined in the
have that (for π΄, π΅ β β1 and a complete conjunction π· β β3 ):
lex literature in a general sense. Above, we provided, to the best
π΄π· |βΌ Ξ π΅ iff for all π β minβͺ―lex (π΄π·), π 1 π 3 |= π΅. With
Ξ of our knowledge, the first general definition of the drowning
Lemma 10, π β minβͺ―lex (π΄π·) iff π 1 β minβͺ―lex (π΄π·). Since problem. As we defined the drowning effect as a violation of
Ξ Ξ1
π΅ β β1 , this implies that if π1 π 3 β minβͺ―lex (π΄π·) then the postulate of conditional independence, it is trivial that any
Ξ1 inductive inference operator that satisfies (Cind) does not show
π 1 π 3 |= π΅.
the drowning problem interpreted in this general, formal sense.
From Proposition 11 and 12, we can immediately obtain the
main result of this section: 6. Lehmannβs desirable closure
Theorem 1. πΆ lex satisfies SynSplit. properties
Lehmann 1995 remarks that in addition to the properties encoded
5. The Drowning Effect as by rational closure, other properties for inductive inference op-
Conditional Independence erators might be desirable. In particular, he lists four properties:
presumption of typicality, presumption of independence, priority
As mentioned in the introduction, the drowning effect, illustrated of typicality and respect for specificity. All of these properties
by Example 2, is intuitively related to syntax splitting. In more are only explained informally and illustrated using examples in
detail, the drowning effect is constituted by the fact that according [1], and to the best of our knowledge, no attempts to formalize
to some inductive inference operators (e.g. system π), exceptional or generalize these notions has been made. In this section, we
subclasses (e.g. penguins) do not inherit any properties of the show how the desired behaviour for all but one of the examples
superclass (e.g. birds), even if these properties are unrelated to the given by [1] can be straightforwardly derived by assuming con-
reason for the subclass being exceptional (e.g. having beaks). To ditional inference relations satisfy (conditional) syntax splitting.
the best of our knowledge, discussion of the drowning effect in We now describe the four properties from [1] and their relation
the literature has been restricted to informal discussions on the with conditional syntax splitting:
67
Presumption of Typicality For a conditional belief base for This section thus shows that all four properties proposed in [1]
which (π₯|π) β β implies, for any inference relation |βΌ Ξ that are subsumed by (conditional) syntax splitting. Hence, any infer-
satisfies rational monotonicity (i.e. to derive from π΄ |βΌ π΅ and ence relation satisfying conditional syntax splitting also satisfies
π΄ ΜΈ|βΌ πΆ that π΄πΆ |βΌ π΅), πβ§π |βΌ Ξ π₯ or π |βΌ Ξ Β¬π. The presumption these properties.
of typicality obliges us, βin absence of a convincing reason to
accept the latterβ [1], to derive π β§ π |βΌ π₯. Lehmann does not
elaborate on what constitutes βa convincing reasonβ, but does 7. Related Work
state that for β1 = {(π₯|π)}, π β§ π |βΌ Ξ1 π₯ should hold. It is clear
that this behaviour follows from (Ind): The phenomenon of syntax splitting has been observed as early
as 1980 in [20] under the name of βsystem independenceβ. The
Fact 2. Let an inductive inference operator satisfying Ind and name syntax splitting was coined in [21] who studied it in the
β1 = {(π₯|π)} be given. Then π β§ π |βΌ Ξ1 π₯ context of belief revision. Later, it was studied for other forms of
belief revision in [22, 11], and for inductive inference operators
βοΈ Let Ξ£1 = {π, π₯} and Ξ£2 = {π}. Then clearly β1 =
Proof.
in [8]. Our paper is a direct continuation of the work done in
β1 Ξ£1 ,Ξ£2 β
and thus with (Ind) we have: π |βΌ Ξ1 π₯ iff π β§
π |βΌ Ξ1 π₯. Since (π₯|π) β β1 , with (DI), π |βΌ Ξ1 π₯ and thus [7], where we have shown that lexicographic inference satisfies
π β§ π |βΌ Ξ1 π₯. syntax splitting, and that the drowning effect is independent of
syntax splitting. This work thus solves an important open question,
Presumption of independence The presumption of inde- namely whether generalization of syntax splitting as studied in
pendence states that βeven if typicality is lost with respect to one [8, 7] can say something about the drowning effect.
consequent, we may still presume typicality with respect to an- Conditional independence for ranking functions has been stud-
other, unless there is a reason to the contraryβ [1]. It is illustrated ied in [12], for belief revision in [23], and for conditional belief
using the conditional belief base β2 = {(π₯|π), (Β¬π|π)}. Then revision in [18]. To the best of our knowledge, it has not been con-
presumption of independence justifies us in deriving πβ§π |βΌ Ξ2 π₯. sidered for inductive inference operators. We connect inductive
Fact 3. Let the inductive inference operator satisfying CInd inference operators with these works, as we show that the same
and β2 = {(π₯|π), (Β¬π|π)} be given. Then π β§ π |βΌ Ξ2 π₯. conditions of conditional independence as studied in [12, 18] on
the total preorders respectively OCFs underlying inductive in-
Proof. ItβοΈ can be easily verified that β2 = ference operators (Definition 11) guarantee conditional syntax
{(π₯|π)} s{π₯},{π} {(Β¬π|π)} | {π}. With DI, we have splitting.
π |βΌ Ξ2 π₯. With CInd we have π β§ π |βΌ Ξ2 π₯. In [16], the class of RC-extending inference relations is de-
scribed. In future work, we plan to give a complete characterisa-
Priority of typicality Priority of typicality gives, in situations
tion of the subclass of RC-extending inference relations satisfying
where the presumption of typicality and the presumption of inde-
syntax splitting.
pendence clash, priority to the former. It is illustrated using the
conditional belief base β3 = {(π₯|π), (Β¬π₯|π β§ π)}. The presump-
tion of typicality justifies us in deriving π β§ π β§ π |βΌ Ξ3 Β¬π₯ (since 8. Conclusion
no reason can be found for accepting π β§ π |βΌ Ξ3 Β¬π), whereas
we can derive both π β§ π β§ π |βΌ Β¬π₯ and π β§ π β§ π |βΌ Ξ3 π₯ with The main contributions of this paper are the following: (1) we
the presumption of independence. Priority of typicality demands define the concept of conditional syntax splitting for inductive
that priority is given to π β§ π β§ π |βΌ Ξ3 Β¬π₯. inference operators, thus bringing a notion of conditional indepen-
Fact 4. Let the inductive inference operator satisfying Ind and dence between sub-signatures to the realm of inductive inference
β3 = {(π₯|π), (Β¬π₯|π β§ π)} be given. Then π β§ π β§ π |βΌ Ξ3 Β¬π₯. operators; (2) we show that lexicographic inference satisfies con-
ditional syntax splitting; (3) we show how the drowning effect
Proof. Let Ξ£ 1 = {π, π, π₯} and Ξ£2 = {π}. Then clearly β3 = can be seen as a violation of conditional syntax splitting, and (4)
βοΈ
β3 Ξ£1 ,Ξ£2 β
and thus with (Ind) we have: π β§ π |βΌ Ξ3 Β¬π₯ iff we show how Lehmanβs desirable properties can be derived from
π β§ π β§ π |βΌ Ξ3 Β¬π₯. Since (Β¬π₯|π β§ π) β β3 , with (DI), we have (conditional) syntax splitting.
π β§ π |βΌ Ξ3 Β¬π₯. There are several main avenues for further work. Firstly, it
Lehmann 1995 uses a second example to illustrate priority of will be interesting to investigate whether other inductive infer-
typicality: ence operators that satisfy (non-conditional) syntax splitting, such
as c-representations ([14, 8] and system W [24, 25], also satisfy
Example 9 (Example 5 in [1]). Let β4 = conditional syntax splitting. Secondly, we want to develop algo-
{(π₯|π), (π|β€), (Β¬π₯|π)} and argues that here, π β§ π |βΌ Ξ4 π₯ rithms for deciding whether and how a conditional belief base
should hold. Here, Lehmann argues that (π|β€) allows us to can be safely split, and investigate their computational complexity.
infer π |βΌ Ξ4 π and thus π is βdefeasibly more specific than πβ. Thirdly, we plan to apply our results to applications of lexico-
Therefore, π β§ π |βΌ Ξ4 π₯ should hold instead of π β§ π |βΌ Ξ4 Β¬π₯. graphic inference to (probabilistic) description logics, and take
However, we argue that this belief base and the resulting desir- advantage of them for the development of efficient implementa-
able inferences cannot be explained in terms of independence, as tions of lexicographic inference.
β4 cannot be safely split into {(π₯|π)} and {(π|β€), (Β¬π₯|π)}.
Respect for specificity The final property, respect for speci-
ficity, gives guidelines on how to decide when the two presump-
tions clash: in that case the inference based on the assertion with
a more specific antecedent should be used to guide the inferential
process. These properties are illustrated in [1] using β3 and β4
as well.
68
Acknowledgments [20] J. Shore, R. Johnson, Axiomatic derivation of the principle
of maximum entropy and the principle of minimum cross-
The work of Jesse Heyninck was partially supported by Fonds entropy, IEEE Transactions on Information Theory IT-26
Wetenschappelijk Onderzoek β Vlaanderen (project G0B2221N). (1980) 26β37.
[21] R. Parikh, Beliefs, belief revision, and splitting languages,
Logic, language and computation 2 (1999) 266β268.
References [22] T. Aravanis, P. Peppas, M.-A. Williams, Full characteriza-
tion of parikhβs relevance-sensitive axiom for belief revision,
[1] D. Lehmann, Another perspective on default reasoning,
Journal of Artificial Intelligence Research 66 (2019) 765β
Annals of mathematics and artificial intelligence 15 (1995)
792.
61β82.
[23] M. J. Lynn, J. P. Delgrande, P. Peppas, Using conditional
[2] G. Casini, U. Straccia, Lexicographic closure for defeasi-
independence for belief revision, in: Proceedings AAAI-22,
ble description logics, in: Proc. of Australasian Ontology
2022.
Workshop, volume 969, 2012, pp. 28β39.
[24] C. Komo, C. Beierle, Nonmonotonic reasoning from con-
[3] T. Lukasiewicz, Expressive probabilistic description logics,
ditional knowledge bases with system w, Annals of Mathe-
Artificial Intelligence 172 (2008) 852β883.
matics and Artificial Intelligence (2021) 1β38.
[4] R. Booth, G. Casini, T. A. Meyer, I. J. Varzinczak, On the en-
[25] J. Haldimann, C. Beierle, Inference with system w satisfies
tailment problem for a logic of typicality, in: Twenty-Fourth
syntax splitting, arXiv preprint arXiv:2202.05511 (2022).
International Joint Conference on Artificial Intelligence,
2015.
[5] M. Goldszmidt, J. Pearl, Qualitative probabilities for default
reasoning, belief revision, and causal modeling, AI 84
(1996) 57β112.
[6] T. Eiter, T. Lukasiewicz, Default reasoning from conditional
knowledge bases: Complexity and tractable cases, Artificial
Intelligence 124 (2000) 169β241.
[7] J. Heyninck, G. Kern-Isberner, T. Meyer, Lexicographic
entailment, syntax splitting and the drowning problem, in:
Accepted for IJCAI 2022, 2022.
[8] G. Kern-Isberner, C. Beierle, G. Brewka, Syntax splitting=
relevance+ independence: New postulates for nonmonotonic
reasoning from conditional belief bases, in: Proceedings of
the International Conference on Principles of Knowledge
Representation and Reasoning, volume 17, 2020, pp. 560β
571.
[9] B. de Finetti, Theory of probability (2 vols.), 1974.
[10] D. Makinson, General theory of cumulative inference,
in: International Workshop on Non-Monotonic Reasoning
(NMR), Springer, 1988, pp. 1β18.
[11] G. Kern-Isberner, G. Brewka, Strong syntax splitting for
iterated belief revision, in: C. Sierra (Ed.), Proceedings
International Joint Conference on Artificial Intelligence,
IJCAI 2017, ijcai.org, 2017, pp. 1131β1137.
[12] W. Spohn, Ordinal conditional functions: A dynamic theory
of epistemic states, in: Causation in decision, belief change,
and statistics, Springer, 1988, pp. 105β134.
[13] S. Kraus, D. Lehmann, M. Magidor, Nonmonotonic reason-
ing, preferential models and cumulative logics, Artificial
intelligence 44 (1990) 167β207.
[14] G. Kern-Isberner, Handling conditionals adequately in un-
certain reasoning and belief revision, Journal of Applied
Non-Classical Logics 12 (2002) 215β237.
[15] D. Lehmann, M. Magidor, What does a conditional knowl-
edge base entail?, Artificial intelligence 55 (1992) 1β60.
[16] G. Casini, T. Meyer, I. Varzinczak, Taking defeasible en-
tailment beyond rational closure, in: European Conference
on Logics in Artificial Intelligence, Springer, 2019, pp. 182β
197.
[17] M. Ritterskamp, G. Kern-Isberner, Preference-based default
reasoning., in: FLAIRS Conference, 2008, pp. 672β677.
[18] G. Kern-Isberner, C. Beierle, J. Heyninck, Conditional
independence for iterated belief revision, in: Accepted for
IJCAI 2022, 2022.
[19] W. Spohn, The laws of belief: Ranking theory and its philo-
sophical applications, Oxford University Press, 2012.
69