Information Technology Reference
In-Depth Information
Definition 2.17
be a
set of predicates contained in T. Let M[T] and M*[T] be two models of T. Then,
M* [T] is called smaller then M[T], written as M*[T]
Let T be a formula of a first-order language L, and let
Ⱦ
X
M[T], if and only if:
(1) M and M* have the same domain;
(2) all the relations and functions occurring in T, except these contained in
,
have the same interpretation in M and M*;
(3) the extension of
in the M* is a subset of
in the M.
A model M of T is called
X
P- minimal if and only if there is no other model
M' of T such that M
X
P
M'.
Definition 2.18
M
m
is a minimal model of
ρ
if and only if M=M
m
for any model
M such that M
X
M
m
.
ρ
For example, let the domain be D={1, 2},
T =
∀
x
∃
y(P(y)
∧
Q(x, y))
= [(P(1)
∧
Q(1, 1))
∨
(P(2)
∧
Q(1, 2))]
∧
[(P(1)
∧
Q(2, 1))
∨
(P(2)
∧
Q(2, 2))]
Let M
and M
*
be the following models:
M P(1)
P(2)
Q(1, 1) Q(1, 2) Q(2, 1) Q(2, 2)
True True
False True False True
M
*
P(1)
P(2)
Q(1, 1)
Q(1, 2) Q(2, 1) Q(2, 2)
False True
False True False True
Then, model M and model M* has the same true assignments on Q. At the same
time, P is true in both (1) and (2) of model M; however, for model M*, P is true
