**2.1 Some Preliminary Results on Neural Network Mapping Capabilities**

In this section, some basic LTG network architectures
are defined and bounds on the number of arbitrary functions which they
can realize are derived. The realization of both Boolean and multivariate
functions of the form *f *: R*n* {0, 1}
are considered.

**2.1.1 Network Realization of Boolean Functions**

A well known result from switching theory (e.g., see Kohavi,
1978) is that any switching function (Boolean function) of *n*-variables
can be realized using a two layer network with at most 2*n*-1
AND gates in the first (hidden) layer and a single OR gate in the second
(output) layer, assuming that the inputs and their complements are available
as inputs. This network is known as the AND-OR network and is shown in
Figure 2.1.1. The parity function is a Boolean function which requires
the largest network, i.e., the network with 2*n*-1
AND gates. For the case *n* = 4, the K-map of the parity
function is shown in Figure 2.1.2.

Figure 2.1.1. AND-OR network structure.

Figure 2.1.2. K-map for the 4-input parity function.

It was shown in Chapter One that a single LTG is a more
powerful logic gate than a single AND (or OR) gate. Thus, one may replace
the hidden layer AND gates in Figure 2.1.1 with LTG's and still retain
the universal logic property of the AND-OR network [The universality of
a properly interconnected network of simple threshold gates was first noted
in a classic paper by McCulloch and Pitts (1943)]. The resulting net with
the LTG's does not require the complements of the input variables as inputs,
as for the AND-OR net. This LTG net will be referred to as a threshold-OR
net. Given the same switching function, the threshold-OR net may require
a smaller number of gates compared to an AND-OR net. The parity function,
though, is an example where the required number of AND gates is equal to
the number of threshold gates in both nets; i.e., 2*n*-1
gates. Note that a fewer number of hidden LTG's than AND gates are needed
if the LTG net employs an LTG for the output unit. However, it can be shown
(see Section 2.2.1) that hidden
LTG's would still be necessary for realizing arbitrary Boolean functions
in the limit of large *n*. Another interesting result is that a two
hidden layer net with LTG's
is necessary for realizing arbitrary Boolean functions (see Section 2.2.2
for details). Here, LTG's are
sufficient.

The synthesis of threshold-OR and other LTG nets for the
realization of arbitrary switching functions was extensively studied in
the sixties and early seventies. A recommended brief introduction to this
subject appears in the book by Kohavi (1978). In fact, several books and
Ph.D. dissertations have been written on threshold logic networks and their
synthesis (refer to the introduction of Chapter One for references). Here,
we give only a simple illustrative example employing the K-map technique
(the K-map was introduced in Section 1.1.1) to realize the Boolean function
*f*(**x**) in Figure 2.1.3(a). Figure 2.1.3(b) shows one possible
decomposition of *f*(**x**) into a minimal number of threshold
patterns (single LTG realizable patterns) *f*1(**x**)
and *f*2(**x**). The
corresponding architecture for the threshold-OR net realization is depicted
in Figure 2.1.3(c). This K-map-based synthesis technique may be extended
to multiple output nets (see Problem 2.1.2), but is only practical for
.

(a) (b) (c)

Figure 2.1.3. Threshold-OR realization of a 3-input switching
function *f*(**x**): (a) K-map for *f*(**x**); (b) K-map
decomposition of *f*(**x**) into two threshold functions; and (c)
Threshold-OR realization of *f*(**x**).

The following theorem establishes an upper bound on the
size of a feedforward net of LTG's for realizing arbitrary, partially specified
switching functions.

* Theorem 2.1.1: Consider a partially specified
switching function f*(

Proof of Theorem 2.1.1:

This theorem can be viewed as a corollary of Theorem 1.4.1
of Chapter One (see Problem 2.1.2).

Theorem 2.1.1 can be easily extended to the case of multiple
output switching functions of the form .
Here, the worst case scenario is to duplicate the above network *L*
times where *L* is the number of output functions! This leads to a
sufficient LTG net realization having *mL* LTG's in its hidden layer
and *L* LTG's in its output layer.

**2.1.2 Bounds on the Number of Functions Realizable
by a Feedforward Network of LTG's**

Consider the following question: How many functions *f *: R*n*
{0, 1} defined on *m* arbitrary points in R*n*
are realizable by a layered net of *k* LTG's? In the following, this
question is answered for three different network architectures. First,
a single hidden layer feedforward network, second, an arbitrarily interconnected
net with no feedback, and finally a two hidden layer feedforward network.
All three nets are assumed to be fully interconnected.

Consider a feedforward net with *k* LTG's in its
hidden layer, all feeding to a single LTG in the output layer as shown
in Figure 2.1.4. We can show that for *m* arbitrary points in R*n*,
with *m* 3*n *+ 2 and *n* 2, this net can realize
at most *F*1(*n, m, k*)
functions, with *F*1 given
by (Winder, 1963)

(2.1.1)

Figure 2.1.4. A two layer feedforward net with *k*
hidden LTG's feeding into a single output LTG.

Proof:

Each of the *k* LTG's can realize at most (Winder,
1963; Also, recall Problem 1.3.3)

functions (dichotomies), and the final LTG can realize
at most

functions. Therefore, the network can realize no more
than

or

functions.

Another interesting type of network is the generally,
fully interconnected net of *k* LTG's with no feedback shown in Figure
2.1.5. This type of network can realize at most *G*(*n*, *m*, *k*)
functions with *G* given by

(2.1.2)

Figure 2.1.5. Generally fully interconnected net
of *k* LTG's with no feedback.

Proof:

Since there is no feedback, the gates (LTG's) can be ordered
as first gate, second gate, ..., *k*th gate, so that the *j*th
gate only receives inputs from the *n* independent variables and the
*j* - 1 gates labeled 1, 2, ..., *j*
- 1 (see Figure 2.1.5). The *j*th gate
can then realize at most

functions. The total network can realize at most

functions, which is less than

This last result can be simplified to

Similarly, it can be shown that the feedforward net shown
in Figure 2.1.6 with two hidden layers of LTG's
each, and with a single output LTG, is capable of realizing at most

(2.1.3)

functions.

Figure 2.1.6. A three layer LTG net having units
in each of the two hidden layers and a single output LTG.

Similar bounds can be derived for points in general position
by simply replacing the bound
on the number of realizable functions by the tighter bound for
input units (units receiving direct connections from all components of
the input vector), since the statistical capacity of a single *d*-input
LTG is 2(*d *+ 1) points, for large *d* (refer to Section
1.3.3).