49
The Semantics of Logic Programs
given in Definition 2.5.4, differs slightly from the version introduced in
[Przymusinska and Przymusinski, 1990]. In order to obtain the original definition, points (2) and (3) of Definition 2.5.4 have to be replaced with the following: (2)
' If the bottom stratum S α is empty or if the bottom layer L α has
no least two-valued model, then the construction stops, and M P = N α ∪ ¬R α
is the (partial) weakly perfect model for P . (3)
' In the remaining case, L α
has a least two-valued model, and we define M α = H ∪ ¬R α , where H is
the three-valued model for L α corresponding to its least two-valued model,
and the construction continues. The original definition is more general due to
the fact that every definite program has a least two-valued model. However,
while the least two-valued model for a definite program can be obtained as
the least fixed point of the monotonic (and even continuous) operator T P ,
we know of no similar result, nor of a general operator, for obtaining the
least two-valued model, if it exists, for programs which are not definite. The
original definition therefore seems to be rather awkward, and indeed, even in
[Przymusinska and Przymusinski, 1990], when defining weakly stratified programs, the more general version was dropped in favour of requiring definite
layers. So Definition 2.5.4 is an adaptation taking the original notion of weakly
stratified program into account and appears to be more natural. Our use,
therefore, of the term weakly perfect model will refer to Definition 2.5.4 unless
stated to the contrary.
Again, an alternative characterization of the weakly perfect model can be
provided using level mappings.
2.5.8 Definition Let P be a normal logic program, let I be a three-valued
model for P , and let l be an I-partial level mapping for P . We say that P
satisfies (WS) with respect to I and l if each A ∈ dom(l) satisfies one of the
following conditions.
(WSi) A ∈ I, and there is a clause A ← L 1 , . . . , L n in ground(P ) such that
L i ∈ I and l(A) > l(L i ) for all i.
(WSii) ¬A ∈ I, and for each clause A ← A 1 , . . . , A n , ¬B 1 , . . . , ¬B m in
ground(P ) one (at least) of the following conditions holds.
(WSiia) There exists i with ¬A i ∈ I and l(A) > l(A i ).
(WSiib) For all k we have l(A) ≥ l(A k ), for all j we have l(A) >
l(B j ), and there exists i with ¬A i ∈ I.
(WSiic) There exists j with B j ∈ I and l(A) > l(B j ).
Noting that the condition (Fii) in Definition 2.4.8 implies that either
(WSiia) or (WSiic) holds, we see that the condition (WSii) above is more
general than (Fii); conditions (WSi) and (Fi) are identical.
2.5.9 Theorem Let P be a normal logic program with weakly perfect model
The Semantics of Logic Programs
given in Definition 2.5.4, differs slightly from the version introduced in
[Przymusinska and Przymusinski, 1990]. In order to obtain the original definition, points (2) and (3) of Definition 2.5.4 have to be replaced with the following: (2)
' If the bottom stratum S α is empty or if the bottom layer L α has
no least two-valued model, then the construction stops, and M P = N α ∪ ¬R α
is the (partial) weakly perfect model for P . (3)
' In the remaining case, L α
has a least two-valued model, and we define M α = H ∪ ¬R α , where H is
the three-valued model for L α corresponding to its least two-valued model,
and the construction continues. The original definition is more general due to
the fact that every definite program has a least two-valued model. However,
while the least two-valued model for a definite program can be obtained as
the least fixed point of the monotonic (and even continuous) operator T P ,
we know of no similar result, nor of a general operator, for obtaining the
least two-valued model, if it exists, for programs which are not definite. The
original definition therefore seems to be rather awkward, and indeed, even in
[Przymusinska and Przymusinski, 1990], when defining weakly stratified programs, the more general version was dropped in favour of requiring definite
layers. So Definition 2.5.4 is an adaptation taking the original notion of weakly
stratified program into account and appears to be more natural. Our use,
therefore, of the term weakly perfect model will refer to Definition 2.5.4 unless
stated to the contrary.
Again, an alternative characterization of the weakly perfect model can be
provided using level mappings.
2.5.8 Definition Let P be a normal logic program, let I be a three-valued
model for P , and let l be an I-partial level mapping for P . We say that P
satisfies (WS) with respect to I and l if each A ∈ dom(l) satisfies one of the
following conditions.
(WSi) A ∈ I, and there is a clause A ← L 1 , . . . , L n in ground(P ) such that
L i ∈ I and l(A) > l(L i ) for all i.
(WSii) ¬A ∈ I, and for each clause A ← A 1 , . . . , A n , ¬B 1 , . . . , ¬B m in
ground(P ) one (at least) of the following conditions holds.
(WSiia) There exists i with ¬A i ∈ I and l(A) > l(A i ).
(WSiib) For all k we have l(A) ≥ l(A k ), for all j we have l(A) >
l(B j ), and there exists i with ¬A i ∈ I.
(WSiic) There exists j with B j ∈ I and l(A) > l(B j ).
Noting that the condition (Fii) in Definition 2.4.8 implies that either
(WSiia) or (WSiic) holds, we see that the condition (WSii) above is more
general than (Fii); conditions (WSi) and (Fi) are identical.
2.5.9 Theorem Let P be a normal logic program with weakly perfect model