Circumscription is a non-monotonic logic created by John McCarthy to formalize the common sense assumption that things are as expected unless otherwise specified. Circumscription was later used by McCarthy in an attempt to solve the frame problem. To implement circumscription in his initial formulation, McCarthy augmented first-order logic to allow the minimization of the extension of some predicates, where the extension of a predicate is the set of tuples of values the predicate is true on. This minimization is similar to the closed world assumption that what is not known to be true is false.
Contents
- The propositional case
- Fixed and varying predicates
- Predicate circumscription
- Pointwise circumscription
- Domain and formula circumscription
- Theory curbing
- References
The original problem considered by McCarthy was that of missionaries and cannibals: there are three missionaries and three cannibals on one bank of a river; they have to cross the river using a boat that can only take two, with the additional constraint that cannibals must never outnumber the missionaries on either bank (as otherwise the missionaries would be killed and, presumably, eaten). The problem considered by McCarthy was not that of finding a sequence of steps to reach the goal (the article on the missionaries and cannibals problem contains one such solution), but rather that of excluding conditions that are not explicitly stated. For example, the solution “go half a mile south and cross the river on the bridge” is intuitively not valid because the statement of the problem does not mention such a bridge. On the other hand, the existence of this bridge is not excluded by the statement of the problem either. That the bridge does not exist is a consequence of the implicit assumption that the statement of the problem contains everything that is relevant to its solution. Explicitly stating that a bridge does not exist is not a solution to this problem, as there are many other exceptional conditions that should be excluded (such as the presence of a rope for fastening the cannibals, the presence of a larger boat nearby, etc.)
Circumscription was later used by McCarthy to formalize the implicit assumption of inertia: things do not change unless otherwise specified. Circumscription seemed to be useful to avoid specifying that conditions are not changed by all actions except those explicitly known to change them; this is known as the frame problem. However, the solution proposed by McCarthy was later shown leading to wrong results in some cases, like in the Yale shooting problem scenario. Other solutions to the frame problem that correctly formalize the Yale shooting problem exist; some use circumscription but in a different way.
The propositional case
While circumscription was initially defined in the first-order logic case, the particularization to the propositional case is easier to define. Given a propositional formula
Formally, propositional models can be represented by sets of propositional variables; namely, each model is represented by the set of propositional variables it assigns to true. For example, the model assigning true to
Given two models
This lets us define models that do not assign variables to true unless necessary. A model
Circumscription is expressed by selecting only the minimal models. It is defined as follows:
Alternatively, one can define
As an example, the formula
-
a ,b ,c are true, i.e.{ a , b , c } ; -
a andb are true,c is false, i.e.{ a , b } ; -
a andc are true,b is false, i.e.{ a , c } .
The first model is not minimal in the set of variables it assigns to true. Indeed, the second model makes the same assignments except for
Intuitively, in circumscription a variable is assigned to true only if this is necessary. Dually, if a variable can be false, it must be false. For example, at least one of
Fixed and varying predicates
The extension of circumscription with fixed and varying predicates is due to Vladimir Lifschitz. The idea is that some conditions are not to be minimized. In propositional logic terms, some variables are not to be falsified if possible. In particular, two kind of variables can be considered:
The difference is that the value of the varying conditions are simply assumed not to matter. The fixed conditions instead characterize a possible situation, so that comparing two situations where these conditions have different value makes no sense.
Formally, the extension of circumscription that incorporate varying and fixed variables is as follows, where
In words, minimization of the variables assigned to true is only done for the variables in
The solution to the frame problem proposed by McCarthy is based on circumscription with no fixed conditions. In the propositional case, this solution can be described as follows: in addition to the formulae directly encoding what is known, one also define new variables representing changes in the values of the conditions; these new variables are then minimized.
For example, of the domain in which there is a door that is closed at time 0 and in which the action of opening the door is executed at time 2, what is explicitly known is represented by the two formulae:
The frame problem shows in this example as the problem that
As shown by the Yale shooting problem, this kind of solution does not work. For example,
Several other formalizations of dynamical domains not suffering from such problems have been developed (see frame problem for an overview). Many use circumscription but in a different way.
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
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
The circumscription of a predicate
The original definition by McCarthy was syntactical rather than semantical. Given a formula
In this formula
In this formula,
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 minimizing a single predicate expressing the abnormality of situations. In particular, every known fact is expressed in logic with the addition of a literal
Pointwise circumscription
Pointwise circumscription is a variant of first-order circumscription that has been introduced by Vladimir Lifschitz. In the propositional case, pointwise and predicate circumscription coincide. The rationale of pointwise circumscription it minimize the value of a predicate for each tuple of values separately, rather than minimizing the extension of the predicate. For example, there are two models of
In pointwise circumscription, each tuple of values is considered separately. For example, in the formula
Domain and formula circumscription
An earlier formulation of circumscription by McCarthy is based on minimizing the domain of first-order models, rather than the extension of predicates. Namely, a model is considered less than another if it has a smaller domain, and the two models coincide on the evaluation of the common tuples of values. This version of circumscription can be reduced to predicate circumscription.
Formula circumscription was a later formalism introduced by McCarthy. This is a generalization of circumscription in which the extension of a formula is minimized, rather than the extension of a predicate. In other words, a formula can be specified so that the set of tuples of values of the domain that satisfy the formula is made as small as possible.
Theory curbing
Circumscription does not always correctly handle disjunctive information. Ray Reiter provided the following example: a coin is tossed over a checkboard, and the result is that the coin is either on a black area, or on a white area, or both. However, there are a large number of other possible places where the coin is not supposed to be on; for example, it is implicit that the coin is not on the floor, or on the refrigerator, or on the moon surface. Circumscription can therefore be used to minimize the extension of
On the other hand, the minimization of the
Theory curbing is a solution proposed by Thomas Eiter, Georg Gottlob, and Yuri Gurevich. The idea is that the model that circumscription fails to select, the one in which both