Computing Circumscription

1. Introduction

Research in the theory of commonsense reasoning has revealed a fundamental difference between how uni­ versal assertions are used in mathematics on the one hand, and in the area of commonsense knowledge on the other. In mathematics, when a proposition is claimed to be universally true, the assertion includes a complete list of conditions on the objects involved under which the proposition is asserted ("for all x i- 0", "for all sufficiently large natural numbers", etc.) But in everyday life we of­ ten assert that a certain proposition is true "in general"; we know that there are exceptions, and we can list some of them, but the list of exceptions is not a part of the assertion. The "abnormality" of each item on the list is a separate piece of commonsense knowledge. We know, for instance, that birds, generally, can fly. We know, ruther­ more, that ostriches are exceptions. And penguins are exceptions. And dead birds arc exceptions. All these assertions appear to be separate commonsense facts.

The language of predicate logic has been created pri­ marily for the purpose of formalizing mathematics, and it does not provide any means for talking about what is "generally true" and what "exceptions" are. If we want to use that language for representing commonsense knowl­ edge then methods for formalizing assertions about ex­ ceptions have to be developed.

The study of such methods belongs to the area of non-monotonic logic. Extending an axiom set can force us to retract some of the conclusions we have derived from the axioms if the new axioms include additional in­ formation about abnormal objects. The set of theorems depends on the set of axioms in a non-monotonic way.

COMPUTING CIRCUMSCRIPTION

Vladimir Lifschitz

Department of Computer Science Stanford University Stanford, CA 94305

Consider a simple example which illustrates some of the difficulties involved. Let BI x, OS x, F L x and AB x represent the conditions "x is a bird", "xis an ostrich", "x can fly" and "x is abnormal". We want to express these commonsense facts: birds, generally, can fly; ostriches are birds and cannot fly. Consider the formulas:

These formulas represent a part of what has been said about the ability of birds to fly, but they do not say one important thing: objects are considered normal if there is no evidence to the contrary. The three available facts imply that ostriches are abnormal, and they give no information about the abnormality of any other objects. We want to be able to conclude then that ostriches are the only exceptions:

But (1) does not follow from the conjunction A of A1 , A2, A3.

We discuss here one of the approaches to this prob­ lem, the theory of circumscription (McCarthy 1980, 1984). The process of circumscription transforms A into a stronger formula A' which says essentially that AB has a minimal possible extension under the condition A. It turns out that A' is equivalent to the conjunction of A and (1).

A' depends on A non-monotonically. In this sense, circumscription provides an interpretation of non­ monotonic reasoning in the usual (monotonic) logic.

In more complex cases, we deal with several kinds of abnormality, aud the extensions of sev<!ral predicates AB 1, AB2, ... have to be minimized . These minimiza­ tions sometimes conflict with each other, and there may be a need to establish relative priorities between them (McCarthy 1984).

Currently there are no working systems of knowl­ edge representation based on circumscription. Such a system would include a database A and a metamathe­ matical statement describing how circumscription should be performed. (Such a description would specify, for in­ stance, which predicates should be minimized, and what their priorities are). The system would also include a theorem prover capable of deriving logical consequences from the result A' of circumscribing A.

The design of such a system has to deal with a ma­ jor difficulty: the definition of circumscription involves a second-order quantifier, so that A' is a formula of a second-order language. The purpose of this paper is to present metamathematical theorems which, in some in­ stances, enable us to replace the result of circumscription by an equivalent first-order formula. These methods can be successfully applied to some examples of circumscrip­ tion that seem to be typical for applications to the fomlal­ ization of commonsense knowledge, and, hopefully, they can be used as a basis for implementing circumscription. Our main tool is a theorem which establishes the equiva­ lence of a special case of circumscription to a modification of Clark's predicate completion (Clark 1978). Connec­ tions between these two concepts were first studied in (Reiter 1982).

Proofs of some special cases of the results stated in this paper can be found in (Lifschitz 1984). Complete proofs will be published elsewhere.

2. Second-Order Formulas

A second order language is defined, just as a first or­ der language, by sets of function constants and predicate constants, each of some arity n, n ~ 0. In the second or­ der language we have, besides object variables, also n-ary fu11ction varia.bles and n-ary predicate variables. (Object. variables and constants arc identified with function vari­ ables and constants of arity 0). fiot.h function ancl predi­ cate variables can be bon.nd by qnm1tiliers. A sentence is a formula without free (function or predicate) variables.

A structure M for a second order language L consists of a non-empty universe IMI, functions from !Min toM representing the function constants and subsets of !Min representing the predicate constants. For any constant K, we denote the object (function or set) representing K in M by M(K). Equality is interpreted as identity, func­ tion variables range over arbitrary functions from !Min to M, and predicate variables range over arbitrary sub­ sets of I Min. A model of a sentence A is any structure M such that A is true in M. A implies fl if every model of A is a model of B; A is equivalent to B if they have the same models.

An n-ary predicate is an expression of the form >.:z:A(:z:), where :z; is a tuple of n object variaoles, A(:z:) a formula. As usual, if U is ,\:z; A(:z:), and tis a tuple of n terms, then Ut stands for A(t). We identify a predicate constant P with the predicate >.:z:P:z:, and similarly for predicate variables.

If U, V are n-ary predicates, then U ~ V stands for Vx(Ux:) V:z:). Thus U ~ V expresses that the extension of U is a subset of the extension of V. We apply this notation to tuples u = u 1, ... , u m and v = vl, ... 'v m of predicates, assuming that they are similar (i.e., that U; and V; have the same arity) : U ~ V stands for

Furthermore, U = V sta.Ji.ds for U ~ V 1\ V ~ U, and U < V stands for U ~ V 1\ -.(V ~ U). If m = 1 then U < V means simply that the extension of U is a proper subset of the extension of V.

3. Parallel Circumscription

First we consider parallel circumscription, when no priorities between the minimized predicates arc specified. Let P be a tuple of predicate constants, Z a tuple of function and/or predicate constants disjoint with P, and let A(P, Z) be a sentence. The circumscription of P in A(P, Z) wit/1 va1·iab/e Z is the sentence

(Here p,z arc tuples of variables similar to P,Z). This formula expresses that P has a minimal possible exten­ sion under the condition A(P, Z) when Z is allowed to vary in the process of minimization. We denote (2) by Circnm(A(P, Z); P; Z). When Z is empty, we write Circum(A(P); P).

In applications to the formalization of commonsense reasoning, A(P, Z) is the conjunction of the axioms , P is the list of abnormality predicates, and Z is the list of symbols that we- intend to characterize by means of circumscription, as F L in the example discussed in the introduction. The circumscription we intend to perform in that case is

The model-theoretic meaning of circumscription can be expressed in terms of the following notation. Let P, Z be as in the definition of circumscription. For any two structures Ml> M2, we write M1 ~P;Z M2 if

• (i) IMll = IM21,
• (ii) M1 [K] = M2[K] for every constant Knot in P,Z,
• (iii) M1[P;] c M2 [P;] for every P; in P.

Thus M1 ~P;Z Mz if M1 and Mz differ only in how they interpret the constants in P and Z, and the exten­ sion of each P; in M1 is a subset of its extension in M2.

Clearly, ~ P;Z is a pre-order (i.e., a reflexive and transitive relation) on the class of all structures. It is possible, however, that M1 ~P;Z M 2 and, at the same time, M2 ~P;Z M1 for two different structures M1 , M2. This happens when M 1 , M 2 differ by the interpretations of symbols in Z. In other words, ~P;Z is, generally, not anti-symmetric and thus not a partial order. Still, we can speak of the minimality of structures with respect to ~P;Z: a structure M is minimal in a class S of struc­ tures if M E S and there is no structure M' E S such that M' <P;Z M. (We write M1 <P;Z Mz if M 1 ~P;Z M2 but not M2 ~P;Z Ml). This concept of minimality was introduced essentially in (McCarthy 1980).

The models of circumscription can be characterized now as follows:

Proposition 1. A structure M is a model ofCircum(A; P; Z) iff M is minimal in the class of models of A with respect to ~ P;Z.

This equivalence follows from the fact that specifying values of p, z for which A(p, z) 1\ p < P is true in M is equivalent to specifying a model M' of A such that M' <P;Z M.

4. Examples

Before describing general methods for determining the result of circumscription, we discuss a few examples. In these examples Z is empty, and Pis a single predicate constant.

Example 1. A = Pa, a an object constant. Circum­ scription asserts that the extension of P is a minimal set satisfying this condition; in other words, a is its only element:

Example. 2. A = --,Pa. This docs not give any "pos­ itive" information about P and is true even when P is identically false. Hence

We get the same result whenever A contains no positive occurP.nccs of P.

Example 3. A = Pa 1\ Pb. Circumscription asserts that a and b are the only elements of P:

Example 4. A = Pa V Pb. In Examples 1-3, circum­ scription provided an explicit definition and thus a unique possible value for P. In this case, there are two minimal values:

Example 5. A = Pa V (Pb/\Pc ). The previous examples suggest that the answer might be

But we should take into consideration that a may be equal to one of b, c, and then the second disjunctive term does not give a minimal P. The correct answer is

Example 6. A = Vx(Qx :J Px). Clearly, circumscrip­ tion simply changes implication to equivalence:

More generally, for any predicate U (without parameters) which does not contain P,

This can be also viewed as a generalization of Exan1ples 1 and 3, because in those examples A can be written in the form U ~ P:

Example 7. A = 3xPx. Circumscription asserts that the extent~ion of P is a "minimal non-empty" t~ct, i.e., a singleton:

Example 8. In all examples above, we were able to ex­ press the result of circumscription without second-order quantifiers. Let now P, Q be binary predicate constants, and A be

Then Circum( A; P) asserts that P is the transitive clo­ sure of Q <md thus is not equivalent to a first-order sen­ tence.

Notice that the formula of this example is "good" by all logical standards: it is universal and, moreover, Hom, and it contains no function symbols. What syntactic fea­ tures make it difficult for circumscription? This question will be answered in the next section.

5. Separable Formulas

In Examples 2 and 6 above we saw that there are two classes of formulas for which the result of circumscription can be easily determined: formulas without positive oc­ curences of P, and formulas of the form U ~ P, where U does not contain P. What about formulas constructed from subformulas of these two types using conjunctions and disjunctions?

First let us look at conjunctions of such formulas. Let P be again a tuple of predicate constants P1, . . . Pm. We say that A(P) is solit~y with respect to P if it is a conjunction of

• (i) formulas containing no positive occurences of Pl,··· Pm, and
• (ii) formulas of the form U ~ P;, where U is a predicate not containing P1, ... Pm·

Using predicate calculus, we can write any solitary formula in the form

where N(P) contains no positive occurences of P1o .. . , P,., and U is a tuple of predicates not containing Pb ... Pm. Then the result of cirqunscription is given by the formula

Using this formula, we can do, in particular, the circum­ scriptions of Examples 1, 2, 3 and 6.

Next we want to be able to handle formulas with disjunctions, like Examples 4 and 5. If a formula is con­ structed from subformulas of forms (i) and (ii) using con­ junctions and disjunctions, we call it separable. In a sep­ arable formula, positive occurenccs of P1 , ··· Pm are sep­ arated by conjunctions and disjunctions from negative occurences and from each other.

Any separable formula is equivalent to a disjunction of solitary formulas and consequently can be written in the form

where N;(P) contains no positive occurences of P1o .. . , Pm, and each Ui is a tuple of predicates not containing Pl,··· Pm·

The following theorem generalizes ( 4) to separable formulas.

Theorem 1. If A(P) is equivalent to (5) tben Circum(A{P); P) is equivalent to

where D; is

Thus the result of circumscription in a separable first-order sentence is a first-order sentence of about the same logical complexity. Circum(A(P); P) asserts that P may have one of the finite number of possible values U 1 , U 2 , ·. ·· Hence every model of Circum(A(P); P) belongs to one of a finite number of classes: there are models in which P is the same as U 1 , models in which P is the same as U 2 , etc. If M is a structure in which P = Ui then D; is the additional condition which, if true in M, guarantees that M is a model of Circum(A(P); P).

The transformation of Ui ~ P into U; = P is based on the same idea as predicate completion of (Clark 1978): transforming sufficient conditions into necessary and suf­ ficient. When applied to non-separable Horn formulas, like the formula of Example 8, predicate completion of­ ten gives conditions that arc weaker than the result of circumscription. On the other hand, the transformation of (5) into (G) is not restricted to Horn formulas and is in this respect more general.

U::;ing Theorem l, we can easily do all circumscrip­ tions of L·:xamples 1-6. Examples. 7 and 8 arc not separa­ ble.

Exrunple 7 shows that there arc non-separable for­ mulas for which circumscription can be done in the first­ order language. Here is one more example:

The first argument can be easily written in the form sep­ arable with respect to P1 and in the form separable with respect to P2, hut it is not equivalent to a formula sepa­ rable with respect to the pair P1 , P2.

Theorem 1 cannot be applied directly to circumscrip­ tions with a non-empty Z, like (3). Two observations often help in such cases.

First, every circumscription with a non-empty Z can be reduced to a circumscription with the empty Z:

Proposition 2. Circum(A(P, Z); P; Z) is equivalent to

For example, (3) reduces to

where fl is a binary predicate variable.

The problem with this trick is, of course, that the first argument of circumscription in (8), generally, con­ tains new second-order quantifiers. In our example, we have to circumscribe AB in a formula with the quantifier 3fl.

The second observation sometimes helps eliminate quantifiers like this. If q is a tuple of predicate variables, and A(q) is separable with respect to q, then we can write A(q) in the form

(Separability with respect to a tuple of predicate variables is defined in the same way as separability with respect to a tuple of predicate constants). It can be easily seen that 3qA(q) is equivalent then to V; Ni[Ui]. In our example, the only positive occurence of fl is in the first conjunctive term, so we write the conjunction as

Then the first argument of (9) is equivalent to the con­ junction of A2 and

In the presence of A2 this simplifies to Vx(OS x :::> AB x). Thus it remains to circumscribe AB in A2 II OS :::; AB. By {4), the result is A2 II OS = AB. The second term here is equivalent to (1).

Many other examples of circumscription arising in connection with the formalization of commonsense rea­ soning can be han riled in the same manner.

6. General Circumscription

In some applications of circumscription we have sev­ eral abnormality predicates which are assigned different priorities. For example, we may wish to minimize AB1 and AB2 , the former at higher priority than the latter. This means that, instead of minimizing ( AB 1, AB2) with respect to the relation :::; defined by

we use the relation

To prepare for the general treatment of priorities in the next section, we define now the generalization of cir­ cumscription needed for that purpose.

Let p, q be disjoint similar tuples of predicate vari­ ables, and let p ::::5 q be a formula which has no parameters besides p, q. We say that p ::S q defines a regular order in a structure M if the sentences

are true in M. As the name suggests, such a formula defines a (partial) order on vectors of subsets of I Min. Clearly, p :::; q defines a regular order in every structure. A more interesting example is given by ( 10). We write p --< q for p ::S q II p =/= q.

As before, let P be a tuple of predicate constants, Z a tuple of constants disjoint with P, A(P, Z) a sentence. Let p ::S q be a formula which does not contain P, Z, and delines a regular order in every model of A(P, Z). The circumscription of Pin A(P, Z) with variable Z witlt respect t.o ~.symbolically Circum:;(A(P, Z); I'; Z), is

The results of Sections 3 and 5 can be extended to general circumscription as follows . We write

if

• (i) IMJI = IM2J,
• (ii) M1[K) = M2[K] for every constant Knot in P,Z,
• (iii) p ~ q is true in M1 (or, equivalently, in M2) for M1[P] asp and M2[P] as q.

Proposition 1'. A structure M is a model of Circum~ (A; P; Z) iff M is minimal in the class of models of A with respect to ::;P;Zd.

Theorem 1'. If A(P) is equivalent to (5) then Circum~ (A(P); P) is equivalent to

where Di is

Notice that this formula for Di differs from the for­ mula of Theorem 1 only when there are at least two dis­ junctive terms. Consequently, the effect of general cir­ cumscription on a solitary formula can be computed us­ ing the same formula ( 4) that we used for parallel cir­ cumscription. Thus we have:

Corollary. If A is solitary then Circum~{A; P) does not depend on :5.

Proposition 2'. Circum~{A(P, Z); P; Z) is equivalent to

In the next section we show how this generalization of circumscription works in applications to the formaliza­ tion of commonsense reasoning.

7. Priorities

The database B defined below contains these com­ monsense facts: things, in general, do not fiy; airplanes and birds, in general, do; hut ostriches and dead birds, generally, do not. lJ is the conjunction of these formulas:

We expect that circumscribing AB1 , ··· ,AB5 in B should give the following result: AB2, AB4 and AB5 are identically false (since there is no evidence that they are not); ostriches and dead birds are the only objects satisfying AB3; airplanes and the birds that are alive and not ostriches are the only objects satisfying AB 1.

However, the circumscription

does not lead to these conclusions. The reason is that the goals of minimizing our five abnormality predicates conflict with each other. For instance, minimizing the extensions of AB2 and AB3 conflicts with the goal of minimizing AB 1·

The solution proposed in (McCarthy 1984) is to es­ tablish priorities between different kinds of abnormality. Let a tuple P of predicate variables be broken into dis­ joint parts Pi, P 2, ... , pk. We want to express the idea that the predicates in P 1 should be minimized at higher priority than the predicates in P 2, P 2 at higher priority than P 3 , etc. Let pi, qi be tuples of predicate variables similar to pi, \)Jld let p, q stand for p1, ... , pk and ql, ... , qk. Define

If k = 1 then (11) defines simply p :::; q. If k = 2, p1 consists of only one predicate P1, and P 2 consists of one predicate P2, then (11) becomes (10).

Formula· ( 11) defines a regular order in every struc­ t~re . We denote the circumscription Circum~ (A; P; Z) w1th respect to this order by

and call it prioritized circumscription.

To see how establishing priorities affects the result of circumscription, compare (7) with the result of prioritized circumscription:

Minimizing P1 at higher priority means that we minimize (Pt,P2) with respect to (10). Without priorities, circum­ scription only leads to the conclusion that P 1 and P2 do not overlap. In {12) we make the extension of P1 as small as possible, even if it leads to making the extension of P2 larger; that makes P1 identically false and P2 identically true.

In applications it is reasonable to assign higher pri­ orities to the abnormality predicates representing excep­ tions to "more specific" commonsense facts. In the ex­ ample above, we use the circumscription

How to compute the result of a prioritized circum­ scription? We can try to use Theorem 1' and Proposition 2'. It turns out, however, that in cases when priorities are essential, the axiom set is usually not separable with respect to the collection of all abnormality predicates; at best, we have separability with respect to individual ABs or small groups of ABs. Even in simple cases, doing prioritized circumscription requires an additional tool.

Such a tool is given by the fact that any prioritized circumscription can be written as a conjunction of paral­ lel circumscriptions, as follows:

Theorem 2. Circum{ A; P 1 > ... > Pk; Z} is equivalent to

According to this theorem, we can do circumscrip­ tion {12) by taking the conjunction of

and

Each of the two circumscriptions can be easily evaluated using the methods of Section 5. The first of them gives Vx·-,J>1x, the second \lx(P2x = -,P1x). The conjunction· of these formulas is equivalent to the right-hand side of {12).

The result of circumscription {13) can be determined along the same lines. We come up with the conclusion that {13) is equivalent to the universal formula

Acknowledgements

I am indebted to John McCarthy for introducing me to problems of non-monotonic reasoning and circumscrip­ tion. I have also benefited from discussing this work with David Etherington, Michael Gelfond, Benjamin Grosof, Kurt Konolige, Nils Nilsson, Donald Perlis and Raymond Reiter.