215
Logic Programming and Artificial Neural Networks
order ≤ � on C by s ≤ � t if and only if s 8 t = t. (So that s ≤ + t if and only if
s + t = t, and s ≤ × t if and only if s × t = t, for finitely determined operations
+ and ×, and similarly for finitely determined operations of disjunction ∨ and
conjunction ∧ in case C is a logic T .)
7.6.3 Example In FOU R, we have t ≤ ∧ u ≤ ∧ f , and t ≤ ∧ b ≤ ∧ f . Also,
f ≤ ∨ u ≤ ∨ t, and f ≤ ∨ b ≤ ∨ t.
In fact, the allowable and excluded sets for s ∈ C can easily be characterized
in terms of the partial orders just defined: s ∈ A
� if and only if s ≤ � t, see
t
[Seda and Lane, 2005, Proposition 3.10]. Because of this fact, we have the
following result.
7.6.4 Proposition Suppose that 8 is a finitely determined binary operation
g
on C and that M is a countable set. Then a product
evaluates to
i∈M t i
the element s ∈ C, where s is the least element in the ordering ≤ � such that
t i ∈ A
� for all i ∈ M .
s
Having now determined how we evaluate the truth values of the bodies of pseudo-clauses in relation to Fitting-style operators F P , we move
next to consider the computation of these operators by neural networks in
the case of propositional normal logic programs P . Indeed, it is shown in
[Lane and Seda, 2006] that one can construct conventional 3-layer feedforward
networks to compute Φ P and Ψ P containing only binary threshold units, in
the style of Theorem 7.4.1.
41 However, extending this approach to the general
case of F P is not so simple, as the constructions become overly complicated.
Therefore, we will adopt a modular approach in which we construct two types
of 2-layer neural networks of binary threshold units. The first of these (the
multiplication unit) will compute products or conjunctions of elements of C,
and the second of them (the addition unit) will compute sums or disjunctions of elements of C. It then remains to construct 3-layer neural networks
to compute F P in which the hidden layer consists of multiplication units and
the output layer consists of addition units; strictly speaking, these networks
have five layers of course. In this context, it is worth noting that the partial
ordering ≤ � , defined previously, and Proposition 7.6.4 play a crucial role in
establishing the results we discuss here.
For the rest of this section, we shall focus on finite sets C with n elements
listed in some fixed order, C = {c 1 , c 2 , . . . , c n } or C = {t 1 , t 2 , . . . , t n }, say. In
order to simulate the operations in C by means of neural networks, we need
to represent the elements of C in a form amenable to their manipulation by
neural networks. To do this, we represent elements of C by vectors of n units,
and it is convenient sometimes to view them as column vectors, where the first
unit represents c 1 , the second unit represents c 2 , and so on. Hence, a vector of
41 See the thesis [Kalinke, 1994], where these results are stated. We thank S. H¨ olldobler
for drawing this reference to our attention.
Logic Programming and Artificial Neural Networks
order ≤ � on C by s ≤ � t if and only if s 8 t = t. (So that s ≤ + t if and only if
s + t = t, and s ≤ × t if and only if s × t = t, for finitely determined operations
+ and ×, and similarly for finitely determined operations of disjunction ∨ and
conjunction ∧ in case C is a logic T .)
7.6.3 Example In FOU R, we have t ≤ ∧ u ≤ ∧ f , and t ≤ ∧ b ≤ ∧ f . Also,
f ≤ ∨ u ≤ ∨ t, and f ≤ ∨ b ≤ ∨ t.
In fact, the allowable and excluded sets for s ∈ C can easily be characterized
in terms of the partial orders just defined: s ∈ A
� if and only if s ≤ � t, see
t
[Seda and Lane, 2005, Proposition 3.10]. Because of this fact, we have the
following result.
7.6.4 Proposition Suppose that 8 is a finitely determined binary operation
g
on C and that M is a countable set. Then a product
evaluates to
i∈M t i
the element s ∈ C, where s is the least element in the ordering ≤ � such that
t i ∈ A
� for all i ∈ M .
s
Having now determined how we evaluate the truth values of the bodies of pseudo-clauses in relation to Fitting-style operators F P , we move
next to consider the computation of these operators by neural networks in
the case of propositional normal logic programs P . Indeed, it is shown in
[Lane and Seda, 2006] that one can construct conventional 3-layer feedforward
networks to compute Φ P and Ψ P containing only binary threshold units, in
the style of Theorem 7.4.1.
41 However, extending this approach to the general
case of F P is not so simple, as the constructions become overly complicated.
Therefore, we will adopt a modular approach in which we construct two types
of 2-layer neural networks of binary threshold units. The first of these (the
multiplication unit) will compute products or conjunctions of elements of C,
and the second of them (the addition unit) will compute sums or disjunctions of elements of C. It then remains to construct 3-layer neural networks
to compute F P in which the hidden layer consists of multiplication units and
the output layer consists of addition units; strictly speaking, these networks
have five layers of course. In this context, it is worth noting that the partial
ordering ≤ � , defined previously, and Proposition 7.6.4 play a crucial role in
establishing the results we discuss here.
For the rest of this section, we shall focus on finite sets C with n elements
listed in some fixed order, C = {c 1 , c 2 , . . . , c n } or C = {t 1 , t 2 , . . . , t n }, say. In
order to simulate the operations in C by means of neural networks, we need
to represent the elements of C in a form amenable to their manipulation by
neural networks. To do this, we represent elements of C by vectors of n units,
and it is convenient sometimes to view them as column vectors, where the first
unit represents c 1 , the second unit represents c 2 , and so on. Hence, a vector of
41 See the thesis [Kalinke, 1994], where these results are stated. We thank S. H¨ olldobler
for drawing this reference to our attention.