Counterfactuals

Abstract

Counterfactuals

Matthew L. Ginsberg

LOGIC GROUP

KNOWLEDGE SYSTEMS LABORATORY

Stanford University Stanford, California 94305

with which to row. This is a fairly general phenomenon: countcrfactuals suggest goal regressions .

Counterfactuals arc a form of commonsense non-mo­ notonic inference that has been of long- term interest to philosophers. In this paper, we begin by dc~cribing some of the impact connterfact:uals can he expcct(!d to have in artificial intelligence, and by reviewing briefly some of the philosophical conclusions which have been drawn about them. Philosophers have noted that the content of any particular connterfactual is in part context-dependent; we present a formal rlescription of counterfactuals that is for­ mally idcutical to the "possible worlds" interpretation due to David Lewis and which allows us to eDcod·e this context­ dependent information clearly in the choice of a sublmi.­ g1mge of the logical language in which we are working. Finally, we examine the application of our ideas in the do­ main of automated diagnosis of hardware faults.

§1. Introduction

A connterfactual is a statement such as, "if p, then q," where p is expected to be false. Typical examples are, "If the electricity hadn't failed, dinner would have been ready on time," or "If the bedroom door were open, I could get the widget I left in there."

From the point of view of logical semantics, counter­ factual s are always true. This is in contrast with our in­ tuitive understanding of their content, which might well accept the statements in the last paragraph while reject­ ing, for example, "If the power hadn't failed, pigs would fly."

Indeed, the distinction between true and false wun­ tcrfactuals seems to underly nmch of our usc of knowledge. When planning the solution to a complicated problem, we reduce it to snhproblems by realizing that we can prove a countcrfactual of i11e form, "lf only thus-and-so "were true, [ would he able t.o solve the original problem." The origi­ nal problem reduces (,o proving the count.erfadual (in some suitable sense) and to arranging for thus-and-so to be true.

Consider t.hc problem of crossing a river if the only boat available has no oars. The countcrfactual, "lf I had some oars, I'd be able to cross the river," suggests replac­ ing the origiual problem with that of Jinding something Countcrfactuals also enable us to describe why plans fail. The example we have already mentioned, "If the electricity hadn't failed, dinner would have been ready on time," is typical. The electricity did fail. But in spite of its lack of logical content, the statement does explain why the soup isn't ready.

Research supported by the Office of Naval H.escrach under grant number N00011-81-K-0001.

Dave Smith has pointed out !.hat additional applica­ tions can he found iu the area of design. Suppose that a machine contains an on-line representation of the design of a complex device. Questions of the form, "If I were to remove the pullup resistor connected to the output of the OR gate, would the output of the circuit change?" arc countcrfactnal in nature.

Diagnosis is similar. The counterfactual , "If the de­ vice fails in this fashion, the AND gate is not functioning," allows us to reason directly from the intended description of the design of the device in question, as opposed to reason­ ing from a description that explicitly allows for the failure of some component, as in [2] . We will also sec that the nature of count.erfactual implication is also such as to sub­ sume the minimal fault assumption.

Finally, countcrfactuals will necessarily play a part in natural language understanding. The extent to which they pervade our communications makes it inevitable that we will eventually need a formal description of them.

There is also a very loose connection between counter­ factuals and causality. In the planning examples we have given, the countcrfactual "if p, then q" corresponds to "·p is a cause for ·q." Tl1c electricity failure is the cause of the lateness of th<! dinner. The lack of oars prevents us from crossing the river.

This connection cannot be pushed too far, however. Suppose that after a MYCIN nm [7], we want to know why the machine asked that a certain clinical test be taken. The response is that, "If the result had been positive, the organism wou.ld have been rodlike." This is a useful coun­ terfactual, hut the causal connection is from the conclusion to the premise, as opposed to the r<!Versc.

An example where there is no causal connection at all can be found in [5]. Suppose that Olga attends a certain party, but that Boris, who is trying to avoid Olga, docs not. If Olga has no similar aversion to Boris, we would have that, "(Even) if Doris had come, Olga would (still)

have come." Here, the counterfactual describes the lack of a causal connection.

My aim in this paper is twofold. Firslly, I would like to describe briefly some of the existing philosophical work that has been done on countcrfactuals, although with an eye toward eventual applications in artificial intelligence. Secondly, I will present a formal description of countcrfac­ tuals that is precise enough to admit a machine implemen­ tation.

§2. Properties of counterfactuals

In his excellent book on counterfactuals, Lewis [5] clar­ ifies the distinction between counterfactuals and standard logical implications by listing some of the properties that distinguish them. The results of this sect ion are not new, but may be unfamiliar to an AI audience. A fairly com­ plete treatment of this topic can also be found in [8].

Contra.position is not necessarily val-id for counterfac­ tuals. If we denote the counterfactual, "if p, then q," by p > q, we cannot conclude -,q > ·p from p > q. Returning to our pow·~r failure example, it may well be the case that if the power hadn't failed, dinner would have been on time:

Tlw power didn't fail > dinner was on time.

It does not follow from this that the electricity would have failed if dinner had been late- there may well be an alter­ native possible cause, such as tardiness on the part of the chef.

Counterfactuals are not necessarily transitive. From p > q and q > r we can not necessarily conclude p > r. The standard cxamplt~ is due to Stalnaker [!>]:

If .1. Eclg,1.r Iloover had been born a Jlussian, then .he would l!a.ve been a CoJJWIIIJiis~, and

If lw had bee11 a Communist, he would l1ave IJeen a traitor

do not tot{etlJcr imply

Tt Hoover had been born a Russia11, he would have hecn a traitor.

Finally, counlt:!]aclua.ls are non-monotonic. Given p > r, we caHJWL ncccss:uily conclu<le p 1\ q > r. In fact, iL is possible to have p > r and p 1\ q > - ·r: The two state­ ments, "lf the electricity hadn't failed, dinner would have been ready on Lime," and "ff the electricity had a 't failed, but 1 had been elected president, dinner would have been late," are coJll pldely consistent.

Glymour and Thomason [1] seem Lo infer from this last observation that the slu<ly of non-Jnonotonic inference generally can be subsumed to some extent under an invcs· tigation of countcrfactuals, but in light of the breadth of the !lOll-monotonic nature of commo11sense reasoning (the frame prohle1n,. default rul.:s, de.), this seems to me to miss the mark. Counterfactuals in fact seem to be a dis­ tinct type of non-monotonic reasoning.

§3. Possible worlds

Following an idea of Stalnake1·'s [9], most modern in­ vestigations of counterfactuals arc based on the notion of possible worlds. Loosely speaking, we analyr.e a counter­ factu:tl p > q by considering the "possible world" that is as similar to our (real) world as possihlc, given that p is true in it. The counterfactual is true or not depe11ding upon whether or not q holds in this world.

Lewis [5] has observed that this "most similar possible world" may not be unique. He defines a counterfactual to be twe if and only if it holds uniforwly in the most similar possible worlds in which the premise holds.

This distinction is apparent if we consio]er the law of the counterfactual excluded middle:

ln Stalnal<cr's view, eithc.r q or --.q will hold in the nearest possible world where p holds , so that the disjunction above will be valid. Lewis points out tl1at this may not be the case by examining the counterfactuals, "If Bi..,ct and Verdi had been compatriots, Bizet would have been Italian," and, "If Bi..,et and Venli had been compatriots, B.izct would not have been Italian." Both of these appear to he invalid.

It is possible to understand the discns:>ion of section 2 in terms of possible worlds; we will discuss only the non­ monotonic nature of counterfactuals here. The other two properties described earlier arc ::;imilar.

The basic reason that p > r and p 1\ q > · r arc con­ sistcnL is that worlds wlwre p 1\ q hold may be much less similar to our own than worlds where p alone holds. It is entirely possible that r holds uniformly in t.hc nearest of the p-worlds while ·r holds uniformly in the (more dis­ tant) nearest of the p 1\ q-worlds. It is also possible that 1· holds in some of the nearest of the p 1\ q-worl<ls while - y holds in others. ln this case we would have only p > r <Uld · (pl\q > r) .

Hel.mning to our power f<tilure t~xamplc, Lhc nearest possible worlds in which the power remained on arc worlds in which dinner was ready on time. ln the nearest of the (much) more distant worlds where I was elected president, dinner was late. In still more distant worlds, such as those where the power remained on and I was elected president, but 110 one bothered to inform me, dinner will once again be prompt.

§4. Framework

From anAl pcrspcct.ivc, the difficulty witl1 the pos­ sible worlds interpretation of couut.erfactuals is that the notion of "simil<1rit.y" is too V<lgucly defined. Our main intention in this paper is to present a sharper definition of it.

Intuitively, there me at least two me11.surcs of the sim­ ilarity, or lack thereof, between different possible worlds. These correspond loosely to the number of propositions whose truth values change and to the relative importance of the prepositions involved.

The latt<'r is the most difficult to understand in any formal sense, since (as we will see in the next section) it is fundamentally dependent upon context. In fact, we will be able to do liLtle more than to provide a way to encode in­ formation concerning the relative importance of the propo­ sitions being considered. It is of some interest to note that the scheme we will present can be used to define a notion of similarity that is unchanged from one possible world to another.

The other source of similarity is more syntactic. If the truth value of a proposition changes unnecessarily, in the sense that the possible world without the change is con­ sistent, the possible world which incorporates the change should be deemed "more distant" from our own than the one which doesn't.

In order to understand this, we will work in a logical system that allows us to assign to a proposition the truth value "unknown" (u) in addition to the more usual ones of "true" (t) or "false"(!). We therefore letT= {t,f,u} be the set of allowable truth values, take L to be the set of sentences in our language, and define a truth function to be a mapping

Intuitively, 1/>(p) = u if we arc uncertain as to the truth or falsity of p.

We will say that a truth function 4> is an extension of a truth function 1/J, writing ¢> S 1/J, if, for all p E L, 1/>(p) = 1/J(p) or 1/J(p) = u. We will call¢> a simple extension if 1/>(p) I 1/J (p) for only a single p E L.

We will also assumt! that we have some way of deter­ mining whether or not a truth function is consistent. In the prcclical.e calculus case upon which W<! arc modelling our analyHis, however, the truth value of a compotmd sen­ tence is delinecl recursively in tenus of the truth values of its components; furthermore, t.he d<'finition only applies if the truth values of these components met or f (as opposed to u). The (consistent) assignment of the truth vah1e8 tor f to all of the sentences in L constitutes an interpretation for L .

This leads us to define a truth function ¢> to be an interpretation if 1/>(p) -:/= u for all pEL. If a truth function 1/; is an interpretation that is an extension of the truth function ¢>, we will say that 1/; is a complete extension of </>. Assuming tliat consistency is defined as a primitive for intcrprctatiom;, we will say that a truth function c/> is consistent iff ¢> has a consistent complete extension. ·

Here are some examples. In the first two cases, 1/J is a consistent complete extension of ¢> . Since 4> in the third case has no consistent complete extension, it is inconsis­ tent.

Proof. The consistent complete extension of such an ex­ tension would he a consistent complete extension of the original (inconsistent) truth function. o

Equivalently, any truth function with a consistent exten­ sion is consistent.

For a consistent truth function ¢>, the closure of ¢> will be the maximally extended truth function 1/J such that every consistent complete extension of ¢> is an extension of 1/J. The closure of ¢> will be denoted cl( ¢> ). If ¢> = cl( ¢>), ¢> will be called closed; it is not hard to sec that this corresponds precisely to logical closure.

In the example below, ¢> 1 and ¢2 are the only consis­ tent complete extensions of ¢>:

Lemma 2. cl( ¢>) S ¢>.

Proof. Let { </>;} be the consistent complete extensions of ¢>. Then ·Pi ::::; ¢> for all i, so that cl( 4>) S ¢>. o

Related t.o the notion of closure is that of reduction: a truth fuuction cfo will he called reduced if all of its simple extensions arc consistent. Tlw idea is that a simple exten­ sion of 4> r.orresponds to the acquisition of mo1·e knowledge about some specific proposition; if every such extension is consistent, the original truth function must have been minimal in the sense that it had no extensions which were "necessary" consequences of it.

Lemma 3. A COJJsist·cnt truth function</> is reduced if and 0111y if it closed.

Proof. For any p E L, if 1/>(p) = u and ¢> is reduced, the tmt!t function obtained by replacing c/J(p) with t (re­ spectively f) is consistent and th<!rcl"orc has a consistent complete extension which we will denote ¢> 1 ,t (respectively </! 11 1 ). Since </lpt(P) = t and cPpJ(P) := /, cl(¢)(p) = u; it follows that 4> is closed if it is reduced.

The reverse implication is similar.

o

§5. Similarity

The terminology introduced in the last ~ection allows us to make precise some of the ideas in section 3: possible worlds correspond to consistent interpretations, and sets of possible worlds to consistent truth functions.

The difficulty with this is th<.~t we still lack a for­ mal notion of similarity. Part of the problem is context­ dependent, as we can see from the pair of counterfactuals

If Caesar had been in command {in Korea], l1e would have used the atom bomb

and If Caesar had been in command, he would l1ave used catapults.

This example is Quine's [6]. Either counterfactual may well be trne (although not both); if the first, Caesar's character is important to onr notion of similarity; if the second, it is the tools he had available which are relevant.

It is clearly impossible to select between these two counterfactuals in advance; the best we can do is to present a method for encoding in our semantic machinery the in­ formation leading to the choice. In order to do this, let L' be a subset of L, and suppose that ¢> is a fixed truth function defined on L - L'. We can now define a truth function '1/J on L' to be consistent if and only if the truth function

is consistent. The elTect of this is to fix the truth values outside of L', so that any consistent truth function on L' must be consistent with then~.

In the above example, if L' includes "Caesar was a ruthless military leader," but not, "Caesar's military tools were those of the Roman Empire at its height," we will have to accept Caesar's usc of c;~tapull.s wil.houl; question, rq;anllcss of the weapons available at the tiuw of tl1e en­ gag<!ment, resulting in the validity of the counterfactnal which concludes that he would have used catapults. If the situation were reversed, the other countcrfactual would be valid. If L' includes both of the statements describ­ ing Caesa1:, the construction we will present will ambigu­ ously select eitlu~r of the counterfactuals, while if both of the dcscriptiom; arc relegated to L, both conntcrfactuals will be vacuously true because no truth function ¢> with </!(Caesar in command) = t will have a consistent exten­ sion to all of L.

Given the choice of a (possibly restricted) language !/,let p be a sentence in U and <P a doHed truth function with <f>(p) = f. We will investigate the consequences of the countcrfactual premise p be defining a new truth function, to be denoted ¢>1 1 , and corresponding to </> with the truth value at p replaced by t.

Throughout this section, we will follow the Caesarian example carefully. We have the following propositions in L':

K = Caesar in comma.nd in Korea

r = Caesar was ruthless

R = Caesar's tools were t.IJose of the Romans

a := the atom bomb was used in Ko1·ea

c = catapults were used in Korea.

In L are the axioms:

The last of these is equivalent to -.( K 1\ r 1\ R). Our initial truth assignment is given by:

Of interest to us is the truth function ¢>1 1(; what if Caesar had been in command in Korea?

The general difficulty is that simply changing <f>(p) to t may well produce an inconsistent truth function. We begin therefore by replacing </J(p) not with t, but with u. This truth function </>' must be consistent (since ¢> is an extension of it), but need not be closed.

Assume now that there is at least one reduced truth function 1/J of which ¢;' is an extension. (We can genearlly take for 1/J the closure of the truth fuuction which assigns u to every p E L.) The set of all such 'if;'s is partially ordered under extension; let </>" be a minimal clement of it.

The result of replacing </>" (p) with t is necessarily con­ sistent, since ¢>" is reduced and <J>"(p) = u initially. Let 0 be the trnL11 function obtained by making this replacement, and take </>ll' to be cl(O). We also define </>(p > q) = cf>lv(q).

The construction we have given works through the construction of the "intermediate" truth function </>". This is in some sense a set of the most similar possible worlds in which we might have ¢>(p) being either true or false. The reason we have done this is because it seems to be technically easier to define similarity for a world of which ours is an extension ( </>' in the above construction) than for one which is not directly comparable with it (as</> with <f;(p) replaced by t would be).

Having construct1:d similar worlds where p might hold, it is stra.ightforward to investigate the consequences if we assume that it does hold. This is the content of our taking ¢>1 1 , to be the closure of</;" with ¢/'(p) replaced by t.

The choice of truth function </;" corresponds to choos­ ing a subset of the possible worlds in which cp(p) = t. In our military example, assuming Caesar to be in command in Korea requin:d our ahaudouing the truth of either r or ll, ami th1: chuic<: of which to discard corresponded to our choice of ,P".

An alternative would be to assume that the worlds where we abandon one description arc just as similar to our own as those in which we abandon another. Lewis might well make this choice; it corresponds to defining ¢>(p > q) to be t or f if it takes this value independent of the choice of </>", and to be u otlwrwise.

Theorem 4. With ti!C above definition, our construction is formally identical to Lewis' possible world iuterpreta­ tiOJI.

Proof. Sec [:1]. o

§6. Example: diagnosis

6.1 Setting

Gcnesereth has proposed [2] that it is pom;ihle for ma­ chines to be used in automated diagnosis, provided that the machines are given both a design for the Jevice in ques­ tion, and the ability to manipulate the device by varying its inputs and observing the results. He investigates the diagnosis of a full adder (top of next page) in considerable detail.

Genesereth describes the design of the full adder in a variant of prefix predicate calculus. Quoting him:

These axioms describe the structural description of the full adder. SDI, for example, states that XI is an exclusive-or gate. SDH states that the first outpnt of Xl i~ connected to the second input of A2.

Genescrcth also states in a similar form results de­ scribing the behavior of the various sorts of gates, and de­ scribing what it means for two points in the circuit to be connected. Using these acldition;il axioms, it; is possible to prove that if, for example, the first input to the full adder is 011 whill! t.he ot.JH:r t.wo arc ofr, the first output should be on whik t.lu! second should be uif.

6.2 Diagnosis using predicate calculus

The situation of interest, of course, is t.hat in which the outputs of the adder are not as predicted by the design. Gencsercth assumes that we have:

A full adder is essentially a one bit adder with carry in and carry out, and it is usually used as one of n elements in an n bit adder. A graphical representation of its design is given [above]. It has three inputs and two outputs and consists of two "xor" gates (Xl and X2), two "and" gates (Al and A2), and an "or" gate (01) ... In nonnal operation, the first output (the "sum" line) is "on" if and only if an odd number of inputs is "on"; the second output (the "carry" line) is "on" if and only if at least two inputs are "on". [4]

In other words, the values of the t.hree inputs to the adder ;u·e as described at the end of the last subsection, but both of the outputs are off.

The observed behavior dtaractcrizcd by 0Bl- OB2 is inconsistent with the design given by ·S.Dl- SD17 and the inputs ACl-AC3. Diagnosis is a matter of resolving this inconsistency.

To do so using predicate calculus, Ceriesereth assumes (correctly') that the device in qu~stion does not satisfy the design description given earlier, but instead satisfies some weaker "device assumptions". In the example we are consirlering, he assumes that: .

1. The connections are all as described in the rlcsign, and
2. At most one of the gates is broken (the single fault assumption).

These device assumptions can be encoded by replacing the structural description axioms SD1-·f)D5 with axioms such as:

These .new axioms <1.re consistent with the observed behavior of the adder, a.nd lead to the conclusions that

and

In other words, one of the exclusive-or gates is broken, and the remaining components are functioning satisfactorily.

The information about the functionality of the AND and OR. gates is useful because it enables us to generate a test to determine which of the two exclusive-or gates is in fact faulty.

The diflicnHy with this approach is that it requires us to generate device assumptions to replace the structural description SD1- SDl7. It is possible that the fault(s) in the device are snch that these assumptions arc invalid, in which case the system will be unable to diagnose the device without a replacement set of device assumptions.

6.3 Diagnosis using counterfactuals

The device assumptions in the last subsection were in­ troduced to encode our belief that the wiring in the adder was correct, and to enable us to take advantage of the sim­ plifying as·mmption that only one of the remaining compo­ nents was damaged. Both of these conditions can be recast naturally in the framework of counterfactuals.

To perform the diagnosis using the methods we have presented, we will assume the stru.ctural description DS1DS17 anrl the inputs achieved by ACI- AC3, and examine the counterfactual consequences of the observed outputs OB1- 0B2. There are three possible explanations for the fault:

1. One or more of the components is faulty.
2. The wiring is faulty.
3. The inputs were not as expected.

We eliminate all but the first from our counterfactual rea­ soning by including only the component a..<>smnptions SD1SD5 in our restricted language L'. The wiring and input a~sumptions SD6- SD17 and AC1- AC3 are therefore as­ sumed to be independent of the countel"factual assump­ tions corresponding to the observed misbehavior of the device.

The conclusion (10) that one of the two exclusive-or gates must he faulty is in fact a logical consequence of the behavior of the device:

OBl/\ OB2-> (OR (NOT (XORG Xi)) (NOT (XORG X2))).

Meanwhile, because the remaining components need not be contributing to the observed fault, their continued per­ formance is counter/actually implied by the observed be­ havior:

OBl/\ 0B2 >(AND (ANDG A1) (ANDG A2) (ORG 01)) ..

This reappearance of (11) is especially useful. Because of the non-monotonic nature of counterfactnal reasoning, it is of course possible that additional observations appended to the lefthand side of the above equation will invalidate its conclusion; this will happen whenever the single fault· assumption is violated. In this case, however, rather than generating a contradiction, the couuterfactual analysis will automatically produce a new diagnosis which once again involves failure for a minimal set of components.

It is possible, however, for a counterfactual analysis to suggest a violation of the single fault assumption when one is not required. If the observed behavior can be explained either by the failure of a single component, or by the failure of a pair of dilTerent components, both will be proposed. There is nothing counterintuitive about this, however-it is quite normal to assume that a group of normally unde­ pendable components has failed before questioning a single part of proven reliability. In any event, we can if neces­ sary retain the single fault assumption by using it to select among the possible <P'"s in the counterfactual construction itself.

§7. Conclusion

Our aim in this paper has been to present a formal description of counterfactuals, describing them in terms of existing logical operators instead of following the usual practice of developing a "counterfactual calculus" to de­ scribe their behavior.

The construction we have presented seems to meet this objective. It has indeed descrilH!d c:ounterfactuals in terms of existing logical primitives, and reduces to the "possible worlds" interpretation of counterfactuals that is accepted by philosophers. .

Om construction also distinguishes clearly between the context dcpmulent and context. independent features of counterfactual implication. It provides us with a pre­ cise method for selecting those aspects of our world which are to be considered inviolable even under a counterfac­ tual assumption; having made such a choice, we proceed to generate possible worlds which respect it.

The biggest difficulty with the approach we have de­ scribed is the raLher heavy-handed nature of the choice described in the last paragraph. Although it is possible to clearly recognize ambiguities remaining in. the analysis of any particular connterfactual (they correspond to the choice of c/J" in our construction), we have no method for choosing consistently between them. In any specific imple­ mentation, it will of course be possible to select a <P" when one is needed, but we have not considered the nature of the formalism that should govern this choice.

Acknowledgement

A preliminary version of this research was presented to MUGS at Stanford, and the author would like to thank the participants in that seminar for their useful comments on this work. Mike Genesereth and Dave Smith were es­ pecially helpful.