THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note THE NUMBER OF TRANSITIVITY SETS OF BOOLEAN FUNCTIONS Michael A. 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 June 1962

SUMMARY Three groups are defined as transformation groups on the class of Boolean functions. The transitivity classes are counted using the famous combinatorial theorem of Polya. In particular, a concise algorithm is found for counting the classes under the group of complementations and permutations thus simplifying a result of Slepian.6 iii

I. INTRODUCTION There is a well known connection between switching theory and Boolean functions. Since the Boolean algebra of functions is a free algebra on n generators, it has 2n atoms and contains 22 functions. Many of the techniques of switching theory require enumeration of functions. To a mathematician, these problems of switching theory are trivial, since if n is finite, 22 is finite and all of the functions may be enumerated. On the other hand, for n' 9, 22 is larger than the number of electrons and protons in the universe and enumeration is impractical. A technique developed to help cut down the number of functions to be enumerated is to define a group as operating on the class of Boolean functions. If the group is intransitive on Boolean functions, one has only to enumerate equivalence classes (also called orbits or transitivity classes) rather than functions. We will consider three groups operating on Boolean functions and in each case we shall count the number of equivalence classes of functions with k atoms in their (unique) normal form expansion by the use of the Hauptsatz of Polya. II. POLYA'S THEOREM In his classic study of trees, chemical isomers, and their relatives, Polya4 proved a theorem which has subsequently become the most famous and most important single result of combinatorial analysis. Polya's theorem has 1

achieved this distinction because of its generality, and simplicity, We shall briefly review this result; using the general formulation of DeBruijn.2 Our discussion involves more generality than is needed for our results; the importance of the theorem justifies the additional generality, Let F be the class of all functions from a finite set D to a finite set R. Suppose D has s elements and that (7y is a permutation group of degree s and order g acting on D. Two functions fl, f2 E F are called equivalent if there exists a permutation a E f such that fl(d) = f2(c(d)) for all d e D (c(d) denotes the image of d under the permutation a). We represent R r as the union of r disjoint subsets, i.e., R = I Ri and Ri Rj = 0 if i f j, i=l Let kl,...,ks be any partition of s. Polya's theorem tells us the number of equivalence classes of functions from D to R such that for ki values of d c D, the image f(d) E Ri for i = l,...,r. Let Vi be the number of elements in Ri and define the figure counting series as 00 *(x) = > ixi i=O Let P(xl,...,xs) be the generating function for the number of classes of functions with the property that for ki values of d C D, the image f(d) is in Ri k, ks e.go, the desired number is the coefficient of x1 l...xs in P(x1,...,X). The polynomial P(xloo,,,xs) is sometimes called the configuration counting series. Before stating Polya's theorem, we must develop the concept of the cycle index polynomial of C( (Zyklenzeiger), denoted by Zi. Let fl,...,fs be s indeterminates, and let gjl,j2, ooo,j be the number of permutations of ( 2

having jk cycles of length k for k = 1, 2,,,.,s. Naturally s I iji = s (1) i=l Then we define z = g gglij2,-.,P,,gjS f1 f2... fs g (J) where the sum is taken over all partitions of s which satisfy (1) Let Z (g(x), g(x2),.,g(xs)) denote the cycle index polynomial with fi replaced by g(xi) (i = l,.,s) for any arbitrary function g(x). Now we can finally state Polya' s theorem which reduces the problem of determining the number of equivalence classes to the determination of the figure counting series and the cycle index polynomial. Theorem 2,1 (Polya). The configuration counting series is obtained by substituting the figure counting series into the cycle index polynomial of o Symbolically P(x1,..S,Xs) = Z (,(x'),,(x ),9..,,(xS)) For the problems to be considered here, Polya's theorem takes an even simpler form. First of all, we deal only with generating functions of one variable, When one considers equivalence of Boolean functions, we have D = 0O, l1n, s = 2n, and R = (0, 1}. Thus r(x) = l+x The only non-trivial calculations that need to be made will be the construction of the cycle index for each group. We can then compute P(x); the 5

coefficient of xk in P(x) will be the number of classes of functions having k atoms in their normal form expansions, n III. THE GROUP 2 The first group to be considered is the direct sum of n copies of the n cyclic group of order 2, denoted by ~. The order of this group is 2n and 2 the elements are n-tuples of zeroes and ones. The group operation is written (0 Now we define this group as operating on the class of Boolean functions following Ashenhurst who first studied this group. n Definition 3.1. Let i E l and let f(xl,...,xn) be a Boolean function of n 2 variables. We define if = (il,.o.,in) f(xl,...,xn) = f(xl,...,xn n) ii xj if ij = 0 where xJ = 3xj if i: = 1 for j = 1,...,n n One defines two functions as equivalent under F if there is an operation of 2 the group which maps one function into the other. Intuitively the functions are equivalent if one can be obtained from the other by complementing some of the variables. Example: The two Boolean functions X12+XlX2 and Xl12+XlX2 are equivalent 2 under 2 n The effect of a permutation i E L is to permute the n-tuples of zeroes 2 and ones for which f(x1,...,xn) is one i.e., the atoms of the normal form ex4

pansion of f(xi,...,xn). It will be convenient to have a notation for the atoms and for the permutations of atoms. n-tuples of zeroes and ones are associated both with the atoms and with the decimal equivalent of the binary number. The correspondence is made clearer in the following table for three variables. Atom Binary Representation Decimal Symbol XX2X3 ~000 0 lEX2X3 001 1 FlX2Xs3 010 2 x-1X2X3 011 3 XR2'X3 100 4 x 1^2X3 101 5 xlx2x3 110 6 X1X2X3 111 7 n If i, j e6 2 then let Pi, pj denote the corresponding permutations of the atoms, and let pij denote the permutation corresponding to iO j. It n is easy to prove that pij = pp* Thus the mapping from i e 2 into the permutation group on the atoms denoted by n is a homomorphism. The mapping is easily seen to be one-to-one but properly into. nis easily seen 2n to be the automorphism group of the Boolean algebra of functions. *If f = Ak is the normal form expansion of f, then pjpjf = Ai j Since j.f = Ai.~k we have pi = PiPj iG j denotes the digitwise modulo two sum of i and j. 5

Example: Let us apply the permutation i = (0, 1, 1) to all the functions of three variables. We apply the permutation to the atoms and write the result using the conventional cyclic notation for permutations. (03)(12)(47)(56) To count the equivalence classes we must determine the cycle structure n of the permutations in our representation of E. n 2 Theorem 3.2. Every i e K different from the identity induces a permutation 2 of the atoms which has 2n-1 transpositions. n Proof. Let Aj and Ak be two atoms and let i e ~ be different from the ident2 ity. Suppose i(Aj) = Ak, then Aj = i(Ak) because i is of order 2. Thus the permutation of atoms associated with i, has disjoint transpositions for its n-1 cycle structure. It cannot have less than 2 transpositions because no atom is invariant under any i. 1 211n n o " _ If2n-1 nn 2n Theorem 535. (Ashenhurst) Z = (fl + (22n - l) f2 ) * 2 Proof. The first term corresponds to the identity element while the second term corresponds to all other elements of the group. *This is a special case of a more general result. If one takes 1 to be the regular representation of the group of order p and type (p,...,p), then it 1 k k- 1 can be shown that Z C = - (fl + (p -l)fp ) for primes p >2 and k > 1. 6

Corollary 3.4. The number of equivalence classes of functions having s atoms n in their (unique) normal form expansion under is 2 2n 2n -s ) if s- 1 mod 2 n n-1 and 1 (( ) + (2n 1) ( ) if s- mod 2 Proof. By Polya's theorem, we get Z (1 + ((1+ x)2 + (2 - )(l + x2) ^ 2n = T (2 xk + (2n _1) 2 2 k k j=) I:f s 1 mod 2, the coefficient of Xs is 1 ( If s Q O mod 2, the coefficient of xS is __ 2 +(2n 2- 1 ((n2n - 1) (2 )) Corollary 3.5. The total number of equivalence classes of Boolean functions n under ) is 1 ( 22n + (2n _ 1)22 / 2n Proof. By Polya's theorem, take fi = l+l1 = 2 in Z 2 Some typical calculations for this group have been made and the results are tabulated below. We use Tn for the total number of equivalence classes and Nk for the number of classes of functions having k atoms in their normal ~n ~k Pk form expansions. Note that Nn =k N -k which is a consequence of the law of duality for Boolean functions. 7

n Nk k 1 2 3 4 5 0 1 1 1 1 1 1 1 1 1 1 1 2 1 3 7 15 31 3 1 7 35 155 4 1 14 140 1,240 5 7 273 6,293 6 7 553 28,861 7 1 715 105,183 8 1 870 330,460 9 715 876,525 10 553 2,020,239 11 273 4,032,015 12 14o 7,063,784 13 5 35 10,855,425 14 1 15 14,743,445 15 1 1 17,678,835 16 1. 18,796,230 Tn 5 7 46 4,336 134,281,216 IV. THE GROUP Now we define the symmetric group on n letters as a group of operators on the Boolean functions. Definition 4.1. For any a E 4 and any f(xi,...,n) E F, we define n af(xi,...,xn) = f(x(l),...,x ( (n)) Again we induce a permutation on the atoms exactly as before. This mapping is again a one-to-one homomorphism from into 2 n n The cycle index for T as a group on n letters is well known, but we 8

need a representation of ]f as a permutation group on 2n objects.* The following theorem allows us to use the cycle index of / as a group on n letters to get the cycle index of the group on the atoms. Theorem 4.2. Permutations of the same cycle structure in f induce permutations of the same cycle structure in 2 n Proof. Let h be the homomorphism from n into (4. Since all permutations of the same cycle structure are conjugates, it is sufficient to show that conjugates of a in correspond to conjugates of h(a) in j. This n 2n is trivial since h(p'ap) = h(p'l)h(c)h(p) = (h(p)) lh( )h(p) because h is a homomorphism. We must devise an algorithm to pass from the symmetric group on n letters to a representation of the group on 2 letters. To accomplish this, we calculate the effect of a cycle of length k on the atoms of the Boolean algebra. Definition 4.3. e(l) = 2 -/ d e(d) dlk e(k) d<k k *Two groups may be isomorphic but not permutationally equivalent. Permutation groups t and aon object sets X and Y are called permutationally equivalent if and only if and J are isomorphic as abstract groups and there is a one-to-one correspondence h: X — ^ Y such that if y is the abstract isomorphism between $( and 4, then for every x E X, ao e, we have h(a x) = (7 a)h(x). 9

Theorem 4.4. A cycle of length k in as a group on letters induces a permutation of the atoms whose cycle structure is given by X' f e(d) d k d where the fd are the indeterminates of the cycle index of n on 2 letters. Proof. Write the numbers from 0 to 2k-1 in binary notation and in natural order. The effect of a permutation of length k can be obtained by removing the left-hand column and writing it as the right-hand column. This has the effect of doubling each number modulo 2k-1. The exponent of fd is independent of n and has the same value every time it occurs. Note that if k is prime, 2k_2 then we get f2fk k. The exponent of fk is an integer; this fact is a consequence of Fermat's theorem. Before writing down the explicit formula for the cycle index of as n a permutation group on the 2 atoms, we construct a multiplication of indeterminates which will facilitate computation. il i^r J1 Jis Definition 4.5. Let al...ar andb b... be two products of indeterminates; the letters ak and bk are not necessarily distinct. The product of these terms (written x) is given by p,q where p x ipJq(p,) app x bq - V = <Pq> where < p,q > denotes the least common multiple of p and q and (p,q) is the greatest common divisor of p and q. Of course, x is an associative and commutative operation. 10

Exaple: We compute the cycle structure of the permutation which corresponds to the product of a cycle of length 2 and a cycle of length 3. This is denoted by t2t3. t2t3 =- (f f2) x (fif) = (ff) ( )(ff2(f2 442p2 424p2 = lfsf2f = f4f2f43f ~~~~~~~~~~n ~~~(p,q) The symbol ai means alx...x an. The reason that fpxfq = f > is Ai* F4 <p< q:f> that we are changing the degree of our representation from p+q to pq, TIbe subscript will be <p,q> as Slepian showed and the exponent occurs because (p,q) <p,q> = pq, the number of objects being permuted. Theorem 4.6. The cycle index for n as a permutation group on the 21 atoms of the Boolean algebra of functions is =~ n,., Jn n fde(d) Z~n n. z jj J 2 in.n i d where the sum is over all partitions of n such thatn iii n i-l and yi = yilx y2x...x yin where y =yJ xn Proof. The coefficient in the sum is the number of permutations of the n letters with ji cycles of length i(i = l,...,n). To see this, choose any permutation with the required cycle structure. If all n; permutations are applied to the letters in the cycles, then the resulting permutations are not distinct for just two reasons, (1) the relative position of the cycles is irrelevant and (2) all cycles with the same elements in the same order are the 11

same. The number of duplications for the first reason jl' Ji2..Jn' The J1 32 in number of duplications for the second reason is 1 2...n so that the desired number is n! n JT i ii i=l Corollary 4.7. The number of equivalence classes under 4 of functions n n with k atoms in their normal form expansion is the coefficient of xk in P(x) = Z (l + x). n Corollary 4.8. The total number of equivalence classes of functions under is (n P(l) = Z (2). 8 n Example: We perform the calculations for n = 2. 1 ( f + ff) Z = f 0'2 P(x) = 1 + 3x + 4x2 + 3x 4 + The twelve equivalence classes are listed below. [0] [1] [xy] [xy] [x+y] [X+y] [x(y] [x = y] [x,y] [3,y ] [x+y x+y] [xy,y ] 12

The results of some computations for modest values of n are shown below. The number of variables is denoted by n and Nn is the number of classes n k 2 -k of functions of n variables having k-atoms. Note that Nn = Nn; again Tn denotes the total number of classes. n k k 1 2 3 4 5 0 1 1 1 1 1 2 3 4 5 6 2 1 4 9 17 28 3 3 16 52 134 4 1 20 136 625 5 16 284 2,674 6 1 9 477 10,195 7 4 655 34,230 8 1 730 100,577 9 655 258,092 10 477 579,208 11 284 1,140,090 12 136 1,974,438 15 52 3,016,994 14 17 4,077,077 15 5 4,881,092 16 1 5,182,326 Tn 4 12 80 3,984 37,333,248 V. THE GROUP 0 n The next group to be considered is the group which allows both complementation and permutations of the variables. This group, denoted by X has n order n!2n; a general element of the group is of the form ia where i c 2 and cr E. Gn is defined as a transformation group on the Boolean functions as follows:! ^in iGf(xl,...,Xn) = f(x (1),...,x ) i(1)i o(n) 13

67yi is also the symmetry group of the n-cube and the dual of the n-cube, Jn the hyperoctahedron.* Polya (5, footnote 7) mentions that is the wreath product (Kranzgruppen) of and X denoted by 2 L ) / however this n 2 n 2 gives n a representation of degree 2n, The 2n objects may be taken as the "-n faces of the n-cube or the vertices of the hyperoctahedron inscribed in the hypercube. Our problem requires that n be given as a permutation group of degree 2n1 Harary3 has constructed an operation called exponentiation of groups for precisely this reason; we review Harary's defintion briefly. Let ()N and j be permutation groups of degrees a and b operating on object sets X and Y; let the orders of (j and $ybe m and n respectively. X The exponentiation group \. has Y, the class of all functions from X to Y, fot as its object set. The elements of } are constructed by permuting the domain X using a permutation in CJ and then permuting the image objects for every domain object by elements of f4. The properties of this group are given below along with the properties of 67 LJ]. The explicit construction of (ILL i may be found in Polya's paper. *This problem may be interpreted as counting the number of distinct ways that the vertices of the n-cube may be painted with two colors. We mean that two paintings of the n-cube are distinct in case one cannot be transfornned into the other by a rotation or reflection of the n-cube. 14

Wreath Product Exponentiation Group f Object Set X Y XxY Y Degree a b ab ba Order m n mna ma Thus =. Note that is isomorphic to t )I ], >n n2 but the groups are not permutationally equivalent since they have different degrees. The important problem of determining Z 4t in terms of Z and Z is still unsolved. We present a method of computing the cycle index of the exponentiation group in this special case. Unfortunately the technique cannot be generalized to arbitrary exponentiations. Slepian has already counted the number of equivalence classes under (4, but his argument was unnecessarily complicated. His method required counting the conjugate classes of the hyperoctahedral group; our result depends on the knowledge of the cycle l/K index of n The derivation of the cycle index rests on the following argument. Since n n V, = I / * every element of M is of the form ia where i Ec (7n 2 n Yn 2 *By the product r y of two groups C and j which are subgroups of a larger group O we mean the group whose domain is fabja E Yt, b ce. This group is defined when one of C or v5 is normal in (f. In our case n n 2 is normal in (1 * Thus n is the least group containing Y and Jo 2n fn 2 n 15

n and ca C Since every element of ) except the identity has the same n cycle structure, we need only compute the effect of the permutation of An n- in pre-multiplied by any permutation consisting of 2 transpositions because VW/~ n we already know the structure of as a group on the 2 atoms. n Definition 5.1. The function g(d) is defined as follows: g(2) = 1 2k - dg(d) dfk d 2k g(2k) = 2k 2k Theorem 5.2. If tk is an indeterminate of the cycle index of, then the following correspondence indicates the cycle structure induced on the atoms in t h,n 1(_ / TT fe(d) + g( f d) tk 2( Aid + fdk d ) 2v dlk d~k d 2k Proof. The first term describes the elements of when i = (0,...,0); this subgroup is just 0. The second term describes the cycle structure n n obtained by pre-multiplying the permutations of by any element n 2 say (0 1)(2 3)...(2n-2, 2n-l). The multiplication of indeterminates is exactly the same as for n and for exactly the same reasons. 16

Theorem 5.3. The cycle index of = is given by n 2 ~1.. n:~'n Xe(d) g(d) Z = n n f + n'2n fd fd 73 Tr1^~n 7 j~ iJ l d i d-i i=l d 12i where the sum is over all partitions of n such that n 2 ^iji = n. i=l The reason that our calculation of the cycle index of (0 is so simple n n is that the cycle index of r has only two terms.'2 Corollary 5.4. The number of equivalence classes under, of functions with k atoms in their normal form expansions is the coefficient of xk in P(x) = (1 + x) n Corollary 5.5. The total number of equivalence classes of functions under, is P(1) = Z (2) fin Example. The calculations for n = 2 yield Z = 1 ((f2 + f2) + f2f2 + f4) 8 = (f4 + 5ff2 + f2 + f4) P(x) = 1 + x + 2x2 + x3 + x4 17

The classes are [0], [1], [xy, xy, xy, xy] [x,x,y,y], [xy,x - y], [x+y,x+y,x+y,x+y] Some results are tabulated below. n Nk k 1 2 3 4 5 0 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 3 1 3 6 10 4 1 6 19 47 5 3 27 131 6 3 50 472 7 1 56 1,326 8 1 74 3,779 9 56 9,013 10 50 19,963 11 27 38,073 12 19 65,664 13 6 98,804 14 4 133,576 15 1 158,658 16 1 169,112 Tn 3 6 22 402 1,228,158 18

REFERENCES 1. Ashenhurst, R. L., "The application of counting techniques, " Proceedings of the Association for Computing Machinery, Pittsburgh Meeting (1952), pp. 293-305. 2. De Bruijn, N. G., "Generalization of Polya's fundamental theorem in enumerative combinatorial analysis," Koninklijke Nederlandse Akademie Van Wetenschappen, Series A, Vol. LXII, No. 2 (1959), ppo 59-69.. Harary, F., "On the number of bi-colored graphs," Pacific Journal of Mathematics, Vol. 8 (1958), pP. 743-755o 4. Polya, G., "Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen, und chemische Verbindungen," Acta Mathematica, Vol. 68 (1937), PP. 145-253. 5. Polya, G., "Sur les types des propositions composees," Journal of Symbolic Logic, Vol. 5 (1940), pp. 98-103. 6. Slepian, D., "On the number of symmetry types of Boolean functions of n variables," Canadian Journal of Mathematics, Vol. 5 (1953), ppo 185-193. 19

UNIVERSITY OF MICHIGAN 3 9015 03026 9180