166
Mathematical Aspects of Logic Programming Semantics
5.4.13 Proposition With the hypotheses stated in the previous paragraph,
any local consequence operator T is a contraction with respect to d.
Proof: Suppose d(I, J) = 2
−n . Then I and J coincide on all atoms of level
less than n. Now let A ∈ B P with l(A) = n. Then by acyclicity of P we
have that all atoms in the body of the pseudo-clause with head A are of
level less than n, and by locality of T we have that T (I)(A) = T (J)(A). So
d(T (I), T (J)) ≤ 2
−(n+1) .
•
We finally obtain the following theorem.
5.4.14 Theorem Let P be an acyclic program, and let T be a local consequence operator for P . Then, for any I ∈ I P , we have that T
n (I) converges
in Q to the unique fixed point of T .
Proof: Since d is a complete metric, we can apply Proposition 5.4.13 and
the Banach contraction mapping theorem. This yields convergence of T
n (I)
in d to a unique fixed point M of T . By definition of d, the convergence of the
sequence of valuations T
n (I) to M is pointwise and, hence, is also convergence
in Q.
•
Theorem 5.4.14 is remarkable since the existence of a fixed point of the
given semantic operator can be guaranteed without any particular or further
knowledge about the underlying multivalued logic.
5.5 Measurability Considerations
As we shall see in Chapter 7, continuity in Q of Fitting-style operators
F P , and T P in particular, is central in relation to whether or not we can
compute them approximately by neural networks. However, in the context
of approximate computation by neural networks, the weaker notion of measurability has some interest, although rather less than that of continuity, see
[Hornik et al., 1989], for example. Thus, we shall close this chapter by briefly
discussing this topic next.
16
In the previous section, we defined Fitting-style operators over finite truth
sets, see Definition 5.4.9. However, unlike the case of the topology Q, finiteness of the truth set T is not of much importance here. Therefore, we begin
by noting that we can, in principle, work over any logic T in which the truth
value in T of disjunctions of possibly infinite countable collections of elements
16 We do not formally introduce the notion of measurability and refer to [Bartle, 1966] for
necessary background. For full details of the results we sketch here, we refer the reader to
[Seda and Lane, 2005].
Mathematical Aspects of Logic Programming Semantics
5.4.13 Proposition With the hypotheses stated in the previous paragraph,
any local consequence operator T is a contraction with respect to d.
Proof: Suppose d(I, J) = 2
−n . Then I and J coincide on all atoms of level
less than n. Now let A ∈ B P with l(A) = n. Then by acyclicity of P we
have that all atoms in the body of the pseudo-clause with head A are of
level less than n, and by locality of T we have that T (I)(A) = T (J)(A). So
d(T (I), T (J)) ≤ 2
−(n+1) .
•
We finally obtain the following theorem.
5.4.14 Theorem Let P be an acyclic program, and let T be a local consequence operator for P . Then, for any I ∈ I P , we have that T
n (I) converges
in Q to the unique fixed point of T .
Proof: Since d is a complete metric, we can apply Proposition 5.4.13 and
the Banach contraction mapping theorem. This yields convergence of T
n (I)
in d to a unique fixed point M of T . By definition of d, the convergence of the
sequence of valuations T
n (I) to M is pointwise and, hence, is also convergence
in Q.
•
Theorem 5.4.14 is remarkable since the existence of a fixed point of the
given semantic operator can be guaranteed without any particular or further
knowledge about the underlying multivalued logic.
5.5 Measurability Considerations
As we shall see in Chapter 7, continuity in Q of Fitting-style operators
F P , and T P in particular, is central in relation to whether or not we can
compute them approximately by neural networks. However, in the context
of approximate computation by neural networks, the weaker notion of measurability has some interest, although rather less than that of continuity, see
[Hornik et al., 1989], for example. Thus, we shall close this chapter by briefly
discussing this topic next.
16
In the previous section, we defined Fitting-style operators over finite truth
sets, see Definition 5.4.9. However, unlike the case of the topology Q, finiteness of the truth set T is not of much importance here. Therefore, we begin
by noting that we can, in principle, work over any logic T in which the truth
value in T of disjunctions of possibly infinite countable collections of elements
16 We do not formally introduce the notion of measurability and refer to [Bartle, 1966] for
necessary background. For full details of the results we sketch here, we refer the reader to
[Seda and Lane, 2005].