1.4 Minimal PTG Realization of Arbitrary Switching Functions

Theorem 1.4.1 (Kashyap, 1966): Any n-variable switching (Boolean) function of m points with m 2n, is realizable using a PTG(r) with m or less terms (degrees of freedom).

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 = [x1 x2 x3 x4]T, and xi = [ 1 1 0 1]T, Equation (1.4.2) gives i(x) = x1 x2 x4. 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 = [w0 w1 w2 ... wm  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 = b 0 (1.4.5)

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 ijth component of B is given by

(1.4.8)

Since we have assumed that 00 = 1, Equation (1.4.8) gives Bii = 1, for i = 0, 1, ..., m  1. Now, since x(i) has more 1's than x(j) when i > j, then Bij = 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.

 Ordered Patterns x1 x2 x3 Class x(0) 0 0 0 1 x(1) 1 0 0 0 x(2) 0 1 0 0 x(3) 1 1 0 1 x(4) 0 1 1 1 x(5) 1 1 1 1

Table 1.4.1. A partially specified Boolean function for Example 1.4.1.

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:

w = [ 1 2 2 4 2 2]T

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

g(x) = 1 2x1 2x2 + 4x1x2 + 2x2x3 2x1x2x3 = 0

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 = 2n, 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 2n, 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).

Goto [1.0][1.1] [1.2] [1.3] [1.5] [1.6] [1.7]