192
Mathematical Aspects of Logic Programming Semantics
assuming that the set T of truth values is finite. Then we obtain a compact
Hausdorff space homeomorphic to the Cantor subset of the unit interval in the
real line as shown in Theorem 3.3.4. Thus, whenever T P is continuous in the
Cantor topology on I P (see Theorem 7.5.3), we can apply Theorem 7.2.2, taking f = f F P , taking K = I P , and given a value of ε > 0, to assert the existence
of a 3-layer feedforward network satisfying the conclusion of Theorem 7.2.2.
Furthermore, by making such a network recurrent, it can also compute iterates of T P provided that conditions prevail under which the error estimate
is uniformly well-behaved relative to ε under iteration. Again, under suitable
conditions and with a suitable choice of initial input I 0 ∈ I (perhaps the bottom element of I), the iterates f F
n
P
(I 0 ) will converge to a fixed point (perhaps
the least) of T P , and these observations will be examined in Sections 7.5.2 and
7.5.6, see also Corollary 7.4.3. Finally, as one might expect, if P is actually a
propositional program, then the need for approximation disappears, and indeed a 3-layer network can be constructed which actually computes T P and,
again under suitable conditions, computes fixed points of T P . In fact, in the
case of propositional programs, networks of binary threshold units suffice for
these purposes, as we shall see. This general method is nowadays known as
the core method, and a number of instances of it are presented in the following
sections.
It is important to note that the proof of Theorem 7.2.2 is non-constructive,
and much of our work in the following sections of this chapter is concerned with
the problem of constructing suitable approximations to semantic operators
in the case of first-order programs.
12 However, we will begin by discussing
propositional programs in these terms in the next section.
7.4 Propositional Programs
The previous section delineates the problem we wish to study in this chapter, and we begin by studying the propositional case first relative to the immediate consequence operator. Before doing this however we note that networks
yet simpler than those just described, namely, 2-layer feedforward networks
of binary threshold units, do not in general suffice to compute the immediate
consequence operator for (definite) propositional logic programs, although we
give no details of this claim here.
13
We now present the main result of this section.
14
12 We know of no constructive proof of Theorem 7.2.2 and refer the reader to the papers
[Cybenko, 1989, Funahashi, 1989, Hornik et al., 1989] for well-known versions of the proof.
13 See [Hitzler et al., 2004] for a discussion of this fact.
14 This result was first established in [H¨ olldobler and Kalinke, 1994]; here, and in the rest
of this section, we follow [Hitzler et al., 2004].
Mathematical Aspects of Logic Programming Semantics
assuming that the set T of truth values is finite. Then we obtain a compact
Hausdorff space homeomorphic to the Cantor subset of the unit interval in the
real line as shown in Theorem 3.3.4. Thus, whenever T P is continuous in the
Cantor topology on I P (see Theorem 7.5.3), we can apply Theorem 7.2.2, taking f = f F P , taking K = I P , and given a value of ε > 0, to assert the existence
of a 3-layer feedforward network satisfying the conclusion of Theorem 7.2.2.
Furthermore, by making such a network recurrent, it can also compute iterates of T P provided that conditions prevail under which the error estimate
is uniformly well-behaved relative to ε under iteration. Again, under suitable
conditions and with a suitable choice of initial input I 0 ∈ I (perhaps the bottom element of I), the iterates f F
n
P
(I 0 ) will converge to a fixed point (perhaps
the least) of T P , and these observations will be examined in Sections 7.5.2 and
7.5.6, see also Corollary 7.4.3. Finally, as one might expect, if P is actually a
propositional program, then the need for approximation disappears, and indeed a 3-layer network can be constructed which actually computes T P and,
again under suitable conditions, computes fixed points of T P . In fact, in the
case of propositional programs, networks of binary threshold units suffice for
these purposes, as we shall see. This general method is nowadays known as
the core method, and a number of instances of it are presented in the following
sections.
It is important to note that the proof of Theorem 7.2.2 is non-constructive,
and much of our work in the following sections of this chapter is concerned with
the problem of constructing suitable approximations to semantic operators
in the case of first-order programs.
12 However, we will begin by discussing
propositional programs in these terms in the next section.
7.4 Propositional Programs
The previous section delineates the problem we wish to study in this chapter, and we begin by studying the propositional case first relative to the immediate consequence operator. Before doing this however we note that networks
yet simpler than those just described, namely, 2-layer feedforward networks
of binary threshold units, do not in general suffice to compute the immediate
consequence operator for (definite) propositional logic programs, although we
give no details of this claim here.
13
We now present the main result of this section.
14
12 We know of no constructive proof of Theorem 7.2.2 and refer the reader to the papers
[Cybenko, 1989, Funahashi, 1989, Hornik et al., 1989] for well-known versions of the proof.
13 See [Hitzler et al., 2004] for a discussion of this fact.
14 This result was first established in [H¨ olldobler and Kalinke, 1994]; here, and in the rest
of this section, we follow [Hitzler et al., 2004].