193
Logic Programming and Artificial Neural Networks
7.4.1 Theorem For each propositional normal logic program P , a 3-layer
feedforward network can be constructed which computes the immediate consequence operator T P .
Proof: Let m and n be the number of propositional variables and the number
of clauses occurring in P , respectively. Without loss of generality, we may
assume that the variables are ordered. The network associated with P can
now be constructed by the following translation algorithm.
(1) Both the input and output layers are vectors of binary threshold units of
length m, where the i-th unit in either of these layers represents the i-th
variable, 1 ≤ i ≤ m. The threshold of each unit occurring in the input or
output layer is set to 0.5.
(2) For each clause of the form A ← L 1 , . . . , L k , k ≥ 0, occurring in P , do
the following.
(2.1) Add a binary threshold unit c to the hidden layer.
(2.2) Connect c to the unit representing A in the output layer with weight
1.
(2.3) For each literal L j , 1 ≤ j ≤ k, connect the unit representing L j in
the input layer to c and, if L j is an atom, then set the weight to 1;
otherwise, set the weight to −1.
(2.4) Set the threshold θ c of c to l − 0.5, where l is the number of positive
literals occurring in L 1 , . . . , L k .
Each interpretation I for P can be represented by a binary vector
(v 1 , . . . , v m ). Such an interpretation is given as input to the network by externally activating corresponding units of the input layer at time t 0 . It remains
to show that T P (I)(A) = t if and only if the unit representing A in the output
layer becomes active at time t 0 + 2Δt.
If T P (I)(A) = t, then there is a clause A ← L 1 , . . . , L k in P such that
for all 1 ≤ j ≤ k we have I(L j ) = t. Let c be the unit in the hidden layer
associated with this clause according to (2.1) of the construction. From (2.3)
and (2.4) we conclude that c becomes active at time t 0 + Δt. Consequently,
(2.2) and the fact that units occurring in the output layer have a threshold of
0.5 (see Step (1) of the construction) ensure that the unit representing A in
the output layer becomes active at time t 0 + 2Δt.
Conversely, suppose that the unit representing the atom A in the output
layer becomes active at time t 0 + 2Δt. From the construction of the network,
we find a unit c in the hidden layer which must have become active at time
t 0 + Δt. This unit is associated with a clause A ← L 1 , . . . , L k . If k = 0,
that is, if the body of the clause is empty, then, according to (2.4), c has
a threshold of −0.5. Furthermore, according to (2.3), c does not receive any
input, that is, p c = 0+0.5, and consequently c will always be active. Otherwise,
if k ≥ 1, then c becomes active only if each unit in the input layer representing
Logic Programming and Artificial Neural Networks
7.4.1 Theorem For each propositional normal logic program P , a 3-layer
feedforward network can be constructed which computes the immediate consequence operator T P .
Proof: Let m and n be the number of propositional variables and the number
of clauses occurring in P , respectively. Without loss of generality, we may
assume that the variables are ordered. The network associated with P can
now be constructed by the following translation algorithm.
(1) Both the input and output layers are vectors of binary threshold units of
length m, where the i-th unit in either of these layers represents the i-th
variable, 1 ≤ i ≤ m. The threshold of each unit occurring in the input or
output layer is set to 0.5.
(2) For each clause of the form A ← L 1 , . . . , L k , k ≥ 0, occurring in P , do
the following.
(2.1) Add a binary threshold unit c to the hidden layer.
(2.2) Connect c to the unit representing A in the output layer with weight
1.
(2.3) For each literal L j , 1 ≤ j ≤ k, connect the unit representing L j in
the input layer to c and, if L j is an atom, then set the weight to 1;
otherwise, set the weight to −1.
(2.4) Set the threshold θ c of c to l − 0.5, where l is the number of positive
literals occurring in L 1 , . . . , L k .
Each interpretation I for P can be represented by a binary vector
(v 1 , . . . , v m ). Such an interpretation is given as input to the network by externally activating corresponding units of the input layer at time t 0 . It remains
to show that T P (I)(A) = t if and only if the unit representing A in the output
layer becomes active at time t 0 + 2Δt.
If T P (I)(A) = t, then there is a clause A ← L 1 , . . . , L k in P such that
for all 1 ≤ j ≤ k we have I(L j ) = t. Let c be the unit in the hidden layer
associated with this clause according to (2.1) of the construction. From (2.3)
and (2.4) we conclude that c becomes active at time t 0 + Δt. Consequently,
(2.2) and the fact that units occurring in the output layer have a threshold of
0.5 (see Step (1) of the construction) ensure that the unit representing A in
the output layer becomes active at time t 0 + 2Δt.
Conversely, suppose that the unit representing the atom A in the output
layer becomes active at time t 0 + 2Δt. From the construction of the network,
we find a unit c in the hidden layer which must have become active at time
t 0 + Δt. This unit is associated with a clause A ← L 1 , . . . , L k . If k = 0,
that is, if the body of the clause is empty, then, according to (2.4), c has
a threshold of −0.5. Furthermore, according to (2.3), c does not receive any
input, that is, p c = 0+0.5, and consequently c will always be active. Otherwise,
if k ≥ 1, then c becomes active only if each unit in the input layer representing