212
Mathematical Aspects of Logic Programming Semantics
It follows that there are unit clauses C 1 ←, C 2 ←, and C 3 ← in ground(P ).
Thus, P 1 is the program
C 1 ←
C 2 ←
C 3 ←
B 2 ←
B 1 ← C 1 , C 2 , C 3
A 1 ← B 1 , B 2
Then we have the following calculations: T P1 ↑ 0 = ∅, T P1 ↑ 1 = T P1 (∅) =
{B 2 , C 1 , C 2 , C 3 }, T P1 ↑ 2 = T P1 ({B 2 , C 1 , C 2 , C 3 }) = {B 1 , B 2 , C 1 , C 2 , C 3 },
T P1 ↑ 3 = {A 1 , B 1 , B 2 , C 1 , C 2 , C 3 }, and T P1 ↑ 4 = T P1 (T P1 ↑ 3) =
{A 1 , B 1 , B 2 , C 1 , C 2 , C 3 } = T P1 ↑ 3. Thus, T P1 ↑ 3 is a fixed point of T P1
and indeed is the least such fixed point. Moreover, A 1 ∈ T P1 ↑ 3.
Further properties of P n can be found in [Seda, 2007].
Now let ε > 0 be given and choose n so large that 2
−n < ε. Then
d l (I n , I) ≤ 2
−n < ε, where I n is the least fixed point of T P , I is the least fixed
point of T P , as noted above,
n
and d l is the metric associated with l. Now apply
the algorithm of Theorem 7.4.1 to the propositional program P n and make
the resulting network F n (which computes T P ) recurrent. On inputting the
n
interpretation ∅ to this network and iterating n times, we obtain I n as output.
Thus, F n approximates I up to ε, and in this sense the family {F n | n ∈ N}
computes I.
7.5.12 Example Take P to be as in Example 3.2.3, that is, the program
p(a) ←
p(s(X)) ← p(X)
Applying the procedure above to P , we obtain a sequence F n of 3-layer feedforward recurrent neural networks which computes the least fixed point of T P
and hence computes the set of natural numbers.
7.6 Some Extensions – The Propositional Case
So far in this chapter, we have concentrated on the operator T P . However,
in this section and the next we want to briefly consider extensions of our results
to other operators and hence to other semantics. In the present section, we will
focus on propositional normal logic programs P and extensions of the results of
Mathematical Aspects of Logic Programming Semantics
It follows that there are unit clauses C 1 ←, C 2 ←, and C 3 ← in ground(P ).
Thus, P 1 is the program
C 1 ←
C 2 ←
C 3 ←
B 2 ←
B 1 ← C 1 , C 2 , C 3
A 1 ← B 1 , B 2
Then we have the following calculations: T P1 ↑ 0 = ∅, T P1 ↑ 1 = T P1 (∅) =
{B 2 , C 1 , C 2 , C 3 }, T P1 ↑ 2 = T P1 ({B 2 , C 1 , C 2 , C 3 }) = {B 1 , B 2 , C 1 , C 2 , C 3 },
T P1 ↑ 3 = {A 1 , B 1 , B 2 , C 1 , C 2 , C 3 }, and T P1 ↑ 4 = T P1 (T P1 ↑ 3) =
{A 1 , B 1 , B 2 , C 1 , C 2 , C 3 } = T P1 ↑ 3. Thus, T P1 ↑ 3 is a fixed point of T P1
and indeed is the least such fixed point. Moreover, A 1 ∈ T P1 ↑ 3.
Further properties of P n can be found in [Seda, 2007].
Now let ε > 0 be given and choose n so large that 2
−n < ε. Then
d l (I n , I) ≤ 2
−n < ε, where I n is the least fixed point of T P , I is the least fixed
point of T P , as noted above,
n
and d l is the metric associated with l. Now apply
the algorithm of Theorem 7.4.1 to the propositional program P n and make
the resulting network F n (which computes T P ) recurrent. On inputting the
n
interpretation ∅ to this network and iterating n times, we obtain I n as output.
Thus, F n approximates I up to ε, and in this sense the family {F n | n ∈ N}
computes I.
7.5.12 Example Take P to be as in Example 3.2.3, that is, the program
p(a) ←
p(s(X)) ← p(X)
Applying the procedure above to P , we obtain a sequence F n of 3-layer feedforward recurrent neural networks which computes the least fixed point of T P
and hence computes the set of natural numbers.
7.6 Some Extensions – The Propositional Case
So far in this chapter, we have concentrated on the operator T P . However,
in this section and the next we want to briefly consider extensions of our results
to other operators and hence to other semantics. In the present section, we will
focus on propositional normal logic programs P and extensions of the results of