78
Mathematical Aspects of Logic Programming Semantics
if ((I i ), I) ∈ C, then, for each A ∈ B P , eventually I i (A) = I(A).
Then, whenever M is an interpretation for P such that ((T
n
P (M )), I) ∈ C, we
have that I is a model for P .
Proof: By Proposition 2.2.2, it suffices to show that T P (I) [ I. So, suppose therefore that T P (I)(A) = t. Then there is a ground instance A ←
A 1 , . . . , A n , ¬B 1 , . . . , ¬B m of a clause in P such that I(A 1 ∧ . . . ∧ A n ∧ ¬B 1 ∧
. . . ∧ ¬B m ) = t. Taking the sequence T
n
P (M ), we have, by the property
stated in the hypothesis (applied to each literal in the conjunction under
consideration), that eventually T
n
P (M )(A 1 ∧ . . . ∧ A n ∧ ¬B 1 ∧ . . . ∧ ¬B m ) =
I(A 1 ∧ . . . ∧ A n ∧ ¬B 1 ∧ . . . ∧ ¬B m ) = t. Therefore, eventually T
n
P (M )(A) = t,
and, by the property stated in the hypothesis again, we obtain I(A) = t.
Hence, whenever T P (I)(A) = t, we have I(A) = t. Thus, T P (I) [ I, as
required.
•
3.3.3 Remark (1) Theorem 3.3.1 shows that the largest convergence class
C to which Proposition 3.3.2 applies is the convergence class C(Q) determined by the topology Q. Therefore, Q is the coarsest topology among
the topologies determined by those convergence classes to which Proposition 3.3.2 can be applied.
(2) In topological terms, Proposition 3.3.2 says that if M is an interpretation
for a normal logic program P such that the sequence (T
n (M )) of iterates
P
converges in the topology Q to some interpretation I for P , then I is a
model for P .
In fact, we note that the construction of the perfect model semantics for
locally stratified programs P , which we give in Chapter 6, rests on the second
of the facts stated in the previous remark.
Notice that Proposition 3.3.2 holds in any convergence class contained in
C(Q). In other words, it holds for any convergence class determined by a topology finer than Q. Furthermore, Q is not the only naturally definable topology
determined by a convergence class for which Proposition 3.3.2 holds. For example, if we define lim i v i ≡ v (C) to mean that eventually v i = v, we obtain
another natural convergence class which trivially satisfies Proposition 3.3.2,
and this convergence class generates the discrete topology on I(X, T ).
Next, we want to investigate the properties of I(X, T ) when endowed with
the topology Q, and indeed the representation of Q given in Theorem 3.3.1 as
a product space makes this relatively easy.
3.3.4 Theorem Let P be a normal logic program, let J be a preinterpretation for P with domain D, let X = B P,J , and let T be a truth set endowed
with the discrete topology. Then in the topology Q on I(X, T ) we have the
following results.
Mathematical Aspects of Logic Programming Semantics
if ((I i ), I) ∈ C, then, for each A ∈ B P , eventually I i (A) = I(A).
Then, whenever M is an interpretation for P such that ((T
n
P (M )), I) ∈ C, we
have that I is a model for P .
Proof: By Proposition 2.2.2, it suffices to show that T P (I) [ I. So, suppose therefore that T P (I)(A) = t. Then there is a ground instance A ←
A 1 , . . . , A n , ¬B 1 , . . . , ¬B m of a clause in P such that I(A 1 ∧ . . . ∧ A n ∧ ¬B 1 ∧
. . . ∧ ¬B m ) = t. Taking the sequence T
n
P (M ), we have, by the property
stated in the hypothesis (applied to each literal in the conjunction under
consideration), that eventually T
n
P (M )(A 1 ∧ . . . ∧ A n ∧ ¬B 1 ∧ . . . ∧ ¬B m ) =
I(A 1 ∧ . . . ∧ A n ∧ ¬B 1 ∧ . . . ∧ ¬B m ) = t. Therefore, eventually T
n
P (M )(A) = t,
and, by the property stated in the hypothesis again, we obtain I(A) = t.
Hence, whenever T P (I)(A) = t, we have I(A) = t. Thus, T P (I) [ I, as
required.
•
3.3.3 Remark (1) Theorem 3.3.1 shows that the largest convergence class
C to which Proposition 3.3.2 applies is the convergence class C(Q) determined by the topology Q. Therefore, Q is the coarsest topology among
the topologies determined by those convergence classes to which Proposition 3.3.2 can be applied.
(2) In topological terms, Proposition 3.3.2 says that if M is an interpretation
for a normal logic program P such that the sequence (T
n (M )) of iterates
P
converges in the topology Q to some interpretation I for P , then I is a
model for P .
In fact, we note that the construction of the perfect model semantics for
locally stratified programs P , which we give in Chapter 6, rests on the second
of the facts stated in the previous remark.
Notice that Proposition 3.3.2 holds in any convergence class contained in
C(Q). In other words, it holds for any convergence class determined by a topology finer than Q. Furthermore, Q is not the only naturally definable topology
determined by a convergence class for which Proposition 3.3.2 holds. For example, if we define lim i v i ≡ v (C) to mean that eventually v i = v, we obtain
another natural convergence class which trivially satisfies Proposition 3.3.2,
and this convergence class generates the discrete topology on I(X, T ).
Next, we want to investigate the properties of I(X, T ) when endowed with
the topology Q, and indeed the representation of Q given in Theorem 3.3.1 as
a product space makes this relatively easy.
3.3.4 Theorem Let P be a normal logic program, let J be a preinterpretation for P with domain D, let X = B P,J , and let T be a truth set endowed
with the discrete topology. Then in the topology Q on I(X, T ) we have the
following results.