A Logic For Causal Reasoning

1 Introduction

Causal theories have been introduced in [McCain and Turner, 1997] as a nonrnonotonic formalism that provides a natural solution for both the frame and ramification problem in rea­ soning about actions (see [Giunchiglia et al., 2001] for a de­ tailed exposition). A causal theory is a set of causal rules A=;. B that express a kind of a causal relation among proposi­ tions. The nonmonotonic semantics of such theories is deter­ mined by causally explained interpretations, namely the in­ terpretations that are both closed with respect to the causal rules and such that every fact holding in them is caused.

The above formalism has been defined semantically, and the main aim of our study consists in laying down its log­ ical foundations. As we will show, such foundations can be built in the framework of an inference system for causal rules that we will call causal production relations. The log­ ical origins of the latter are in input/output logics [Makinson and der Torre, 2000], but we will supply them with a nat­ ural nonmonotonic semantics allowing to represent signifi­ cant parts of nonrnonotonic reasoning. Thus, the main result of the present study is that causal production relations com­ pletely characterize the inference rules for causal condition­ als that preserve the nonmonotonic semantics of causal theo­ ries. It will be shown also that any causal theory is reducible with respect to this semantics to a determinate causal the­ ory that contain only Horn causal rules with literals in heads.

The importance of determinate theories lies in the fact that (modulo some mild finiteness restrictions) the explained in­ terpretations of such a theory are precisely the interpretations of its classical completion (see [McCain and Turner, 1997]). Consequently, the nonmonotonic consequences of such the­ ories are obtainable by the use of classical inference tools (such as the Causal Calculator, described in [Giunchiglia et al., 2001 ]).

Finally, we will describe a relationship between causal re­ lations and abductive reasoning. As we will see, the latter will be representable via a special kind of causal relations called abductive causal relations. This will serve as yet an­ other justification for our general claim that causal produc­ tion relations could be used as a general-purpose formalism for nonmonotonic reasoning, a viable alternative to other non­ monotonic formalisms (such as default logic).

2 Causal production relations

We will assume that our language is an ordinary proposi­ tional language with the classical connectives and constants {A, v, ·, -+, t, f}. In addition, F and Th will denote, respec­ tively, the classical entailment and the associated logical clo­ sure operator.

A causal rule is a rule of the form A==? B, where A and B are classical propositions. Informally, such a rule says that, whenever A holds, B is caused. The following defini­ tion describes an inference system for causal rules that will be shown to be adequate (and complete) for causal theories. Ac­ tually, many of the postulates below (e.g., And and Or) have already been suggested in the literature (see, [Lifschitz, 1997; Schwind, 1999]).

Definition 2.1. A causal production relation (or simply a causal relation) is a relation==;. on the set of propositions sat­ isfying the following conditions:

(Strengthening) If A F Band B ==? C, then A==? C;

(Weakening) If A==;. Band B F C, then A==;. C;

(And) If A==;. Band A==;. C, then A==;. B A C;

(Or) If A==;. C and B ==;. C, then A VB==;. C;

(Cut) If A==;. Band A A B ==;. C, then A==;. C;

(Truth) t ==;. t;

(Falsity) f ==;.f.

Though causal relations satisfy most of the rules for clas­ sical entailment, their distinctive feature is that they are ir­ reflexive, that is, they do not satisfy the postulate A=> A. Ac­ tually, such relations correspond to a strongest kind of input­ output logics from [Makinson and der Torre, 2000], basic input-output logics with reusable output, with the only dis­ tinction that causal relations satisfy also Falsity. The latter restricts the universe of discourse to consistent theories 1 ·

As a consequence of Cut, any causal relation will already be transitive, that is, it will satisfy

However, transitivity is a weaker property than Cut, since it does not imply the latter (see [Makinson and der Torre, 2000]). In addition, the material implications corresponding to the causal rules can be used as auxiliary asswnptions in making derivations. This is a consequence of the following property that holds for causal relations:

Remark. The notion of a causal production sanctioned by the above postulates is atemporal. For example, the rule pl\ q => ·q cannot be understood as saying that p and q jointly cause ·q (afterwards) in a temporal sense; instead, by Cut and Falsity it implies p 1\ q => f, which means, in effect, that p 1\ q cannot hold. Speaking generally, 'causally consistent' propositions cannot cause an effect incompatible with them. A representation of temporal and action domains in this for­ malism can be achieved, however, by adding explicit tempo­ ral arguments to propositions, just as in the classical logic (see [Giunchiglia et al., 2001]).

A constraint is a causal rule of the form A=> f. Such constraints correspond to state constraints in action theories. Now, any causal rule implies the corresponding constraint:

Note, however, that the reverse entailment does not hold. Actually, given the rest of the postulates, Reduction can re­ place the Cut postulate:

Lemma 2.1. Cut is equivalent to Reduction.

Another important fact about causal relations is the follow­ ing 'decomposition' of causal rules:

Lemma 2.2. Any causal rule A=> B is equivalent to a pair of rules A 1\ ·B => f and A 1\ B =>B.

Causal rules of the form AI\B =>Bare 'classically trivial', but they play an important explanatory role in non-reflexive causal reasoning. Namely, they say that, in any causally ex­ plained interpretation in which A holds, we can freely accept B, since it is self-explanatory in this context. Accordingly, such rules could be called conditional abducibles. We will discuss the role of abducibles later as part of the general cor­ respondence between causal and abductive reasoning 2 .

1 In fact, it has been shown in [Bachman, 2002] that other, weaker input-output logics can also be given a semantics of the kind de­ scribed in what follows.

2 Note also that, under the general correspondence between causal inference and default logic (see [Turner, 1999]), such rules correspond to normal defaults in default logic.

Now the above lemma says that any causal rule can be de­ composed into a (non-causal) constraint and a conditional ab­ ducible. This decomposition neatly delineates two kinds of information conveyed by causal rules. One is a logical infor­ mation that constraints the set of admissible models, while the other is an explanatory information describing what proposi­ tions are caused (explainable) in such models 3 .

For a finite set u of propositions, 1\ u will denote their con­ junction. We will extend causal rules to rules having arbitrary sets of propositions as premises using the following 'com­ pactness' recipe: for any set u,

For a given causal relation=>, we will denote by C(u) the set of propositions caused by u, that is

The operator C will play much the same role as the usual derivability operator for consequence relations. It satisfies the following familiar properties:

Still, Cis not inclusive, that is, u ~ C(u) does not always hold. Also, it is not idempotent, that is, C(C(u)) can be dis­ tinct from C(u).

3 Monotonic semantics of causal inference

We will describe now a monotonic semantics for causal re­ lations. Actually, it will be just a slight modification of the semantics given in [Turner, 1999].

A fully formal semantic interpretation of causal relations could be given in terms of possible worlds frames of the form (i, W), where i is a propositional interpretation, while W is a set of propositional interpretations that contains i (see [Turner, 1999]). In order to make our descriptions more trans­ parent, however, we will identify such frames with pairs of theories of the form (a, u), where a is a world (maximal de­ ductively closed set), while u is a deductively closed set in­ cluded in a. Such pairs will be called bitheories. Clearly, any possible worlds frame ( i, W) determines a certain bithe­ ory, and vice versa, so all our definitions will admit a purely semantic reformulation.

By a causal semantics we will mean a set of bitheories. The corresponding notion of validity for causal rules is given in the next definition.

Definition 3.1. · A causal rule A=> B holds in a bitheory (a, u) if either Art a, orB E u.

• A=> B is valid with respect to a causal semantics B if it holds in all bitheories from B.

We will denote by => B the set of all causal rules that are valid in a causal semantics B. It can be easily verified that this set is closed with respect to the postulates for causal relations, and hence we have

3 Cf. a similar decomposition of causal rules in [Thielscher, 1997].

Lemma 3.1. '* B is a causal production relation.

To prove completeness, for any causal relation '* we con­ sider its canonical causal semantics defined as the set B~ of all bitheories of the form ( o:, C( o:)) such that C( o:) ~ o:. Then the following theorem shows that this semantics determines precisely the source causal relation, including the causal rules with arbitrary sets of premises. In other words, the source causal relation is strongly complete for this semantics.

Theorem 3.2. For any set of propositions v,

Thus, any causal semantics determines a causal relation and vice versa, any causal relation is generated by some causal semantics. Hence we conclude with the following gen­ eral completeness result:

Corollary 3.3. A relation on propositions is a causal relation iff it is generated by a causal semantics.

3.1 Possible worlds semantics

Causal relations can also be given a semantic interpretation in terms of standard possible worlds models.

As usual, a possible worlds model is a triple W = (W, R, V), where W is a set of worlds, R is a binary acces­ sibility relation on W, while V is a function assigning each world a propositional interpretation. Intuitively, o:R{3 means that o: and {3 are, respectively, an initial state (input) and a possible output state of a causal production based on a given set of causal rules. A possible worlds model is quasi-reflexive if its accessibility relation satisfies the condition:

The following definition provides the notion of validity for causal rules in such models:

Definition 3.2. A'* B will be said to be valid in a possible worlds model (W, R) if, for any worlds o:, {3 such that o:R{3, if A holds in o:, then B holds in {3.

Then we have

Theorem 3.4. A relation is causal if and only if it is deter­ mined by a quasi-reflexive possible worlds model.

The above semantics immediately suggests a modal trans­ lation of causal rules (see [Turner, 1999]). Namely, the valid­ ity of A'* B in a possible worlds model is equivalent to valid­ ity of the formula A -+DB, where 0 is a standard modal op­ erator. Consequently, causal rules are representable by such modal formulas.

4 The nonmonotonic semantics

In addition to the monotonic semantics, a causal relation de­ termines also a natural nonmonotonic semantics.

Recall that the canonical semantics of a causal relation '* is determined by all worlds o: for which C(o:)~o:. These are the worlds that are closed with respect to the causal rules of '*· Still, due to non-reflexivity of '*, only some of them are worlds in which any proposition is also caused by some causal rule. These are the worlds o: that are fixed points of C, that is, the worlds for which o: = C(o:). In such worlds any fact is causally explained. It is these worlds that determine the nonmonotonic semantics, defined below.

Definition 4.1. A causally explained world for a causal rela­ tion'* is a world o: such that o: = C(o:). The nonmonotonic semantics of'* is the set of all causally explained worlds.

Propositions that hold in all causally explained worlds are considered as the nonmonotonic consequences determined by the causal relation. This semantics is indeed nonmonotonic, since the set of such consequences changes nonmonotonically with changes in the underlying set of causal rules.

Now we will establish a correspondence between the above semantics and the nonmonotonic semantics of causal theories from [McCain and Turner, 1997].

A causal theory is an arbitrary set of causal rules. Given a causal theory ,0. and a set u of propositions, we define the following set:

According to [McCain and Turner, 1997], a world o: is causally explained with respect to .0. if it is the only world containing .0.(o:). Or, equivalently, when o: = Th(.0.(o:)) .

Now, causal relations can also be considered as (rather big) causal theories. Moreover, it can be easily verified that for the latter the above definition is equivalent to the definition of causally explained worlds, given earlier. Note also that for any causal theory .0. there exists a least causal relation that includes .0.. We will denote it by '*D.. Actually, '*D. is the set of all causal rules that can be derived from .0. using the postulates for causal relations.

Let us introduce now the following definition:

Definition 4.2. Two causal theories will be called (non­ monotonically) equivalent if they determine the same set of causally explained worlds.

As a first part of our general result, the next theorem shows that the postulates of causal inference preserve the above non­ monotonic semantics.

Theorem 4.1. '*D. is equivalent to .0..

The above theorem shows, in effect, that the logic of causal relations is adequate for the nonmonotonic reasoning in causal theories.

Let us say that a causal rule is Horn one if it has the form A'* l, where lis a literal or the falsity constant f 4 . Our next result will show that any causal theory is equivalent to a Hom theory. But first one more distinction.

• Definition 4.3. · A causal theory is determinate if it contains only Hom rules. A causal relation will be called determinate if it is generated by a determinate causal theory.
• A causal theory .0. will be said to be locally finite if, for any propositional atom p, there is only a finite number of causal rules in ,0. that contain p in their heads.
• A causal theory will be called definite if it is determinate and locally finite.

Clearly, any finite causal theory will be locally finite, though not vice versa. Similarly, any finite determinate the­ ory will be definite. As can be easily verified, a determinate causal theory is definite if and only if, for any literal l, there is no more than a finite number of rules with the head Z. Con­ sequently, our definition of definite theories turns out to be equivalent to that given in [McCain and Turner, 1997].

4 Thus, any constraint A=* f will be a Hom rule in this sense.

By a determinate subrelation of a causal relation => we will mean the least causal relation generated by the set of all Horn rules from=>. Then we have

Theorem 4.2. Any causal relation is nonmonotonically equivalent to its determinate subrelation.

By Theorem 4.1 we can conclude now that any causal the­ ory is equivalent to some determinate theory.

Example. The causal theory

has a single causally explained interpretation {p, ·q}. The last rule t => p V q is not Horn, but it implies a constraint ·(p V q) => f (by Reduction), and it can be verified that the determinate causal theory obtained by replacing the rule with this constraint will be equivalent to the original theory.

Actually, there is a simple algorithm of transforming any causal theory~ into an equivalent determinate theory ~d· It consists in two steps:

1. For any causal rule A=> B from ~, a constraint A 1\ ·B => f is added to ~d;
2. If { Ai => Bi} is a (minimal) set of rules from ~ such that 1\ Bi F Z, for some literall, then a rule 1\ Ai => l is added to ~d·

Then the following result can be proved:

Lemma 4.3. ~ is equivalent to ~d·

Unfortunately, the above algorithm is not modular. More­ over, it does not preserve local finiteness: there are locally finite causal theories such that their determinate counterparts are not locally finite. Still, in many simple cases it gives a convenient recipe for transforming an arbitrary causal theory into an equivalent determinate theory.

Now we are going to show the second part of our main result, namely that causal relations constitute a maximal logic suitable for reasoning in causal theories. To begin with, we introduce

Definition 4.4. Causal theories ~ and r are causally equiv­ alent if=> t:. coincides with =>r.

Two theories are causally equivalent if each can be ob­ tained from the other using the postulates of causal relations. In other words, they are equivalent in the 'causal logic' asso­ ciated with the latter. For example, a theory {A V B => C} is causally equivalent to the theory {A=> C, B => C} (by Strengthening and Or). Speaking generally, any causal the­ ory is causally equivalent to a theory with rules of the form 1\ li => V Zj, where li, lj are literals.

Now, by Theorem 4.1 , we immediately obtain

Corollary 4.4. Causally equivalent theories are nonmono­ tonically equivalent.

The reverse implication in the above corollary does not hold, and a deep reason for this is that the causal equivalence is a monotonic (logical) notion, and hence, unlike the non­ monotonic equivalence, it is preserved under addition of new causal rules. For example, though any causal theory is equiv­ alent to a determinate one, they may give different results if we add some causal rules to them.

Example. (continued) Let us add a rule t => ·p V q both to the causal theory in the preceding example, and to its deter­ minate counterpart. In the first case we obtain a theory which implies t => q (by And), and hence it will have two explained interpretations {p, q} and { ·p, q}. For the reduced determi­ nate theory, however, the addition of this rule will give {p, q} as the only explained interpretation.

What we need is a stronger, monotonic counterpart of the notion of equivalence that would be preserved under addition of new causal rules. This immediately suggests the following definition.

Definition 4.5. Two causal theories ~ and r will be said to be strongly equivalent if, for any set <I> of causal rules, ~ U <I> is nonmonotonically equivalent tor U <I>.

Strongly equivalent theories are 'equivalent forever', that is, they are interchangeable in any larger causal theory with­ out changing the nonrnonotonic semantics. Consequently, strong equivalence can be seen as an equivalence with respect to the monotonic logic of causal theories. And the next result shows that this logic is precisely the logic of causal relations.

Theorem 4.5. Two causal theories are strongly equivalent if and only if they are causally equivalent.

The above result (and its proof) has the same pattern as the corresponding results about strong equivalence of logic programs and default theories (see [Lifschitz et al., 2001; Turner, 2001]).

The above result implies, in effect, that causal relations are maximal inference relations that are adequate for reasoning with causal theories: any postulate that is not valid for causal relations can be 'falsified' by finding a suitable extension of two causal theories that would determine different causally explained interpretations, and hence would produce different nonmonotonic conclusions.

5 Causation versus abduction

Causal inference has numerous connections with other non­ monotonic formalisms. Thus, [Turner, 1999] describes there­ lations with circumscription, autoepistemic and default logic. In this section we will describe a correspondence between causal inference and abductive reasoning. In addition to spe­ cific results, this will give us a broader perspective on the representation capabilities of causal relations.

A general abductive framework can be defined as a pair A = (Cn, A), where Cn is a supraclassical consequence relation, while A is a distinguished set of abducibles. A proposition A is explainable in an abductive framework A if there exists a consistent set of abducibles a C A such that A E Cn(a) . -

A general correspondence between abductive frameworks and input-output logics has been established in [Bochrnan, 2002], based on the identification between the above notion of explainability and input-output derivability. By this corre­ spondence, abducibles are representable by 'reflexive' propo­ sitions satisfying input-output rules A=> A, while abductive frameworks themselves correspond exactly to input-output logics satisfying an additional postulate of Abduction (see below). By these results, input-output logics allow to give a syntax-independent representation of abductive reasoning.

5.1 The abductive subrelation

We will begin with the following definitions:

Definition 5.1. · A proposition A is an abducible in a causal relation => if A => A;

• A causal relation is abductive if it satisfies

(Abduction) If A=> B, then A=> C => B, for some ab­ ducible C.

Causal inference in abductive causal relations is always mediated by abducibles. Consequently, propositions caused by worlds are caused, in effect, by the abducibles that hold in these worlds:

where A is the set of abducibles. As we mentioned, abduc­ tive causal relations correspond to a certain class of abductive systems. Moreover, it has been shown in [Bochman, 2002] that the nonmonotonic semantics of such causal relations de­ scribes, in effect, the explanatory closure, or completion, in associated abductive frameworks (see [Console et al., 1991 ]) .

It turns out that any causal relation => includes a greatest abductive subrelation. The latter can be defined as follows:

Theorem 5.1. If=> is a causal relation, then =>a is the great­ est abductive causal relation included in =>.

The abductive subrelation of a causal relation preserves many properties of the latter. For example, both have the same constraints and abducibles.

Recall that in causally explained interpretations any propo­ sition is caused by other propositions, the latter are also caused by accepted propositions, and so on. Clearly, if our 'causal resources' are limited, such a causal chain should stop somewhere. More exactly, it should reach abducible (self­ explanatory) propositions. This indicates that in many cases the nonmonotonic semantics associated with a causal theory should be determined by the corresponding abductive subre­ lation. Below we will make this claim precise.

Definition 5.2. A causal relation will be called weakly ab­ ductive ifit is nonmonotonically equivalent to its abductive subrelation.

The next definition will give us an important sufficient con­ dition for weak abductivity.

Definition 5.3. A causal relation => is well-founded if any infinite sequence {A0 , A1 , A2 , . .. } of propositions such that An+l =>An, for every n ;:::: 0, contains an abducible.

The above definition describes a variant of a standard notion of well-foundedness with respect to the (transitive) causal order. It should be clear that any causal relation in a finite language should be well-founded. Moreover, let us say that a causal relation is finitary if it is generated by some finite set of causal rules. Then we have Lemma 5.2. Any finitary causal relation is well-founded.

Finally, the next result shows that all such causal relations will be weakly abductive.

Theorem 5.3. Any well-founded causal relation is weakly abductive.

It turns out that well-foundedness is not the only condi­ tion that is sufficient for weak abductivity. Thus, adequately acyclic causal theories (see [McCain and Turner, 1998] for a definition) are not in general well-founded, but they also satisfy this property.

Theorem 5.4. Any adequately acyclic causal relation is weakly abductive.

The above results show that in many cases of interest, the nonmonotonic semantics of causal theories can also be com­ puted using abduction. Still, as a general conclusion, we can say that causal inference constitutes a proper generalization of abductive reasoning beyond the situations where facts are explainable by reference to a fixed set of self-explanatory ab­ ducibles.

6 Conclusions and perspectives

Summing up the main results, we can argue that causal rela­ tions constitute a powerful formalism for nonmonotonic rea­ soning, especially suitable for representing action domains. It has been shown, in particular, that it gives an exact descrip­ tion of the logic underlying causal theories. We have seen also that it allows to give a syntax-independent representa­ tion of abductive reasoning. If we add to this also the natural correspondences with other nonmonotonic formalisms, such as default logic and circumscription (see [Turner, 1999]), we can safely conclude that causal inference covers a significant part of nonmonotonic reasoning.

Viewed from this perspective, there is still much to be done in order to realize the opportunities created by the formalism. There are two kinds of problems that need to resolved in this respect.

The nonmonotonic semantics for causal theories is based on the principle of universal causation which is obviously very strong. The principle implies, for example, that if we have no causal rules for a certain proposition, it should be false in all explainable interpretations. As a result, adding a new propositional atom to the language makes any causal theory inconsistent, since we have no causal rules for it. This makes causal theories extremely sensitive to the underlying language in which they are formulated. One way out has been suggested in [Lifschitz, 1997]; it amounts to restricting the principle of universal causation to a particular subset of explainable propositions. This approach, however, is purely syntactical and hence retains language dependence.

More subtle, yet perceptible difficulties arise also in rep­ resenting indeterminate situations in causal theories. Thus, since any causal theory is reducible to a determinate theory, causal rules with disjunctive heads are ignored in the non­ monotonic semantics; more exactly, they are informative only to the extent that they imply corresponding non-causal con­ straints or Horn rules. This does not mean, however, that we cannot represent indeterminate information in causal the­ ories. Actually, one of the main contributions of [McCain and Turner, 1997] consisted in showing how we can do this quite naturally in common cases (see also [Lin, 1996]). Still, there is yet no systematic understanding whether and how an indeterminate information can be represented by Horn causal rules.

A more general problem concerns the role and place of causal inference in general nonrnonotonic reasoning. Though the former covers many areas of nonrnonotonic reasoning, it does not cover them all. Thus, it does not seem suitable for solving the qualification problem in representing actions. Speaking generally, causal reasoning appears to be indepen­ dent of the kind of nonmonotonicity described by preferential inference from [Kraus et al., 1990]. This naturally suggests that the two kinds of nonmonotonic reasoning with condition­ als could be combined into a single formalism, a grand uni­ form theory of nonrnonotonic reasoning. Actually, this idea is not new; it has been explored more than ten years ago in [Geffner, 1992]. It remains to be seen whether current stud­ ies of causal reasoning can contribute to viability of such a general theory.

Acknowledgments. The author is grateful to Vladimir Lifs­ chitz, Hudson Turner, David Makinson and Leendert van der Torre, as well as to the anonymous referees, for their instruc­ tive comments and suggestions.