80
Mathematical Aspects of Logic Programming Semantics
3.3.6 Example Consider again the program Even, see Program 2.1.3. To
ease notation here, it will be convenient to denote this program by P and also
to replace the predicate symbol even by p. Thus P denotes the program
p(a) ←
p(s(X)) ← ¬p(X)
We consider the iterates of T P on the interpretation ∅, as follows.
T
0 (∅) = ∅
P
T
1 (∅) = {p(a), p(s(a)), p(s
2 (a)), p(s
3 (a)), p(s
4 (a)), . . .}
P
T
2 (∅) = {p(a)}
P
T
3 (∅) = {p(a), p(s
2 (a)), p(s
3 (a)), p(s
4 (a)), p(s
5 (a)), . . .}
P
T
4 (∅) = {p(a), p(s
2 (a))}
P
T
5 (∅) = {p(a), p(s
2 (a)), p(s
4 (a)), p(s
5 (a)), p(s
6 (a)), . . .}
P
T
6 (∅) = {p(a), p(s
2 (a)), p(s
4 (a))}
P
T
7 (∅) = {p(a), p(s
2 (a)), p(s
4 (a)), p(s
6 (a)), p(s
7 (a)), . . .}
P
T
8 (∅) = {p(a), p(s
2 (a)), p(s
4 (a)), p(s
6 (a))}
P
and so on. On letting I n denote T
n (∅) and also letting I denote the set
P
{p(a), p(s
2 (a)), p(s
4 (a)), . . .} of “even” natural numbers, we note that the sequence (I n ) oscillates quite wildly about I. Nevertheless, it is easy to see by
means of Proposition 3.3.5 that (I n ) converges in Q to I. Therefore, by Remark 3.3.3, I is a model for P . Indeed, I is a fixed point of T P and is the
unique supported model for P .
In fact, the oscillatory behaviour exhibited in this example in relation to
the single-step operator is typical of programs containing negation. Indeed,
for this example, T P is not Scott continuous, and therefore Theorem 1.1.9 is
not applicable to T P . Hence, the theory developed for the semantics of definite
programs in Chapter 2 is not applicable here either.
3.3.7 Example It is immediate from (a) of Theorem 3.2.6 and Proposition 3.3.5 that whenever a net (I i ) converges to I in Q, then it converges
to I in the Scott topology, and this is borne out by Example 3.2.8 and Corollary 3.3.10, just below, which show that the topology Q is finer than the Scott
topology in the case of two-valued interpretations.
On the other hand, the sequence (I n ) defined in the first paragraph of (3)
of Example 3.2.7 converges in the Scott topology (to several interpretations),
but does not converge (to anything) in Q.
The point of view that the topology Q is appropriate for studying the
semantics of logic programs with negation is given strong support by examples
such as Example 3.3.6. It is given further support in the most usual case, where
Mathematical Aspects of Logic Programming Semantics
3.3.6 Example Consider again the program Even, see Program 2.1.3. To
ease notation here, it will be convenient to denote this program by P and also
to replace the predicate symbol even by p. Thus P denotes the program
p(a) ←
p(s(X)) ← ¬p(X)
We consider the iterates of T P on the interpretation ∅, as follows.
T
0 (∅) = ∅
P
T
1 (∅) = {p(a), p(s(a)), p(s
2 (a)), p(s
3 (a)), p(s
4 (a)), . . .}
P
T
2 (∅) = {p(a)}
P
T
3 (∅) = {p(a), p(s
2 (a)), p(s
3 (a)), p(s
4 (a)), p(s
5 (a)), . . .}
P
T
4 (∅) = {p(a), p(s
2 (a))}
P
T
5 (∅) = {p(a), p(s
2 (a)), p(s
4 (a)), p(s
5 (a)), p(s
6 (a)), . . .}
P
T
6 (∅) = {p(a), p(s
2 (a)), p(s
4 (a))}
P
T
7 (∅) = {p(a), p(s
2 (a)), p(s
4 (a)), p(s
6 (a)), p(s
7 (a)), . . .}
P
T
8 (∅) = {p(a), p(s
2 (a)), p(s
4 (a)), p(s
6 (a))}
P
and so on. On letting I n denote T
n (∅) and also letting I denote the set
P
{p(a), p(s
2 (a)), p(s
4 (a)), . . .} of “even” natural numbers, we note that the sequence (I n ) oscillates quite wildly about I. Nevertheless, it is easy to see by
means of Proposition 3.3.5 that (I n ) converges in Q to I. Therefore, by Remark 3.3.3, I is a model for P . Indeed, I is a fixed point of T P and is the
unique supported model for P .
In fact, the oscillatory behaviour exhibited in this example in relation to
the single-step operator is typical of programs containing negation. Indeed,
for this example, T P is not Scott continuous, and therefore Theorem 1.1.9 is
not applicable to T P . Hence, the theory developed for the semantics of definite
programs in Chapter 2 is not applicable here either.
3.3.7 Example It is immediate from (a) of Theorem 3.2.6 and Proposition 3.3.5 that whenever a net (I i ) converges to I in Q, then it converges
to I in the Scott topology, and this is borne out by Example 3.2.8 and Corollary 3.3.10, just below, which show that the topology Q is finer than the Scott
topology in the case of two-valued interpretations.
On the other hand, the sequence (I n ) defined in the first paragraph of (3)
of Example 3.2.7 converges in the Scott topology (to several interpretations),
but does not converge (to anything) in Q.
The point of view that the topology Q is appropriate for studying the
semantics of logic programs with negation is given strong support by examples
such as Example 3.3.6. It is given further support in the most usual case, where