next up previous
Next: THE MODEL THEORY OF Up: CIRCUMSCRIPTION-A FORM OF NONMONOTONIC Previous: THE FORMALISM OF CIRCUMSCRIPTION

DOMAIN CIRCUMSCRIPTION

The form of circumscription described in this paper generalizes an earlier version called minimal inference. Minimal inference has a semantic counterpart called minimal entailment, and both are discussed in (McCarthy 1977) and more extensively in (Davis 1980). The general idea of minimal entailment is that a sentence q is minimally entailed by an axiom A, written tex2html_wrap_inline709 , if q is true in all minimal models of A, where one model if is considered less than another if they agree on common elements, but the domain of the larger many contain elements not in the domain of the smaller. We shall call the earlier form domain circumscription to contrast it with the predicate circumscription discussed in this paper.

The domain circumscription of the sentence A is the sentence

  equation171

where tex2html_wrap_inline637 is the relativization of A with respect to tex2html_wrap_inline473 and is formed by replacing each universal quantifier tex2html_wrap_inline643 in A by tex2html_wrap_inline647 and each existential quantifier tex2html_wrap_inline649 by tex2html_wrap_inline651 . tex2html_wrap_inline653 is the conjunction of sentences tex2html_wrap_inline655 for each constant a and sentences tex2html_wrap_inline659 for each function symbol f and the corresponding sentences for functions of higher arities.

Domain circumscription can be reduced to predicate circumscription by relativizing A with respect to a new one place predicate called (say) all, then circumscribing all in tex2html_wrap_inline669 , thus getting

  equation176

Now we justify our using the name all by adding the axiom tex2html_wrap_inline675 so that (20) then simplifies precisely to (19).

In the case of the natural numbers, the domain circumscription of true, the identically true sentence, again leads to the axiom schema of induction. Here Axiom does all the work, because it asserts that 0 is in the domain and that the domain is closed under the successor operation.



John McCarthy
Tue May 14 00:04:52 PDT 1996