Nonmonotonic Inferences with Qualitative Conditionals Based on Preferred Structures on Worlds

Abstract

A conditional knowledge base $\mathcal {R}$ is a set of conditionals of the form “If A then usually B”. Using structural information derived from the conditionals in $\mathcal {R}$, we introduce the preferred structure relation on worlds. The preferred structure relation is the core ingredient of a new inference relation called system W inference that inductively completes the knowledge given explicitly in $\mathcal {R}$. We show that system W exhibits desirable inference properties like satisfying system P and avoiding, in contrast to, e.g., system Z, the drowning problem. It fully captures and strictly extends both system Z and skeptical c-inference. In contrast to skeptical c-inference, it does not require to solve a complex constraint satisfaction problem, but is as tractable as system Z.

1 Introduction

In the area of knowledge representation and reasoning, conditionals play a prominent role. Nonmonotonic reasoning investigates qualitative conditionals of the form “If A then usually B”. Various semantical approaches for inferences based on sets of such conditionals as well as criteria and postulates for evaluating the obtained inference relations have been proposed (cf. [1, 4, 7, 8, 10, 12, 14, 19,20,21,22]). Among the different semantical models of conditional knowledge bases are Spohn’s ordinal conditional functions (OCFs)  [24, 25], also called ranking functions. An OCF $\kappa$ assigns a degree of surprise (or degree of implausibility) to each world $\omega$, the higher the value $\kappa (\omega )$ assigned to $\omega$, the more surprising $\omega$. Each $\kappa$ that accepts a set $\mathcal {R}$ of conditionals, called a knowledge base, induces a nonmonotonic inference relation that inductively completes the explicit knowledge given in $\mathcal {R}$.

Two inference relations which are defined based on specific OCFs obtained from a knowledge base $\mathcal {R}$ have received some attention: system Z  [13, 23] and c-representations  [14, 15], or the induced inference relations, respectively, both show excellent inference properties. System Z is based upon the ranking function $\kappa ^Z$, which is the unique Pareto-minimal OCF that accepts $\mathcal {R}$. The definition of $\kappa ^Z$ crucially relies on the notions of tolerance and of inclusion-maximal ordered partition of $\mathcal {R}$ obtained via the tolerance relation  [13, 23]. Among the OCF models of $\mathcal {R}$, c-representations are special models obtained by assigning an individual impact to each conditional and generating the world ranks as the sum of impacts of falsified conditionals [14, 15]. While for each consistent $\mathcal {R}$, the system Z ranking function $\kappa ^Z$ is uniquely determined, there may be many different c-representations of $\mathcal {R}$. Skeptical c-inference [2, 5] is the inference relation obtained by taking all c-representations of $\mathcal {R}$ into account.

It is known that system Z and skeptical c-inference both satisfy system P [5, 13, 19] and other desirable properties. Furthermore, there are system Z inferences that are not obtained by skeptical c-inference, and on the other hand, there are skeptical c-inferences that are not system Z inferences [5]. Another notable difference between system Z and skeptical c-inference is that the single unique system Z model [23] can be computed much easier than skeptical c-inference which involves many models obtained from the solutions of a complex constraint satisfaction problem [5]. In recently published work [18], we showed that the exponential lower bound $2^{n-1}$ is needed as possible impact factor for c-representations to fully realize skeptical c-inference, supporting the observation that skeptical c-inference is less tractable than system Z inference (cf. [5, 13]).

Inspired by our findings in [18], here we develop the preferred structure relation on worlds and propose the new nonomonotonic system W inference based on it. The main contributions of this paper are:

• We introduce the preferred structure relation $<^\mathsf{{w}}_{\mathcal {R}}$on worlds based on the notions of tolerance and verification/falsification behavior of a knowledge base $\mathcal {R}$.

• By exploiting $<^\mathsf{{w}}_{\mathcal {R}}$, we develop a new inference relation, called system W inference, which is as tractable as system Z.

• We prove that system W inference captures and strictly extends both system Z inference and skeptical c-inference.

• We show that system W inference exhibits desirable inference properties like satisfying the axioms of system P and avoiding the drowning problem.

The rest of the paper is organized as follows. After briefly recalling the required background in Sect. 2, we introduce the preferred structure on worlds and prove several of its properties in Sect. 3. In Sect. 4, we give the formal definition of system W, illustrate it with various examples and show its main properties. In Sect. 5, we conclude and point out future work.

2 Conditional Logic, System Z, and C-Representations

Let $\varSigma =\{v_1,...,v_m\}$ be a propositional alphabet. A literal is the positive ($v_i$) or negated ($\overline{v_i}$) form of a propositional variable, $\dot{v}_i$ stands for either $v_i$ or $\overline{v_i}$. From these we obtain the propositional language $\mathcal {L}$ as the set of formulas of $\varSigma$ closed under negation $\lnot$, conjunction $\wedge$, and disjunction $\vee$. For shorter formulas, we abbreviate conjunction by juxtaposition (i.e., AB stands for $A\wedge B$), and negation by overlining (i.e., $\overline{A}$ is equivalent to $\lnot A$). Let $\varOmega _{\varSigma }$ denote the set of possible worlds over $\mathcal {L}$; $\varOmega _{\varSigma }$ will be taken here simply as the set of all propositional interpretations over $\mathcal {L}$ and can be identified with the set of all complete conjunctions over $\varSigma$; we will often just write $\varOmega$ instead of $\varOmega _{\varSigma }$. For $\omega \in \varOmega$, $\omega \models A$ means that the propositional formula $A \in \mathcal {L}$ holds in the possible world $\omega$. With $\varOmega _A = \{\omega \in \varOmega _{\varSigma } \mid \omega \models A\}$, we denote the set of all worlds in which A holds, and $\equiv$ denotes propositional equivalence.

A conditional (B|A) with $A,B\in \mathcal {L}$ encodes the defeasible rule “if A then normally B” and is a trivalent logical entity with the evaluation [11, 14]

(1)

An ordinal conditional function (OCF, ranking function)  [24, 25] is a function $\kappa :\varOmega \rightarrow \mathbb {N}_0\cup \{\infty \}$ that assigns to each world $\omega \in \varOmega$ an implausibility rank $\kappa (\omega )$: the higher $\kappa (\omega )$, the more surprising $\omega$ is. OCFs have to satisfy the normalization condition that there has to be a world that is maximally plausible, i.e., $\kappa ^{-1}(0)\ne \emptyset$. The rank of a formula A is defined by $\kappa (A)=\min \{\kappa (\omega ) \mid \omega \models A\}$ where $\min \emptyset = \infty$. An OCF $\kappa$ accepts a conditional $(B|A)$, denoted by $\kappa \models (B|A)$, if the verification of the conditional is less surprising than its falsification, i.e., $\kappa \models (B|A)$ iff $\kappa (AB) < \kappa (A\overline{B})$. This can also be understood as a nonmonotonic inference relation between the premise A and the conclusion B: Basically, we say that A $\kappa$-entails B, written , if $\kappa$ accepts (B|A); formally, this is given by

(2)

Note that the reason for including the disjunctive condition in (2) is to ensure that satisfies supraclassicality, i.e., $A \models B$ implies , also for the case $A \equiv \bot$ as it is required, for instance, by the reflexivity axiom of system P [1, 19]. Let us remark that $\kappa$-entailment is based on the total preorder on possible worlds induced by a ranking function and can be expressed equivalently by:

(3)

The acceptance relation is extended as usual to a set $\mathcal {R}$ of conditionals, called a knowledge base, by defining $\kappa \models \mathcal {R}$ iff $\kappa \models (B|A)$ for all $(B|A) \in \mathcal {R}$. This is synonymous to saying that $\kappa$ is admissible with respect to $\mathcal {R}$ [13], or that $\kappa$ is a ranking model of $\mathcal {R}$. $\mathcal {R}$ is consistent iff it has a ranking model.

Two inference relations which are defined by specific OCFs obtained from a knowledge base $\mathcal {R}$ have received some attention: system Z  [23] and c-representations  [14, 15], or the induced inference relations, respectively, both show excellent inference properties. We recall both approaches briefly.

System Z  [23] is based upon the ranking function $\kappa ^Z$, which is the unique Pareto-minimal OCF that accepts $\mathcal {R}$. The definition of $\kappa ^Z$ crucially relies on the notion of tolerance. A conditional $(B|A)$ is tolerated by a set of conditionals $\mathcal {R}$ if there is a world $\omega \in \varOmega$ such that $\omega \models AB$ and $\omega \models \bigwedge _{i=1}^n(\overline{A_i} \vee B_i)$, i.e., iff $\omega$ verifies $(B|A)$ and does not falsify any conditional in $\mathcal {R}$. For every consistent knowledge base, the notion of tolerance yields an ordered partition $(\mathcal {R}_0,...,\mathcal {R}_k)$ of $\mathcal {R}$, where each $\mathcal {R}_i$ is tolerated by $\bigcup _{j=i}^k\mathcal {R}_j$. The inclusion-maximal partition of $\mathcal {R}$, in the following denoted by ${ OP }(\mathcal {R}) = (\mathcal {R}_0,\ldots ,\mathcal {R}_k)$, is the ordered partition of $\mathcal {R}$ where each $\mathcal {R}_i$ is the (with respect to set inclusion) maximal subset of $\bigcup _{j=i}^k\mathcal {R}_j$ that is tolerated by $\bigcup _{j=i}^k\mathcal {R}_j$. This partitioning is unique due to the maximality and can be computed using the consistency test algorithm given in  [13]; for an inconsistent knowledge base $\mathcal {R}$, ${ OP }(\mathcal {R})$ does not exist. Using ${ OP }(\mathcal {R}) = (\mathcal {R}_0,\ldots ,\mathcal {R}_k)$, the system Z ranking function $\kappa ^Z$ is defined by

$$\begin{aligned} \kappa ^Z(\omega ) := {\left\{ \begin{array}{ll} 0 \, , &{} \text { if } \omega \text { does not falsify any conditional }r\in \mathcal {R}, \\ 1 + \max _{ \begin{array}{c} 1\leqslant i \leqslant n \\ \omega \models A_i \overline{B_i } \end{array} } Z(r_i) ,&\text {otherwise} , \end{array}\right. } \end{aligned}$$

(4)

where the function $Z:\mathcal {R} \rightarrow \mathbb {N}_0$ is given by $Z(r_i) = j$ if $r_i \in \mathcal {R}_j$.

Definition 1

(system Z inference, [13]). Let $\mathcal {R}$ be a knowledge base and let A, B be formulas. We say that B can be inferred from A by system Z in the context of $\mathcal {R}$, denoted by , iff holds.

Among the OCF models of $\mathcal {R}$, c-representations are special models obtained by assigning an individual impact to each conditional and generating the world ranks as the sum of impacts of falsified conditionals. For an in-depth introduction to c-representations and their use of the principle of conditional preservation ensured by respecting conditional structures, we refer to [14, 15]. The central definition is the following:

Definition 2

(c-representation [14]). A c-representation of a knowledge base $\mathcal {R}$ is a ranking function constructed from with integer impacts $\eta _{i}\in \mathbb {N}_0 \, , i \in \{1\, , \ldots \, , n \}$ assigned to each conditional $(B_i|A_i)$ such that $\kappa$ accepts $\mathcal {R}$ and is given by:

(5)

We will denote the set of all c-representations of $\mathcal {R}$ by $\mathcal {O}(CR(\mathcal {R}))$.

As every ranking model of $\mathcal {R}$, each c-representation gives rise to an inference relation according to (2). While for each consistent $\mathcal {R}$, the system Z ranking function $\kappa ^Z$ is uniquely determined, there may be many different c-representations of $\mathcal {R}$. C-inference [2, 5] is an inference relation taking all c-representations of $\mathcal {R}$ into account.

Definition 3

(c-inference, [2]). Let $\mathcal {R}$ be a knowledge base and let A, B be formulas. B is a (skeptical) c-inference from A in the context of $\mathcal {R}$, denoted by , iff holds for all c-representations $\kappa$ for $\mathcal {R}$.

In [5] a modeling of c-representations as solutions of a constraint satisfaction problem $CR (\mathcal {R})$ is given and shown to be sound and complete with respect to the set of all c-representations of $\mathcal {R}$.

Definition 4

($\varvec{ CR (\mathcal {R})}$ [2]). Let $\mathcal {R}= \{(B_1|A_1),\ldots ,(B_n|A_n)\}$. The constraint satisfaction problem for c-representations of $\mathcal {R}$, denoted by $CR (\mathcal {R})$, on the constraint variables $\{\eta _{1}, \ldots , \eta _{n}\}$ ranging over $\mathbb {N}_0$ is given by the conjunction of the constraints, for all $i \in \{1,\ldots ,n\}$:

$$\begin{aligned}&\eta _{i} \geqslant 0 \end{aligned}$$

(6)

$$\begin{aligned}&\eta _{i} > \min _{\omega \models A_i B_i} \sum _{\begin{array}{c} j \ne i \\ \omega \models A_j \overline{B_j} \end{array}} \eta _{j} - \min _{\omega \models A_i \overline{B}_i} \sum _{\begin{array}{c} j \ne i \\ \omega \models A_j \overline{B_j} \end{array}} \eta _{j} \end{aligned}$$

(7)

A solution of $CR (\mathcal {R})$ is an $n$-tuple $(\eta _{1}, \ldots , \eta _{n}) \in \mathbb {N}_0^n .$ For a constraint satisfaction problem $CSP$, the set of solutions is denoted by $Sol ( CSP )$. Thus, with $Sol ( CR (\mathcal {R}))$ we denote the set of all solutions of $CR (\mathcal {R})$.

Proposition 1

(soundness and completeness of $CR (\mathcal {R})$ [5]). Let $\mathcal {R} = \{(B_1|A_1), \ldots , (B_n|A_n) \}$ be a knowledge base. With as in (5), we then have:

(8)

Example 1

($\mathcal {R}_{bird}$). To illustrate the definitions and concepts presented in this paper let us consider an instance of the well known penguin bird example. This example is our running example and it will be continued and extended throughout the paper. Consider the propositional alphabet $\varSigma = \{p \, , b \, , f \}$ representing whether something is a penguin (p), whether it is a bird (b), or whether it can fly (f). Thus, the set of worlds is $\varOmega = \{ p \,b \,f \, , p \, b\, \overline{f} \, , p \, \overline{b} \, f \, , p \, \overline{b} \, \overline{f} \, , \overline{p} \, b \, f \, , \overline{p}\, b \,\overline{f} \, , \overline{p}\, \overline{b} \,f \, ,\overline{p} \, \overline{b} \, \overline{f} \}$. The knowledge base $\mathcal {R}_{\text {bird}} = \{r_1\, , r_2\, , r_3 \, , r_4 \}$ contains the conditionals

For $\mathcal {R}_0=\{(f|b)\}$ and $\mathcal {R}_1={\mathcal {R}_{ bird }}\setminus \mathcal {R}_0$ we have the ordered partitioning $(\mathcal {R}_0,\mathcal {R}_1)$ such that every conditional in $\mathcal {R}_0$ is tolerated by $\mathcal {R}_0\cup \mathcal {R}_1={\mathcal {R}_{ bird }}$ and every conditional in $\mathcal {R}_1$ is tolerated by $\mathcal {R}_1$. For instance, $(f|b)$ is tolerated by ${\mathcal {R}_{ bird }}$ since there is, for example, the world $\overline{p}bf$ with $\overline{p}bf\models bf$ as well as $\overline{p}bf\models (p\Rightarrow \overline{f})\wedge (pb\Rightarrow \overline{f})\wedge (p\Rightarrow b)$. Furthermore $(\mathcal {R}_0 \, , \mathcal {R}_1)$ is indeed the inclusion-maximal partition of $\mathcal {R}$. Therefore, $\mathcal {R}$ is consistent. An OCF $\kappa$ that accepts ${\mathcal {R}_{ bird }}$ is:

$\omega$	$p\,b\,f$	$p\,b\,\overline{f}$	$p\,\overline{b}\,f$	$p\,\overline{b}\,\overline{f}$	$\overline{p}\,b\,f$	$\overline{p}\,b\,\overline{f}$	$\overline{p}\,\overline{b}\,f$	$\overline{p}\,\overline{b}\,\overline{f}$
$\kappa (\omega )$	2	1	2	2	0	1	0	0

For instance, we have $\kappa \models (f|b)$ since $\kappa (bf)=\min \{\kappa (pbf),\, \kappa (\overline{p}bf)\}=\min \{2,0\}=0$ and $\kappa (b\overline{f})=\min \{\kappa (pb\overline{f}),\, \kappa (\overline{p}b\overline{f})\}=\min \{1,1\}=1$ and therefore $\kappa (bf)<\kappa (b\overline{f})$.

3 Preferred Structure on Worlds

Aiming at developing a nonmonotonic inference relation combining advantages of system Z like tractability and of skeptical c-inference like, for instance, avoidance of the downing problem [9, 23], we first introduce the new notion of preferred structure on worlds with respect to a knowledge base $\mathcal {R}$. The idea is to take into account both the tolerance information expressed by the ordered partition of $\mathcal {R}$ and the structural information which conditionals are falsified.

Definition 5

($\xi ^j$, $\xi$, preferred structure $<^\mathsf{{w}}_{\mathcal {R}}$ on worlds). Consider a consistent knowledge base $\mathcal {R} = \{ r_i=(B_i|A_i) \mid i \in \{1, \ldots , n\} \}$ with ${ OP }(\mathcal {R}) = (\mathcal {R}_0,\ldots ,\mathcal {R}_k)$. For $j \in \{0,\ldots ,k\}$, $\xi ^j$ and $\xi$ are the functions mapping worlds to the set of falsified conditionals from the tolerance partition $\mathcal {R}_j$ and from $\mathcal {R}$, respectively, given by

$$\begin{aligned} \xi ^j (\omega )&:= \{ r_i \in \mathcal {R}_ j \mid \omega \models A_i \overline{B_i } \}, \end{aligned}$$

(9)

$$\begin{aligned} \xi (\omega )&:= \{ r_i \in \mathcal {R} \mid \omega \models A_i \overline{B_i } \}. \end{aligned}$$

(10)

The preferred structure on worlds is given by the binary relation $<^\mathsf{{w}}_{\mathcal {R}}\subseteq \varOmega \times \varOmega$ defined by, for any $\omega \, , \omega ' \in \varOmega$,

(11)

Thus, $\omega <^\mathsf{{w}}_{\mathcal {R}}\omega '$ if and only if $\omega$ falsifies strictly less conditionals than $\omega '$ in the partition with the biggest index m where the conditionals falsified by $\omega$ and $\omega '$ differ. The preferred structure on worlds will be the basis for defining a new inference relation induced by $\mathcal {R}$. Before formally defining this new inference relation and elaborating its properties, we proceed by illustrating the preferred structure on worlds for a knowledge base $\mathcal {R}$, relating it to c-representations of $\mathcal {R}$, and proving a set of its properties that will be useful for investigating the characteristics and properties of the resulting inference relation.

Example 2

( $<^\mathsf{{w}}_{{\mathcal {R}_{ bird }}}$). Let us determine the preferred structure on worlds $<^\mathsf{{w}}_{{\mathcal {R}_{ bird }}}$ for the knowledge base ${\mathcal {R}_{ bird }}$ from Example 1 whose verification/falsification behavior is shown in Table 1. The inclusion-maximal partition ${ OP }({\mathcal {R}_{ bird }}) = (\mathcal {R}_0, \mathcal {R}_1)$ is given by $\mathcal {R}_0 = \{ r_1 = (f | b) \}$ and $\mathcal {R}_1 = \{ r_2 = (\overline{f} | p) \, , r_3 = (\overline{f} | bp) \, , r_4 = (b | p) \}$. Figure 1 shows the preferred structure on worlds $<^\mathsf{{w}}_{{\mathcal {R}_{ bird }}}$ for the knowledge base ${\mathcal {R}_{ bird }}$. An edge $\omega \rightarrow \omega '$ between two worlds indicates that $\omega <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} \omega '$. The full relation $<^\mathsf{{w}}_{{\mathcal {R}_{ bird }}}$ is obtained from the transitive closure of $\rightarrow$ in Fig. 1.

Table 1. Verification/falsification behavior of the knowledge base ${\mathcal {R}_{ bird }}$; ($\mathsf {v}$) indicates verification, ($\mathsf {f}$) falsification, and ($-$) non-applicability. The OCF $\kappa ^Z$ is the ranking function obtained from ${\mathcal {R}_{ bird }}$ using system Z.

Fig. 1.

The preferred structure relation $<^\mathsf{{w}}_{{\mathcal {R}_{ bird }}}$ on worlds for the knowledge base ${\mathcal {R}_{ bird }}$.

The following proposition can be seen as a generalization of a result from [6]. It extends [6, Proposition 15] to the relation $<^\mathsf{{w}}_{\mathcal {R}}$ and to arbitrary knowledge bases, not just knowledge bases only consisting of conditional facts as in [6, Proposition 15]. It tells us that the set of c-representations is rich enough to guarantee the existence of a particular c-representation fulfilling the ordering constraints given in the proposition.

Proposition 2

Let $\mathcal {R} = \{ r_i = (B_i|A_i) \mid i =1 \, , \ldots \, , n \}$ be a consistent knowledge base, let $\omega ' \in \varOmega$ and let $\varOmega _V \subseteq \varOmega$. Assume that $\omega \not <^\mathsf{{w}}_{\mathcal {R}}\omega '$ for all $\omega \in \varOmega _V$. Then there exists a solution and thus a c-representation, such that, for all $\omega \in \varOmega _V$, we have:

(12)

Proof

(Sketch) Due to lack of space, we give a sketch of the proof. The claim follows by combining the following two statements:

• (i) If $\eta _i \in \mathbb {N} \, , i \in \{1\, , \ldots \, , n \}$, satisfy

  $$\begin{aligned} \eta _i > \sum _{ \begin{array}{c} j \in \{1 , \ldots , n \} \\ r_j \in \bigcup _{l=0}^{m-1} \mathcal {R}_l \end{array} } \eta _j \end{aligned}$$

  (13)

  for all $i \in \{ 1 \, , \ldots \, , n \}$ where $m=m(i)\in \{0\, , \ldots \, , k \}$ with $r_i \in \mathcal {R}_m$ then is a solution of $CR(\mathcal {R})$ and so defined as in (5) is a c-representation of $\mathcal {R}$.

• (ii) Because of $\omega \not <^\mathsf{{w}}_{\mathcal {R}}\omega '$ for all $\omega \in \varOmega _V$ we can choose satisfying (13) such that defined as in (5) satisfies (12) for all $\omega \in \varOmega _V$.

A complete proof that (i) and (ii) hold is given in the full version of this paper [17].    $\square$

The rest of this section is dedicated to the investigation of further properties of the relation $<^\mathsf{{w}}_{\mathcal {R}}$. Let us start with a lemma that tells us that worlds falsifying the same sets of conditionals are equivalent with respect to $<^\mathsf{{w}}_{\mathcal {R}}$.

Lemma 1

Let $\mathcal {R}= \{ (B_i|A_i) \mid i =1, \ldots , n \}$ be a knowledge base, and let $\omega _1 \, , \omega _2 \in \varOmega$ falsify the same sets of conditionals, i.e., for all $i \in \{1\, , \ldots \, , n \}$, we have $\omega _1 \models A_i \overline{B}_i$ iff $\omega _2 \models A_i \overline{B}_i$. Then $\omega _1 \,, \omega _2$ behave exactly the same way with respect to $\mathcal {R}$, i.e., for all $\omega \in \varOmega$, the following equivalences hold:

$$\begin{aligned} \omega<^\mathsf{{w}}_{\mathcal {R}}\omega _1 \quad \textit{iff } \quad \omega<^\mathsf{{w}}_{\mathcal {R}}\omega _2 \, , \\ \omega _1<^\mathsf{{w}}_{\mathcal {R}}\omega \quad \textit{iff } \quad \omega _2 <^\mathsf{{w}}_{\mathcal {R}}\omega \, . \end{aligned}$$

Proof

The claim follows from $\xi ^i(\omega _1) = \xi ^i(\omega _2)$ for all $i \in \{0 \, , \ldots \, , k \}$.    $\square$

In general, the relation $<^\mathsf{{w}}_{\mathcal {R}}$ cannot be obtained from a ranking function.

Lemma 2

There exists a knowledge base $\mathcal {R}$ such that there is no ranking function $\kappa : \varOmega \rightarrow \mathbb {N}_0^{\infty }$ with $\omega _1 <^\mathsf{{w}}_{\mathcal {R}}\omega _2$ iff $\kappa (\omega _1) < \kappa (\omega _2)$.

Proof

The proof is by contradiction. Assume there is a ranking function $\kappa : \varOmega \rightarrow \mathbb {N}_0^{\infty }$ with $\omega _1 <^\mathsf{{w}}_{\mathcal {R}}\omega _2$ iff $\kappa (\omega _1) < \kappa (\omega _2)$ for ${\mathcal {R}_{ bird }}$. For $<^\mathsf{{w}}_{\mathcal {R}}$ (cf. Fig. 1) we have $p \, b \, f \not <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} p \, \overline{b} \, f$ and $p \, \overline{b} \, f \not <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} p \, b \, f$ and furthermore $p \, b \, f \not <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} p \, \overline{b} \, \overline{f}$ and $p \, \overline{b} \, \overline{f} \not <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} p \, b \, f$. Therefore, we obtain $\kappa (p \, b \, f ) = \kappa ( p \, \overline{b} \, f)$ and $\kappa (p \, b \, f = \kappa (p \, \overline{b} \, \overline{f})$. Thus, $\kappa ( p \, \overline{b} \, f) = \kappa (p \, \overline{b} \, \overline{f})$ which is a contradiction to $p \, \overline{b} \, \overline{f} <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} p \, \overline{b} \, f$.    $\square$

Let us end this subsection by proving that $<^\mathsf{{w}}_{\mathcal {R}}$ defines a strict partial order.

Lemma 3

The relation $<^\mathsf{{w}}_{\mathcal {R}}$ is irreflexive, asymmetric, and transitive, meaning that $<^\mathsf{{w}}_{\mathcal {R}}$ is a strict partial order.

Proof

Condition (11) immediately yields that $<^\mathsf{{w}}_{\mathcal {R}}$ is irreflexive and asymmetric. It remains to show that $<^\mathsf{{w}}_{\mathcal {R}}$ is transitive. Define $a := \max \{ i \in \{0, \ldots , k \} \mid \xi ^i(\omega _1) \ne \xi ^i(\omega _2) \}$ and $b := \max \{ i \in \{0, \ldots , k \} \mid \xi ^i(\omega _2) \ne \xi ^i(\omega _3) \}$. Then $\omega _1 <^\mathsf{{w}}_{\mathcal {R}}\omega _2$ and $\omega _2 <^\mathsf{{w}}_{\mathcal {R}}\omega _3$ is equivalent to $\xi ^a(\omega _1) \subsetneqq \xi ^a(\omega _2)$ and $\xi ^b(\omega _2) \subsetneqq \xi ^b(\omega _3)$.

If $a = b$ then $\xi ^a(\omega _1) \subsetneqq \xi ^a(\omega _3)$ and $a = \max \{ i \in \{0, \ldots , k \} \mid \xi ^i(\omega _1) \ne \xi ^i(\omega _3) \}$ and so $\omega _1 <^\mathsf{{w}}_{\mathcal {R}}\omega _3$. If $a < b$ then $\xi ^b(\omega _1) \subsetneqq \xi ^b(\omega _3)$ and $b = \max \{ i \in \{0, \ldots , k \} \mid \xi ^i(\omega _1) \ne \xi ^i(\omega _3) \}$ and so $\omega _1 <^\mathsf{{w}}_{\mathcal {R}}\omega _3$. If $a > b$ then $\xi ^i(\omega _2) = \xi ^i(\omega _3)$ for all $i \in \{ b+1, \ldots , k \}$ and $b+1 \leqslant a \leqslant k$; therefore $\xi ^a(\omega _1) \subsetneqq \xi ^a(\omega _3)$ and $a = \max \{ i \in \{0, \ldots , k \} \mid \xi ^i(\omega _1) \ne \xi ^i(\omega _3) \}$ and so $\omega _1 <^\mathsf{{w}}_{\mathcal {R}}\omega _3$.    $\square$

4 System W

The preferred structure $<^\mathsf{{w}}_{\mathcal {R}}$ on worlds for a knowledge base $\mathcal {R}$ is defined using both the tolerance information provided by the inclusion-maximal ordered partition ${ OP }(\mathcal {R})$ and information on the set of falsified conditionals. Inference based on $<^\mathsf{{w}}_{\mathcal {R}}$ is called system W inference and is defined as follows.

Definition 6

(system W, ). Let $\mathcal {R}$ be a knowledge base and A, B be formulas. Then B is a system W inference from A (in the context of $\mathcal {R}$ ), denoted

(14)

A consequence of this definition is that system W inference is as tractable as system Z because the preferred structure on worlds is obtained directly from the ordered partition of $\mathcal {R}$ and the verification/falsification behavior of $\mathcal {R}$. We apply the definition of system W to our running example.

Example 3

( ${\mathcal {R}_{ bird }}$ , cont.). Consider again ${\mathcal {R}_{ bird }}$ from Example 1. Let us show that for $A=b \, f$ and $B = \overline{p}$ we have , i.e., that flying birds are usually not penguins. Due to $\xi ( b \, f \, \overline{p} ) = \varnothing$ and $\xi (b \, f \, p) = \{ r_2, r _3 \}$ (see Table 1) it follows that $b \, f \, \overline{p} <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} b \, f \, p$. Therefore, since $\varOmega _{A B} = \{ b \, f \, \overline{p} \}$ and $\varOmega _{A \overline{B}} = \{ b \, f \, p \}$, from (14) it follows that indeed .

Note that , i.e., this inference is also a skeptical c-inference (cf. [5, Example 5]). Therefore, Example 3 presents a c-inference that is also a system W inference. The following proposition tells us that always implies .

Proposition 3

(system W captures c-inference). Let $\mathcal {R}$ be a consistent knowledge base. Then we have for all formulas $A \, , B \in \mathcal {L}$:

(15)

Proof

The proof of (15) is by contraposition. Assume and thus

$$\begin{aligned} \exists \omega ' \in \varOmega _{A\overline{B}} \; \forall \omega \in \varOmega _{A B} \; \omega \not <^\mathsf{{w}}_{\mathcal {R}}\omega ' \, . \end{aligned}$$

(16)

Our goal is to show . Let us fix $\omega ' \in \varOmega _{A \overline{B} }$ such that (16) holds. Let us define $\varOmega _V := \varOmega _{A B}$. Then $\omega \not <^\mathsf{{w}}_{\mathcal {R}}\omega '$ for all $\omega \in \varOmega _V$. Due to Lemma 2 there exists a c-representation such that for all $\omega \in \varOmega _{A B}$. This means that and so indeed .    $\square$

Furthermore, every system Z inference is also a system W inference.

Proposition 4

(system W captures system Z). Let $\mathcal {R}$ be a consistent knowledge base. Then we have for all formulas $A \, , B \in \mathcal {L}$

(17)

Proof

Inspecting (4) and (11) and given any worlds $\omega , \omega ' \in \varOmega$, we conclude that $\kappa ^Z(\omega ) < \kappa ^Z(\omega ')$ implies $\omega <^\mathsf{{w}}_{\mathcal {R}}\omega '$. Therefore, comparing (3), applied to the ranking function $\kappa ^{Z}$, with (14), shows that (17) is fulfilled.    $\square$

In [16], a preference relation on worlds is defined that is based on structural information by preferring a world $\omega$ to a world $\omega '$ if $\omega$ falsifies fewer conditionals than $\omega '$ and $\omega '$ falsifies at least all conditionals falsified by $\omega$. Using this preference relation, the following entailment relation along the scheme as given by (3) is obtained; we present the definition from [16] in a slightly modified form adapted to our notion $\xi (\omega )$ for the set of conditionals from $\mathcal {R}$ falsified by $\omega$.

Definition 7

($\sigma _{\mathcal {R}}$-structural inference [16]). Let $\mathcal {R}= \{r_1,\ldots ,r_n\}$ with $r_i = (B_i|A_i)$ for $i = 1,\ldots ,n$ be a knowledge base, A, B formulas, and let $<_{\mathcal {R}}^{\sigma }$ be the relation on worlds given by $\omega <_{\mathcal {R}}^{\sigma } \omega '$ iff $\xi (\omega ) \subsetneqq \xi (\omega ')$. Then B can be structurally inferred, or $\sigma _{\mathcal {R}}$-inferred, from A, written as

(18)

We can show that every $\sigma _{\mathcal {R}}$-structural inference is also a system W inference.

Proposition 5

(system W captures $\sigma _{\mathcal {R}}$-structural inference). Let $\mathcal {R}$ be a consistent knowledge base. Then we have for all formulas $A \, , B \in \mathcal {L}$

(19)

Proof

Inspecting (11) and the definition of $<_{\mathcal {R}}^{\sigma }$, we conclude that $\omega <_{\mathcal {R}}^{\sigma } \omega '$ implies $\omega <^\mathsf{{w}}_{\mathcal {R}}\omega '$ for all $\omega , \omega ' \in \varOmega$. Combining (11) and (18) yields (19).    $\square$

The following proposition summarizes Propositions 3, 4, and 5 and shows aditionally that system W strictly extends skeptical c-inference, system Z, and structural inference by licensing more entailments than each of these three inference modes.

Proposition 6

(system W) For every consistent knowledge base $\mathcal {R}$

(20)

Furthermore, there are knowledge bases $\mathcal {R}_1 \, , \mathcal {R}_2 \, , \mathcal {R}_3$ such that the inclusions in (20) are strict, i.e.:

(21)

(22)

(23)

Proof

The inclusions in (20) are shown in Propositions 3, 4, and 5. Thus, we are left to show that the inclusions in (21)–(23) are strict.

• 1. For proving the strictness part of (21), consider the knowledge base $\mathcal {R}^* = \{(b|a) , ( b \, c| a) \}$ whose verification/falsification behavior is given by Table 2. First, due to $\xi (a \, b \, \overline{c} ) = \{ ( b \, c| a) \} \subsetneqq \{(b|a) , ( b \, c| a) \} = \xi ( a \, \overline{ b} \, \overline{c} )$, we obtain . Making use of the verification/falsification behavior stated in Table 2, for $CR (\mathcal {R}^*)$ we obtain $\eta _1 > -\eta _2$ and $\eta _2 > 0$. Now consider the solution vector . For the associated c-representation (see Table 2) we then obtain and thus .

• 2. For proving the strictness part of (22), consider the knowledge base ${\mathcal {R}_{ bird }}$ from Example 1. Let us show that for $A=p \, \overline{b}$ and $B = \overline{f}$ we have , i.e., that penguins which are no bird usually do not fly. According to Example 2, we have $p \, \overline{b} \, \overline{f} <^\mathsf{{w}}_{{\mathcal {R}_{ bird }}} p \, \overline{b} \, f$. Therefore, since $\varOmega _{A B} = \{ p \, \overline{b} \, \overline{f} \}$ and $\varOmega _{A \overline{B}} = \{ p \, \overline{b} \, f \}$ it follows from (14) that indeed . Looking at Table 1, we observe $\kappa ^Z(A B) = 2 = \kappa ^Z(A \overline{B})$ and thus .

• 3. For proving the strictness part of (23), consider again ${\mathcal {R}_{ bird }}$ with ${ OP }({\mathcal {R}_{ bird }}) = (\mathcal {R}_0, \mathcal {R}_1)$ where $\mathcal {R}_0 = \{ (f | b) \}$ and $\mathcal {R}_1 = \{ (\overline{f} | p), \, (\overline{f} | bp), \, (b | p) \}$ (cf. Example 2). For $\omega = p \, b \, f$, we get (cf. Table 1) that $\xi (\omega ) = \{ (\overline{f}|p), (\overline{f}|pb) \}$, $\xi (p \, b \, \overline{f} ) = \{ (f|b) \}$ and $\xi (p \, \overline{b} \, \overline{f}) = \{( b|p ) \}$. Thus, there is no world $\omega ' \in \varOmega$ with $\omega ' \models p \, \overline{f}$ and $\omega ' <_{{\mathcal {R}_{ bird }}}^{\sigma } \omega$ (which is equivalent to $\xi (\omega ') \subsetneqq \xi (\omega )$). Therefore, . To show fix any $\omega \in \varOmega$ with $\omega \models p \, f$. Then $(\overline{f} | p) \in \xi (\omega )$ where $(\overline{f} | p) \in R_1$. For $\omega ' = p \, b \, \overline{f}$ we have $\omega ' <^\mathsf{{w}}_{\mathcal {R}}\omega$ due to $\xi (\omega ') = \{(f|b) \}$ where $(f|b) \in \mathcal {R}_0$. Thus, indeed .    $\square$

Table 2. Verification/falsification behavior and (generic) c-representation of the knowledge base $\mathcal {R}^{*}$ in the proof of Proposition 6; ($\mathsf {v}$) indicates verification, ($\mathsf {f}$) falsification and ($-$) non-applicability.

After comparing system W with other established inference methods let us deal with further of its properties.

Proposition 7

In general, system W inference cannot be obtained from a ranking function, i.e., there exists a knowledge base $\mathcal {R}$ such that there is no ranking function $\kappa : \varOmega \rightarrow \mathbb {N}_0^{\infty }$ with .

Proof

This follows immediately from Lemma 2.    $\square$

Nonmonotonic inference relations are usually evaluated by means of properties. In particular, the axiom system P  [1, 19] provides an important standard for plausible, nonmonotonic inferences.

Proposition 8

System W inference satisfies System P.

Proof

According to Lemma 3, $<^\mathsf{{w}}_{\mathcal {R}}$ is a strict transitive relation. Furthermore, since $\varOmega$ is finite, the triple $\mathcal {M}^{w}(\mathcal {R}) = [ \varOmega , \models , <^\mathsf{{w}}_{\mathcal {R}}]$ is a stoppered classical preferential model [22]. Thus, the definition of system W given by (14) in Definition 6 ensures that system W inference is a preferential inference, hence satisfying system P (cf. [19, 22]).    $\square$

An inference relation suffers from the Drowning Problem [9, 23] if it does not allow to infer properties of a superclass for a subclass that is exceptional with respect to another property because the respective conditional is “drowned” by others. E.g., penguins are exceptional birds with respect to flying but not with respect to having wings. So we would reasonably expect that penguins have wings.

Example 4

( $\mathcal {R}_{ bird }^{*}$ [5]). We extend the alphabet $\varSigma =\{ p,b,f \}$ of our running example knowledge base ${\mathcal {R}_{ bird }}$ from Example 1 with the variable w for having wings, the variable a for being airborne, and the variable r for being red, obtaining the alphabet $\varSigma ^*=\{ p,b,f,w,a,r \}$. We use the knowledge base

$$ \mathcal {R}_{ bird }^{*}=\big \{ (f|b),\,\, (\overline{f}|p),\,\, (b|p),\,\, (w|b),\,\, (a|f)\big \} $$

where the conditional $(w|b)$ encodes the rule that birds usually have wings, and the conditional $(a|f)$ encodes the rule that flying things are usually airborne; the other three conditionals $(f|b)$, $(\overline{f}|p)$, $(b|p)$ are the same as in ${\mathcal {R}_{ bird }}$.

The Drowning Problem distinguishes between inference relations that allow for subclass inheritance only for non-exceptional subclasses (like system Z inference) and inference relations that allow for subclass inheritance for exceptional subclasses (like skeptical c-inference  [5, Observation 1] and inference with minimal c-representations, cf.  [16, 26]). As an illustration for the drowning problem, consider $\mathcal {R}_{ bird }^{*}$ from Example 4. Here, we have $\kappa ^Z(p \, \overline{w}) = 1 = \kappa ^Z (p \, w)$, and consequently (cf. [5, Example 9]), illustrating that system Z suffers from the drowning problem. In contrast, the following observation shows that system W licenses the inference that penguins usually have wings and thus avoids this drowning phenomenon.

Observation 1

System W inference does not suffer from the drowning problem in Example 4, i.e., we have .

Proof

The inclusion-maximal partition ${ OP }(\mathcal {R}_{ bird }^{*}) =(\mathcal {R}_0,\mathcal {R}_1)$ of $\mathcal {R}_{ bird }^{*}$ in Example 4 is given by $\mathcal {R}_0=\{ (f|b), (w|b), (a|f)\}$ and $\mathcal {R}_1=\{ (\overline{f} |p) , (b|p)\}$.

Consider $\omega \in \varOmega$ with $\omega \models p \, \overline{w}$. Choose an arbitrary $\omega ' \in \varOmega$ with $\omega ' \models p \, b \, \overline{f} w$. We will show $\omega ' <^\mathsf{{w}}_{\mathcal {R}_{ bird }^{*}} \omega$. Obviously, $\omega '$ falsifies only the conditional (f|b) which is in $\mathcal {R}_0$, written as a formula $\xi (\omega ) = \{ (f|b) \}$. Since $\omega \models p \overline{w}$, we can distinguish the following two cases:

• (i) If $\omega \models p \, \overline{w} \, f$ then the conditional $(\overline{f} |p)$ from $\mathcal {R}_1$ is falsified.

• (ii) If $\omega \models p \, \overline{w} \, \overline{f}$ then we can again distinguish two cases:

  • (a) If $\omega \models p \, \overline{w} \, \overline{f} \, \overline{b}$ then (b|p) from $\mathcal {R}_1$ is falsified.

  • (b) If $\omega \models p \, \overline{w} \, \overline{f} \, b$ then at least (f|b), (w|b) (both from $\mathcal {R}_0$) are falsified.

Due to (11), we thus get $\omega ' <^\mathsf{{w}}_{\mathcal {R}_{ bird }^{*}} \omega$ in every case, implying .    $\square$

5 Conclusions and Future Work

In this paper, we introduced system W and its underlying preferred structure of worlds. System W inference captures both System Z inference and skeptical c-inference and exhibits desirable properties. For instance, in contrast to system Z, it avoids the drowning problem. In contrast to skeptical c-inference, it does not require to solve a complex constraint satisfaction problem, but is as tractable as system Z because the preferred structure on worlds is obtained directly from the ordered partition of $\mathcal {R}$ and the verification/falsification behavior of $\mathcal {R}$. In future work, we will empirically evalute system W with the reasoning platform InfOCF  [3] and investigate further inference properties of it.