Circumscription (logic) - Predicate Circumscription

Predicate Circumscription

The original definition of circumscription proposed by McCarthy is about first-order logic. The role of variables in propositional logic (something that can be true or false) is played in first-order logic by predicates. Namely, a propositional formula can be expressed in first-order logic by replacing each propositional variable with a predicate of zero arity (i.e., a predicate with no arguments). Therefore, minimization is done on predicates in the first-order logic version of circumscription: the circumscription of a formula is obtained forcing predicates to be false whenever possible.

Given a first-order logic formula containing a predicate, circumscribing this predicate amounts to selecting only the models of in which is assigned to true on a minimal set of tuples of values.

Formally, the extension of a predicate in a first-order model is the set of tuples of values this predicate assign to true in the model. First-order models indeed includes the evaluation of each predicate symbol; such an evaluation tells whether the predicate is true or false for any possible value of its arguments. Since each argument of a predicate must be a term, and each term evaluates to a value, the models tells whether is true for any possible tuple of values . The extension of in a model is the set of tuples of terms such that is true in the model.

The circumscription of a predicate in a formula is obtained by selecting only the models of with a minimal extension of . For example, if a formula has only two models, differing only because is true in one and false in the second, then only the second model is selected. This is because is in the extension of in the first model but not in the second.

The original definition by McCarthy was syntactical rather than semantical. Given a formula and a predicate, circumscribing in is the following second-order formula:

In this formula is a predicate of the same arity as . This is a second-order formula because it contains a quantification over a predicate. The subformula is a shorthand for:

In this formula, is a n-tuple of terms, where n is the arity of . This formula states that extension minimization has to be done: in order for a truth evaluation on of a model being considered, it must be the case that no other predicate can assign to false every tuple that assigns to false and yet being different from .

This definition only allows circumscribing a single predicate. While the extension to more than one predicate is trivial, minimizing the extension of a single predicate has an important application: capturing the idea that things are usually as expected. This idea can be formalized by minimized a single predicate expressing the abnormality of situations. In particular, every known fact is expressed in logic with the addition of a literal stating that the fact holds only in normal situations. Minimizing the extension of this predicate allows for reasoning under the implicit assumption that things are as expected (that is, they are not abnormal), and that this assumption is made only if possible (abnormality can be assumed false only if this is consistent with the facts.)