PRIORITIZED CIRCUMSCRIPTION

An alternate way of introducing formula circumscription is by means of an ordering on tuples of predicates satisfying an axiom. We define by  

 

That P0 is a relative minimum in this ordering is expressed by

 

 

where equality is interpreted extensionally, i.e. we have

 

 

Assuming that we look for a minimum among predicates P satisfying A(P), (46) expands to precisely to the circumscription formula (1). In some earlier expositions of circumscription this ordering approach was used, and Vladimir Lifschitz in a recent seminar advocated returning to it as a more fundamental and understandable concept.

I'm beginning to think he's right about it being more understandable, and there seems to be a more fundamental reason for using it. Namely, certain common sense axiomatizations are easier to formalize if we use a new kind of ordering, and circumscription based on this kind of ordering doesn't seem to reduce to ordinary formula circumscription.

We call it prioritized circumscription.

Suppose we write some bird axioms in the form  

 

and  

 

The intent is clear. The goal is that being a bird and not abnormal in aspect2 prevents the application of (49). However, circumscribing with the conjunction of (49) and (50) as A(ab) doesn't have this effect, because (50) is equivalent to  

 

and there is no indication that one would prefer to have abnormal rather than to have abnormal. Circumscription then results in a disjunction which is not wanted in this case. The need to avoid this disjunction is why the axioms in section 5 (page ) included cancellation of inheritance axioms.

However, by using a new kind of ordering we can leave (49) and (50) as is, and still get the desired effect.

We define two orderings on ab predicates, namely  

 

and  

 

We then combine these orderings lexicographically giving priority over getting  

 

Choosing ab0 so as to minimize this ordering yields the result that exactly birds can fly. However, if we add  

 

we'll get that ostriches (whether or not ostriches are birds) don't fly without further axioms. If we use  

 

instead of (55), we'll have to revise our notion of ordering to put minimizing at higher priority than minimizing and at higher priority than minimizing aspect1.

This suggests providing a partial ordering on aspects giving their priorities and providing axioms that permit deducing the ordering on ab from the sentences that describe the ordering relations. Lifschitz (1985) further develops the idea of prioritized circumscription.

I expect that will turn out to be the most natural and powerful variant.

Simple abnormality theories seem to be inadequate also for the blocks world described in section 11. I am indebted to Lifschitz for the following example. Consider

where S0 is a situation with exactly blocks A and B on the table. Intuitively, the second action is unsuccessful, because after the first action A is on B, and so B isn't clear. Suppose we provide by a suitable axiom that when the block to be moved is not clear or the destination place is not clear, then the situation is normally unchanged. Then S2 should be the same situation as S1 = result(move(A,B),S0). However, simple circumscription of ab won't give this result, because the first move is only normally successful, and if the first move is unsuccessful for some unspecified reason, the second move may succeed after all. Therefore, circumscription of ab only gives a disjunction.

Clearly the priorities need to be arranged to avoid this kind of unintended ``sneak disjunction''. The best way to do it by imposing priorities isn't clear at the time of this writing.