Circumscription
Encyclopedia
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
. In its original first-order logic
formulation, circumscription minimizes 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.
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 .
, its circumscription is the formula having only the models
of
that do not assign a variable to true unless necessary.
Formally, propositional models can be represented by sets of propositional variable
s; namely, each model is represented by the set of propositional variables it assigns to true. For example, the model assigning true to
, false to 
, and true to 
is represented by the set 
, because 
and 
are exactly the variables that are assigned to true by this model.
Given two models
and 
represented this way, the condition 
is equivalent to 
setting to true every variable that 
sets to true. In other words, 
models the relation of “setting to true less variables”. 
means that 
but these two models do not coincide.
This lets us define models that do not assign variables to true unless necessary.
A model
of a theory 
is called minimal, if and only if there is no model
of 
for which 
.
Circumscription is expressed by selecting only the minimal models. It is defined as follows:
Alternatively, one can define
as a formula having exactly the above set of models; furthermore, one can also avoid giving a definition of 
and only define minimal inference as 
if and only if every minimal model of 
is also a model of 
.
As an example, the formula
has three models:
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
, which is assigned to false and not to true. Therefore, the first model is not minimal. The second and third models are incomparable: while the second assigns true to 
, the third assigns true to 
instead. Therefore, the models circumscribing 
are the second and third models of the list. A propositional formula having exactly these two models is the following one:
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
and 
must be assigned to true according to 
; in the circumscription exactly one of the two variables must be true. The variable 
cannot be false in any model of 
and neither of the circumscription.
. 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:
varying : these are variables that are not to be taken into account at all in the course of minimization;
fixed : these are variables considered fixed while doing a minimization; in other words, minimization can be done only by comparing models with the same values of these variables.
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
is the set of variables to minimize, 
the fixed variables, and the varying variables are those not in 
:
In words, minimization of the variables assigned to true is only done for the variables in
; moreover, models are only compared if the assign the same values on the variables of 
. All other variables are not taken into account while comparing models.
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
is not a consequence of the above formulae, while the door is supposed to stay closed until the action of opening it is performed. Circumscription can be used to this aim by defining new variables 
to model changes and then minimizing them:
As shown by the Yale shooting problem
, this kind of solution does not work. For example,
is not yet entailed by the circumscription of the formulae above: the model in which 
is true and 
is false is incomparable with the model with the opposite values. Therefore, the situation in which the door becomes open at time 1 and then remains open as a consequence of the action is not excluded by circumscription.
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.
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.)
. 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
with domain 
, one setting 
and the other setting 
. Since the extension of 
in the first model is 
while the extension for the second is 
, circumscription only selects the first model.
In pointwise circumscription, each tuple of values is considered separately. For example, in the formula
one would consider the value of 
separately from 
. A model is minimal only it is not possible to turn any such value from true to false while still satisfying the formula. As a result, the model in which 
is selected by pointwise circumscription because turning only 
into false does not satisfy the formula, and the same happens for 
.
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.
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
predicate, so that 
is false even if this is not explicitly stated.
On the other hand, the minimization of the
predicate leads
to the wrong result that the coin is either on a black area or on a white area, but not both. This is because the models in which
is true only on 
and only on 
have a minimal extension of 
, while the model in which the extension of 
is composed of both pairs is not minimal.
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
and 
are true, is a model of the formula that is greater (w.r.t. the extension of 
) than both the two models that are selected. More specifically, among the models of the formula, the excluded model is the least upper bound of the two selected models. Theory curbing selects such least upper bounds models in addition to the ones selected by circumscription. This inclusion is done until the set of models is closed, in the sense that it includes all least upper bounds of all sets of models it contains.
Non-monotonic logic
A non-monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. Intuitively, monotonicity indicates that learning a...
created by John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
to formalize the common sense
Common sense
Common sense is defined by Merriam-Webster as, "sound and prudent judgment based on a simple perception of the situation or facts." Thus, "common sense" equates to the knowledge and experience which most people already have, or which the person using the term believes that they do or should have...
assumption that things are as expected unless otherwise specified. Circumscription was later used by McCarthy in an attempt to solve the frame problem
Frame problem
In artificial intelligence, the frame problem was initially formulated as the problem of expressing a dynamical domain in logic without explicitly specifying which conditions are not affected by an action. John McCarthy and Patrick J. Hayes defined this problem in their 1969 article, Some...
. In its original first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
formulation, circumscription minimizes the extension
Extension (semantics)
In any of several studies that treat the use of signs - for example, in linguistics, logic, mathematics, semantics, and semiotics - the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of...
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
Closed world assumption
The closed world assumption is the presumption that what is not currently known to be true, is false. The same name also refers to a logical formalization of this assumption by Raymond Reiter. The opposite of the closed world assumption is the open world assumption , stating that lack of knowledge...
that what is not known to be true is false.
The original problem considered by McCarthy was that of missionaries and cannibals
Missionaries and cannibals problem
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems. The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used by Saul Amarel as an example of problem...
: 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
Missionaries and cannibals problem
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems. The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used by Saul Amarel as an example of 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
Inertia
Inertia is the resistance of any physical object to a change in its state of motion or rest, or the tendency of an object to resist any change in its motion. It is proportional to an object's mass. The principle of inertia is one of the fundamental principles of classical physics which are used to...
: 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
Frame problem
In artificial intelligence, the frame problem was initially formulated as the problem of expressing a dynamical domain in logic without explicitly specifying which conditions are not affected by an action. John McCarthy and Patrick J. Hayes defined this problem in their 1969 article, Some...
. However, the solution proposed by McCarthy was later shown leading to wrong results in some cases, like in the Yale shooting problem
Yale shooting problem
The Yale shooting problem is a conundrum or scenario in formal situational logic on which early logical solutions to the frame problem fail. The name of this problem derives from its inventors, Steve Hanks and Drew McDermott, working at Yale University when they proposed it. In this scenario, Fred ...
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 formulaPropositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value...
, its circumscription is the formula having only the modelsStructure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
of
that do not assign a variable to true unless necessary.Formally, propositional models can be represented by sets of propositional variable
Propositional variable
In mathematical logic, a propositional variable is a variable which can either be true or false...
s; namely, each model is represented by the set of propositional variables it assigns to true. For example, the model assigning true to
, false to , and true to is represented by the set , because and are exactly the variables that are assigned to true by this model.Given two models
and represented this way, the condition is equivalent to setting to true every variable that sets to true. In other words, models the relation of “setting to true less variables”. means that but these two models do not coincide.This lets us define models that do not assign variables to true unless necessary.
A model
of a theory is called minimal, if and only if there is no model of for which .Circumscription is expressed by selecting only the minimal models. It is defined as follows:
Alternatively, one can define
as a formula having exactly the above set of models; furthermore, one can also avoid giving a definition of and only define minimal inference as if and only if every minimal model of is also a model of .As an example, the formula
has three models:-
, 
, 
are true, i.e. 
; -
and 
are true, 
is false, i.e. 
; -
and 
are true, 
is false, i.e. 
.
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
, which is assigned to false and not to true. Therefore, the first model is not minimal. The second and third models are incomparable: while the second assigns true to , the third assigns true to instead. Therefore, the models circumscribing are the second and third models of the list. A propositional formula having exactly these two models is the following one: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
and must be assigned to true according to ; in the circumscription exactly one of the two variables must be true. The variable cannot be false in any model of and neither of the circumscription.Fixed and varying predicates
The extension of circumscription with fixed and varying predicates is due to Vladimir LifschitzVladimir Lifschitz
Vladimir Lifschitz is Gottesman Family Centennial Professor in Computer Sciences at the University of Texas at Austin. He received a degree in mathematics from the Steklov Institute of Mathematics in Russia in 1971 and emigrated to the United States in 1976. Lifschitz's research interests are in...
. 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:
varying : these are variables that are not to be taken into account at all in the course of minimization;
fixed : these are variables considered fixed while doing a minimization; in other words, minimization can be done only by comparing models with the same values of these variables.
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
is the set of variables to minimize, the fixed variables, and the varying variables are those not in :In words, minimization of the variables assigned to true is only done for the variables in
; moreover, models are only compared if the assign the same values on the variables of . All other variables are not taken into account while comparing models.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
is not a consequence of the above formulae, while the door is supposed to stay closed until the action of opening it is performed. Circumscription can be used to this aim by defining new variables to model changes and then minimizing them:
- ...
As shown by the Yale shooting problem
Yale shooting problem
The Yale shooting problem is a conundrum or scenario in formal situational logic on which early logical solutions to the frame problem fail. The name of this problem derives from its inventors, Steve Hanks and Drew McDermott, working at Yale University when they proposed it. In this scenario, Fred ...
, this kind of solution does not work. For example,
is not yet entailed by the circumscription of the formulae above: the model in which is true and is false is incomparable with the model with the opposite values. Therefore, the situation in which the door becomes open at time 1 and then remains open as a consequence of the action is not excluded by circumscription.Several other formalizations of dynamical domains not suffering from such problems have been developed (see frame problem
Frame problem
In artificial intelligence, the frame problem was initially formulated as the problem of expressing a dynamical domain in logic without explicitly specifying which conditions are not affected by an action. John McCarthy and Patrick J. Hayes defined this problem in their 1969 article, Some...
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
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.)Pointwise circumscription
Pointwise circumscription is a variant of first-order circumscription that has been introduced by Vladimir LifschitzVladimir Lifschitz
Vladimir Lifschitz is Gottesman Family Centennial Professor in Computer Sciences at the University of Texas at Austin. He received a degree in mathematics from the Steklov Institute of Mathematics in Russia in 1971 and emigrated to the United States in 1976. Lifschitz's research interests are in...
. 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
with domain , one setting and the other setting . Since the extension of in the first model is while the extension for the second is , circumscription only selects the first model.In pointwise circumscription, each tuple of values is considered separately. For example, in the formula
one would consider the value of separately from . A model is minimal only it is not possible to turn any such value from true to false while still satisfying the formula. As a result, the model in which is selected by pointwise circumscription because turning only into false does not satisfy the formula, and the same happens for .Domain and formula circumscription
An earlier formulation of circumscription by McCarthy is based on minimizing the domainDomain (mathematics)
In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...
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 ReiterRaymond Reiter
Raymond Reiter , was a Canadian computer scientist and logician. He was one of the founders of the field of non-monotonic reasoning with his work on default logic, model-based diagnosis, closed world reasoning, and truth maintenance systems...
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
predicate, so that is false even if this is not explicitly stated.On the other hand, the minimization of the
predicate leadsto the wrong result that the coin is either on a black area or on a white area, but not both. This is because the models in which
is true only on and only on have a minimal extension of , while the model in which the extension of is composed of both pairs is not minimal.Theory curbing is a solution proposed by Thomas Eiter, Georg Gottlob
Georg Gottlob
Georg Gottlob FRS is an Oxford-based Austrian computer scientist who works in the areas of database theory, logic, and artificial intelligence.Gottlob obtained his PhD in computer science at Vienna University of Technology in 1981...
, and Yuri Gurevich
Yuri Gurevich
Yuri Gurevich is an American computer scientist and mathematician and the inventor of abstract state machines. He is currently Principal Researcher at Microsoft Research, where he founded the Foundations of Software Engineering group,...
. The idea is that the model that circumscription fails to select, the one in which both
and are true, is a model of the formula that is greater (w.r.t. the extension of ) than both the two models that are selected. More specifically, among the models of the formula, the excluded model is the least upper bound of the two selected models. Theory curbing selects such least upper bounds models in addition to the ones selected by circumscription. This inclusion is done until the set of models is closed, in the sense that it includes all least upper bounds of all sets of models it contains.