Page 123 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 6: Formalized Symbolic Logics

arguments). Therefore, minimization is done on predicates in the first-order logic version of Notes
circumscription: the circumscription of a formula is obtained forcing predicates to be false
whenever possible.
Given a first-order logic formula T containing a predicate P, circumscribing this predicate amounts
to selecting only the models of T in which P 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 P(v ,…v ) is true for any possible tuple of values
1 n
〈v ,…v 〉. The extension of P in a model is the set of tuples of terms such that P(v ,…v ) is true in
1 n 1 n
the model.
The circumscription of a predicate P in a formula T is obtained by selecting only the models of
T with a minimal extension of P. For example, if a formula has only two models, differing only
because P(v ,…v ) is true in one and false in the second, then only the second model is selected.
1 n
This is because 〈v ,…v 〉 is in the extension of P in the first model but not in the second.
1 n
The original definition by McCarthy was syntactical rather than semantical. Given a formula T
and a predicate P, circumscribing P in T is the following second-order formula:
T(P) ∧ ∀p¬(T(P) ∧ p < P)
In this formula, p is a predicate of the same arity as P. This is a second-order formula because it
contains a quantification over a predicate. The subformula p < P is a shorthand for:
"x(p(x) → P(x)) ∧ ¬"x(P(x) → p(x))

In this formula, x is a n-tuple of terms, where n is the arity of P. This formula states that extension
minimization has to be done: in order for a truth evaluation on P of a model being considered,
it must be the case that no other predicate p can assign to false every tuple that P assigns to false
and yet being different from P.
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 ¬Abnormal(…) 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.)

6.9.4 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 P(a) ≡ P(b) with domain {a, b}, one setting P(a) = P(b) = false and the other setting
P(a) = P(b) = true. Since, the extension of P in the first model is 0 while the extension for the
second is {a, b}, circumscription only selects the first model.

LOVELY PROFESSIONAL UNIVERSITY 117