THE UNIVERS ITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note SYMMETRIC AND PARTIALLY SYMMETRIC BOOLEAN FUNCTIONS Michael Ao Harrison ORA Project 04879 under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF 33(657)-7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1962

TABLE OF CONTENTS Page SUMMARY v I. INTRODUCTION 1 II. PERMUTATION GROUPS 2 III. S'YMETRIC FUNCTIONS 4 IV. EXAMPLES AND COMPUTATIONAL SUGGESTIONS 6 V0 PARTIALLY SYMMETRIC FUNCTIONS 8 VI. TIE GEOMETRIC REPRESENTATIONS OF SYMMETRIC FUNCTIONS 10 VII MISCELLANTEOUS PROPERTIES OF SYMMETRIC FUNCTIONS 15 VIII. SOME ALGEBRAIC RESULTS 21 REFERENCES 23 1ii

SUIiMARY Algorithms for detecting symmetric and partially symmetric Boolean functions are derived using the generators of the symmetric group. Certain properties of symmetric functions are discussed, in particular the behavior of symmetric functions under the group of permutations and complementations. These results indicate the connection between ordinary symmetric functions and snymetric functions of mixed variables. v

I. INTRODUCTION Since almost all switching functions are arbitrarily complex, it is desirable to restrict our attention to special classes of functions in practical design problems, Two classes of interesting functions are the symmetric and partially symmetric functions If we consider the realization of switching functions by relay contacts, and if the number of variables n is reasonably large, 2n1 then an arbitrary switching function asymptotically requires -- contacts, while a symmetric function requires at most n contacts, and a partially symmetric function of n variables, symmetric in k of them, requires at most min (k + 1) (X(n - k) + k), (k + 1)(2 k+ k - 2) + 2 Thus we easily see that these classes of functions are more economical to realize than an arbitrarily selected function.* The only algorithms for detecting whether a function is symmetric are due 2 8 to Caldwell and McCluskey. Caldwell's method uses a generalization of the Karnaugh map to detect symmetric functions. Since the use of this map becomes prohibitive for even a moderate number of variables, we shall exclude this technique from our consideration. The algorithm to be presented here competes favorably with the method of McCluskey, but its real importance is that it can *The question of complexity of switching functions was raised by Shannon1ll He was able to show that for any c > 0 and n > no(C) that (1 - c) I- < \(n) < 2n+2 (1 + C) -— 2, and he conjectured that for any c > 0, almost all functions have a complexity exceeding 1 - e. In a sequence of papers, Povarov and Lupanov improved these results, and Lupanov finished the problem by showing that \(n) ~ - o These authors have extended their results and obtained some information n about propositional functionse it is gratifying to see an application of switching theory to logic. 1

be generalized to an algorithm for detecting partially symmetric functions. The method to be given here applies only to functions of unmixed variables, i.e., functions of Xl,,,,.oxn or functions of xi,, ooxn, but not functions of, say, xl, x2,.. jxn. Example. S 3,31(x, x2,x3) = xlx2 + x2x3 + xlx3 is a symmetric function, while S[2,3)(xlx2,x3) = x1X2 + X2x3 + X1X3 is a mixed symmetric function and is excluded in our considerations. The larger problem of functions of mixed variables is intimately connected with the group invariance of switching functions and will be considered in a later paper. In Section VII of this report the connection between symmetric functions of mixed and unmixed variables will be discussed. i o PERMUTATION GROUPS To derive the algorithm to be given, a few results from the elementary theory of permutation groups are required. A reader familiar with the symmetric group may profitably skip this section. Consider the set S = (1,2,...,n). By a permutation of the set S we mean a one-to-one mapping from S onto S. The set of all permutations of S = (1,2,...,n) forms a group called the symmetric group of n letters, denoted by jo. The group operation is the composition of the mappings. We shall establish the convention of applying the mappings from the right. That is, if o,Pe J-, then (cp)(x) = a(P(x)). The order of t is clearly n! The usual notation for permutations will be employed. Consider the permutation a in I6 which replaces 1 by 3, replaces 3 by 5, replaces 5 by 1, interchanges 2 and 4, and leaves 6 in2

variant We write =a (135)(24)(6) There is no reason to write the cycles of length one, so they will be omitted henceforth Example Let a - (135)(24) and 3 = (23). Then p = (25134) and = (12435). We now derive a few elementary facts about?o Theorem 2.1. Any permutation ac ~ can be written as a product of disjoint cycles. Proof. Choose any oean and select a number al[el,o..,n]o Construct &al = a2, aa2 = a3,... until we reach a number already in the list, say oak = ai (1 < i < k). The predecessor of aj is aj- for j > 1, and therefore rak = al. Thus we have cj = (al,oo.,ak)o If k < n, the remaining numbers are permuted among themselves by ao The argument is repeated on the remaining numbers. Since n is finite, the argument will terminate with a = (al,~ooak)(bloo.,bm).*(clooo.cp)o Corollary 2.2. Any ca t- may be written as a product of transpositions~ A transposition is a cycle of length two, i.e. (ab). Proof. Note that (al,...,ak) = (ala2)(ala3)...(alak) The following lemma is very useful in actually carrying out computations with permutations. Two elements of a group, say a and T, are said to be conjugate it there exists an element p in the group such that a = pTp 1 The next lemma says that if one has T and p in our cyclic notation, pTp-" may be calculated by performing the permutation p on the digits in the cycles of To Lemma 2~3~ If T = (alo.e,,alp) (aa2,.,a2q).(akl, a o a9kr) and p replaces 5

aij by bij, then pTp-1 (blll,..,bip) (b2 o.,baq). b(kbk i q. bkr). Proof. P01 ~ bij — "ij T: aij -7z a ^i p ai j+- bij+i Thus bij —bij+l by pTp-1 as claimed. Example. Suppose T = (12)(345) and p = (1345). Then PTp (23)(145). Corollary 2.4. Two permutations are conjugate in ( if and only if they have the same number of cycles of each length. Proof. The preceding lemma shows that conjugate permutations have the same cycle structure. Conversely, suppose a = (a=-,,.. oaip)(aai). (a^ a,).. ( akl,...,akr) and T = (b1-,..-)blp).- (bki;-evbkri). Then take p as the permutation which replaces aij'by bi, and then T = p=ro III. SYETRIC FUN'CTION S For any switching function of n variables f(xi,,,oo.x ) and any permutation crcrn, we define their product rf as follows~ af(xi4..Vx, X =* f(x^^ O^. o ^^n) ^ Example. Suppose a = (124) and f(xx,2,X3sX4) 7f(Xs + X4) + -EX2s then af(xl,x2,X3,X4) = f(x2,x4,xsxl) = 1 s(xi + x3) + x[o Definition 3.1. A switching function f s said to be symmretric if and only 4

if af = f for every c.* To detect whether a function is symmetric, the use of the above definition would require n' tests, but it will be shown that the symmetric group on n letters is generated by only two permutations, one of which is a transposition. Since Pn is not cyclic for n 35, there is no algorithm with fewer than two tests. Lemma 3.2. n is generated by the n - 1 transpositions (1 n), (2 if), (3 n).., (n - l,n). Proof. Every element aet may be written as a product of transpositions by by corollary 2.2. It is sufficient to show that all n(n 1) transpositions can be obtained from these n - 1 transpositions. This is trivial because (i j) = (i n)(j n)(i n). Theorem 53-3- is generated by the two permutations a = (1 2 3..o n - 1) and B = (n - l,n). Proof. It will be shown that one can obtain the permutations which occur in the hypothesis of the previous lemma with these two permutations. Corollary 2o4 tells us how to proceed. We compute the conjugates of f by Ci for i = 1,.e.n - 1. Using lemma 253, we get *The definition of a symmetric function which has been given is not quite correct. Let O( be a commutative ring with identity, and O [xl,,.,oXn be the ring of polynomials in the indeterminants xl,,..,xn over 6(. The mapping a o: a-af is an automorphism of 0{ and the mapping a-+, is an isomorphism of An onto the automorphism group of C. The symmetric functions form a ring m and in fact(I( xi,.oX is a Galois extension of % of degree n' and whose Galois group is isomorphic to j. Our definition identifies An and the automorphism group, but since these groups are isomorphic this is a harmless identification, 5

oakra = (1 n) Cig-1 = (i n) for i =2,..,n - 2 Cn-1 = 1 implies an-jlD-(n-l) = (n - l,n) By lemma 5.2, a and P generate rn Theorem 3.4. If any group 9J is generated by lJ,,...,Or, and if Cif= f for i = l,...,r then of = f for any oeL_/ Proof. The argument is a trivial induction on the number of generators r. The algorithm is now apparent. If a function is invariant under (1 2.* n - 1) and (n - l,n), then the function is symmetric. Restating this in functional notation we get the following corollary. Corollary 3.5. A Boolean function f(xl,...,xn) is symmetric if and only if f(X1x2,o,X2,,xn ) f(X2,X3.,,Xn'xlxn) and f(xl,...,x x,x) = f(x19..., Xn-2XnXn- ) IV. EXAMPLES AND COMPUTATIONAL SUGGESTIONS The algorithm is extremely easy to use. If the function is in expanded normal form and if the fundamental products are represented as n-tuples of zeros and ones in the usual way, then one may form a matrix which represents the function. This matrix will have n columns and as many rows as there are terms in the normal form expansion. To check for invariance under (n - l,n) merely interchange the last two columns of the matrix. This may permute the rows of the matrix, but if a reordering of rows is performed which returns the new matrix to the original matrix, then the function is invariant under (n - l,n). 6

To check for invariance under (1 2...n - 1), move all the columns to the left one position except the nth column which remains unmoved. The n - 1 column is replaced by the first column. We now reorder and check. These calculations may be carried out with permutation matrices, but there appears to be no reason to do so. Example. Let f = x1x2x3x4 + xx2x3 + x1x2x + xXaxx3x4 We will use a double arrow (< —>) to indicate the correspondence between a function and its matrix; we will use (~) to denote an equivalence relation between matrices such that if A and B are two matrices of the same order comprised of zeros and ones, then A B iff A may be obtained from B by permuting the rows of Bo f1!1 O 1 1 1 f: 1 0 1 1 1 1 l /1 1 1 i (34)f 10 1 o 01 is i i111 \l 101 *1 O 2 \ 1 1 01o Thus this function is invariant under (3 4)~,1 i 0 1\ o 1 11\ (12 5)f K ->O 1 1 0 1 1 - f 1 0 1 1 1 l 0 1 \ i 11 1 0 This function is symmetric. The row weights are the "a-numbers*" (Recall that the a-numbers are integers between zero and n such that when any "a" of the variables are one, then the function is one.) Example. Let g = x1x2x3S + Xx2X3X4 + XIX2X3X4. 1001 (i 0 1 ) 1 10 7

01 0 1 d (1 2 3)g ->O 0 1 0 1 1 p 1 1 O ~ 0 1 This function is therefore not symmetric. David E. Wood has programmed this algorithm for the IBM-7090. Wood's program determines if a function has partial symmetries, and if so, the program determines in which variables the function is symmetric. If the function is totally symmetric, then the program determines the "a" numbers of the function. V. PARTIALLY SYMMETRIC FUNCTIONS The importance of the algorithm given in the previous section is that it can be generalized to the case of partially symmetric functions. Definition 5.1. A Boolean function of n variables f(xl,...,xn) is said to be partially symmetric if and only if there exists a permutation aejt different from the identity permutation such that af = f. The set of permutations a such that af = f forms a subgroup of / since if af = f and Tf = f, then (aT)(f) = a(T(f)) = a(f) = f.* The detection of symmetric functions was accomplished by finding a set of convenient generators for n The detection of partially symmetric functions involves finding a set of generators for the set of all subgroups of. *A subgroup is a subset of the domain of the group ~ closed under the group operation, containing inverses and the identity. The requirement about containing the identity may be dropped since if the first two conditions are satisfied then ac implies a" ~7 which implies aa1 = e1. In a finite group, the requirement o containing inverses is redundant. Cfo Ref. 5, Section 1-2, problem 4. 8

The algorithm is provided by corollary o2~2 One computes of for every n(n - 1) transposition a. There are ---- transpositionso The set of all transpositions which leave f invariant will immediately tell us which variables the function is partially symmetric in. The calculations must be performed on the expanded normal form. The algorithm is illustrated in the following example Example. Let f = xlx2X3X4 + xix23X4x + xlX2x3X.a + XiXaX3X4 + XX2X3X4 + X1X2X3X4. The transpositions which must be used in the test are (1 2), (1 3), (1 4), (2 3), (2 4), and (3 4) It is important to use the permutations in this order. If the function is invariant under all of (1 2),.oo,(1 4), then the function is totally symmetric because (i j) = (1 i)(l j)(1 i). These transpositions are another set of generators of /: f O I O S X 1 1 0 i 10 0 0 e+o010 0 1 0 1 1 101 1/ f! 11 1 01 010 1 (1 2)f > 1 0 1 1 O 1 1. f 0 1 21 011 0 1 1 1 1 l 1 In a similar fashion we see that all the other transpositions do not leave f invariant. Thus f is partially symmetric in x1 and x2s *Finding a set of generators and relations for -n has been a popular indoor sport since 1897 when Burnside and Moore each gave generators and relations for /n' Cf. Refo 4. 4n has a geometric interpretation as the symmetry group of the n - 1 dimensional simplex. 9

VIo THE GEOMETRIC REPRESENTATIONS OF SYMIETRIC FUNCTIONS In this section some geometrical interpretations of symmetric functions are discussed. Theorem 6.2 is well known; theorems 6.4 and 6.5 are due to Lee, but are reworded here to obtain greater clarity. Theorem 6.6 is due to Lupanov. The reader is assumed to be familiarL with t-hhe usual representation of 7 switching functions on the n-dimensional cube as developed by Lee.7 Definition 6.1o The n + 1 elementary symmetric functions are defined as follows: ao (xl,... ) = 1x2.o-xn ol (X1,.,Xn) = XlX2. l + XoXn X2' + x2.. oE + + X2-ooXn (an (xl,. oxn) = XX2...Xn ai(xl',o'ox) has (i) terms in its normal form expansion and ai(Xlj,..,xn) = 1 if and only if any i of its variables are ones. Therefore, 6i(xl,..,xn) = Sji)(xl,.o,Xn) for i = 0O,...,n. Of course i \ j implies oi(xl,..,xn)aj n (sl,ooo,xn) = 0 and Z oj(xi,ooo.,X) = lo j=o Theorem 6.2. Every symmetric function has a unique expansion as a sum of elementary symmetric functions. This theorem is the analog of the symmetric function theorem for ordinary polynomials. It has been discovered (and re-discovered) 7 9 5 by Lee,7 Povarov, myself, and probably others. Let X and Y be two vertices of the n-cubeo We write X = (xio.o.,Xn) and Y = (yl,. y,Yn) where xi,Yi(0O,l) (cfo Fig. 1 for an. example in three dimensions). n We define the distance between X and Y to be d(X,Y) = Z (xi ~ Yi) where the i=l 10

110 100 /010 031 001 Fig. 1. The graphical representation of the function f(X1,x2,X3) = X2X3 + 3lX2X3. summation indicates addition of natural numbers. d(X,Y) satisfies the axioms of a metric.5 Definition 6.. We denote a sphere of radius r about the center C as rC (% stands for Kugel) where C r = (X d(X,C) = r). These spheres have two centers, one at radius r and one at radius n - r assuming r < n - r. The centers are bit-wise complements of one another. A sphere of radius r has (r) points. Theorem 6.4. The elementary symmetric switching functions ai(xl...xn) (i = 11

0,...n) form spheres on the n-cube. The elementary symmetric functions have centers at (0,..oo,) and (1,...,1) with radii i and n - i, respectively. Conversely, any such sphere corresponds to an elementary symmetric function. Proof: Merely note that ai(xl,...,x) has (i) terms in its expanded normal form. Each term is of weight i, so its radius from the origin is i. The converse is obvious. Arbitrary spheres on the n-cube correspond to elementary symmetric functions of mixed variables. Theorem 6.5. A sphere of radius r on the n-cube with center C corresponds to an elementary symmetric function of mixed variables and conversely. The positions in which C has a one are the variables which are complemented. The radius of the sphere is the subscript of the elementary symmetric function. Proof: The complementation operator which takes C into (0,...,0) [and the far center into (1,...,1)] preserves the radius. Use theorem 6.4. Example. The set of points (0,0,0,1) (1,0,1,1) (0,0,1,0) (1,1,0,1) (0,1,0,0) (1,1,1,0) forms a sphere with radius 2 and centers (1,0,0,0) and (0,1,1,1). Complementing xl, we get (1,0,0,1) (0,0,1,1) (1,0,1,0) (0,1,0,1) (1,1,0,0) (0,1,1,0) This function is c2(X1,x2,x3,x4). 2 Caldwell's graphical technique is in fact an attempt at finding these spheress. 12

The geometry of the elementary symmetric functions of n variables is rather interesting. The points of the spheres may be connected to form regular n - 1 dimensional polytopes for all the elementary symmetric functions of 2, 3 and 4 variables. The function a2(X1,x2,x3,x4,x5), however, furnishes a counter example to the general conjecture. This function has () = 10 vertices. There is no regular four-dimensional polytope with 10 vertices.3 See Fig. 2 for an example. These spheres may be classified in other ways also. 111 / vl^^^ ^^T110 110010 0 10 10011 I100 0101 1000</ 0011 I00 0001 0000 Fig. 2. The symmetric function c3(x1,x2,x3,x4). The heavy lines form a regular tetrahedron whose edges are two units long as measured with the discrete metric. 13

These spheres may be exploited in many ways. The following algebraic identity enables one to construct complete decoding networks which asymptotically require one-half the contacts in a tree network.5 Theorem 6.6. If al(zl,.o.,zn) is the characteristic function of the sphere of radius one with center C = (cl,...,cn), then ci cl ci_ ci Ci+l en Zi 1Y(Z1, -X.,Zn) = Zi oo. zi_ Zi Zi+l o Zn where if ci = 0 _A0 if Ci = 1 for i = l,ooono When one investigates the symmetric functions algebraically, one immediately looks for elementary symmetric functions. The 5-functions about to be introduced have the same form as the elementary symmetric functions in an ordinary commutative ring. They are, however, not as convenient to work with, and they are of secondary importance. The reader will recognize the 5-functions as the majority functions so widely used in work on reliability, Definition 67o. The 5-functions are defined as follows: 5o = 1 n \1 = / XI 2 ) xixj 14 ~2 - = XjXj On = X2400Xn 14

Thus 5k(Xl e xn) = 1 iff at least k of the variables are 1. The.following theorem gives some simple identities about the 5 functionso Theorem 6.8. a. 8k(xl.o- Xn) = X X Xik S(kk+l,. o n)(Xl0-Xf)n) <_i <i2< o o o<ik<n S0,1.,k l) (X1,0 ~ ^.on) for k = l,..,n b. 5. o'k = max(j) c. i + 6j = 5min(ij). d. bk(x1.'x ^n)) = S(k,..,n (xl'~ xn) = S(Ol,.. k-1 (xl o0'xn) e 8j < 5k iff j > k where < is the usual partial ordering relation of a Boolean algebra a5 These functions are sufficient to serve as "generators" of the symmetric functions Theorem 6.9, Every symmetric function has a unique expansion in terms of oi and 5li Proof: Note that ok(xlooo, x) bk(xX, ooo,)Xn)6k+l( Xl,~ exn)o Apply theorem 6.2. VII. MISCELLAIEOUS PROPERTIES OF SYMMETRIC FUNCTIONS We list some elementary properties of symmetric functions due to various writers, and exploit some of the results to discuss the relation of symmetric functions to mixed symmetric functionso Theorem 71ol (Lee). ao If f fs a symmetric function of n variables, then 15

f(Xloo.,xn) = a i(xI,...,xn) = Si](xlq'..Xn) iIe i~I where I is some subset of (Q,l,...,n) = Z+1. b If f is symmetric, then f is symmetric and f(xi,...Xn) = i(xi,...Xn) = x S(i}(X,...Xn)o ie(Zn+l- I) ie(Zn+l- I) c. X1 $.oo ~ xn = a2k+l (xl,...xn) where 1 denotes the k=O largest integer not exceeding -1O e- Jxj if ej = 1 d. Defining xi = we have ----— n a 3~= [ if ej = O, n Xl ~ o0o. ~ Xn if ei 1 mod 2 el "en i= Xl 3 ~o $ Xn n xl @ o. Xn if ei 0 mod 2 C i=lCaldwell's paper produced some interesting discussions. The following theorem due to Karnaugh is contained in this discussion6 Theorem 7.2 (Karnaugh)o Cra(Xi,,"Xn) = U (i(X1lo.-Xk) aj(x(k+l),. ooXn) i+j=a O<i<k COj<n-k One can interpret geometrically the set of points in the summation. Draw the i, j plane and consider points with integer coordinates such that ie [0,k] je [O,n - k]. Then the set of points over which we sum is the straight line of slope -1 passing through (aO) and (O0a)o This theorem allows us to decompose 16

the set of variables into disjoint subsets. This theorem may be proven by induction on ko For k = 1, this is Caldwell's expansion theorem for symmetric functions. Karnaugh's theorem generalizes immediately to the following result which was implicitly stated in Reft 60 Theorem 7-3. A function f(xlo o.,xo) is symmetric if and only if m f(xl- o. xn) = ) a i(xl^ xk)j (x+- r=O i+j=a Q0<e,_ O<j<n-k for any 0 < k < n. Proof: Note that S [aam(,,^x~o~xn) = O ar (x ^ n) r=O and apply theorem 7.2. The rather unpleasant indices in the above su-mnation can be simplified. The following form of theorem 7-3 is due to Povarov. Theorem 7.4. A Boolean function if(xl,,xn) is syLmetric if and only if k f(~~~~....XI) _... f(xi,*.~Xn) = i(axa-xk)Saiai.e9aim.l(Xk+~~i- xn) i=0 where 0 < k < n and each diagonal directed downwards from left to right in a point lattice of n - k + 1 horizontal coordinates and k + 1 vertical points is either completely occupied or unoccupied by the points (iaij), The procedure given in this theorem allows us to easily characterize the numbers given in the summation of theorem 7~35 Example. We will illustrate the procedure for f(X!~oooXlo) = So) j 2 5 7] 17

(Xlx2,..., 1o). Taking k = 6 and drawing Fig. 3 3 n-k 0 I 2 3 4 5 6 k Fig. 3. The set of operating points for the symmetric function S l (Xy..,Xio) * S o,o1,2,5,7} (x1,...,X0o) f(x1,...Xlo) = So(X,...x ). S0,1,2) (X1.. X10o) + S1(X,...X6) S(Ol,,4)(X7,...Xlo) + S2(Xl,...X6) S(2,3)(X7,..X1o) + S3(X,...X6) S2,4)(7,...X10o) + S4(X1,...X) S[13) (X7, *-X10) + S5(X1, —.~X) S0,2)(X7,.-.Xo10) + S6(x1,...xn) S 2)(x7,...xlo) + The calculation involved taking each "a" number of f and decomposing it into the sum of two numbers i and j such that i + j =a O< i<6 J < 4 18

The calculations are: 1. a = 0 (0O0) 2. a = 1 (0,1) and (1,G) 3. a = 2 (0,2), (1, ), (250) 4. a = 5 (194), (2.), (59 2 ), ( 0) 59 a = 7 (34) L () (2 (6, ) These points completely occupy the diagonals ins Fig. 53 The numbers (iaij) are called the operating points of the function'e ai, are graphically found as the ordinates along the vertical line x = i which intersects the diagonals. The importance of this theorem is that iet is useful in the group invariance problem for determining the structure of the equivalence classes containing symmetric functions, The reader is assumed to be familiar with group invariance of switching functions as introduced by Shannon. Let ( be the group of complementations and permutationsL'T3 wo( func tion.s are said to ~be equivalent iff they are in the same transitivity se-t i ee., iff there exists an element of?/ which maps one function into the other. Sha:non; described the structure of this group as the direct product of< C 2 ithit where.n denotes the direct product of the cyclic group of order two with itself n times This is not correct. The situation is slightiy more compllicated Actually, { = 2 n *The groupi$ of complementations and permutations wras famous prior to its connection with logic and switching theory. * / t is the simmletry group of the ncube or measure polytope which has Schlaflii symbol (4,53n- ) It is also the symmetry group of the reciprocal polytope having Schlafli symbol ({3n2, 4)} This is called the cross polytope,9 and it is the n-dimensional analog of the octahedron. The group may also be described as t~he s rmmetry group of the n dimensional Cartesian frame formed by - mutulaly perpendilcular lines through a pointo There is also a connection between this group,-n and the automorphis-mi group of the free group with n generators. 19

where 2? } denotes the Wreath product of 2 and J. The structure of this group will be discussed in a forthcoming report. Theorem 7.5 (Povarov). The number of equivalence classes undern which contain at least one symmetric function is 2n 2n 2 + 2 (n+l) - n - 1 where [x]is the largest integer not exceeding x. Theorem 7.6 (Povarov). The number of functions equivalent to some symmetric function under 0n is 22n _ 2n+1 + 4 These two theorems tell us the connection between ordinary symmetric functions and symmetric functions of mixed variables. Theorem 7.5 counts the number of different networks necessary to realize symmetric functions. Theorem 7.6 gives the total number of symmetric functions of mixed and unmixed variables. Caldwell distinguished between these two types of functions in his paper. The discussion by Washburn2 appears to have convinced Caldwell that no distinction is necessary. Caldwell should have stuck to his original position because the functions are different while the physical networks are essentially the same. The confusion stems from misinterpretation of the meaning of group invariance, To sum up, equivalent functions under n have essentially the same network associated with them. Example. The two elementary symmetric functions ai(xl,.,xn) and an-i(xl,...,xn) are equivalent under 1n. They have essentially the network realization, but are quite different. The following theorem shows that any function of n variables is a symmetric 20

function of a sufficiently large number of variables. Theorem 7.7. Any function f(xl,...xn) of n variables may be written as a symmetric function of 2n - 1 variables. If decimal numbers are used to denote the terms of the disjunction normal form of f, then these are the "a" numbers of the symmetric function of 2n - 1 variables. Proof: Consider the mapping which sends f(x1,..,xn) —>S (xlx2,x2,...,xn...xn) where each xi is replaced by 21-1 xi's in the image and each ai corresponds to a term in the expanded normal form of f. Thus the n image is a function of L 2i1 = 2n - 1 variable. This mapping sends every i=function of n variables into a symmetric function of 2n - 1 variables. The mapping is clearly onto, one-to-one, and preserves +, ~ and -. The mapping n is really an isomorphism of the Boolean algebra of all 2" functions of n variables onto the Boolean algebra of symmetric functions of 2n - 1 variables. This theorem does not have an immediate practical application. Most functions of n variables require 2n/n contacts for large n. A function realized by this scheme requires (2n - 1)2 contacts. This latter number is larger than 2n/n for n > 2. Thus it is more expensive to realize an arbitrary function as a symmetric function of a larger number of variables. VIII. SOME ALGEBRAIC RESULTS The symmetric functions of n variables form a Boolean algebra of 2 elements. The elementary symmetric functions are the atoms. This remark indicates why the &-functions were not called the elementary symmetric functions of the Boolean algebra. This Boolean algebra is a quotient algebra of the 21

Boolean algebra of all switching functions module a certain ideal. The choice of this ideal is not unique, but the resulting quotient algebras are isomorphic. Each residue class contains 22 (n+f) functions. The partially symmetric functions of the same k (2 < k < n - 1) variables form a Boolean algebra containing the Boolean algebra of symmetric functions. (k+1)2n-k This algebra has 2 (k+)n elements, All the results may be simplified using the theory of ideals (or filters) in a Boolean algebra. Associated with these decompositions are synthesis procedures. For instance, any function f may be realized as a function of a symmetric function and a function in the ideal which determines the algebra of symmetric functionso This ideal is the kernel of the homomorphism. It has also been shown directly that almost all functions are not partially symmetric. 22

REFERENCES 1. N. Bourbaki, Elements De Mathematique, i Les Structures Fondamentales De L'Analyse, Libre Ii, Algebre, Hermann, Paris, 1959, Chapitres 1 et 4. 2. S. H. Caldwell, "The Recognition and Ide-tification of Symmetric Switching Functions," A.I.E.E. Transactions Part I, Comrrunications and Electronics, Volume 73, pp 142-146; May 1954. 35 H. S. M. Coxeter, Regular Polytopes, Metheusen and Co. Ltd., London; 1948. 4. H. S. M. Coxeter and WO 0. J. Moser, Generators and Relations for Discrete Groups, Springer-Verlag, Berlin, 19579 5. M. A. Harrison, "Notes for a Course in Switching and Automata Theory," unpublished. 6. M. Karnaugh, "Discussion" (of[7]), A.I E.E. Transactions, Part I; Communications and Electronics, Volume 735 PP. 146-147; May 1954. 7. C. Y. Lee, "Switching Functions on an n-Dimensional Cube," AI.EE. Transactions, Part I, Communications and Electronics, Volume 735 pp289-291; September 1954. 8. Eo J. McCluskey, Jr., "Detection of Group Invariance or Total Symmetry of a Boolean Function," The Bell System Technical Journal, Volume 355, pp 1445-1453; November 1956. 9. G. N. Povarov, "A Mathematical Theory for the Synthesis of Contact Networks with one Input and k Outputs,"' Proceedings of an International Symposium on the Theory of Switching, Part ITL, Hiarvard University Press, Cambridge, Massachusetts; 1959e 10. C..Shannon, "A Symbolic Analysis of Relay and Switching Circuits," A.I.E.E. Transactions, Volume 57, ppo 753-723; 1938. 11. C. E. Shannon, "The Synthesis of Two-Terminal Switching Circuits," The Bell System Technical Journal, Volume 28, ppc 59-98, January 1949, 12. S. H. Washburn, "Discussion" (of [7]) A IE E.' Transactions, Part I, Communications and Electronics, Volume 735 P. 146; May 1954. 25

UNIVERSITY OF MICHIGAN 3 9015 03026 9743