A modal reconstruction of Rational Closure

   Laura Giordano1, Valentina Gliozzi2 , Nicola Olivetti3 , and Gian Luca Pozzato2
   1
       Dipartimento di Informatica - Universitá del Piemonte Orientale “Amedeo Avogadro”,
                                       Alessandria, Italy
                                  laura@mfn.unipmn.it
              2
                Dipartimento di Informatica - Universitá degli Studi di Torino, Italy
                           {gliozzi,pozzato}@di.unito.it
         3
           LSIS-UMR CNRS 6168, Université “Paul Cézanne” Aix-Marseille 3, France
                         nicola.olivetti@univ-cezanne.fr



        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 in-
        terpretations 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 condition-
        als. 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.


1 Introduction
In a seminal work Kraus Lehmann and Magidor [7] (henceforth KLM) proposed an ax-
iomatic 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 sys-
tems, [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 con-
ditional 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 postu-
lates/rules are just axioms. We use ⊢P C (resp. |=P C ) to denote provability (resp. va-
lidity) in the propositional calculus .

All axioms and rules of propositional logic
A |∼ A                                                                              (REF)
if ⊢P C A ↔ B then (A |∼ C) → (B |∼ C),                                             (LLE)
if ⊢P C A → B then (C |∼ A) → (C |∼ B)                                               (RW)
((A |∼ B) ∧ (A |∼ C)) → (A ∧ B |∼ C)                                                 (CM)
((A |∼ B) ∧ (A |∼ C)) → (A |∼ B ∧ C)                                               (AND)
((A |∼ C) ∧ (B |∼ C)) → (A ∨ B |∼ C)                                                  (OR)
((A |∼ B) ∧ ¬(A |∼ ¬C)) → (A ∧ C) |∼ B)                                              (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 so-
called 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 sys-
tems 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 condi-
tionals (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 con-
sequences 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 sat-
   isfying 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 prob-
   lems 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 re-
stricting 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 inconsis-
tent 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 condi-
tionals (and propositional formulas). Our language L is defined from a set of proposi-
tional variables ATM . We use A, B, C, . . . to denote propositional formulas (not con-
taining |∼), 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 proposi-
tional 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 ra-
tional6 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 inM   < (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 inM                   ′
      < (A) then M, w |= B. Last we define the Smoothness Condition: if M, w |= A,
then w ∈ M in< (A) or there is w′ ∈ M inM
                  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 inM                     ′
            < (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 inM        < (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 in-
terpretations in terms of conditionals that are falsified by a world. Intuitively mini-
mal 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).
3 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 condi-
tionals 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 defi-
nition in terms of rank of a formula.

Definition 7. Let K be a knowledge base (i.e. a finite set of positive conditional asser-
tions) 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 num-
ber 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 asser-
tions 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 clo-
sure. 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 , Vi i 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 mini-
mal 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 eas-
ily 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 men-
tioned 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 = (W, <, V ) of K ′ , which is minimal w.r.t. VIMS , as
follows:
   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 pro-
posed. 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 differ-
ent 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 Defi-
nition 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 , VM i 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 alterna-
tives 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 re-
mark 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 defini-
tion 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 entail-
ment) cannot cope with conditionals having an inconsistent antecedent. This limitation
is deliberate and is motivated by a probabilistic interpretation of conditionals: in assert-
ing 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 seman-
tics). 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 com-
binations 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., Niemelä, 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: Fermüller, C.G., Voronkov, A. (eds.) Proceedings of LPAR 2010
    (17th Conference on Logic for Programming, Artificial Intelligence, and Reasoning). AR-
    CoSS 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 ratio-
    nal 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 Intel-
    ligence 55(1), 1–60 (1992)
 9. Pearl, J.: System Z: A natural ordering of defaults with tractable applications to nonmono-
    tonic 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: Pro-
    ceedings 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)