Relating Default Logic and Circumscription

1. Introduction

Circumscription (McCarthy 1980. 1986; Lifschitz · 1984} and default logic (Reiter 1980} are both formal­ isms for reasoning in the absence of complete informa­ tion. Often, the available knowledge about the state of the world (problem domain, task) is incomplete, in the sense that required details are unknown. Certain plausible assumptions can sometimes be made - to fill in some of these missing details - that may further the goals of the reasoning system. These assumptions may or may not prove correct when further information becomes available. for example through further obser­ vation. The availability of additional information may thus lead to the retraction of certain conclusions. This property is called nonmonotonicity.

Both default logic and circumscription can be used to enforce ··policies" (defaults. preferences . ... ) that (ideally) lead to highly plausible .conjectures in the absence of definite information. The actual world is assumed to be among some restricted subset of those worlds that meet the criteria of what is known. This selection of "preferred" worlds may be externally jus­ tified by convention. probabilities. etc, but these exter­ nal justifications do not play a direct role in the theory. Beyond these intuitive similarities. the two approaches are different on both the syntacti~ and semantic levels.

1 Parts of this work were done at the University of British Columbia, and supported in part by an I. W. Killam Predoctoral Scholarship and NSERC grant A7642.

Default logic and circumscription were developed at approximately the same time as attempts to formal­ ize nonmonotonic inference. which was recognized as an important facet of intelligent behaviour. In the intervening years. there has been considerable activity in this area. Both formalisms have been extensively studied, and several new paradigms have been pro­ posed. These two. however, have had remarkable staying power. and applications and refinements con­ tinue to surface. Since both attempt to capture similar phenomena, the natural question is whether either subsumes the other.

Is there a direct mapping by which default theories subsume circumscription, or vice versa? There is, as yet, no definitive answer to this question. In what follows, we draw together results that begin to provide answers. Because there are many criteria that can be used to determine "subsumption", a plurality of "answers" is perhaps the best that can be provided. As we proceed we outline the assumptions that under­ lie the partial answers that can be provided to date .

We generally refer to Lifschitz' (1984} generaliza­ tion of circumscription, which we simply call "cir­ cumscription". This version allows the denotations of terms, as well as of predicates, to be varied. Where appropriate in what follows, we draw attention to the effect of the presence or absence of variable terms.

In what follows, we present l'ery brief sketches of semantic underpinnings for the two formalisms . These sketches are then contrasted and compared to help determine some of the relationships between the tech­ niques .

2. Circumscription

One form of preference is the "Closed-World Assumption". or CWA. This is the assumption that all the facts about the world have been stated (Reiter 1978]. Those facts that do not follow from the given facts can thus be assumed to be false. The assumption of complete knowledge about the world can be prob­ lematic if applied indiscriminately. but it is sometimes reasonable to assume complete information. especially about particular predicates. If such an assumption is warranted. the world can be characterized by its being among those models having the smallest possible extension for the predicates in question. given the con­ straints of what is known. Syntactically. this amounts to assuming the negation of every atomic fact (over the predicates for which complete information is assumed) not entailed by the original theory.

In general. this idea can be extended to predicates about which only incomplete information is available. so long as it is reasonable to assume that they cover as few individuals as necessary. In such cases. the models satisfying this "generalized" CW A [Minker 1982] need not agree on the extensions of the predi­ cates concerned, only on the minimality (with respect to the original theory) of those extensions.

The idea of minimization can be generalized from subset minimality of predicates' extensions to minimal­ ity according some arbitrary pre-order on models. Circumscription is a syntactic device that characterizes what is true in a theory's minimal models. 2 The theory is augmented by a second-order axiom that can be obtained deterministically. given a particular choice of an ordering on models. This axiom represents the assumption that the world is among the theory's minimal models. The conjectures of interest then follow from this extended theory by normal deduction.

A typical application would be to axiomatize the "normal" state of the world and then circumscriptively minimize the set of abnormalities; conjecturing that things are as normal as possible [McCarthy 1986]. This approach allows circumscription to be used for some forms of default reasoning, although the full details

remain to be worked out.

3. Default Logic

Default logic sanctions conjectures based on infer­ ence rules. called defaults . These have the form ~. and can be read "If a is believed. and ~ is not 'Y disbelieved. then -y can be assumed". Because of Ws role. defaults allow conjectures based on both what is known and what is not known. Intuitively, the defaults provide criteria for preferring world­ descriptions over one another. Roughly speaking, each default. ~. sanctions a conjecture (-y) that 'Y specializes a world-description provided certain "prerequisites" (a) are believed, so long as it remains consistent to believe certain "gating facts" or ·'justifi­ cations" (~). A default theory consists of a set of defaults and a set of first-order axioms. Ideally, the defaults induce (possibly several) stable, maximal, spe­ cializations - called extensions- of the theory given by the axioms.

2 For simplicity's sake, we ignore the issue of incom­ pleteness. See [Perlis & Minker 1986) or (Etherington 1987a) for a discussion.

In spite of the apparent simplicity and naturalness of defaults, the semantics of default logic is more complex than that of circumscription. There are two reasons for this. First. defaults are by nature global: each refers to everything that is believed or not believed. This means that the semantics must be based on sets of models (which we call world-descriptions), rather than individual models, to allow the concepts of belief and unbelief to be represented. Second. since the justification (~) and consequent (-y) of a default need not coincide. defaults can predicate conjectures on the continuing lack of belief in certain propositions without asserting or otherwise enforcing this lack of belief. Thus. although local comparisons between world-descriptions can be used to partially represent the preference relation, information not inherent 'in the world-descriptions must be considered in the final determination of preference. The semantics must somehow make this information available.

Given these caveats, we can define a semantics for default logic analogous to the minimal model semantics of cit:cumscription. The defaults define a preference ordering that, in turn, determines a set of minimal world-descriptions. These must be further restricted to exclude those that violate the lack-of­ belief constraints that implicitly gave them rise. Each of the remaining world-descriptions consists of all the models of some extension of the default theory , and each extension can be so characterized. 3

4. Default Logic as Subsuming

Circumscription

Since circumscription's proof-theory avoids the consistency checking (in general not semidecidable) associated with default logic proofs, it would be nice if circumscription subsumed default logic. This would allow us to deal only with circumscriptive theories. Unfortunately, this is not the case.

Theorem 1

Default logic can make conjectures that cannot be obtained by generalized circumscription without .variable terms. I

3 This semantics is developed in detail elsewhere [Eth­ erington 1987a,b).

d h ( { :aa ~bb }· { }) has a The efault t eory .,... unique extension, containing a * b. Without variable terms, generalized circumscription can­ not conjecture such new inequalities . I

Allowing variable terms precludes our proof for Theorem 1. The question of whether a version of the theorem still holds with variable terms remains open.

The converse of Theorem 1 is apparently false . Let us denote the generalized circumscription of the theory. T. with the predicates/terms in X variable. according to some ordering, R, by CLOSURE (T; X; R) . Assuming CLOSURE (T; X; R) is consistent. the default theory (with an infinite set of defaults):

obviously produces the required results. This seems an unsatisfactory answer to the question of whether default logic can capture circumscription. however! It requires first determining the result of any particular circumscription, then copying it into the default theory. It is not clear exactly what constitutes a trans­ lation, although one might at least require a finite set of defaults, for example. We will return to this ques­ tion shortly.

S. "Translations" from Default Logic to Circumscription

Theorem 1 makes the title of this section seem paradoxical. There has been some work on partial translations. however . Grosof [ 1984] presents two equivalent translation schemes for normal default theories, one involving 'ab' predicates (c f., [McCarthy 1986]), the other involving m1mmlzmg arbitrary expressions. We will discuss the former. as it is con­ ceptually simpler .

Given a default theory. ~ =(D. W). the transla­ tion scheme carries the first-order axioms , W, over Ci ; : f3; unchanged. For each closed normal default , ~

the axiom a; 1\ -f3; :::> ab (i) is added. Then ab is cir­ cumscribed in the resulting theory, varying ab and each predicate that occurs in any of the f3; 's. Grosof observes that this "translation" actually differs from default logic in several respects .

First. the equality predicate is not affected by the circumscriptive theory. Grosof proposes excluding defaults about equality to remedy this. but this is insufficient. Any default that affects equality will not behave "correctly" in the circumscriptive theory .

A further difference is that the circumscriptive theory inherits circumscription's ··cautious'' nature . 4 The multiplicity of extensions of a default theory are reflected in disjunctive statements in the translated theory. Thus the conjectures given by the translated theory may be weaker than those sanctioned by the original default theory. Opinion seems to be split over whether this should be viewed as a liability or an asset.

Finally, Grosof's translation of the normal default ,. . A I I d :a:::>f3 ' a actually more c ose y correspon s to Ci :::> f3 since the translation allows the conjecture of -a from -f3. Grosof appears not to have noticed this.

Even allowing for these discrepancies. Grosof presents only intuitive arguments and examples in sup­ port of the suitability of his translation scheme . It is not clear. in general. to what degree the translated theory corresponds to the original default theory.

Imielinski [1985] takes the complementary. more restrictive. tack of defining a translation scheme to be adequate if theories and their translations produce precisely the same conclusions , and furthermore the translation scheme is "modular". Modularity requires the translation of the defaults and that of the first­ order facts to be independent.

Imielinski views the translation of a set of defaults as a collection of first-order facts and a pre­ order relation. Both of these must be determined from the defaults (D) alone. without reference to the specific facts (W) at hand. This is a desirable pro­ perty, since one would rather not have to recompute one's representation of knowledge (in addition to the necessary adjustments to the set of one's conjectures) every time a new fact is learned. ·

Given these strictures. Imielinski proves that even normal defaults can not be modularly translated to generalized circumscription. There are some defaults that do have modular translations. however . These include propositional semi-normal defaults without prerequisites (e .g., :a;@). The proof of this result does not directly generalize to open first-order defaults , 5 although such defaults may have modular translations. It also remains open whether other classes of defaults can be modularly translated.

4 McDermott [1982] distinguishes "cautious" nonmono­ tonic systems (such as circumscription), which define "theorems" as those facts true in all preferred worlds, from "brave" systems (such as default logic) , which allow a rea­ soner to commit to a particular preferred world.

5 The inclusion of domain-closure axioms is sufficient to allow the generalization, but this violates the requirement that the translation must be independent of the first-order theory.

The reasons that only prerequisite-free defaults have modular translations become clear if we contrast the semantics we have sketched for default logic and the minimal-model semantics of circumscription. The former is based on orderings over sets of models . the latter on orderings over individual models. Sets of models are necessary to capture the proof-theoretic notion of provability. Since the prerequisites of a default must be provable for the default to have any effect. default logic's semantics must be based on sets of models . Circumscription's submodel relation, how­ e.ver. only considers pairs of models . Prerequisite-free defaults fit nicely into circumscription precisely because they are prerequisite-free . Such defaults impose no (global) provability requirements. only con­ sistency requirements. Consistency can be determined by the existence of a single model. and so can be locally determined. This model-theoretic perspective yields a much simpler, more direct , proof that cir­ cumscription can provide a modular translation of default theories - even in the propositional case - only for prerequisite free defaults.

It is arguable that the requirement that a theory and its "translation" have identical sets of theorems is too strong. For example. we have noted that default logic is a "brave" reasoner while circumscription is "cautious". It seems reasonable to expect that a cir­ cumscriptive translation of default theories would reflect this cautious nature. perhaps returning those facts true in all extensions . Conversely . circumscrip­ tive conjectures apply to all individuals, whereas those resulting from open defaults apply only to individuals having names in the language. It might , therefore , be reasonable to expect circumscriptive versions of default theories with open defaults to prove certain stronger conjectures (at least for theories without domain closure axioms) . Perhaps such side-effects of translation are sufficiently benign that they can be accepted.

These considerations suggest that Imielinski's results might be taken as a "worst case" scenario. leav­ ing open the possibility of acceptable translation schemes for defaults with prerequisites, given a weaker notion of "acceptable". The question remains open, and we do not further consider this possibility here.

6. Translations from Circumscription to Default Logic

The dual of the question we have been examining is whether default logic can be used to circumscribe (in any but the trivial sense mentioned at the begin­ ning of this paper). The previous section outlined some of the different capabilities of the two formal­ isms: brave vs cautious, effects on equality. global

(provability) vs local (consistency) comparisons in the model-theory (proof-theory), and statements about "unnamed" individuals. In all but the last of these categories, default logic is stronger . This suggests that the search for a direct embedding of circumscription in default logic might be more successful than the con­ verse attempt. The answer to this is , "Yes , and no.".

One facet of generalized circumscription is com­ pletely absent from default logic. Circumscription may hold some predicates constant. while others are allowed to vary. In default logic. there is no way to restrict the repercussions of the defaults to some par­ ticular set of predicates (and/or individuals). Because predicates can be richly interconnected, the effects of a default inference may be arbitrarily far-reaching . This seems to preclude a completely-general , direct embedding.

In restricted cases. better results obtain. We can rule out unnamed individuals by requiring the domain to be closed, and decide the equality theory to prevent defaults from affecting equality. If we then consider circumscription, with all predicates required to be variable, we get the correspondence outlined in

Theorem 2.

Theorem 2

Assume that we are given a set of ground terms, a 1, ... ,an ; that T j-- '\1 x . x = a1 V .. . V x =an; that for each i and j , T j-- a i "¢ aj or T j-­ a i = aj; and that X includes all the predicates of L. Then those formulae true in every exten-

This result readily generalizes to the joint circumscrip­ tion of multiple predicates.

The semantics of circumscription is defined rela­

tive to those models of T that are minimal according to the ordering dictated by the choice of X and R in CLOSURE (T; X; R). The proof of Theorem 2 allows us to relate these models to extensions of the default theory . .1.

Corollary 3

If E is an extension of a. then every model of E is an (X, Sp)-minimal model ofT. I

6 Sp denotes the (subset) minimization relation for the predicate, P.

Corollary 4

If M is an (X, Sp)·minimal model ofT. then M is a model for some extension of ~ . I

For this restricted class of theories. the default theory . .i , has the advantage that different extensions (assuming there are more than one) allow the reasoner to explore the various alternative minimizations. The brave/cautious distinction can be seen to be exactly the difference between considering only one of or all of the default theory's extensions. In a sense, .i captures the brave circumscription of P in T with every predi· cate variable.

Notice that Theorem 2 requires that T have a domain-closure axiom and decide the equality of each pair of terms mentioned therein. If the theory does not decide the equality of these terms, then the default theory becomes stronger than the circumscrip· tive theory. in the sense that Corollary 3 continues to hold but Theorem 2 and Corollary 4 do not. Because of the limitations of open defaults concerning unnamed individuals. none of the results generalize to theories with no domain-closure axiom, and we have Theorem 5.

TheoremS

If T does not entail a domain-closure axiom (and T ¥- 'd x. -Px), then every extension for .i has models that are not (X, Sp )· minimal. I

Even more pessimistic is Theorem 6. which states that fixed predicates preclude the straightforward transla­ tion of circumscription to default logic we have con­ sidered, even for closed-domain, unique-name

theories.

Theorem 6

There are theories, T. such that T t­ 'd x . x = a 1 Y ... V x = <Xn and fori :#= j , T f­ a; *- a j · and (let no combination of the extensions of A = { : .. -:.:x l T) precisely characterIzes the (X, :Sp)-mlnimal models of T, when X does not include all the predicates of T. I

We experimented with an extended version of default logic that allowed for the specification of "fixed" predicates. Although we were able to show that the results in [Reiter 1980, chapters 2 and 3) hold for this logic, and - at least for finite theories - the obvious generalization of the semantics sketched above applies, we abandoned this approach. It proved incapable of yielding an analogue for Theorem 2 in the presence of fixed predicates. (The best that could be szuaranteed was that those szround literals in P contained in all extensions were true in all minimal models. As Example 2 illustrates. this is significantly weaker - sufficiently so that we doubt that the (abun­ dant) extra machinery required is worthwhile.

Example 2

Let Q be fixed, and let T be fu' X. X =a V X =b. a "*- b, -.Pa 1\ -.Pb ::> Qa} . The P-minimal models of T are (loosely represented):

There are no ground literals in P true in every P-minimal model. However,

In other words, one can circumscriptively con­ jecture that there is exactly one P if -.Qa. and none otherwise. I

Gelfond and Przymusinska [1985) prove the weak result alluded to above for their version of Minker's [1982) generalized closed-world assumption, which allows fixed predicates. Gelfond, Przymusinska, and Przymusinski [1986] have developed a further generali­ zation of the CWA, called the extended closed-world assumption (ECW A). Where the CW A and GCW A extend theories by adding negative ground literals, the ECW A adds the negations of arbitrary formulae meet­ ing certain criteria. Gelfond et a/ prove a much stronger result for the ECWA.

Proposition 7 (Gelfond et al)

A structure, M. is a model for ECW A (T) iff it is a miniqtal model forT. I

At first glance this might suggest that there should be some analogous result for some default theory. It appears that the ECW A actually achieves this power by the subterfuge discussed near the beginning of this paper: by adding every instance of the circumscrip­ tion schema. This is certainly the case in the absence of variable predicates.

Theorem 8

If there are no variable predicates, then ECW A (T) augments T with every instance of the circumscription schema.

We have seen that - if such a thing exists - any general translation from circumscription to default logic, short of adding defaults for each instance of the circumscription schema, requires more power than the closed-world default provides. The existence of an appropriate translation remains open.

7. Autoepistemic Logic

In light of recent developments, we should men­ tion Moore's (1985) autoepistemic logic in this context. Autoepistemic logic is a modal language allowing non­ monotonic reasoning, based on agents' introspection on their knowledge. Default reasoning is achieved by explicitly predicating conjectures on the absence of knowledge . Any fact not a consequence of what is known is explicitly marked as unknown.

Konolige (1987] has shown that autoepistemic logic and default logic - though superficially dissimi­ lar - are formally equivalent. From this it is possible to infer that the statements we have made - and the theorems we have proven - on the relationship between default logic and circumscription apply equally to that between autoepistemic logic and circumscription.

8. Conclusions

We have considered the relationship between default logic and circumscription. We showed that the closed-world default sometimes coincides with cir­ cumscnptiOn; that, in a particularly useless way, default logic subsumes circumscription; and that default logic is capable of affecting the equality theory while generalized circumscription (without variable terms) is not.

For particular classes of theories, we have pro­ vided a translation from circumscription to default logic. This translation applies only to theories with domain-closure axioms, and then only when the cir­ cumscriptive theory specifies all predicates as variable. We showed that the introduction of fixed predicates and applications to open domains each provide cir­ cumscription with capabilities not available using sim­ ple closed-world default theories.

Finally, we used semantic comparisons to highlight some of the essential differences between the two approaches. This allowed us to suggest that some of the work on translations between the two formal­ isms may not have noticed the essential characteristics that should be carefully considered in determining adequacy conditions for translations.