**Theorem 1.4.1 (*** Kashyap, 1966):
Any n-variable switching (Boolean) function of m points with m*
2

Proof of Theorem 1.4.1:

Let *g*(**x**) represent the weighted-sum
signal (the signal just before thresholding) for a PTG with *m*
degrees of freedom (here, the threshold *T* will be set to
zero),

(1.4.1)

where

(1.4.2)

For example, if *n* = 4,* ***x***
= *[*x*1* x*2*
x*3 *x*4]T,
and **x***i =*
[ 1 1 0 1]T, Equation
(1.4.2) gives *i*(**x**)*
= x*1* x*2*
x*4. Note that by
convention 00 = 1. Next,
we rearrange the *m* points (vertices) of a given switching
function as **x**(0)*, ***x**(1)*, ..., ***x**(*m1)*,
so that the number of 1's in **x**(*i*)
is larger than or equal to those in **x**(*j*)
if *i *>* j*. To find the separating surface, *g*(**x**)*
*= 0, that separates the *m* points into the two designated
classes (0 and 1), the function *g*(**x**) must satisfy:

, for *i* = 0, 1, ..., *m* 1**
**(1.4.3)

where

(1.4.4)

and **w** = [*w*0 *w*1 *w*2 ... *w**m* 1]T
is the PTG weight vector. If the vector **y** is normalized
by multiplying patterns of class 0 by 1, then Equation (1.4.3)
may be rewritten in the following compact form

**Aw **=

where **b** is an arbitrary positive margin vector.
Here, **A** = **TB**, where **B** is defined as the
*m m* matrix

(1.4.6)

and **T** is an *m m* diagonal matrix given
by

(1.4.7)

The **A** matrix is a square matrix and its singularity
depends on the **B** matrix. Using Equations (1.4.4) and (1.4.6),
the *ij*th component of **B** is given by

(1.4.8)

Since we have assumed that 00
= 1, Equation (1.4.8) gives **B***ii
= *1, for *i *= 0, 1, ..., *m* 1.
Now, since **x**(*i*) has
more 1's than **x**(*j*)*
*when *i* > *j*, then **B***ij*
= 0 for *i* *j*. Hence, **B** is a lower triangular
and nonsingular matrix. Accordingly, **A** is a triangular
nonsingular matrix, thus, the solution vector **w** exists
and can be easily calculated by forward substitution (e.g., see
Gerald, 1978) in Equation (1.4.5). Note that some of the components
of the solution vector **w** may be forced to zero with proper
selection of the margin vector **b**. This completes the proof
of the Theorem.

**Example 1.4.1: **Consider
the partially specified non-threshold Boolean function in Table
1.4.1. The patterns in Table 1.4.1 are shown sorted in an ascending
order in terms of the number of 1's in each pattern.

| x1 | x2 | x3 | |

x(0) | ||||

x(1) | ||||

x(2) | | |||

x(3) | ||||

x(4) | | |||

x(5) |

From Equation (1.4.8), the **B** matrix is computed as

and from Equation (1.4.7), the **T** matrix is given by

Thus, **A** = **T B** is given as

Now, using forward substitution in Equation (1.4.5) with **b***
=* [ 1 1 1 1 1 1]T, we arrive
at the solution:

Substituting this **w** in Equation (1.4.1) allows
us to write the equation for the separating surface (-surface)
realized by the above PTG as

In general, the margin vector may be chosen in such
a way that some of the components of the weight vector **w**
are forced to zero, thus resulting in a simpler realization of
the PTG. Experimental evidence (Kashyap, 1966) indicates that
the number of nonzero components of vector **w** varies roughly
from to about .
Note also that for *m* = 2*n*,
Theorem 1.4.1 is equivalent to Theorem 1.2.1. To prove this,
we note that according to Theorem 1.4.1, a PTG with
is sufficient for guaranteed realizability of *m* arbitrary
points in {0,1}*n*.
Now, for *r* = *n*, *d* takes on its largest possible
value of 2*n*, which
is the largest possible value for *m*. Therefore, any Boolean
function of *n*-variables is realizable by a single PTG(*r*
*n*) (this proves Theorem 1.2.1).