�
61
The Semantics of Logic Programs
P 1 = P/∅ = P . The only minimal component of P 1 is the set {p, q}, and hence
the bottom layer of P 1 is P ; it follows that the (partial) weakly perfect model
for P is ∅. However, by applying Theorem 2.6.8, it is easy to see that {¬p, ¬q}
'
is the well-founded model for P . Indeed, more directly, we have T (∅) = ∅,
P
and U P (∅) = {p, q}. Therefore, W P ↑ 2 = W P (W P ↑ 1) = W P (∅ ∪ {¬p, ¬q}) =
{¬p, ¬q} = W P ↑ 1, and it follows that the well-founded model for P is indeed
{¬p, ¬q}.
An irregular property of the weakly perfect model semantics is that certain
changes in the program affect the semantics, although inutitively they should
not.
2.6.12 Program (Tweety4) Consider again the program Tweety4 of Example 2.5.5. As noted earlier, this program is a variation of Tweety2 (Program 2.3.9), with the last clause changed; it is intuitively clear that this change
should not alter the semantics of the program.
While the program Tweety2, which is locally stratified, has the expected
weakly perfect model as discussed in Example 2.5.3, the program Tweety4 has
weakly perfect model
{penguin(tweety), bird(bob), bird(tweety), ¬flies(tweety)},
as shown in Example 2.5.5. So again we are unable to determine whether or
not bob is a penguin.
The well-founded semantics, however, does not suffer from the same deficiency. Indeed, it turns out to be M ∪ ¬(B P \ M ), where M is as in Example
2.2.7. So in this semantics bob is not a penguin and flies.
An alternative way of characterizing the well-founded semantics is via the
Gelfond–Lifschitz operator from Section 2.3. Recall from Theorem 2.3.7 that
the Gelfond–Lifschitz operator is antitonic. In particular, this means that
for any program P , the operator GL
2 , obtained by applying GL P twice, is
P
monotonic. Therefore, by the Knaster-Tarski theorem, GL
2 has a least fixed
P
point, L P . Note further that I P,2 is a complete lattice in the dual of the truth
ordering on I P,2 . So, on applying the Knaster-Tarski theorem again, we also
obtain that GL
2 has a greatest fixed point, G P . Since L P ⊆ G P , we obtain
P
that L P ∪ ¬(B P \ G P ) is a three-valued interpretation for P and is, in fact, a
model for P , as we show next, called the alternating fixed point model for P .
We are going to show that the alternating fixed point model coincides
with the well-founded model. Let us first introduce some temporary notation,
where P is an arbitrary program.
L 0 = ∅
G 0 = B P
L α+1 = GL P (G α )
G α+1 = GL P (L α )
for any ordinal α
L α =
L β
G α =
G β
for a limit ordinal α.
β<α
β<α
61
The Semantics of Logic Programs
P 1 = P/∅ = P . The only minimal component of P 1 is the set {p, q}, and hence
the bottom layer of P 1 is P ; it follows that the (partial) weakly perfect model
for P is ∅. However, by applying Theorem 2.6.8, it is easy to see that {¬p, ¬q}
'
is the well-founded model for P . Indeed, more directly, we have T (∅) = ∅,
P
and U P (∅) = {p, q}. Therefore, W P ↑ 2 = W P (W P ↑ 1) = W P (∅ ∪ {¬p, ¬q}) =
{¬p, ¬q} = W P ↑ 1, and it follows that the well-founded model for P is indeed
{¬p, ¬q}.
An irregular property of the weakly perfect model semantics is that certain
changes in the program affect the semantics, although inutitively they should
not.
2.6.12 Program (Tweety4) Consider again the program Tweety4 of Example 2.5.5. As noted earlier, this program is a variation of Tweety2 (Program 2.3.9), with the last clause changed; it is intuitively clear that this change
should not alter the semantics of the program.
While the program Tweety2, which is locally stratified, has the expected
weakly perfect model as discussed in Example 2.5.3, the program Tweety4 has
weakly perfect model
{penguin(tweety), bird(bob), bird(tweety), ¬flies(tweety)},
as shown in Example 2.5.5. So again we are unable to determine whether or
not bob is a penguin.
The well-founded semantics, however, does not suffer from the same deficiency. Indeed, it turns out to be M ∪ ¬(B P \ M ), where M is as in Example
2.2.7. So in this semantics bob is not a penguin and flies.
An alternative way of characterizing the well-founded semantics is via the
Gelfond–Lifschitz operator from Section 2.3. Recall from Theorem 2.3.7 that
the Gelfond–Lifschitz operator is antitonic. In particular, this means that
for any program P , the operator GL
2 , obtained by applying GL P twice, is
P
monotonic. Therefore, by the Knaster-Tarski theorem, GL
2 has a least fixed
P
point, L P . Note further that I P,2 is a complete lattice in the dual of the truth
ordering on I P,2 . So, on applying the Knaster-Tarski theorem again, we also
obtain that GL
2 has a greatest fixed point, G P . Since L P ⊆ G P , we obtain
P
that L P ∪ ¬(B P \ G P ) is a three-valued interpretation for P and is, in fact, a
model for P , as we show next, called the alternating fixed point model for P .
We are going to show that the alternating fixed point model coincides
with the well-founded model. Let us first introduce some temporary notation,
where P is an arbitrary program.
L 0 = ∅
G 0 = B P
L α+1 = GL P (G α )
G α+1 = GL P (L α )
for any ordinal α
L α =
L β
G α =
G β
for a limit ordinal α.
β<α
β<α