Circumscription (logic) - The Propositional Case

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, 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 variables; 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:

1. , are true, i.e. ;
2. and are true, is false, i.e. ;
3. 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.