Varying Selection Functions to Relate Conditional Logics and Preferential Models

Chitta Baral Department of Computer Science University of Texas at El Paso El Paso, Texas 79968 chitta@cs.ep.utexas.edu

Abstract

In this paper we study the relationship between preferential model semantics of Shoham [Sho87b] and Kraus et al. [KLM90] with the flat version of conditional logic defined by Bell [Bel90] and its variations. We present a new selection function without constraining or changing the relation between the possible worlds. Using our selection function we construct a conditional logic equivalent to Shoham’s preferential model semantics [Sho87a].

1 Introduction and Motivation

The purpose of this paper is to present a selection function using which a conditional logic equivalent to Shoham’s preferential model semantics [Sho87a] can be constructed. Bell [Bel91] in his recent paper has shown that his pragmatic logic is more general than Shoham’s preference logics. But in his proof he defines the closest worlds as the preferred worlds. In this paper we give a particular construction of the selection function which makes the closest worlds as the preferred worlds. Hence, the main contribution of this paper is the construction of the selection function. Our construction is a modification of Bell’s construction of the selection function in his previous paper on C-logic [Bel90] and unlike [Nej91] we do not constrain the ≤ relation between the possible worlds.

The field of conditional logic was developed by philosophers and logicians to describe the meaning of conditional statements and counterfactuals. A collection of important papers in this area is edited in [SHP81]. Our attention to this field was drawn by the invited lecture given by Robert Stalnaker in the Third conference on theoretical aspects of reasoning about knowledge in 1990.

In general, conditional logics (for instance Stalnaker’s logic) do not validate the “antecedent strengthening law”; which means that, the validity of “If A then B” (written as A > B by Stalnaker)^{1} does not force the sentence “If A and C then B” to be valid. Harper in [SHP81] gives the following example to support Stalnaker’s logic. The validity of the statement “If I put sugar in this cup of tea it will test fine” does not make the sentence “If I put sugar and diesel in this cup of tea it will test fine” to be valid. This example is in principle similar to the “tweety” examples given by AI researchers to explain the nonmonotonic nature of common sense reasoning. Thus it is not surprising that there are formal connections between nonmonotonic and conditional logics.

Logicians and Philosophers have been working on the semantics of conditional statements for a long time [Bur81, Nut84, Sta68, Vel86, Ada66, Ada75, vB84]. Stalnaker and Thomason [ST70, Sta68] developed a semantic theory of conditionals (i.e. a semantics for logics based on conditional statements) based on possible worlds. Their theory is based on the model theory which says that a conditional “If A then B” is true in a possible world ϕ, if B is true in the closest possible world of ϕ where A is true.

Recently connections have been discovered between conditional logics (i.e. logics based on conditional statements) and nonmonotonic reasoning [Bel91, Bou, Del88, DM92, KS91, KLM90, Mak89, Nej91, Sho87a]. Shoham [Sho87a] notes that this connection was pointed out to him by van Benthem. Bell [Bel90] and Delgrande [Del88] have formulated nonmonotonic reasoning mechanisms based on conditional logics. Bell’s conditional logic (called Clogic) is based on the conditional semantics of Stalnaker with a particular selection function.

1In the rest of the paper we use the notation used by Bell [Bel90] and write A ⇒ B

Bell extends Stalnaker’s definition of the truth value of a conditional statement with respect to a particular world, to define the truth value of a conditional statement with respect to a set of possible worlds, given an ordering relation between them.

Kraus et al. [KLM90] study several nonmonotonic consequence relations based on proof theoretic and model theoretic semantics. Intuitively, the meaning of their nonmonotonic consequence relation ( |∼ ) is as follows: α |∼ β means that α is a good enough reason to believe β, or β is a plausible consequence of α. The model theoretic semantics of Kraus et al. is a little different from the preferential model semantics of Shoham [Sho87b]. While the semantics of Shoham is based on worlds, Kraus et al. use states which are a collection of worlds. Kraus et al. [KLM90] discuss the difference between the conditional operator ⇒ and the nonmonotonic consequence relation |∼. But they do not discuss in detail the similarity between these two approaches. Besides the difference in intuitive meaning of the conditional operator ⇒ and the nonmonotonic consequence relation |∼, conditional logic allows nesting of conditional operators. Conditional logics which do not allow nesting of conditionals are called flat conditional logics.

In this paper we study the connections between the flat version of Bell’s conditional logic with alternative selection functions, and the preferential model semantics [KLM90, Sho87b]. The rest of the paper is organized as follows. In section 2, we review Stalnaker’s [ST70, Sta68] conditional logic, state his conditions for a valid selection function and review Bell’s extension [Bel90] of Stalnaker’s [ST70, Sta68] conditional logic. We show that the selection function used by Bell satisfies suitable modifications of Stalnaker’s conditions. In section 3, we review the preferential model semantics [Sho87b, KLM90]. The main contributions of this paper are in section 4 and 5.

• In section 4, we show that the set of conditional statements true with respect to the flat version of Bell’s conditional logic is a subset of the set of conditional statements true with respect to the preferential model semantics of Shoham [Sho87b].

• In section 5, we introduce a new valid selection function and show that the conditional semantics based on this selection function is equivalent to the preferential model semantics of Shoham [Sho87b].

This result can be easily extended to show that for a particular selection function, a flat conditional logic based on states instead of worlds is equivalent to the preferential model semantics of Kraus et al. [KLM90].

Hence, we expose the power and expressiveness of conditional logic and show that by choosing an appropriate selection function many interesting non-monotonic logics can be derived.

In section 6, we compare our result with other works in the literature that relate or unify conditional logics and non-monotonic formalisms.

The expressiveness of conditional logic and the possibility that its semantics may be tailored to specifications by using an appropriate selection function further motivates to study nonmonotonic reasoning mechanisms based on conditional logics.

2 Conditional Logic

We consider the language of conditional logic to include conditional statements of the type A ⇒ B. In a flat conditional statement A ⇒ B, A and B are free of the conditional operator ⇒. Flat conditional logics only allow flat conditional statements. In the rest of the paper we consider flat conditional logics. The semantics of conditional logics given by Stalnaker and Thomason [ST70] is based on possible worlds and a selection function on them. Given a possible world i and a proposition A, the selection function f selects a possible world j = f(A, i). According to Stalnaker’s theory of conditionals, A ⇒ B is true in a possible world ϕ, if B is true in the closest possible world of ϕ where A is true. (i.e. B is true in f(A, ϕ).) Stalnaker [Sta] requires that the selection function satisfy the following conditions.

1. If f(A, i) is defined then A is true in it.

2. If A is true in i then f(A, i) = i.

3. If A is true in f(B, i) and B is true in f(A, i) then f(A, i) = f(B, i) Since Stalnaker’s selection function selects a single world, the semantics based on it controversially considers the statement (p ⇒ q) ∨ (p ⇒ ¬q) to be true.

Hence, we use Lewis’s extension [Lew73] of Stalnaker’s theory. In this extension, given a world w and a proposition P, the selection function selects a set of worlds (not a single world) close to w, where a given proposition is true. A proposition P is then said to be true with respect to a set of possible world, S, if it is true in all of them. When this set, S, is empty, the proposition is vacuously true with respect to it. We modify Stalnaker’s original conditions which a selection function should satisfy and call it modified Stalnaker’s conditions.

Definition 2.1 The modified Stalnaker’s conditions that a selection function F (a, w) should satisfy are

1. If a is true in w then F (a, w) = {w}

2. If a is true in F (b, w) and b is true in F (a, w) then F (a, w) = F (b, w)

According to the modified conditional semantics (MCS), a conditional statement A ⇒ B is said to be true in a possible world ϕ with a given selection function f, iff B is true in all closest worlds of ϕ (based on the selection function f) where A is true. (i.e. B is true in all worlds in f(A, ϕ).) Bell’s conditional logic is based on the modified conditional semantics. We now formally define Bell’s conditional logic.

Definition 2.2 [Bel90] A C-Model is a pair M = ⟨I, ≤⟩ where I is a nonempty set of possible worlds and ≤ is a well-founded partial ordering on I.

The selection function F_{B}(a, i) that Bell uses to select the closest worlds of i where a is true is defined as follows.

Definition 2.3 [Bel90]Bell’s definition of Closest World If a is true in i then F_{B}(a, i) = {i}

else F_{B}(a, i) = the minimal possible worlds (with respect to ≤_{i}) amongst the possible worlds in I_{i} where a is true; where I_{i} = {j : i ≤ j} and ≤_{i} is the restriction of ≤ to I_{i}.

Lemma 2.1 F_{B} satisfies the modified Stalnaker’s conditions.

Proof: It is obvious that the first condition is satisfied. The second condition is “If a is true in F_{B}(b, i) and b is true in F_{B}(a, i) then F_{B}(a, i) = F_{B}(b, i)” Assume that a is true in F_{B}(b, i) and b is true in F_{B}(a, i). Let i_{1} ∈ F_{B}(a, i). By our assumption we have both a and b true in i_{1}. Consider F_{B}(b, i) and assume that i_{1} ∉ F_{B}(b, i). This means there exists an i′ ∈ F_{B}(b, i) such that i ≤ i′ < i_{1} and b is true in i′. (as i′ ∈ I_{i} hence i ≤ i′) By our assumption we have a true in i′. But then i_{1} will not be in F_{B}(a, i). Hence, our assumption that i_{1} ∉ F_{B}(b, i) is false and hence, i_{1} ∈ F_{B}(b,i). This means F_{B}(a, i) ⊆ F_{B}(b, i). By similar argument it can be shown that F_{B}(b, i) ⊆ F_{B}(a, i). Hence, F_{B}(a, i) = F_{B}(b, i) and the second condition is satisfied. □

One of the main contribution of Bell [Bel90] is the extension of the definition of the truth of a conditional statement with respect to a possible world to the truth of a conditional statement with respect to a C-Model.

Definition 2.4 [Bel90] A ⇒_{B} B with respect to a C-Model, ⟨I, ≤⟩, iff for all minimal possible worlds i in I, B is true in all closest world of i where A is true. (i.e B is true in F_{B}(A, i).)

3 Preferential Model Semantics

In this section we review the preferential model semantics of Shoham [Sho87b] and Kraus et al. [KLM90]. Kraus et al. consider a model as a set of possible states with a binary relation on them. The similar structure considered by Shoham is a set of possible worlds with a binary relation on them. This is the only difference between these two approaches. To avoid confusion we refer to the structure considered by Shoham as s-model and the model of Kraus et al. by k-model.

A k-model essentially consists of a set of states (they represent possible states of affairs, including perhaps the state of mind or knowledge of the reasoner) and a binary relation on those states. The relation represents the preferences the reasoner may have between different states. For example he could prefer states in which Tweety is a bird and flies to those in which Tweety is a bird but does not fly. The reasoner, described by a k-model, accepts a conditional assertion α ∼ β iff all those states that are most preferred among all states satisfying α, satisfy β.

In a k-model every state is labeled with a set of worlds (intuitively the set of all worlds the reasoner thinks are possible in this state). ^{2}.

Definition 3.1 [KLM90] A cumulative k- model is a triple ⟨ S, l, ≤⟩, where S is a set, the elements of which are called states, l : S ↦ 2^{U} is a function that labels every state with a non-empty set of worlds and ≤ is a binary relation on S.

Definition 3.2 [KLM90] Let ⟨ S, l, ≤⟩ be as above. If α is a formula, s ∈ S is said to satisfy α (written as s ≡ α) iff for every world m ∈ l(s), α is true in m.

Definition 3.3 [KLM90] A cumulative ordered k-model is a cumulative k-model in which the relation ≤ is a strict partial order. (i.e. an irreflexive, transitive relation)

Preferential k-models are cumulative ordered k-models in which states are labeled by single worlds (and not sets of worlds). The reasoner has, then, essentially, a preference over worlds (except that the same world may label different states).

Definition 3.4 [KLM90] A preferential k-model W is a triple ⟨ S, l, ≤⟩ where S is a set, the elements of which will be called states, l : S ↦ U assigns a world to each state and ≤ is a strict partial order on S (i.e. an irreflexive, transitive relation).

Shoham, in [Sho87b], proposes a more restricted notion of preferential models. He requires the set of states S to be a subset of the universe U and the labeling function l to be the identity. In other words in s-model each state corresponded to a particular world and there is a one to one relation between the set of states and set of worlds. We denote the s-model corresponding to the k-model ⟨ S, l, ≤⟩ with l as the identity function simply by the pair ⟨ S, ≤⟩. Shoham also requires the relation ≤ be a well-order. Henceforth we refer to Shoham’s restricted notion of preferential k-models as preferential s-models.

2Considering a binary relation on states labeled by sets of worlds, instead of considering a binary relation on sets of worlds, gives an additional degree of freedom in building models: the same set of worlds may appear at many states (that are not equivalent from the point of view of the binary relation). This additional freedom is vital for the representation theorem [KLM90] to hold, and was missing from Shoham’s account [Sho87b]

Definition 3.5 Let ⟨I, ≤⟩ be a preferential s-model (or the part of a preferential k-model) and A be a proposition. The set, {X|X ∈ I and A is true in X} is denoted by S(A, I).

Definition 3.6 A |∼_{1}B with respect to an s-model ⟨I, ≤⟩ iff B is true in all minimal worlds (with respect to ≤) in S(A, I)

4 Bell’s Conditional Logic vs Preferential s-models

In this section we show that the set of conditional statements true with respect to the flat version of Bell’s conditional logic is a subset of the set of conditional statements true with respect to the preferential model semantics of Shoham [Sho87b].

Definition 4.1 Let M be the set of all possible worlds. (i.e I in a C-model and S in a preferential s-model) and ≤ be a well-ordered partial order on M. Let i ∈ M and A be a propositional sentence. S = minimal possible worlds amongst the set of all possible worlds. S(A) = Possible worlds in M where A is true. MS(A) = Minimal possible worlds amongst the possible worlds in S(A). F_{B}(A, i) = Closest worlds of i where A is true. F S_{B}(A) = {X|X ∈ F_{B}(A, i) for some i ∈ S}.

Lemma 4.1 MS(A) ⊆ F S_{B}(A)

Proof: Let X ∈ MS(A). This means X ∈ S(A) and ∄Y such that Y ∈ S(A) and Y ≤ X. By definition of S there exists i ∈ S such that i ≤ X. Hence, if i ≠ X then i ∉ S(A) otherwise X won’t be in MS(A). Consider F_{B}(A, i). We claim that X ∈ F_{B}(A, i). Suppose this claim is wrong. That is ∃Y |Y ≤ X and Y ∈ F_{B}(A, i). But in that case Y ∈ S(A), and since Y ≤ X hence X won’t be in MS(A). Hence our claim is right. That means ∃i ∈ S|X ∈ F_{B}(A, i). Hence X ∈ F S_{B}(A). □

Theorem 1 If A ⇒_{B} B with respect to a C-Model ⟨I, ≤⟩ then A |∼_{1}B with respect to the preferential s-model ⟨I, ≤⟩.

Proof: A ⇒_{B} B implies B is true in all possible worlds in F S_{B}(A). Since MS(A) ⊆ F S_{B}(A), B is true in all possible worlds in MS(A). Hence A |∼_{1}B. □

We now show through an example that F S_{B}(A) ⊈ MS(A).

[figure: Y; X; i; A, ¬ B; ¬ A, ¬ B; A, B; ≤; ≤]

Figure 1: Counterexample

Example 4.1 Consider M = {X, Y, i}. The possible world in M are defined as follows. A and B both are true in Y. A is true and B is false in X. A and B both are false in i. The preference relation between them is as follows. Y ≤ X and i ≤ X. S = {Y, i} (the minimal elements of M with respect to ≤). F S_{B}(A) = {Y, X} (Because F_{B}(A, i) = X and F_{B}(A, Y) = Y). S(A) = {Y, X} ( possible worlds in M where A is true). MS(A) = {Y } ( minimal possible worlds in S(A)). Clearly in this example F S_{B}(A) ⊈ MS(A). Also in this example A |∼ _{1}B as B is true in Y and Y is the only minimal possible world in S(A). But, A ⇒_{B} B does not hold as B is not true in X where X is the closest world of i where A is true and i is a minimal possible world in M. Hence, If A |∼_{1}B with respect to the s-model ⟨M, l, ≤⟩ then A ⇒_{B} B does not necessarily hold with respect to the C-Model, M = ⟨I, ≤⟩. □

Corollary 4.1 The converse of Theorem 1 is not true.

5 A Flat Conditional Logic Equivalent to the Preferential s-Models

In this section we construct a new valid selection function and prove that a flat conditional logic based on it is equivalent to the preferential s-model semantics of Shoham. Intuitively, the meaning of this function F is as follows. On input i and a, where i is a possible world and a is a proposition, x ∈ F (a, i) if x is found by the following procedure. We climb up the ≤ relation on any arbitrary path until we find the first world y which has ≤ smaller worlds where a is true. We then climb down the ≤ relation until we reach a world x where a is true, and all whose ≤ less worlds do not have a as true. In essence, we climb up as little as necessary and then climb down as much as we can. This intuition is shown in Figure 1.

The importance of this function lies in the fact that using it we can find a equivalence between the two seemingly different approaches of conditional logics and preferential models. This also suggests that the formalism of conditional logic is very general and depending upon the requirement a suitable selection function can be constructed so as to obtain a particular nonmonotonic semantics. We also show that the function we define satisfies the modified Stalnaker’s conditions.

Definition 5.1 Let M be the set of all possible worlds. (i.e I in a C-model and S in a preferential s-model) and ≤ be a well-ordered partial order on M. Let i ∈ M and a and A be propositional sentences. The selection function F, that determines the closest worlds of a given possible world with respect to a particular propositional sentence is defined as follows: If a is true in i then F(a,i) = {i} else F(a,i) = { x | a is true in x and ∃ y : x ≤ y and i ≤ y, and

1. (∀ z, such that i ≤ z < y there does not exist a w such that w ≤ z and a is true in w) ^{3} and

2. (for all u, such that u < x, a is false in u) } FS(A) = {X | X ∈ F(A,i) and i ∈ S.} S, S(A) and MS(A) are as defined in Definition 4.1

The first condition in the definition is useful in proving Lemma 5.2 and the second one is necessary in proving Lemma 5.3.

Lemma 5.1 F as defined in Definition 5.1 satisfies modified Stalnaker’s condition.

Proof:

3a < b iff a ≤ b and b ≰ a

[figure: ⋯; ≤; ≤; ⋯; ⋯; w; ¬ a; ≤; u; ¬ a; ⋯; ≤; x; a; ≤; ⋯; ≤; ⋯; ≤; y; z; ⋯; i]

Figure 2: x ∈ F(a,i)

It is obvious that the first condition is satisfied. The second condition is “If a is true in F(b,i) and b is true in F(a,i) then F(a,i) = F(b,i)” Assume that a is true in F(b,i) and b is true in F(a,i). Let i_{1} ∈ F(a,i). By our assumption we have both a and b true in i_{1}. Consider F(b,i) and assume that i_{1} ∉ F(b,i). Then there are two possible cases. case 1: There exists j < i_{1}, such j ∈F(b,i). By our assumption a will be true in j. But then j will be in F(a,i) and i_{i} won’t be in F(a,i) which is a contradiction. case 2: There exists a k, such that k is the least upper bound of i and i_{1} (it exists because i_{1} ∈ F(a,i)) and there exists a k_{1} such that i ≤ k_{1} < k, and there exists k_{2} such that k_{2} ≤ k_{1} and k_{2} ∈F(b,i). By assumption a will be true in k_{2}. But then k_{2} will be in F(a,i) and i_{i} won’t be in F(a,i) which is a contradiction. Hence, our assumption that i_{1} ∉ F(b,i) is wrong and hence, i_{1} ∈ F(b,i). This means F(a,i) ⊆ F(b,i). By similar argument it can be shown that F(b,i) ⊆ F(a,i). Hence, F(a,i) = F(b,i) and the second condition is satisfied. □

Definition 5.2 A ⇒_{1} B with respect to a C-Model, ⟨I, ≤⟩ iff for all minimal possible worlds

[figure: ⋯; ≤; ≤; ⋯; ⋯; k_{2}; ≤; j; ⋯; ≤; i_{1}; a,b; ≤; ⋯; ≤; ⋯; ≤; k; k_{1}; ⋯; i]

Figure 3: F satisfies modified Stalnaker’s conditions

i in I, B is true in all worlds in F(A,i).

Lemma 5.2 MS(A) ⊆ F S(A)

Proof: Assume that x ∈ MS(A). Since S is the set of minimal possible worlds, there exists an i ∈ S such that i ≤ x. Suppose that x ∉ F (A, i). Then there are two possible cases: case 1: ∃z such that i ≤ z < x and ∃v such that v ≤ z and A is true in v. But since v ≤ z and z < x, v < x . Since v < x and v ∈ S(A) , x ∉ MS(A), which contradicts our assumption. case 2: ∃u such that u < x and A is true in u. But then u ∈ S(A) and since u < x, x ∉ MS(A), which contradicts our assumption. Hence, x ∈ F (A, i), for some i in S. Hence x ∈ F S(A). □

Lemma 5.3 F S(A) ⊆ MS(A)

Proof: Assume that x ∈ F S(A). This means, there exists an i, such that i ∈ S and x ∈ F (A, i).

Assume that x ∉ MS(A). This means, there exists a y such that y ≤ x and y ∈ MS(A). But this means x ∉ F (a, i) for any i; which in turn means that x ∉ F S(A). But this contradicts our initial assumption that x ∈ F S(A). Hence our assumption that x ∉ MS(A) is incorrect and hence x ∈ MS(A). □

Theorem 2 A ⇒_{1} B with respect to the C-Model, ⟨I, ≤⟩ iff A |∼_{1} B with respect to the preferential s-model ⟨I, ≤⟩.

6 Comparison with other works

In this section we compare our result with other recent works in the literature that attempt to relate and unify conditional logics and non-monotonic formalisms.

P-systems of [Nej91] In [Nej91], Nejdl introduces P-systems as a framework to classify the various kinds of nonmonotonic logic using constraints on the relation between different possible situations. He also observes that several different conditional logics can be generated by modifying the selection function. While in this paper we do not specify any constraints on the relation ≤ between the possible worlds and change the way the selection function is defined, Nejdl [Nej91] keeps the basic structure of the selection function intact but puts constraints on the relation ≤ so as to construct various conditional logics.

Ordered structures of [KS91] Katsuno and Satoh define ordered structures and families of ordered structures as a common language to develop a unified view of existing work on consequence relations, conditional logics, belief revision and updates. They relate conditional logics developed in the literature: VW [Lew73, Nut84], VC [Lew73, Nut84] and C [Nut84, Bel90] to various consequence relations using axiomatizations (FTO,FTOM and FPOM) of their ordered structures. In contrast, in this paper we modify the conditional logic C by modifying the selection function, so as to make it equivalent to Shoham’s preferential models.

Relation between KLM [KLM90] and MAK Models [Mak89]: [DM92] Makinson in [Mak89] develops another variant of the general notion of preferential models. In [DM92], Dix and Makinson show the relation between KLM[KLM90] and MAK [Mak89] models. In particular they show that one can swap KLM’s family of labeled set of worlds by a background consequence operation and a single satisfaction relation on states (both satisfying appropriate constraints) as used in the definition of MAK-models. The results in this paper thus can be used to relate the MAK-models with conditional logics.

Pragmatic logics: [Bel91] Bell in [Bel91] defines pragmatic logics as a generalization of his C-logic and shows how by varying the selection function his pragmatic logic can generalize other non-monotonic formalisms. In particular he shows that pragmatic logic is more general than Shoham’s preference logics. But in his proof he defines the closest worlds as the preferred worlds. In this paper we give a particular construction of the selection function which makes the closest worlds as the preferred worlds. Hence, the main contribution of this paper is the construction of the selection function. Our construction is a modification of Bell’s construction of the selection function in his previous paper on C-logic [Bel90].

7 Conclusion

In this paper we have shown that the set of conditional statements true with respect to the flat version of Bell’s conditional logic is a subset of the set of conditional statements true with respect to the preferential model semantics of Shoham [Sho87b]. We modified the selection function of the flat version of Bell’s conditional logic and showed that this modified version is equivalent to the preferential models of Shoham [Sho87b].

The main difference between the approach taken in Bell’s conditional logic [Bel90] and other attempts (especially Thomason’s [Tho]) is that according to Thomason, a ⇒ b is true in a set of strictly partial ordered worlds (let the relation be ≤) iff it is true in all the worlds; while according to Bell [Bel90] (we also advocate his approach), a ⇒ b is true in a set of strictly partial ordered worlds (let the relation be ≤) iff it is true in all the ≤-minimal worlds.

Results similar to the results present in this paper were presented in the 3rd International Workshop in Non-monotonic reasoning held in Lake Tahoe. Goldszmidt and Pearl [GP90] compared the relation between Rational Closure (very similar to preferential models) and System-Z. Craig Boutilier [Bou] presented a conditional logic similar to the one defined by Delgrande [Del88] and compared it with the preferential model semantics. We described other recent results that relate conditional logics and non-monotonic formalisms in section 6.

The preferential model semantics considered in this paper deals only with propositions and is one of the five families of models and consequence relations described in [KLM90]. We do not consider the other four models in this paper. Lehman et al. [LM90] have extended the preferential model semantics to first order theories. The relation between their extension and a similar generalization of conditional logic remains to be explored. Besides the above, presently we are also studying the behavior of conditional operators as nonmonotonic consequence relations.

Acknowledgement

The author would like to thank anonymous referees for their extremely valuable comments on the draft of this paper. We would also like to acknowledge the support by NSF through grants IRI-9211662 and CDA 90-15-006.

References

[Ada66] Ernest W. Adams. Probability and the logic of conditional. In J. Hintikka and P. Suppes, editors, Aspects of Inductive Logic. North Holland, Amsterdam, 1966.

[Ada75] Ernest W. Adams. The Logic of Conditionals. D. Reidel, Dordrecht, 1975.

[Bel90] John Bell. The Logic of Nonmonotonicity. Artificial Intelligence, 41:365–374, 1990.

[Bel91] John Bell. Pragmatic Logics. In Proceedings of Second International Conference on Principles of Knowledge Representation and Reasoning, 51-60, 1991.

[Bou] Craig Boutilier. Conditional Logic and Preferential Models. Presented in the rump session of Third International Workshop in Non-monotonic reasoning held in Lake Tahoe.

[Bur81] John P. Burgess. Quick completeness proofs for some logics of conditionals. Notre Dame Journal of Formal Logic, 22:76–84, 1981.

[Del88] James P. Delgrande. An approach to default reasoning based on a first-order conditional logic: Revised report. Artificial Intelligence, 36:63–90, August 1988.

[DM92] Jürgen Dix and David Makinson. The relationship between KLM and MAK models for nonmonotonic inference operations. In Journal of Logic, Language and Information 1: 1-10, 1992.

[Gin87] M. Ginsberg, editor. Readings in Nonmonotonic Reasoning. Morgan Kaufmann, 1987.

[GP90] Moises Goldszmidt and Judea Pearl. On the relation between Rational Closure and System-Z. In Third International Workshop in Non-monotonic Reasoning, South Lake Tahoe, May-June 1990.

[KS91] Hirofumi Katsuno and Ken Satoh. A unified view of consequence relation, belief revision and conditional logic. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 406–412, Morgan Kaufmann Publishers, Inc., Sidney, August 1991.

[KLM90] Sarit Kraus, Daniel Lehmann, and Menachem Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44(1–2):167–207, 1990.

[Lew73] D. Lewis. Counterfactuals. Harvard University Press, 1973.

[LM90] D. Lehmann and M. Magidor. Preferential Logics: the Predicate Calculus case. In R. Parikh, editor, Proc. of the Third International Conference on Theoretical Aspects of Reasoning about Knowledge, pages 57–71, Asilomar, California, 1990. Morgan Kaufmann.

[Mak89] D. Makinson. General Theory of Cumulative Inference. In Reinfrank, de Kleer, Ginsberg, and Sandewall, editors, Non-monotonic Reasoning. Lecture Notes in AI 346, Springer-Verlag, January 1989.

[Nej91] Wolfgang Nejdl. The P-Systems: a systematic classification of logics of nonmonotonicity. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 366–372, Anaheim, CA, July 1991.

[Nut84] Donald Nute. Conditional logic. In Dov M. Gabbay and Franz Guenthner, editors, Handbook of Philosophical Logic, chapter Chapter II.8, pages 387–439. D. Reidel, Dordrecht, 1984.

[Sho87a] Y. Shoham. Nonmonotonic Logics: Meaning and Utility. In Proceedings of IJCAI 87, Milan, Italy, pages 388–393, 1987.

[Sho87b] Yoav Shoham. A semantical approach to nonmonotonic logics. In Proc. Logics in Computer Science, pages 275–279, Ithaca, N.Y., 1987.

[SHP81] R. Stalnaker, W. Harper and G. Pearce, editors. Ifs. D. Reidel Publishing Company, 1981.

[ST70] R. Stalnaker and R. Thomason. A Semantical Analysis of Conditional Logic. Theoria, 36, 1970.

[Sta] R. Stalnaker. Conditional Semantics. Invited talk in Third International Conference on Theoretical Aspects of Reasoning about Knowledge.

[Sta68] R. Stalnaker. A theory of conditionals. In Nicholas Rescher, editor, Studies in Logical Theory, volume 2 of American Philosophical Quarterly Monograph Series, pages 98–112. Blackwell, Oxford, 1968.

[Tho] Rich Thomason. personal conversation.

[vB84] Johan van Benthem. Foundations of conditional logic. Journal of Philosophical Logic, 13:303–349, 1984.

[Vel86] Frank Veltman. Logics for Conditionals. PhD thesis, Filosofisch Instituut, Universiteit van Amsterdam, 1986.