In Section (Non-series-parallel circuits), the problem of determining a Boolean function to represent a non-series-parallel circuit was discussed, and it was pointed out that it is difficult to design such a circuit to represent a given function. The general solution to this problem is not known. However, there are certain types of functions,  called symmetric functions, for which the solution is known. The purpose of this section is to show how the most economical circuits for such functions can be constructed.

We will say that a function of n variables .x₁, x₂ . . . . . . . x_n, is symmetric in these variables if and only if the interchange of any pair of variables leaves the function identically the same.

As examples, the function xy'+ x'y is symmetric in x and y, the function xyz + x'y'z' is symmetric in x, y, and z, and .ry'z - r'yz - r'y'z' is symmetric in x, y, and z'. In addition to the many symmetric functions that arise, it is often possible to write a function in such a way that a factor, or a summand, of the function is symmetric. In these cases, the symmetric part of the function may be realized by the type of circuit discussed in this section and then combined in series or parallel with the remainder of the function.

The following theorem gives the basis for the method of design of circuits for symmetric functions.

THEOREM. A necessary and sufficient condition that a function of n variables be symmetric is that it may be specified by stating a set of numbers n₁, n₂, ... , n_k, 0≤ni ≤ n for each i, such that if any set of exactly n_i, i = 1, 2, . . . , k, of the variables are 1, the function has the value 1 and not otherwise.

Proof. If the function is symmetric, then interchanging the variables does not change the function, hence the number of variables taking the value 1 determines the function rather than any specific assignment of 1's among the variables. Conversely, if the number of variables which have the value 1 is sufficient to determine the value of the function, the variables may be interchanged without altering the function, and hence the function is symmetric.

We will call the set of numbers n₁, n₂, ... , n_k associated with a symmetric function the characteristic numbers for the function. The symmetric function xy + xz + yz has characteristic numbers 2 and 3 since if either two or three of the variables are 1, the function has the value 1. Similarly,  xy' + x'y has the single characteristic number 1. To find the character- istic numbers for a symmetric function, it is necessary only to evaluate the function with 0, 1, ... , n of its variables as 1, and the rest as 0, in any single order and record those numbers for which the function is 1.

FIG. 1-1. Circuit for symmetric functions of three variables.

FIG. 1-2. Symmetric circuit of x, y, and z, with 2 as the characteristic number.

FIG. 1-3. General circuit for symmetric functions of n variables.

It can be shown that the product of two symmetric functions in the same variables is symmetric and has for its characteristic numbers those numbers common to both functions. The sum of two symmetric functions in the same variables is symmetric and has for its characteristic numbers all characteristic numbers of either or both sumniands. Finally, the negative (or complement) of a symmetric function in n variables is symmetric and has for its characteristic numbers all numbers from 0 to n inclusive except those which are characteristic numbers of the given function.

Before considering the general symmetric function of n variables, we will first discuss the case of three variables. Figure 1-1 shows a circuit capable of realizing any symmetric function of three variables. The levels on the right, numbered 0, 1, 2. and 3, correspond to characteristic numbers. A closed circuit between T₁ and position 2, for instance, results if and only if any two of the switches are closed.

Hence, to realize a symmetric function of three variables with characteristic numbers n₁, n₂, ... , n_k, we connect levels n₁, n₂, ... , n_k. each to T₂ and then delete any portions of the circuit not used. For example,  the function xyz' + xy'z -r'yz is symmetric and has characteristic number 2. Beginning with the diagram of Fig. 1-1and omitting unused portions, we obtain the circuit of Fig. 1-2(a), redrawn in Fig. 1-2(b),  to show the bridge circuit of Section (Non-series-parallel circuits).

From this illustration, it should be reasonably clear that the diagram in Fig. 1-3 will realize any symmetric function of n variables. Levels associated with each characteristic number are connected to the terminal T₂. The resulting non-series-parallel circuit will in general be more economical of switches than a series-parallel circuit, although there are some exceptions. Further simplification is possible in certain special cases.

If it happens that some relation holds between the characteristic numbers for a symmetric function, it may be possible to effect further simplifications. We will illustrate the possibilities by an example of the symmetric function in x, y, z, u, z', and w which has characteristic numbers 1,  3, and 5 (numbers in arithmetic progression). We begin with the circuit of Fig. 1-4, formed as described above, and label certain vertices for reference. Since the requirement is that the circuit be closed when an odd number of switches is closed, each closed path may be thought of as being obtained by tracing any path through the circuit in which the tracing pencil rises by one level an odd number of times. Since each level is identical to that part of every level immediately below it, an equivalent circuit could be obtained by eliminating all but the first two levels and connecting points A, B, C, and D to points A", B", C", and D" by the appropriate switch which formerly connected these points to

FIG. 1-4. Symmetric function; characteristic numbers 1, 3, and 5.

FIG. 1-5. Simplification of Fig. 1-4by shifting down.

A', B', C', and Y. Then, instead of thinking of a path which rises an odd number of levels, we may describe the circuit as consisting of any path formed by an odd number of changes of level. We have as a result of this process of "shifting down," the diagram of Fig. 1-5, where the lower level corresponds to levels 0, 2, 4, and 6, and the upper level to the original levels 1, 3, and 5 simultaneously. The circuit is clearly equivalent to that of Fig. 1-4 but contains twenty switches instead of thirty-six.

This method can sometimes, with modifications, be applied to cases in which the characteristic numbers are not in arithmetic progression.  In any case, it illustrates a possibility that should be kept in mind. The problem of the n-way light-switch control circuit can readily be solved by using this method.

مواضيع ذات صلة

Zero Polynomial

Kronecker,s Polynomial Theorem

THE ALGEBRA OF SETS-The number of elements in a set

THE ALGEBRA OF SETS-Solution of equations

THE ALGEBRA OF SETS-Conditional equations

THE ALGEBRA OF SETS-Properties of set inclusion

THE ALGEBRA OF SETS- Expanding, factoring, and simplifying

THE ALGEBRA OF SETS-Fundamental laws

THE ALGEBRA OF SETS-Venn diagrams

THE ALGEBRA OF SETS-The combination of sets

THE ALGEBRA OF SETS-Element and set

THE ALGEBRA OF SETS-Introduction