Next: MORE ON BLOCKS Up: CIRCUMSCRIPTION-A FORM OF NONMONOTONIC Previous: DOMAIN CIRCUMSCRIPTION

# THE MODEL THEORY OF PREDICATE CIRCUMSCRIPTION

This treatment is similar to Davis's (1980) treatment of domain circumscription. Pat Hayes (1979) pointed out that the same ideas would work.

The intuitive idea of circumscription is saying that a tuple satisfies the predicate P only if it has to. It has to satisfy P if this follows from the sentence A. The model-theoretic counterpart of circumscription is minimal entailment. A sentence q is minimally entailed by A, if q is true in all minimal models of A, where a model is minimal if as few as possible tuples satisfy the predicate P. More formally, this works out as follows.

Definition. Let M(A) and N(A) be models of the sentence A. We say that M is a submodel of N in P, writing , if M and N have the same domain, all other predicate symbols in A besides P have the same extensions in M and N, but the extension of P in M is included in its extension in N.

Definition. A model M of A is called minimal in P if only if . As discussed by Davis (1980), minimal models don't always exist.

Definition. We say that A minimally entails q with respect to P, written provided q is true in all models of A that are minimal in P.

Theorem. Any instance of the circumscription of P in A is true in all models of A minimal in P, i.e. is minimally entailed by A in P.

Proof. Let M be a model of A minimal in P. Let be a predicate satisfying the left side of (1) when substituted for . By the second conjunct of the left side P is an extension of . If the right side of (1) were not satisfied, P would be a proper extension of . In that case, we could get a proper submodel of M by letting agree with M on all predicates except P and agree with on P. This would contradict the assumed minimality of M.

Corollary. If , then .

While we have discussed minimal entailment in a single predicate P, the relation , models minimal in P and Q, and have corresponding properties and a corresponding relation to the syntactic notion mentioned earlier.

Next: MORE ON BLOCKS Up: CIRCUMSCRIPTION-A FORM OF NONMONOTONIC Previous: DOMAIN CIRCUMSCRIPTION

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