A modal reconstruction of Rational Closure

Abstract

This paper provides a general semantic framework for nonmonotonic reasoning, based on a minimal models semantics on the top of KLM systems for nonmonotonic reasoning. This general framework can be instantiated in order to provide a semantic reconstruction within modal logic of the notion of rational closure, introduced by Lehmann and Magidor. We give two characterizations of rational closure: the first one in terms of minimal models where propositional interpretations associated to worlds are fixed along minimization, the second one where they are allowed to vary. In both cases a knowledge base must be expanded with a suitable set of consistency assumptions, represented by negated conditionals. The correspondence between rational closure and minimal model semantics suggests the possibility of defining variants of rational closure by changing either the underlying modal logic or the comparison relation on models.

-

In a seminal work Kraus Lehmann and Magidor [ 7 ] (henceforth KLM) proposed an axiomatic approach to nonmonotonic reasoning. Plausible inferences are represented by nonmonotonic conditionals of the form A |∼ B, to be read as “typically or normally A entails B”: for instance monday |∼ go work, “normally on Monday I go to work”. The conditional is nonmonotonic since from A |∼ B one cannot derive A ∧ C |∼ B, in our example, one cannot derive monday ∧ ill |∼ go work. KLM proposed a hierarchy of four systems, from the weakest to the strongest: cumulative logic C, loop-cumulative logic CL, preferential logic P and rational logic R. Each system is characterized by a set of postulates expressing natural properties of nonmonotonic inference. We present below an axiomatization of the two stronger logics P and R (C and CL being too weak to be taken as an axiomatic base for nonmonotonic reasoning). But before presenting the axiomatization, let us clarify one point: in the original presentation of KLM systems, [ 7 ] a conditional A |∼ B is considered as a consequence relation between a pair of formulas A and B, so that their systems provide a set of “postulates” (or closure conditions) that the intended consequence relations must satisfy. Alternatively, these postulates may be seen as rules to derive new conditionals from given ones. We take a slightly different viewpoint, shared among others by Halpern and Friedman [ 4 ] (see Section 8) and Boutilier [ 2 ] who proposed a modal interpretation of KLM systems P and R: in our understanding these systems are ordinary logical systems in which a conditional A |∼ B is a propositional formula belonging to the object language. Whenever we restrict our consideration, as done by Kraus Lehmann and Magidor, to the entailment of a conditional from a set of conditionals, the two viewpoints coincide: a conditional is a logical consequence in logic P/R of a set of conditionals if and only if it belongs to all preferential/rational consequence relations extending that set of conditionals, or (in semantic terms), it is valid in all preferential/rational models (as defined by KLM) of that set.

Here is the axiomatization of logics P and R, in our presentation KLM postulates/rules are just axioms. We use ⊢P C (resp. |=P C ) to denote provability (resp. validity) in the propositional calculus .

All axioms and rules of propositional logic

A |∼ A if ⊢P C A ↔ B then (A |∼ C) → (B |∼ C), if ⊢P C A → B then (C |∼ A) → (C |∼ B) ((A |∼ B) ∧ (A |∼ C)) → (A ∧ B |∼ C) ((A |∼ B) ∧ (A |∼ C)) → (A |∼ B ∧ C) ((A |∼ C) ∧ (B |∼ C)) → (A ∨ B |∼ C) ((A |∼ B) ∧ ¬(A |∼ ¬C)) → (A ∧ C) |∼ B) (REF) (LLE) (RW) (CM) (AND) (OR) (RM) The axiom (CM) is called cumulative monotony and it is characteristic of all KLM logics, axiom (RM) is called rational monotony and it characterizes the logic of rational entailment R. The weaker logic of preferential entailment P contains all axioms, but (RM). P and R seem to capture the core properties of nonmonotonic reasoning, as shown in [ 4 ] they are quite ubiquitous being characterized by different semantics (all of them being instances of so-called plausibility structures).

Logics P and R enjoy a very simple modal semantics, actually it turns out that they are the flat fragment of some well-known conditional logics. For P the modal semantics is defined by considering a set of worlds W equipped by an accessibility (or preference) relation < assumed to be transitive, irreflexive, and satisfying the socalled Smoothness Condition. For the stronger R < is further assumed to be modular. Intuitively the meaning of x < y is that x is more normal/less exceptional than y. We say that A |∼ B is true in a model if B holds in all most normal worlds where A is true, i.e. in all <-minimal worlds satisfying A.

KLM systems formalize desired properties of nonmonotonic inference. However, they are too weak to perform useful nonmonotonic inferences. For instance KLM systems cannot handle irrelevant information in conditionals: from monday |∼ go work, there is no way of concluding monday ∧ shines |∼ go work in any one of KLM systems. Partially motivated by the weakness of the axiomatic approach, Lehmann and Magidor have proposed a true nonmonotonic mechanism on the top of logic R called rational closure. Rational clsure on the one hand preserves the properties of R, on the other hand allows one to perform some truthful nonmonotonic inferences, like the one just mentioned (monday ∧ shines |∼ go work).4 The authors has given a syntactic procedure to calculate the set of conditionals entailed by the rational closure as well as a quite complex semantic construction. It is worth noticing that a strongly related construction has been proposed by Pearl [ 9 ] with his notion of 1-entailment, motivated by a probabilistic interpretation of conditionals.

In this work we tackle the problem of giving a purely semantic characterization of rational closure, stemming directly from the modal semantics of logic R. Notice that we restrict our attention to finite knowledge bases. More precisely, we try to answer to the following question: given the fact that logic R is characterized by a specific class of Kripke models, how can we characterize the Kripke models of the rational closure of a set of positive conditionals?

The characterization we propose may be seen as an instance of a general recipe for defining nonmonotonic inference: (i) fix an underlying modal semantics for conditionals (such as the one of P or R), (ii) obtain nonmonotonic inference by restricting semantic consequence to a class of “minimal” models according to some preference relation on models. The preference relation in itself is defined independently from the language and from the set of conditionals (knowledge base) whose nonmonotonic consequences we want to determine. In this respect our approach is similar in spirit to “minimal models” approaches to nonmonotonic reasoning, such as circumscription.

The general recipe for defining nonmonotonic inference we have sketched may have a wider interest than that of capturing Lehmnan and Magidor’s rational closure. First of all, we may think of studying variants of rational closure based on other modal logics and/or on other comparison relations on models. Secondly, being a purely semantic approach (the preference relation is independent from the language), our semantics can cope with a larger language than the one considered in KLM framework. To this regard, already in this paper, we consider a richer language allowing boolean combinations of conditionals5. In the future, we may think of applying our semantics to Nonmonotonic Description Logics, where an extension of rational closure has been recently considered [ 3 ].

In any case, the quest of a modal characterization of rational closure turns out to be harder than expected. Our semantic account is based on the minimization of the height of worlds in models, where the height of a world is defined in terms of length of the <-chains starting from the world. Intuitively, the lower the height of a world, the more normal (or less exceptional)is the world and our minimization corresponds intuitively to the idea of minimizing less-normal or less-plausible worlds (or maximizing most plausible ones). 4 Actually the main motivation of Lehmann and Magidor leading to the definition of rational closure was technical: it turns out that the intersection of all rational consequence relations satisfying a set of conditionals coincides with the least preferential consequence relation satisfying that set, so that (i) the axiom/rule (RM) does not add anything and (ii) such relation in itself fails to satisfy (RM). Their notion of rational closure provides a solution to both problems and can be seen as the “minimal” (in some sense) rational consequence completing a set of conditionals. 5 An extension of rational closure to knowledge bases comprising both positive and negative conditionals has been proposed in [ 1 ].

We begin by considering the nonmonotonic inference relation determined by restricting considerations to models which minimize the height of worlds. In this first characterization we keep fixed the propositional interpretation associated to worlds. The consequence relation makes sense in its own, but as we show it is strictly weaker than rational closure. We can obtain nonetheless a first characterization of rational closure if we further restrict attention to minimal canonical models that is to say, to models that contain all propositional interpretations compatible with the knowledge base K (i.e. all propositional interpretations except those that satisfy some formulas inconsistent with the knowledge base K ). Restricting attention to canonical models amounts to expanding K by all formulas ¬(A |∼ ⊥) (read as “A is possible”, as it encodes S5 3A) for all formulas A such that K 6|=R A |∼ ⊥. We thus obtain a very simple and neat characterization of rational closure, but at the price of an exponential increase of the K .

We then propose a second characterization that does not entail this exponential blow up. In analogy with circumscription, we consider a stronger form of minimization where we minimize the height of worlds, but we allow to vary the propositional interpretation associated to worlds. Again the resulting minimal consequence relation makes sense in its own, but as we show it still does not correspond to rational closure. In order to capture rational closure, we must basically add the assumption that there are “enough” worlds to satisfy all conditionals consistent with the knowledge base K . This amounts to adding a small set of consistency assumptions (represented by negative conditionals). In this way we capture exactly rational closure, without an exponential increase of the knowledge base. 2

General Semantics In KLM framework the language of both logics P and R consists only of conditionals A |∼ B. We consider here a richer language allowing boolean combinations of conditionals (and propositional formulas). Our language L is defined from a set of propositional variables ATM . We use A, B, C, . . . to denote propositional formulas (not containing |∼), and F, G, . . . to denote arbitrary formulas. More precisely, the formulas of L are defined as follows: if A is a propositional formula, A ∈ L; if A and B are propositional formulas, A |∼ B ∈ L; if F is a boolean combination of formulas of L, F ∈ L. A knowledge base K is any set of formulas: as already mentioned in this work we restrict our attention to finite knowledge bases.

The semantics of P and R is defined respectively in terms of preferential and rational6 models, that are possible world structures equipped with a preference relation <, intuitively x < y means that the world/individual x is more normal/ more typical than the world/individual y. The intuitive idea is that A |∼ B holds in a model if the most typical/normal worlds/individuals satisfying A satisfy also B. Preferential models presented in [ 7 ] characterize the system P, whereas the more restricted class of rational models characterize the system R [ 8 ]. 6 We use the expression “rational model” rather than “ranked model” which is also used in the literature in order to avoid any confusion with the notion of rank used in rational closure. Definition 1. A preferential model is a triple M = hW , <, V i where W is a non-empty set of items, < is an irreflexive, transitive relation on W satisfying the Smoothness relation defined below. V is a function V : W 7−→ 2ATM , which assigns to every world w the set of atoms holding in that world. If F is a boolean combination of formulas, its truth conditions (M, w |= F ) are defined as for propositional logic. Let A be a propositional formula; we define M in<M(A) = {w ∈ W | M, w |= A and ∀w′, w′ < w implies M, w′ 6|= A}. We also define M, w |= A |∼ B if for all w′, if w′ ∈ M in<M(A) then M, w′ |= B. Last we define the Smoothness Condition: if M, w |= A, then w ∈ M in<M(A) or there is w′ ∈ M in<M(A) such that w′ < w. Validity and satisfiability of a formula are defined as usual. Given a set of formulas K of L and a model M = hW , <, V i, we say that M is a model of K , written M |= K , if, for every F ∈ K , and every w ∈ W , we have that M, w |= F . K preferentially entails a formula F , written K |=P F if F is valid in all preferential models of K .

Since we limit our attention to finite knowledge bases, we can restrict our attention to finite models, as the logic enjoys the finite model property (observe that in this case the smoothness condition is ensured trivially by the irreflexivity of the preference relation). From Definition 1, we have that the truth condition of A |∼ B is “global” in a model M = hW , <, V i: given a world w, we have that M, w |= A |∼ B if, for all w′, if w′ ∈ M in<M(A) then M, w′ |= B. It immediately follows that A |∼ B holds in w if only if A |∼ B is valid in a model, i.e. it holds that M, w′ |= A |∼ B for all w′ in W ; for this reason we will often write M |= A |∼ B. Moreover, when the reference to the model M is unambiguous, we will simply write M in<(A) instead of M in<M(A). Definition 2. A rational model is a preferential model in which < is further assumed to be modular: for all x, y, z ∈ W , if x < y then either x < z or z < y. K rationally entails a formula F , written K |=R F if F is valid in all rational models of K . When the logic is clear from the context we shall write K |= F instead of K |=P F or K |=R F . From now on, we restrict our attention to rational models.

Definition 3. The height kM of a world w in M is the length of any chain w0 < . . . < w from w to a w0 such that for no w′ it holds that w′ < w0 7.

Notice that in a rational model hW , V, <i, kM is uniquely determined. Moreover, finite Rational models can be equivalently defined by postulating the existence of a function k : W → N, and then letting x < y iff k(x) < k(y).

Definition 4. The height kM(F ) of a formula F is i = min{kM(w) : M, w |= F }. If there is no w | M, w |= F , F has no height.

Proposition 1. For any M = hW , V, <i and any w ∈ W , we have M |= A |∼ B iff kM(A ∧ B) < kM(A ∧ ¬B). 7 In the literature the function kM is usually called ranking, but we call it height in order to avoid any confusion with the different notion of ranking as defined by Lehmann and Magidor and used in this paper as well. Our notion of ranking is similar to the one originally introduced by Spohn [ 11 ] and to the one introduced by Pearl [ 9 ]. The definition of height can be adapted to preferential models by considering the longest chain rather than any chain in the definition. As already mentioned, although the operator |∼ j is nonmonotonic, the notion of logical entailment just defined is itself monotonic: if K |=P F and K ⊆ K′ then also K′ |=P F (the same holds for |=R). In order to define a nonmonotonic entailment we introduce our second ingredient of minimal models. The underlying idea is to restrict attention to models that minimize the height of worlds. Informally, given two models of K, one in which a given x has height 2 (because for instance z < y < x) , and another in which it has height 1 (because only y < x), we would prefer the latter, as in this model x is “more normal” than in the former.

In analogy with circumscription, there are mainly two ways of comparing models with the same domain: 1) by keeping the valuation function fixed (only comparing M and M′ if V and V ′ in the two models respectively coincide); 2) by also comparing M and M′ in case V 6= V ′. We consider the two possible semantics resulting from these alternatives. The first semantics is a fixed interpretations minimal semantics, for short FIMS .

Definition 5 (FIMS ). Given M = hW, <, V i and M′ = hW′, <′, V ′i we say that M is preferred to M′ with respect to the fixed interpretations minimal semantics (M <FIMS M′) if W = W′, V = V ′, and for all x, kM(x) ≤ kM′ (x) whereas there exists x′ : kM(x′) < kM′ (x′). We say that M is minimal w.r.t. <FIMS in case there is no M′ such that M′ <FIMS M. We say that K minimally entails a formula F w.r.t. FIMS , and we write K |=FIMS F , if F is valid in all models of K which are minimal w.r.t. <FIMS .

The following theorem shows that we can characterize minimal models with fixed interpretations in terms of conditionals that are falsified by a world. Intuitively minimal models are those where the worlds of height 0 satisfy all conditionals, and the height (> 0) of a world x is determined by the height kM(C) of the antecedents C of conditionals falsified by x. Given a model M = hW, <, V i and x ∈ W, we define Sx = {C |∼ D ∈ K | M, x |= C ∧ ¬D}.

Proposition 2. Let K be a knowledge base and M a model, then M |= K if and only if M satisfies the following, for every x ∈ W: 1. if kM(x) = 0 then Sx = ∅ 2. if Sx 6= ∅, then kM(x) > kM(C) for every C |∼ D ∈ Sx.

Observe that condition 1 is a consequence of condition 2, since by 2 if Sx 6= ∅ then trivially kM(x) > 0; we have explicitly mentioned it for clarity (see the subsequent proposition and theorem, whose proofs can be found in [ 6 ]).

Proposition 3. Let K be a knowledge base and let M be a minimal model of K with respect to FIMS ; then M satisfies for every x ∈ W: 1. if Sx = ∅ then kM(x) = 0. 2. if Sx 6= ∅, then kM(x) = 1 + max{kM(C) | C |∼ D ∈ Sx}.

Theorem 1. Let K be a knowledge base and let M be any model, then M is a FIMS minimal model of K if and only if M satisfies for every x ∈ W: 1. Sx = ∅ iff kM(x) = 0. 2. if Sx 6= ∅, then kM(x) = 1 + max{kM(C) | C |∼ D ∈ Sx}.

In our second semantics, we let the interpretations vary. The semantics is called variable interpretations minimal semantics, for short VIMS .

Definition 6 (VIMS ). Given M = hW, <, V i and M′ = hW′, <′, V ′i we say that M is preferred to M′ with respect to the variable interpretations minimal semantics, and write M <VIMS M′, if W = W′, and for all x, kM(x) ≤ kM′ (x) whereas there exists x′ : kM(x′) < kM′ (x′). We say that M is minimal w.r.t. <VIMS in case there is no M′ such that M′ <VIMS M. We say that K minimally entails (with respect to VIMS ) F , and write K |=VIMS F , if F is valid in all models of K which are minimal w.r.t. <VIMS .

It is easy to realize that the two semantics, FIMS and VIMS , define different sets of minimal models. This is illustrated by the following example.

Example 1. Let K = {penguin |∼ bird, penguin |∼ ¬f ly, bird |∼ f ly}. We derive that K 6|=FIMS penguin ∧ black |∼ ¬f ly. Indeed in FIMS there can be a model M in which W = {x, y, z}, V (x) = {penguin, bird, f ly, black}, V (y) = {penguin, bird}, V (z) = {bird, f ly}, and z < y < x. M is a model of K, and it is minimal with respect to FIMS (indeed once fixed V (x), V (y), V (z) as above, it is not possible to lower the height of x nor of y nor of z unless we falsify K). Furthermore, in M x is a typical black penguin (since there is no other black penguin preferred to it) that flies. Therefore, K 6|=FIMS penguin ∧ black |∼ ¬f ly.

On the other hand, M is not minimal w.r.t. VIMS . Indeed, consider the model M′ = hW, <′, V ′i obtained from M by letting V ′(x) = {penguin, bird, black}, V ′(y) = V (y), V ′(z) = V (z) and by defining <′ as: z <′ y and z <′ x. Clearly M′ |= K, and M′ <V IMS M, since kM′ (x) < kM(x), while kM′ = kM for all other worlds. The example above shows that FIMS and VIMS lead to different sets of minimal models for a given K. Notice however that the model M′ we have used to illustrate this fact is not a minimal model for K in VIMS . A minimal model in VIMS for K that can be defined on the domain W is given by V (x) = V (y) = V (z) = {bird, f ly}, and the empty relation <. This is quite a degenerate model of K in which there are no penguins. This illustrates the strength of VIMS : in case of knowledge bases that only contain positive conditionals, logical entailment in VIMS collapses into classical logic entailment. This feature corresponds to a similar feature of the non-monotonic logic Pmin in [ 5 ], and can be proven in the same way.

Proposition 4. Let K be a set of positive conditionals. Let us replace all formulas of the form A |∼ B in K with A → B, and call K′ the resulting set of formulas. We have that K |=VIMS A |∼ B if and only if K′ |=P C A → B.

As for Pmin this strong feature of VIMS can be avoided when considering knowledge bases that include existence assertions: these are negated conditionals, in the example for instance we could add ¬(penguin |∼⊥) to force us to consider non trivial models in which penguins exist. In the next section, we will use VIMS in this kind of way, by always considering knowledge bases that include existence assertions (expressed by negated conditionals).

A Semantical Reconstruction of Rational Closure We provide a semantic characterization of the well known rational closure, described in [ 8 ] within the two semantics described in the previous section. More precisely, we can give two semantic characterizations of rational closure, the first based on FIMS , the second based on VIMS . Since in rational closure no boolean combinations of conditionals are allowed, in the following, the knowledge base K is just a finite set of positive conditional assertions. We recall the notion rational closure, giving its syntactical definition in terms of rank of a formula.

Definition 7. Let K be a knowledge base (i.e. a finite set of positive conditional assertions) and A a propositional formula. A is said to be exceptional for K iff K |=R ⊤ |∼ ¬A8.

The set of conditional formulas which are exceptional for K will be denoted as E(K). It is possible to define a non sequence of subsets of K C0 ⊇ C1, . . . by letting C0 = K and, for i > 0, Ci = E(Ci−1). Observe that, being K finite, there is a n ≥ 0 such that for all m > n, Cm = Cn or Cm = ∅.

Definition 8. A propositional formula A has rank i for K iff i is the least natural number for which A is not exceptional for Ci. If A is exceptional for all Ci then A has no rank.

The notion of rank of a formula allows to define the rational closure of a knowledge base K.

Definition 9. Let K be a conditional knowledge base. The rational closure K¯ of K is the set of all A |∼ B such that either (1) the rank of A is strictly less than the rank of A ∧ ¬B (this includes the case A has a rank and A ∧ ¬B has none), or (2) A has no rank.

The rational closure of a knowledge base K seemingly contains all conditional assertions that, in the analysis of nonmonotonic reasoning provided in [ 8 ], one rationally wants to derive from K. For a full discussion, see [ 8 ].

Can we capture rational closure within our semantics? A first conjecture might be that the FIMS of Definition 5 could capture rational closure. However, we are soon forced to recognize that this is not the case. For instance, Example 1 above illustrates that {penguin |∼ bird, penguin |∼ ¬f ly, bird |∼ f ly} 6|=FIMS penguin ∧ black |∼ ¬f ly. On the contrary, it can be easily verified that penguin ∧ black |∼ ¬f ly is in the rational closure of {penguin |∼ bird, penguin |∼ ¬f ly, bird |∼ f ly}. Therefore, FIMS as it is does not allow us to define a semantics corresponding to rational closure. Things change if we consider FIMS applied to models that contain all possible valuations compatible with a given knowledge base K. We call these models canonical models. 8 In [ 8 ], |=P is used instead of |=R. However when K contains only positive conditionals the two notions coincide (see footnote 1) and we prefer to use |=R here since we consider rational models.

Example 2. Consider Example 1 above. If we restrict our attention to models that also contain a w with V (w) = {penguin, bird, black} which is a black penguin that does not fly and can therefore be assumed to be a typical penguin, we are able to conclude that typically black penguins do not fly, as in rational closure. Indeed, in all minimal models of K that also contain w with V (w) = {penguin, bird, black}, it holds that penguin ∧ black |∼ ¬f ly.

We are led to the conjecture that FIMS restricted to canonical models could be the right semantics for rational closure. Fix a propositional language LProp comprising a finite set of propositional variables ATM , a propositional interpretation v : ATM −→ {true, f alse} is compatible with K , if there is no formula A ∈ LProp such that v(A) = true and K |=R A |∼ ⊥.

Definition 10. A model M = hW , <, V i satisfying a knowledge base K is said to be canonical if it contains (at least) a world associated to each propositional interpretation compatible with K , that is to say: if v is compatible with K , then there exists a world w in W , such that for all propositional formulas B M, w |= B iff v(B) = true.

It can be easily shown that:

Theorem 2. For a given domain W , there exists a unique canonical model M for K over W such that, for all other canonical models M′ over W , we have M <FIMS M′. In the following, we show that the canonical models that are minimal with respect to FIMS are an adequate semantic counterpart of rational closure.

To prove the correspondence between the rational closure of a knowledge base K and the fixed interpretation minimal model semantics of K , we need to prove some propositions. The next one is a restatement for rational models of Lemma 5.18 in [ 8 ], and it can be proved in a similar way. Note that, as a difference, point 2 in Lemma 5.18 is an “if and only if” rather than an “if” statement.

Proposition 5. Let M = hW , <, V i be a rational model of K . Let M0 = M and, for all i, let Mi = hWi, <i, Vii be the rational model obtained from M by removing all the worlds w with kM(w) < i, i.e., Wi = {w ∈ W | kM(w) ≥ i}. For any propositional formula A, if rank(A) ≥ i, then: (1) kM(A) ≥ i; (2) If A |∼ B is preferentially entailed by Ci, then Mi satisfies A |∼ B.

Fact 1 If {A1 → B1, . . . , An → Bn} |=P C ¬C then {A1 |∼ B1, . . . , An |∼ Bn} ⊢R ⊤ |∼ ¬C.

The following propositions hold (proofs can be found in [6]):

Proposition 6. Let M = hW , <, V i be a canonical model of K , minimal w.r.t. <FIMS . For all w ∈ W it holds that: if M, w |= A → B for all A |∼ B in Ci, then kM(w) ≤ i. Proposition 7. Let M be a canonical model of K minimal w.r.t. <FIMS . Then, rank(A) = i iff kM(A) = i.

We can now prove the following theorem (the proof is in [6]):

Theorem 3. Let K be a knowledge base and M be a canonical model of K minimal w.r.t. <FIMS . We show that, for all conditionals A |∼ B:

M |= A |∼ B if and only if A |∼ B ∈ K, where K is the rational closure of K .

In Theorem 3 we have shown a correspondence between rational closure and minimal models with fixed interpretations, on the proviso that we restrict our attention to minimal canonical models. We can obtain the same effect by extending K into K ′ by adding negated conditionals: K ′ = K ∪ {¬(C |∼⊥) | K 6|=R (C |∼⊥)}. Indeed it can be easily verified that all models of K ′ are canonical, hence restricting FIMS to canonical models on the one hand and considering the extension of K as K ′ on the other hand amounts to the same effect. We can therefore restate Theorem 3 above as follows: Theorem 4. K ′ |=FIMS A |∼ B iff A |∼ B ∈ K .

Notice that the size of K ′ is exponential in that of K .

Can we lift the restriction to canonical models by adopting a semantics based on variable valuations? In the general case, the answer is negative. We have already mentioned that if we consider knowledge bases consisting only positive conditionals logical entailment in VIMS collapses into classical logic entailment. To avoid this collapse, we can require that, when we are checking for entailment of a conditional A |∼ B from a K , at least an A ∧ B world and an A ∧ ¬B world are present in K . This can be obtained by adding to K the conditionals ¬(A ∧ B |∼ ⊥) and ¬(A ∧ ¬B |∼ ⊥). Also in this case, however, we cannot give a positive answer to the above question. In fact, it is possible to build a model of K , minimal w.r.t. VIMS , which falsifies a conditional A |∼ B which on the contrary is satisfied in all the canonical minimal models of K under FIMS . This is shown by the following example:

Example 3. Let K be the following:

{T |∼ S, S |∼ ¬D, L |∼ P , R |∼ Q, E |∼ F , H |∼ G, D |∼ ¬P ∧ ¬Q ∧ ¬F ∧ ¬G, S |∼ ¬(L ∧ R), S |∼ ¬(L ∧ E), S |∼ ¬(L ∧ H ), S |∼ ¬(R ∧ E), S |∼ ¬(R ∧ H ),

S |∼ ¬(E ∧ H )}.

Let A = D ∧ S ∧ R ∧ L ∧ E ∧ H , B = ¬Q ∧ ¬P ∧ ¬F ∧ ¬G and let K ′ = K ∪ {¬(A ∧ B |∼ ⊥), ¬(A ∧ ¬B |∼ ⊥)}.

We define a model M follows:

= (W, <, V ) of K′, which is minimal w.r.t. VIMS , as W = {x, w, y1.y2, y3}, where: V (y1) = {S, ¬D, ¬R, ¬L, ¬E, ¬H, P, Q, F, G} V (y2) = {¬S, ¬D, R, L, E, H, P, Q, F, G} V (y3) = {¬S, ¬D, R, L, E, H, P, Q, F, G} V (x) = {D, S, R, L, E, H, ¬Q, ¬P, ¬F, ¬G}

V (w) = {D, S, R, L, E, H, Q, ¬P, ¬F, ¬G} with kM(y1) = 0, kM(y2) = 1, kM(y3) = 1, kM(x) = 2 and kM(w) = 2. Observe that: x is an A ∧ B minimal world; w is an A ∧ ¬B minimal world; y1 is an S minimal world; y2 is a minimal world for R, L, E and H; and y3 is a D minimal world.

M is a model of K which is minimal w.r.t. VIMS . Also, A |∼ B is falsified in M, while, on the contrary, A |∼ B holds in all the canonical models minimal w.r.t. FIMS . Indeed, in all such models the height of k(A ∧ B) = 2 while k(A ∧ ¬B) = 3. However, it is not possible to construct a model M′ with 5 worlds so that M′ <V IMS M. In particular, assigning to x or w height 1 would require the introduction of minimal worlds for R, L, E and H with height 0. But world y2 cannot be given height 0, as it does not satisfy the conditionals with antecedent S. In canonical models there are distinct minimal R worlds, L worlds, E worlds and H worlds height 0 (which are also minimal S worlds).

As suggested by this example, in order to characterize rational closure in terms of VIMS , we should restrict our consideration to models which contain “enough” worlds. In the following, as in Theorem 4, we enrich K with negated conditionals but, as a difference with K′ of Theorem 4, we only need to add to K a polynomial number of negated conditionals (instead of an exponential number). The purpose of the addition is that of restricting our attention to models minimal with respect to <VIMS that have a domain large enough to have, in principle, a distinct most-preferred world for each antecedent of conditional in K. For this reason, we add for each antecedent C of K a new corresponding atom φC . If the problem to be addressed is that of knowing whether A |∼ B is logically entailed by K, we also introduce φA∧B and φA∧¬B, and we define K′ as follows.

Definition 11. We define: – AK,A|∼B = {C | either for some D, C |∼ D ∈ K or C = A ∧ B or C = A ∧ ¬B, and K 6⊢R C |∼⊥}; – K′ = K ∪ {¬(C ∧ φC |∼⊥) | C ∈ AK,A|∼B} ∪ {(φCi ∧ φCj |∼⊥) | Ci, Cj ∈

AK,A|∼B}.

We here establish a correspondence between FIMS and VIMS . By virtue of Theorem 3, this allows us to establish a correspondence between rational closure and VIMS , as stated by Theorem 6.

Theorem 5. Let M be a canonical model of K, minimal with respect to FIMS , and let K′ be the extension of K defined as in Definition 11. We have that:

M |= A |∼ B iff K ′ |=VIMS A |∼ B.

The proof can be found in [6]. From Theorem 3 and Theorem 5 just shown, it follows that:

Theorem 6. A |∼ B ∈ K¯ iff K ′ |=VIMS A |∼ B for K ′ of Definition 11. 4

Relation with Pmin and Pearl’s System Z In [ 5 ] an alternative nonmonotonic extension of preferential logic P called Pmin is proposed. Similarly to the semantics presented in this work, Pmin is based on a minimal modal semantics. However the preference relation among models is defined in a different way. Intuitively, in Pmin the fact that a world x is a minimal A-world is expressed by the fact that x satisfies A∧2¬A, where 2 is defined with respect to the inverse of the preference relation (i.e. w.r.t. the accessibility relation given by Ruv iff v < u). The idea is that preferred models are those that minimize the set of worlds where ¬ ¬A holds, that is A-worlds which are not minimal. As a difference from the approach presented in this work, the semantics of Pmin is defined starting from preferential models of Definition 1, in which the relation < is irreflexive and transitive (thus, no longer modular). Pmin is a nonmonotonic logic considering only P models that, intuitively, minimize the non-typical worlds. More precisely, given a set of formulas K , a model M = hWM, <M, VMi of K and a model N = hWN , <N , VN i of K , we say that M is preferred to N if WM = WN , and the set of pairs (w, ¬ ¬A) such that M, w |= ¬ ¬A is strictly included in the corresponding set for N . A model M is a minimal model for K if it is a model of K and there is no a model M′ of K which is preferred to M. Entailment in Pmin is restricted to minimal models of a given set of formulas K . In Section 3 of [ 5 ] it is observed that the logic Pmin turns out to be quite strong. In general, if we only consider knowledge bases containing only positive conditionals, we get the same trivialization result (part of Proposition 1 in [ 5 ]) as the one contained in Proposition 4 for VIMS . This does not hold for rational closure. This is the reason why we have introduced the additional assumptions of Definition 11 in order to obtain an equivalence with rational closure. Similarly, in order to tackle this trivialization in Pmin , Section 3 in [ 5 ] is focused on the so called well-behaved knowledge bases, that explicitly include that A is possible (¬(A |∼ ⊥)) for all conditional assertions A |∼ B in the knowledge base.

We can now wonder whether Pmin is equivalent to VIMS , which is the semantics to which it resembles the most. Or whether VIMS is equivalent to a stronger version of Pmin obtained by replacing P with R as the underlying logic. We call Rmin this stronger version of Pmin .

Example 4. Let K = {PhD |∼ ¬worker , PhD |∼ adult , adult |∼ worker ,italian |∼ house owner , PhD |∼ ¬house owner }.

What do we derive in Pmin and Rmin, and what in VIMS ? By what said above, since K only contains positive conditionals, both in Pmin and Rmin, on the one side, and in VIMS , on the other side, we derive that italian ∧ PhD |∼⊥. So let’s add to K the constraint that people who are italian and have a PhD do exist by introducing in K a conditional ¬(italian ∧ PhD |∼⊥), thus obtaining: K′ = {PhD |∼ ¬worker , PhD |∼ adult , adult |∼ worker ,italian |∼ house owner , PhD |∼ ¬house owner ,¬(italian ∧ PhD |∼⊥)}.

Notice that since ¬(italian ∧ PhD |∼⊥) entails both that ¬(italian |∼⊥) and that ¬(PhD |∼⊥), and that this in turn entails ¬(adult |∼⊥), K′ is also well-behaved.

It can be easily verified that the logical consequences of K′ in Pmin , Rmin, and VIMS differ. In both Pmin and Rmin, for instance, we derive neither that italian ∧ PhD |∼ house owner nor that italian ∧ PhD |∼ ¬house owner: the two alternatives are equivalent. On the other hand, in VIMS we derive that italian ∧ PhD |∼ ¬house owner .

The previous example shows that in some cases VIMS is stronger than both Pmin and Rmin. The following one shows that the two approaches are incomparable, since there are also logical consequences that hold for both Pmin and Rmin but not for VIMS . Example 5. Let K = {PhD |∼ adult , adult |∼ work , PhD |∼ ¬work , italian |∼ house owner }.

What do we derive about typical italian ∧ PhD ∧ work , for instance? Do they inherit the property of typical italians of being house owner? Again, in order to prevent the entailment of italian ∧ PhD ∧ work |∼⊥ from K both in VIMS and in Pmin and Rmin, we add to K the constraint that italians with a PhD who work exist, henceforth they also have typical instances. Therefore we expand K into:

K′ = {PhD |∼ adult , adult |∼ work , PhD |∼ ¬work , italian |∼ house owner , ¬(italian ∧ PhD ∧ work |∼⊥)}.

By reasoning as in Example 4 we can show that K′ is a well-behaved knowledge base. Now it can be shown that

italian ∧ PhD ∧ work |∼ house owner is entailed in Pmin and Rmin, whereas nothing is entailed in VIMS . This difference can be explained intuitively as follows. The set of properties for which an individual is atypical matters in Pmin and Rmin where one has to minimize the set of distinct ¬ ¬C: even if an italian ∧ PhD ∧ work is an atypical PhD, Pmin and Rmin still maximize its typicality as an italian, and therefore entail that it is a house owner, as all typical italians. As a difference, in VIMS , what matters is the set of individuals which are more typical than a given x, rather than the set of properties by which they are more typical. As a consequence, since an x which is italian ∧ PhD ∧ work is an atypical PhD, there is no need to maximize its typicality as an italian, as long as this does not increase the set of individuals more typical than x.

In [ 9 ] Pearl has introduced two notions of 0-entailment and 1-entailment to perform nonmonotonic reasoning. We recall here the semantic definition of both and then we remark upon their relation with our semantics and rational closure. A model M for a finite knowledge base K has the form M = ({true, f alse}ATM , kM) where {true, f alse}ATM is the set of propositional interpretations for, say, a fixed finite propositional language, and kM is our height function mapping propositional interpretations to N , the definition of height kM(A) of a formula is the same as in our semantic. A conditional A |∼ B is true in a model M if kM(A∧B) < kM(A∧¬B). Then the two entailments relations are defined as follows:

K |=0−ent A |∼ B if A |∼ B is true in all models of K K |=1−ent A |∼ B if A |∼ B is true in the (unique) model M of K which is minimal w.r.t. kM. (minimal w.r.t. kM means that no other model M′ assigns a lower value kM′ to any propositional interpretation). First, observe that Pearl’s semantics (both 0 and 1 entailment) cannot cope with conditionals having an inconsistent antecedent. This limitation is deliberate and is motivated by a probabilistic interpretation of conditionals: in asserting A |∼ B, A must not be impossible, no matter how it is unlikely. For this reason, a knowledge base such as K = {A |∼ P, A |∼ ¬P, B |∼ Q} is out of the scope of Pearl’s semantics, and nothing can be said about its consequences. As a difference with respect to Pearls approach we are able to consider such K, we just derive that A is impossible, without concluding that K is inconsistent or trivial, in the sense that everything follows from it. Moreover both 0-entailment and 1-entailment fail to validate:

∅ |=0−ent/1−ent A |∼ ⊤ whenever ⊢P C ¬A which is valid in any KLM logic, whence in rational closure (as well as in our semantics). However two definitions should make apparent the relations with our semantics and rational closure. If we consider a K such that ∀A |∼ B ∈ K, K 6|=R A |∼ ⊥, we get an obvious correspondence between our canonical models (which will contain worlds for very possible propositional interpretation) and models of Pearl’s semantics. The correspondence preserves FIMS minimality, so that we get immediately: Proposition 8. K |=1−ent A |∼ B iff A |∼ B holds in any FIMS -minimal canonical model of K.

By Theorem 3, we therefore obtain K |=1−ent A |∼ B iff A |∼ B ∈ K¯ . This is not a surprise, the correspondence between 1-entailment and rational closure was already observed by Pearl in [ 9, 10 ]. However, it only works for knowledge bases with the strong consistency assumption as above. 5

Conclusions and Future Works We have provided a semantic reconstruction of the known rational closure within modal logic. We have provided two minimal model semantics, based on the idea that preferred rational models are those one in which the height of the worlds is minimized. We have then shown that adding suitable possibility assumptions to a knowledge base, these two minimal model semantics correspond to rational closure.

The correspondence between the proposed minimal model semantics and rational closure suggests the possibility of defining variants of rational closure by varying the three ingredients underlying our approach, namely: (i) the properties of the preference relation <: for instance just preorder, or multi-linear [ 5 ], or weakly-connected (observe that P is complete w.r.t. any of the three classes); (ii) the comparison relation on models: for instance based on the heights of the worlds or on the inclusion between the relations <, or on negated boxed formulas satisfied by a world, as in the logic Pmin ; (iii) the choice between fixed or variable interpretations. The systems obtained by various combinations of the three ingredients are largely unexplored and may give rise to useful nonmonotonic logics. We finally intend to extend our approach to richer languages, notably in the context of nonmonotonic description logics.

References

1. Booth , R. , Paris, J.: A note on the rational closure of knowledge bases with both positive and negative knowledge . Journal of Logic, Language and Information 7 , 165 - 190 ( 1998 )

2. Boutilier , C. : Conditional logics of normality: a modal approach . Artificial Intelligence 68 ( 1 ), 87 - 154 ( 1994 )

3. Casini , G. , Straccia , U. : Rational closure for defeasible Description Logics . In: Janhunen, T. , Niemela¨, I. (eds.) Proceedings of JELIA 2010 (12th European Conference on Logics in Artificial Intelligence) . LNAI , vol. 6341 , pp. 77 - 90 . Springer, Helsinki, Finland ( September 2010 )

4. Friedman , N. , Halpern , J.Y.: Plausibility measures and default reasoning . Journal of the ACM 48 ( 4 ), 648 - 685 ( 2001 )

5. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L.: A nonmonotonic extension of KLM preferential logic P . In: Fermu¨ller, C.G., Voronkov , A . (eds.) Proceedings of LPAR 2010 ( 17th Conference on Logic for Programming , Artificial Intelligence, and Reasoning) . ARCoSS LNCS , vol. 6397 , pp. 317 - 332 . Springer-Verlag, Yogyakarta, Indonesia ( October 2010 )

6. Giordano , L. , Gliozzi , V. , Olivetti , N. , Pozzato , G.L.: A minimal model semantics for rational closure . In: Rosati, R. , Woltran , S. (eds.) Proceedings of NMR 2012 (14th International Workshop on Non-Monotonic Reasoning) . to appear, Roma, Italy (June 8-10 2012 )

7. Kraus , S. , Lehmann , D. , Magidor , M. : Nonmonotonic reasoning, preferential models and cumulative logics . Artificial Intelligence 44 ( 1-2 ), 167 - 207 ( 1990 )

8. Lehmann , D. , Magidor , M. : What does a conditional knowledge base entail? Artificial Intelligence 55 ( 1 ), 1 - 60 ( 1992 )

9. Pearl , J. : System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning . In: Parikh, R . (ed.) Proceedings of TARK (3rd Conference on Theoretical Aspects of Reasoning about Knowledge) . pp. 121 - 135 . Morgan Kaufmann, Pacific Grove, CA, USA (March 1990 )

10. Pearl , J. , Goldszmidt , M. : On the relation between rational closure and System-Z . In: Proceedings of NMR 1990 (3rd International Workshop on Non-Monotonic Reasoning) . South Lake Tahoe, California, USA ( 1990 )

11. Spohn , W.: Ordinal conditional functions: A dynamic theory of epistemic states . In: Harper, W. , Skyrms , B . (eds.) Causation in Decision, Belief Change , and Statistics. pp. 105 - 134 . Kluwer, Dordrecht ( 1988 )