Circumscribing Defaults

1 Introduction

Various logics have- been developed to formalize non­ monotonic reasoning [Rei87]. They mainly fall into two camps: consistency-based logics, such as default logic [Rei80] and autoepistemic logic [Moo85], and minimal model-based logics, such as various forms of circumscriptions[McC80, Lif85]. Understanding the re­ lation between the two is important. It will not only enable us to compare the relative expressive powers of these logics, but it may also suggest a logic with the advantages of both approaches.

To compare the expressive powers of these logics, two questions are asked: can circumscription be expressed in default logic or autoepistemic logic, and vice versa.

The former question has been answered by Ethering­ ton [Eth87] and Konolige [Kon89]. Etherington showed that circumscription can be translated to default logic under the domain closure assumption. Konolige ex­ tended the autoepistemic logic so that it can handle 'quantifying-in', and then showed that circumscription can be translated to the extended autoepistemic logic.

The latter, expressing default logic in circumscription· [Gro84], seems to be more interesting. One of the reasons is that circumscription is within the framework of classical logic, which has been well-studied and has many known properties. In addition, circum­ scription avoids consistency checks; it seems more at­ tractive computationally.

*Since the equivalence between default logic and autoepis­ temic logic has been established[Kon87], the solution to the

While it is desirable to express default logic in the existing forms of circumscription, it is, unfortunately, impossible to do so. Imielinski[Imi87] proved that de­ fault logic could not be modularly translated to circum­ scription in general. Informally, circumscription seems to correspond to default logic with a special form of de­ fault - that is, normal default without prerequisites. It has difficulty in expressing non-normal default, which is very useful in dealing with certain problems in common sense reasoning[Mor88, Gel88] .

A natural question then, is whether it is possible to ex­ tend circumscription so that it has the expressive power of default logic. That is, is it possible to construct a "default logic" in the spirit of circumscription? Since circumscription is nothing but an axiomatization of a certain nonmonotonic reasoning in classical logic, the above question then becomes - is it possible to axiom­ atize the type of nonmonotonic reasoning permitted by consistency-based logics in terms of classical logic, with­ out referring to modal operators, non-language expres­ sions (such as defaults, which need consistency tests) , and fixed points?

Some of the extensions of circumscription, such as autocircumscription[Per88] and introspective circumscription[Lif89], do extend the expressive power of circumscription. In particular, they can express cer­ tain non-normal defaults. However, a closer examina­ tion shows that they are still not as expressive as default logic or autoepistemic logic, in the sense that inconsis­ tency may arise in some cases where default logic and/or autoepistemic logic are consistentt.

The results in this paper demonstrate that certain lim­ itations of the expressive power of circumscription are not due to the language (first-order in most cases, plus a certain second-order formula) itself. Almost all the ex­ pressive power of default logic can be achieved by mere classical logic with a fixed point operator. This further clarifies the relation between circumscription and default logic.

problem of expressing default logic in circumscription will automatically lead to the solution to a similar problem for autoepistemic logic.

t Application of autocircumscription or introspective cir­ cumscription to the Yale Shooting Problem in [Gel88]'s for­ mulation is one of the examples.

This paper is organized as follows. We begin with an informal discussion which leads to the formal definition and semantics of a circumscriptive extension for a default theory. We then show that the new formalism is indeed an extension of circumscription. We proceed to show that the circumscriptive extension and the original ex­ tension of default logic, as defined by Reiter[Rei80], are equivalent under the domain closure assumption and the unique names assumption. Finally, we show the applica­ tions of the new formalism to some well-known problems in default reasoning, problems that involve non-normal defaults.

2 Consistency, Minimization and Fixed Point

In this section, we discuss what is necessary and what is not necessary for default reasoning. We also suggest how circumscription can be extended so that it will have the expressive power of default logic.

Classical logic allows us to represent our knowledge about the world by sentences of a logical language and to derive more facts about the world through its deductive system. However, our knowledge about the world is in most cases incomplete. To fill in the gaps, assumptions areoften made in default reasoning. These assumptions are often based on what is known, as well as what is not known. In order to formalize this, nonmonotonic logic augments the classical logic with certain mecha­ nisms which can permit assumptions to be made under certain conditions.

In default logic, rules called "default" are used for this purpose. A default correctly captures the patterns in default reasoning: assume 1 whenever a is known and -.{3 is not known. Although a default looks simple, it turns out to be quite expressive. For instance, Konolige [Kon87] shows that every set of sentences in autoepis­ temic logic, which involve complicated constructions as embedded £-operators, can be effectively ·rewritten as a default theory. However, default logic departs from clas­ sical logic in that it expresses the defaults neither in the language of classical logic, nor as inference rules. Also, default logic requires an explicit consistency test, which is not even semidecidable.

On the other hand, circumscription is a second-order formula, which means that it requires nothing more than classical logic. In particular, ignorance of knowledge is detected by formula or predicate minimization instead of by an explicit consistency test. Circumscription seems, however, incapable of expressing non-normal defaults. The main reason is that it always forces the predicate circumscribed to be minimal in itself. In fact, finding a minimal extension of a formula (or a maximal extension of the negation of the formula) is very closely related to the consistency test of a formula. Consider a sentence T and a predicate Q, for an individual a in the universe. T rj -.Q( a) ( Q( a) is consistent with T) is equivalent to the following: there exists a model M ofT, such that M F= Q(a). Assuming that models ofT have the same universe and denotation functions, a set of all a such that T rj -.Q( a) is clearly the union of extensions of Q in all those models t. The union of all such extensions, similar to a minimal extension of a predicate, can be expressed by a second-order formula, which can be used as the basis for sanctioning other formulas. This will allow us to have a formalism with full expressive power of default logic but still within the classical logic. In addition, we will gain the ability to reason about open domain freely, as we shall show later.

In both default logic and autoepistemic logic, the con­ sistency of a formula is tested globally (with respect to the final set of beliefs, instead of the premises). This is especially necessary when non-normal defaults are in­ volved, because otherwise, inconsistency may arise when new assumptions are added. To test the consistency of a formula globally, the concept of a fixed point seems to be inevitable. The use of fixed point does not change the language itself, but it complicates the logic. It seems that this is the price we have to pay to gain the full expressive power of the default logic.

In what follows, we show how defaults can be repre­ sented by second-order formulas, and how an extension of a default theory can be defined as a fixed point.

3 Circumscriptive Extension

A default is an expression of the form a(x) : {3(x)h(x), where a (x), {3 (x) and 1 (x) are first-order formulas whose free variables are among those of x = x1, ... , X 0 · In the rest of the paper, we will use x for x, if confusion does not arise from the context. A default is closed iff a, {3 and 1 contain no free variables; otherwise, it is open. A default theory is a pair (A, D) where A is a set of first­ order sentences and D is a set of defaults. A default theory is open if at least one default in D is open.

Given a default theory (A, D), for each default a;(x): {3;(x)h;(x) E D, we introduce new predicate constants P; and Q; and add an axiom 'v'x(a;(x) +-+ P;(x)) 1\ 'v'x({3;(x) +-+ Q;(x)) to A. The default a;(x): {3;(x)h;(x) can then be rewritten as P;(x) : Q;(x )h;(x ). We assume that all default theories (A, D) in this paper have been rewritten in this way.

Let S, T be sentences. Let P;, Q; be some predi­ cate constants in S, T and let Z be a tuple of all other predicate constants in S,T. We write S(p;,q;,z) and T(p;, q;, z) for the sentences resulting from substituting all occurrences of P;, Q; and Z qy corresponding predi­ cate variables p;, q; and corresponding tuple of predicate variables z, respectively.

Definition 3.1 Given a default theory (A, D) where both A and D are finite, we define an opemtor ~ on two sentences S, T as follows: ~(S,T) =:

*This discussion is informal. The intuition is formalized in lemmas 5.1 and 5.2 in section 5.

Definition 3.2 Given a default theory (A , D) where both A and D are finite , let

A first-order sentence B is defined to be a circumscripoo tive extension of (A ,D) iff Mod(B) = Mod(UB;) j:O where Mod(T) = {MIM f= T} .

Informally, the sentence Vx['lp;q;z(S(p;, q;,z) -+ p;(x)) A 3p;q;z(T(p;,q;,z) A q;(x))-+ -y;(x)] says that if a;(x) follows from Sand -.{j;(x) does not follow from T , then -y;(x) is true. By iterating with the operator 6. and defining circumscriptive extension as a fixed point of the iteration, we make sure that -y;(x) is in the circumscrip­ tive extension whenever 1) a;(x) can be derived only from the premises A and the assumptions which have been made up to each point of an iterative step, and 2) {1;(x) is consistent with the circumscriptive extension.

We have the following proposition, which follows from definition 3.2 directly.

Proposition 3.1 § If B is a circumscriptive extension of a default theory (A , D), then Cn(B) = Cn(l.J: 0 B;) where Cn(T) = { <pl<p is a first-order sentence and T f= <p } .

In what follows, we give some examples to illustrate the usage of circumscriptive extensions.

Example 1 Let A:: P(a) A P(b) A (-.P = Q) f . and D = { : -.P(x)I-.P(x)} .

There is only one circumscriptive extension of (A, D) , namely, B = AAVx(x "I a Ax "I b-+ ...,p(z)). Note that this is exactly equivalent to circumscription of P in A.

Example 2 Let A= (P(a) V P(b)) A (-.P = Q) and D = {: -.P(x)I-.P(x)} .

There are two circumscriptive extension of (A, D) , namely, B1 = A A Vx(x "I a -+ -.P(x)) and B2 = AAVx(x "I b-+ -.P(x)) . Note that B1 V B2 is equivalent to circumscription of P in A .

Example 3 Let A :: T(a) A T(b) A B(a) A a "# b A (-.ab1 = Q1) A (-.ab2 = Q2). Let D = {T(x) : -.ab1(x)I-.F(x) , B(x) : ...,ab2(x)l F(x) , B(x) : -,ab2( x) I ab 1 ( x)}. This is a simplified version of the Bird Problem under Morris' formulation[Mor88] . Note that T stands for 'thing', B stands for 'bird', and F stands for 'fly'. There is a unique circumscriptive extension for this default theory (A,D) , which is B:: A A Vx(x =a-+ F(x)) A Vx(x = b-+ -.F(x)) A Vx(x = a -+ ab1(x)) . It follows that, B 1- -.F(b) and B 1- F(a) . Note that this problem involves non-normal defaults, which cannot be handled by ordinary circumscription.

Semantically, circumscriptive extension can be char­ acterized as follows. Let A be a sentence, and P be a predicate constant. Let Mod( A) be the class of all the models of A. Let M be a structure. Using the notations similar to that in [Lif89], let X be a set of tuples of ele­ ments in the universe of M such that the length of each tuple in X equals the arity of P. We write M[X I P] for the structure which differs from M in that it interprets some or all predicate constants differently, in particular it interprets P as X. In addition, we use M [P] to de­ note the interpretation of Pin M (sometimes P could be a wff); IMI denotes the universe (domain) of M. Let M be a class of structures. We define a sequence of classes of structures in the following way: let

SProofs of proposition, lemmas, and theorems are either omitted or sketched in this paper due to space restriction. Interested readers are referred to [Qia91]

f...,p = Q stands for Vx(...,P(x) +-+ Q(x)) . This conjunct is necessary for A, so that the wff ...,p( x) in the default can be replaced by a new predicate constant Q.

where

Theorem 3.1 A class of structures M is the class of all the models of a circumscriptive extension B of a default

Proof Note that for any structure M,

0

Note that , unlike the conventional semantics of clas­ sical logic, the satisfaction relation between a structure and a circumscriptive extension cannot be defined with­ out referring to other structures. This is similar to modal logic where the satisfaction relation between a structure and a modal sentence is defined in terms of a set of pos­ sible worlds. However, in our case, the "possible worlds" are the very structures which satisfy the circumscriptive extension. Therefore, we define the class of all the mod­ els of a circumscriptive extension as a fixed point of a sequence of applications of the operator 0 . The opera­ tor 0(./1!, M) picks up the structures in ./If which satisfy

for each default in D. Consider the structures with the same universe and interpretations for object and func­ tion constants as M . Let Oa;(M) be the intersection of extensions of P; in all such structures in ./If and Op;(M) be the union of extensions of Q; in all such structures in M. 0(./lf, M) then picks up those structures in .N such that the intersection of Oa;(M) and Op;(M) is a subset of the interpretation of 'Yi in M for all defaults in D .

4 Circumscriptive Extension and Circumscription

In this section, we will show that circumscriptive exten­ sion is indeed an extension of circumscription.

Circumscription exists in many different versions. Here, we compare circumscriptive extension with a model-theoretic definition of circumscription. Let A be a first-order sentence and P be a tuple of predicate con­ stants to be circumscribed. Semantically, circumscrip­ tion is defined as sentences that are true in all P-minimal models of A. Given two models M and N of A with the same domain and the same interpretations of object and function constants, M 5:P N if the extension of P; in M is a subset of the extension of P; in N for all P; in P. A P-minimal model of A is then a model M of A minimal with respect to the relation 5,p.

As we mentioned earlier, circumscription itself seems to correspond to a special case of default reason­ ing, namely, the default reasoning with defaults ": ...,P(x)/...,P(x)." Let Bn be a circumscriptive extension of (A, D) where D = {: ...,p;(x)j...,P;(x)IP; E P}. Obvi­ ously, Bn satisfies the following equation: Cn(Bn) =:

Cn(A 1\ 1\P;EP Vx[3p;z(Bn(p;, z) 1\ ...,p;(x))---+ ...,p;(x)]) Lemma 4.1 Models of Bn are P-minimal models of A. Lemma 4.2 If M is a P-minimal model of A, then M satisfies some Bn.

Theorem 4.1 A first-order formula <p is true in all P­ minimal models of A iff it follows from all Bn.

Proof The theorem follows directly from lemmas 4.1 and 4.2. 0

Since the first-order sentences that follow from circum­ scription are true in all P-minimal models of A, circum­ scription corresponds to the sentences that follow from all circumscriptive extensions of (A,{: ...,P(x)j-,P(x)}). This reflects the different attitude between default logic and circumscription towards nonmonotonic reasoning, as pointed out by [Eth87]. Default logic is a "brave" reasoner while circumscription is "cautious". In defin­ ing circumscriptive extension, we follow the "brave" ap­ proach of default logic. To be "cautious", one can always just believe the sentences that follow from all circum­ scriptive extensions.

In addition, in a more general definition of circum­ scription, some of the predicates are considered as vari­ ables and the others are fixed. While in translating de­ fault theory to circumscriptive extension, however, all the predicates are considered as variables. As has been proven in [DeK89), fixed predicates are not essential in circumscription. In other words, fixed predicates can be eliminated by circumscribing a slightly different set of axioms A, while allowing all predicates to vary. Because of this, the above results can be extended to circumscrip­ tion with fixed variables.

5 Circumscriptive Extension and Default Logic Extension

In this section, we establish a relation between circum­ scriptive extension with default logic extension. First, we review the definition of an extension of a default the­ ory.

Given a closed default theory (A, D), Reiter[Rei80] de­ fines an extension of (A, D) as a fixed point of an oper­ ator r. For any set of wffs S, f(S) is the smallest set such that: 1) it contains A, 2) it is closed under logical consequence, and 3) it contains 1 whenever a : !3/r ED and a E f(S) and -,p ¢ S . An extension of an open default theory is defined as an extension of a closed de­ fault theory (A,CLOSED(D)), where CLOSED(D) is a set of closed defaults resulting from instantiating each open default in D by ground terms constructible from all the object constants, function constants and the Skolem functions of the Skolemized form of the default theory.

It is obvious that, in default logic, the domain clo­ sure assumption (DCA) is implicitly made. The domain closure assumption essentially assumes that the domain contains only those individuals which are explicitly re­ ferred to in the theory. In circumscriptive extension, however, we do not make this assumption, and therefore, we can make conjectures about individuals in "open do­ main." For instance, the extension of the default theory for the example 1 is Cn(A). No conjecture is made about individuals without names; whereas in circumscriptive extension, we have V x( x i- a 1\ x i- b ---+ ...,p( x)). How­ ever, comparison between circumscriptive extension and default theory extension can be made under DC A .

The other difference concerns equality. In default logic, one can make conjectures about equalities. For ex­ ample, an extension of a default theory(~,{: a i- b/a i­ b}) contains a i- b. Etherington [Eth88] pointed out t~at circumscription has difficulty in deriving such a conJec­ ture. The same is true for circumscriptive extension. In the above example, one needs to maximize inequality. However, Op(M) gives us the union of extensions of j3 in different structures with the same universe and deno­ tation functions . This will. not enable us to pick up the structures which interpret a and b differently. Therefore, we add the unique-names assumption (UN A) explicitly, in order to compare default logic extension and circum­ scriptive extension. UN A says that each individual in the universe has a unique name.

One can express DCA and UN A in first-order logic if the language of default theory has a finite number of ob­ ject constants and is function-free. In fact, DCA can be expressed by the first-order sentence Vx(x = c1 V ... V x = cn), where c; 's are the set of all object constants in the language, and UN A can be expressed by the conjunc­ tion of c; f- Cj for each pair of distinct object constants in the language.

As discussed in the previous section, in circumscrip­ tive extension, a second-order formula is used to replace the consistency test in the definition of extension in de­ fault logic. The first published result directly relating consistency test to first-order schema is in [Per88] . The following lemmas make this relation more general. They also establish the major link between circumscriptive ex­ tension and default logic extension.

Lemma 5.1 Let T be a sentence. Let Q be a predicate constant in T, and let Z be a tuple of all other predicate constants in T. If 3qz(T( q, z) 1\ q( a)) is satisfiable, then T ~ -.Q(a).

Lemma 5.2 LetT be a sentence such that T F= DCA/\ UN A. Let Q, Z be the same as in lemma 5.1. If T ~ -.Q(a) then DCA 1\ UN A F= 3qz(T(q, z) 1\ q(a)).

Proof Suppose T ~ -.Q( a), then there exists a model M ofT such that M F= Q(a) . For if this is not true, then for all model M ofT, M F= -.Q(a). This means that T F= -.Q( a) which contradicts the hypothesis.

To show that DCA 1\ UN A F= 3q, z(T(q, z) 1\ q(a)), it suffices to show that for all the models M of DCA 1\ UNA, M F= 3q,z(T(q,z)l\q(a)). Let M be an arbi­ trary model of DCA 1\ UN A. From above, there exists a structure M' such that M' F= T 1\ Q(a). In the fol­ lowing, we show that M' is isomorphic to M* which is a structure the same as M except for the interpretation of all predicate constants in T.

Let f and g be functions which map all the ground terms in T to IMI and IM'I respectively. Since T F= DCA 1\ UN A and since both M and M' satisfy DCA 1\ UN A, both f and g are bijections. Obviously f- 1 exists and is a bijection too. Let h = go f- 1 . Since both g and f- 1 are bijections, h is a bijection from M to M'. Let M* be a structure, the same as M, except that it interprets the predicate symbols in the following way. For n-place predicate symbol Q, and for each n-tuple < a1, .. . , an > of elements of 1M* I,

Similarly, for each n-place predicate symbol Pin Z,

Since M* has the same domain and interpretation of all the constant symbols as M, for all i, h(M* (c;l) = M' (c;D. Clearly, h is an isomorphism from M* onto M' . Hence, M' and M* are isomorphic. Therefore, they are elementarily equivalent and since M' F= T 1\ Q( a), M* F T 1\ Q(a). Let X = M* lQD and Y = M* (ZJ, then M[XjQ, Y/Z] = M* ~ M'. Since M[X/Q, Y/Z] p T(Q, Z) 1\ Q(a), M F= 3qz(T(q, z) 1\ q(a)) . Since M is an arbitrary model of DCA 1\ UN A , DCA 1\ UN A F= 3qz(T(q, z) 1\ q(a)) . 0

To establish the relation between circumscriptive ex­ tension and extension as defined in default logic, we also need the following lemmas.

Lemma 5.3 Let T be a sentence. Let P be a predicate constant in T , and let Z be a tuple of all other predicate constants in T. lfT F= P(a) then 'Vpz(T(p, z)-+ p(a)).

Lemma 5.4 LetT be a sentence such that T F= DCA/\ UN A . Let P, Z be the same as in lemma 5.9. if there is a structure M such that M F= DCA 1\ UN A, and M F= 'Vpz (T(p, z)-+ p(a)), then T F= P(a) .

Proof Similar to the proof of lemma 5.2. 0

Now, we are able to present the theorem which shows that circumscriptive extension and default theory exten­ sion are equivalent under DCA and UN A .

Theorem 5.1 Given a default theory (A , D) where A F= DCA AU N A. A finitely axiomatizable theory E is an extension of(A,CLOSED(D)) iff E = Cn(B) and B is a circumscriptive extension of (A , D).

The theorem demonstrates that circumscriptive exten­ sion essentially has the same expressive power as exten­ sion except for UN A . Specifically, circumscriptive ex­ tension can handle non-normal defaults. Moreover, it can also make conjectures about individuals in open dcr mam.

6 Applications

Example 4 (Yale Shooting Problem)

This is a well known problem suggested by Hanks and McDermott [HaM87] to demonstrate that nonmonotonic logics have difficulty in reasoning about a class of prob­ lems including the frame problem. It essentially shows that for this problem, two extensions could be derived using either default logic or circumscription. While one extension corresponds to intuition, the other is counter­ intuitive. Morris [Mor88]presented a simple solution to the problem. He used standard default logic. The only difference between his and Hanks and McDermott's for­ mulations is that Morris used non-normal default to rep­ resent frame axiom. Gelfond [Gel88] also showed that the Yale shooting problem could be solved by autoepis­ temic logic using a formulation similar to that of Morris. Below, we show a solution to this problem by finding the circumscriptive extension for a default theory under Morris' formulation. Axioms A is a conjunction of UN A and the followings :

Also, there is a set of actions:

We have one default for the frame axiom:

For this default theory (A, D) , there is a unique circum­ scriptive extension.

Obviously, t(DEAD, 53 ) is in the circumscriptive ex­ tension. Notice that inconsistency will arise for both this and the next examples, when introspective circumscrip­ tion and autocircumscription are applied.

Example 5 (Nixon Diamond)

This is another well known example originally sug­ gested by Reiter to demonstrate the situation of mul­ tiple extensions. Using non-normal defaults, it can be formulated as follows:

where A is a conjunction of (9) and (10), and D contains (11) to (14).

There are two circumscriptive extensions for this de­ fault theory.

7 Conclusion

In this paper, we constructed a "default logic" in the spirit of circumscription. We showed that it is indeed an extension of circumscription and it has the expressive power of default logic. These lead us to conclude that: 1. Default logic can be expressed by classical logic with a fixed point operator. Certain syntactic structures in consistency-based logics such as modal operator, non­ language expressions like defaults, and consistency test are not essential. Fixed point construction, however, is necessary. 2. The method of circumscription provides some flexibility in reasoning about "open domain" . 3. Our extension of circumscription still cannot conjecture the unique-names assumptionll.