Abstract
Circumscription is a form of non-monotonic reasoning, introduced by McCarthy as a way of characterizing defaults using second order logic. The consequences of circumscription are those formulas true in the minimal models under a pre-order on models. In the case of domain circumscription the pre-order was the sub-model relation. Formula circumscription is characterized by minimizing a set of formulas---one model is preferred to another model when the extensions of the minimized formulas in the first are subsets of the extensions in the second.
We show that the propositional version of formula circumscription can capture all pre-orders on valuations of finite languages. We consider the question of infinite languages, and give the corresponding representation theorems. Infinitary propositional logics are of interest as they correspond closely to first order logics with fixed domains. We show that even logics with countable connectives cannot describe all pre-orders on models of countable infinite languages. We further show that there are natural defaults, captured by inductive definitions, that cannot be captured by circumscription in the first order case. Formulas of this sort have been suggested as an extension of circumscription by Lifschitz.
Finally, contrary to previous claims, we show that propositional formula circumscription can capture all preferential consequence relations over finite propositional languages, as defined by Kraus et al. Thus, in the finite propositional case, there is no restriction on the kinds of preferential defaults that circumscription can describe.
Abstract
Circumscription is a form of non-monotonic reasoning. The first version of circumscription, domain circumscription, is analogous to mathematical induction. Given a theory, it chooses the models of that theory whose domains are minimal with respect to inclusion. It captures the assumption that as few objects exist as possible.
Predicate and formula circumscription, introduced later, are characterized by a set of predicates or formulas to minimize. They choose the models that have as few objects true of the minimized predicates/formulas as possible. However, they do not compare models of different cardinality. Thus they are not an extension of domain circumscription, they are incomparable in expressive power.
We introduce a new form of circumscription that allows models that differ on domains to be compared. It extends both domain and formula circumscription, hence its name. It removes the artificial constraint that predicate and formula circumscription impose, and thus gives more intuitive semantics.