(a) (b)
Figure 1.1.1. (a) Symbolic representation of a linear
threshold gate and (b) its transfer function.
The vector x in Equation (1.1.1) is n
dimensional with binary or real components (i.e., x {0, 1}n
or x Rn)
and . Thus, the LTG output y
may assume either of the following mapping forms:
or
An LTG performs a linear weightedsum operation
followed by a nonlinear hard clipping/thresholding operation,
as described in Equation (1.1.1). Figure 1.1.2 shows an example
LTG which realizes the Boolean function y given by:
(1.1.2)
where x1
and x2 belong to
{0, 1}. Equation (1.1.2) reads y = [(NOT
x1) AND x2] OR [x2 AND (NOT
x3)]. Here, the
weight vector w = [1 2 1]T
and threshold T = lead
to a correct realization of y. One way of arriving at
the solution for w and T is to directly solve the
following set of eight inequalities:
0 < T w1 + w2 T
w1 < T w1 + w3 < T
w2 T w2 + w3 T
w3 < T w1 +
w2 + w3 < T
These inequalities are obtained by substituting all
eight binary input combinations (x1,
x2, x3)
and their associated y values from Equation (1.1.2), in
Equation (1.1.1). For example, for input (x1, x2, x3) = (0, 0, 0),
the output y [using Equation (1.1.2)] is given by y = 0.
Hence, for a proper operation of the LTG, we require: 0w1 + 0w2 + 0w3 < T,
which gives the first of the above eight inequalities: 0 < T.
The other seven inequalities are obtained similarly for each
of the remaining cases: (x1, x2, x3) = (0, 0, 1)
through (1, 1, 1). It should be noted that the solution
given in Figure 1.1.2 is one of an infinite number of possible
solutions for the above set of inequalities.
There exists a total of
unique Boolean functions (switching functions) of n variables,
there are 2n combinations
of n independent binary variables which lead to
unique ways of labeling these 2n
combinations into two distinct categories (i.e., 0 or 1). It
can be shown (see Section 1.2) that a single ninput LTG
is capable of realizing only a small subset of these
Boolean functions (refer to Figure 1.1.3). A Boolean function
which can be realized by a single LTG is known as a threshold
function. A threshold function is a linearly separable function,
that is, a function with inputs belonging to two distinct categories
(classes) such that the inputs corresponding to one category may
be perfectly, geometrically separated from the inputs corresponding
to the other category by a hyperplane. Any function that is not
linearly separable, such as the exclusiveOR (XOR) function ,
cannot be realized using a single LTG and is termed a nonthreshold
function. Linear and nonlinear separability are illustrated
in Figure 1.1.4 (a) and (b), respectively.
Figure 1.1.3. Pictorial representation depicting
the set of threshold functions as a small subset of the set of
all Boolean functions.
(a) (b)
Figure 1.1.4. Linear versus nonlinear separability:
(a) Linearly separable function, and (b) nonlinearly separable
function. Filled circles and open squares designate points in
the first class and second class, respectively.
Threshold functions have been exhaustively enumerated
for small n (Cameron, 1960 ; Muroga, 1971) as shown in Table
1.1.1. This table shows the limitation of a single LTG with regard
to the realization of an arbitrary Boolean function. Here, as
, the ratio of the number of LTGrealizable
Boolean functions, Bn,
to the total number of Boolean functions approaches zero; formally,
(1.1.3)
This result is verified in Section 1.2.

 
Table 1.1.1. Comparison of the number of threshold functions versus
the number of all possible Boolean functions for selected values
of n.
Although a single LTG cannot represent all Boolean functions,
it is capable of realizing the universal NAND (or NOR) logic operation
( and ). Hence,
the LTG is a universal logic gate; any Boolean function is realizable
using a network of LTG's (only two logic levels are needed).
Besides the basic NAND and NOR functions, though, an LTG is capable
of realizing many more Boolean functions. Therefore a single
ninput LTG is a much more powerful gate than a single
ninput NAND or NOR gate.
For n 5, a Karnaugh map (or Kmap) may be employed to
identify thresholding functions or to perform the decomposition
of nonthreshold functions into two or more factors, each of which
will be a threshold function. This decomposition allows for obtaining
an LTG network realization for Boolean functions as illustrated
later in Section 2.1.1 of Chapter 2. Figure 1.1.5 shows the admissible
Kmap threshold patterns for n = 3. The Kmap for the
threshold function in Equation (1.1.2) is shown in Figure 1.1.6
along with its corresponding threshold pattern. Each admissible
pattern may be in any position on the map, provided that its basic
topological structure is preserved. Note that the complements
of such patterns also represent admissible threshold patterns
(refer to Example 1.2.1 in Section 1.2 for an example). Admissible
patterns of Boolean functions of n variables are also admissible
for functions of n + 1 or more variables (Kohavi,
1978).
Figure 1.1.6. A Karnaugh map representation for the threshold
function . The 1's of this function can
be grouped as shown to form one of the threshold patterns depicted
in Figure 1.1.5.
1.1.2 Quadratic Threshold Gates
 

1.1.3 Polynomial Threshold Gates
In this case, the number of degrees of freedom is given by