Page 121 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 6: Formalized Symbolic Logics

the goal (the article on the missionaries and cannibals problem contains one such solution), but Notes
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.)
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 T, its circumscription is
the formula having only the models of T 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 a, false to b, and true to c is represented by the set {a, c}, because a and
c are exactly the variables that are assigned to true by this model. Given two models M and N
represented this way, the condition N ⊆ M is equivalent to M setting to true every variable that
N sets to true. In other words, ⊆ models the relation of “setting to true less variables”. N ⊂ M
means that N ⊆ M but these two models do not coincide.

This lets us define models that do not assign variables to true unless necessary. A model M of a
theory T is called minimal, if and only if there is no model N of T for which N ⊂ M.
Circumscription is expressed by selecting only the minimal models. It is defined as follows:
CIRC(T) = {M|M is a minimal model of T}

Alternatively, one can define CIRC(T) as a formula having exactly the above set of models;
furthermore, one can also avoid giving a definition of CIRC and only define minimal inference
as T Q if and only if every minimal model of T is also a model of Q.
M
As an example, the formula T = a ∧ (b ∨ c) has three models:
1. a, b, are c true, i.e. {a, b, c};
2. a and b are true, c is false, i.e. {a, b};

3. a and c 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 c, 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 b, the third assigns true to c instead. Therefore, the models circumscribing T are
the second and third models of the list. A propositional formula having exactly these two
models is the following one:
a ∧ ¬ (b ↔ c)
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 b and c must be assigned to true
according to T; in the circumscription exactly one of the two variables must be true. The variable
cannot be false in any model of T and neither of the circumscription.

6.9.2 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:

LOVELY PROFESSIONAL UNIVERSITY 115