GAP (Thelma) - Chapter 4: Networks of Threshold Elements

Not all Boolean functions can be realized by a single threshold element. However, all of them can be realized by a multi-layered network of threshold elements, with a number of threshold elements on a first layer and conjunction or a disjunction on the second layer. In this chapter we will decribe some functions regarding such networks.

4.1 Basic Operations

In this section we describe some operations, similar to the ones described in Section 3.1.

4.1-1 NeuralNetwork

For the list of threshold elements InnerLayer and the Boolean variable OuterLayer, which can be either true (for disjunction), false (for conjunction), or fail (if there is only one layer) the function NeuralNetwork returns a neural network built from this inputs.


gap> te1:=ThresholdElement([1,1],1);
< threshold element with weight vector [ 1, 1 ] and threshold 1 >
gap> te2:=ThresholdElement([-1,-2],-2);
< threshold element with weight vector [ -1, -2 ] and threshold -2 >
gap> inner:=[te1,te2];
[ < threshold element with weight vector [ 1, 1 ] and threshold 1 >,
  < threshold element with weight vector [ -1, -2 ] and threshold -2 > ]
gap> nn:=NeuralNetwork(inner,false);
< neural network with
2 threshold elements on inner layer and conjunction on outer level >
gap> Display(last);
Inner Layer:
[ [[ 1, 1 ], 1], [[ -1, -2 ], -2] ]
Outer Layer: conjunction
Neural Network realizes the function f :
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 1
[ 1, 0 ] || 1
[ 1, 1 ] || 0
Sum of Products:[ 1, 2 ]

4.1-2 IsNeuralNetwork

For the object Obj the function IsNeuralNetwork returns true if Obj is a neural network (see NeuralNetwork (4.1-1)), and false otherwise.


gap> ## Consider the neural network <C>nn</C> from the previous example.
gap> IsNeuralNetwork(nn);
true

4.1-3 OutputOfNeuralNetwork

For the neural network NNetwork the function OutputOfNeuralNetwork returns the Boolean function, realized by NNetwork.


gap> f:=OutputOfNeuralNetwork(nn);
< Boolean function of 2 variables >
gap> Display(last);
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 1
[ 1, 0 ] || 1
[ 1, 1 ] || 0

4.2 Networks of Threshold Elements

4.2-1 BooleanFunctionByNeuralNetwork

For the Boolean function Func the function BooleanFunctionByNeuralNetwork returns a two-layered neural network, which realizes Func (see NeuralNetwork (4.1-1)). The realization of this function is based on the algorithm proposed in [GPR83].


gap> x:=Indeterminate(GF(2),"x");;
gap> y:=Indeterminate(GF(2),"y");;
gap> z:=Indeterminate(GF(2),"z");;
gap> f:=PolynomialToBooleanFunction(x*y+z,3);
< Boolean function of 3 variables >
gap> nn:=BooleanFunctionByNeuralNetwork(f);
< neural network with
2 threshold elements on inner layer and disjunction on outer level >
gap> Display(last);
Inner Layer:
[ [[ -1, -2, 4 ], 2], [[ 1, 2, -3 ], 3] ]
Outer Layer: disjunction
Neural Network realizes the function f :
Boolean function of 3 variables.
[ 0, 0, 0 ] || 0
[ 0, 0, 1 ] || 1
[ 0, 1, 0 ] || 0
[ 0, 1, 1 ] || 1
[ 1, 0, 0 ] || 0
[ 1, 0, 1 ] || 1
[ 1, 1, 0 ] || 1
[ 1, 1, 1 ] || 0
Sum of Products:[ 1, 3, 5, 6 ]

4.2-2 BooleanFunctionByNeuralNetworkDASG

For the Boolean function Func the function BooleanFunctionByNeuralNetworkDASG returns a two-layered neural network which realizes Func (see NeuralNetwork (4.1-1)). The realization of this function is based on decomposition of Func by the non-unate variables with the biggest influence. The DASG algorithm (DASG - Decomposition Algorithm for Synthesis and Generalization) was proposed in [SJF08], however we use a slightly modified version of this algorithm.


gap> f:=LogicFunction(3,2,[0,0,0,0,0,1,1,0]);
< Boolean function of 3 variables >
gap> nn:=BooleanFunctionByNeuralNetworkDASG(f);
< neural network with 2 threshold elements on inner layer and conjunction on outer level >
gap> Display(last);
Inner Layer:
[ [[ 1, 4, 2 ], 3], [[ 1, -4, -2 ], -3] ]
Outer Layer: conjunction
Neural Network realizes the function f :
Boolean function of 3 variables.
[ 0, 0, 0 ] || 0
[ 0, 0, 1 ] || 0
[ 0, 1, 0 ] || 0
[ 0, 1, 1 ] || 0
[ 1, 0, 0 ] || 0
[ 1, 0, 1 ] || 1
[ 1, 1, 0 ] || 1
[ 1, 1, 1 ] || 0
Sum of Products:[ 5, 6 ]