Next, we consider the capabilities of PTG's in realizing arbitrary
Boolean functions. Let us start with a theorem which establishes
the universality of a single *n*-input PTG(*r*) in the
realization of arbitrary Boolean functions.

**Theorem 1.2.1 (****Nilsson, 1965; Krishnan, 1966):** Any Boolean
function of n-variables can be realized using a PTG of order r*n.
*

The proof of this theorem follows from the discussion in Section
1.4*.* Theorem 1.2.1 indicates that *r = n* is an upper
bound on the order of the PTG for realizing arbitrary Boolean
functions. It implies that the most difficult *n*-variable
Boolean function to implement by a PTG(*r*) requires *r = n*,
and this may require parameters*.
*So, in the worst case, the number of required parameters increases
exponentially in *n*.

Winder (1963) gave the following upper bound on the number of
realizable Boolean functions, B*n*(*r*),
of *n* variables by a PTG(*r*), *r* *n* (see
Section 1.3.4 for details):

(1.2.1)

Where *d* is given by Equation (1.1.7) and

(1.2.2)

A couple of special cases are interesting to examine.
The first is when *r = n*. From Theorem 1.2.1, any *n*-variable
Boolean function is realizable using a single PTG(*n*).
This means that the right hand side of Equation (1.2.1) should
not exceed the number of *n*-variable Boolean functions,
, if it is to be a tight upper bound.
Indeed, this can be shown to be the case by first starting with
Equation (1.2.1) and then finding the limit of C(2*n*, *d 1)
as r* approaches *n.* Since ,
we have

(1.2.3)

or

(1.2.4)

which is the desired result.

The other interesting case is for *r* = 1,
which leads to the case of an LTG. Employing Equation (1.2.1)
with *d* = *n *+ 1, *n* 2,
gives the following upper bound on the number of *n*-input
threshold functions:

(1.2.5)

It can be shown (Winder, 1963; see Problem 1.3.3)
that a yet tighter upper bound on B*n*(1)
is . Equation (1.2.5) allows us to validate
Equation (1.1.3) by taking the following limit:

(1.2.6)

Table 1.2.1 extends Table 1.1.1 by evaluating the
above upper bounds on the number of threshold functions. Note
that, despite the pessimistic fact implied by Equation (1.2.6),
a single LTG remains a powerful logic gate by being able to realize
a very large number of Boolean functions. This can be seen from
the enumerated results in Table 1.2.1 (see the column labeled
B*n*(1)). In fact,
B*n*(1) scales exponentially
in *n* as can be deduced from the following lower bound (Muroga,
1965)

(1.2.7)

*n*

Table 1.2.1. Enumeration of threshold functions and evaluations
of various upper bounds for *n* 8.

By its very definition, a PTG may be thought of as a two layer
network with a fixed preprocessing layer followed by a high fan-in
LTG. Kaszerman (1963) showed that a PTG(*r*) with binary
inputs can be realized as the cascade of a layer of
AND gates, each having a fan-in between two to *r* input
lines, and a single LTG with inputs (representing
the inputs received from the AND gates plus the original *n*
inputs). The resulting architecture is shown in Figure 1.2.1.

**Example 1.2.1:** Consider the XNOR function (also known as
the equivalence function):

Using a Karnaugh map (shown in Figure 1.2.2), it can be verified
that this function is not a threshold function; therefore, it
cannot be realized using a single 2-input LTG (a diagonal pattern
of 1's in the K-map is a non-threshold pattern and indicates a
non-threshold/non-linearly separable function).

Since *n* = 2, Theorem 1.2.1 implies that a PTG(2) is sufficient;
i.e., the QTG with three weights, shown in Figure 1.2.3, should
be sufficient to realize the XNOR function.

By defining , we can treat the PTG as
a 3-input LTG and generate the K-map shown in Figure 1.2.4.

Since is defined as ,
there are some undefined states which we will refer to as "don't
care" states; these states can be assigned either a 1 or
0, to our liking, and give us the flexibility to identify the
threshold pattern shown in Figure 1.2.5 (this pattern is the complement
of one of the threshold patterns shown in Figure 1.1.5, and therefore
it is an admissible threshold pattern).

Figure 1.2.5. Karnaugh map after an appropriate assignment of
1's and 0's to the "don't care" states of the map in
Figure 1.2.4.

The above K-map verifies that is realizable
using a single LTG. The QTG in Figure 1.2.3 will realize the
desired XNOR function with weight assignments as shown in Figure
1.2.6. Dertouzos (1965) describes a tabular method for determining
weights for LTG's with small *n*. This method works well
here, but will not be discussed. The topic of adaptive weight
computation for LTG's is treated in Chapter Three.

A geometric interpretation of the synthesized QTG may be obtained
by first employing Equation (1.1.5), which gives

(1.2.8)

In arriving at this result, we took the liberty of interpreting
the AND operation as multiplication. Note that this interpretation
does not affect the QTG in Figure 1.2.6 when the inputs are in
{0, 1}. Next, Equation (1.2.8) may be used to define a separating
surface *g* that discriminates between the 1 and 0 vertices,
according to

(1.2.9)

(here '' is the symbol for "defined
as"). A plot of this function is shown in Figure 1.2.7,
which illustrates how the QTG employs a nonlinear separating surface
in order to correctly classify all vertices of the XNOR problem.

Another way of geometrically interpreting the operation of the
QTG described by Equation (1.2.8) is possible if we define the
product *x*1*x*2
as a new input *x*3.
Now, we can visualize the surface of Equation (1.2.9) in 3-dimensions
as a plane which properly separates the four vertices (patterns)
of the XNOR function (see Problem 1.2.4 for an exploration of
this idea).