Circumscription (logic) - Fixed and Varying Predicates

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:

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.