THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Technical Note THE NUMBER OF EQUIVALENCE CLASSES OF BOOLEAN FUNCTIONS UNDER GROUPS CONTAINING NEGATION Michael A." HarrisOn. ORA Projeet 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 4 In my recent paper on combinatorial analysis, algorithms were constructed for counting the number of transitivity sets of Boolean functions under three groups. The results of this previous paper will be assumed; we shall enlarge the groups under consideration by allowing complementation of functions as well as the other group operations. Algorithms are obtained for counting the number of equivalence classes under the enlarged groups. The results are ap2 plied to simplify a recent result of Elspas. The duality group is defined, and the number of classes is shown to be the same as with the negation group except in one case. iii

I. INTRODUCTION In this paper, we extend the results obtained in reference 4 to the case where negation of Boolean functions is also allowed. The negation of a Boolean function is obtained by the action of a negation group to be denoted by Y has order two; one element is the identity mapping and the other element denoted by r has the property: @:f f — f for any Boolean function f. The groups to be considered are 2x n L x d, and V x ( 2 n (n One can trivially show that if }Jis any permutation group on the atoms of the free Boolean algebra, then the (abstract) structure of the group X enlarged by allowing complementation of functions is ) x 6 where the cross indicates the direct product. Our results will be obtained by applying a special case of a theorem by De Bruijn. De BruijnIs paper states that this theorem is a generalization of Polya's famous theorem, but Harary has informed this writer (oral communication) that De Bruijn's theorem would follow from Polya's if one could find Z c in terms of Zv and Z. Unfortunately the latter result is not yet known. Cf. Harrison for an example of exponentiation of permutation groups. 1

II. DE BRUIJN'S THEOREM For our purposes we shall need a form of De Bruijn's theorem 2. The result to be used is an extremely weak consequence of this general theorem. Let D be a finite set of d elements and R a finite set of r elements. Consider the class of functions from D to R. Let A and L denote permutation groups acting on D and R respectively. Two functions fl and f2 are said to be equivalent if and only if there exist elements a E, 3 E L such that fl(d) = 5 f2(a(d)) for d C D. Since this is a genuine equivalence relation, the family of functions is decomposed into equivalence classes. } denotes the set of all such classes and F will denote an equivalence class of functions from D into R. Before stating De Bruijn's theorem, we briefly review the concept of the cycle index polynomial (Zyklenzieger) of a permutation group U whose order is g and whose degree is s. Let fl,...,f be s indeterminates and let o... be the number of permutations of ] having ik cycles of length k for k = 1,2,...,s. Naturally s _ iJi = s (1) i=l Then we define 7 1 g. J. f Jlf2 f3s g gjlj2,.f2..f (ji ) where the sum is taken over all partitions of s which satisfy (1). 2

We can now state our simplified form of De Bruijn's theorem. Theorem 1. (De Bruijn) If we let 00 ht = exp t z for t =l,...,r k=l then 1 = Z (_.a. -. a )Z (hl,...,hr) evaluated at z1 = z2 =... = Zs = 0. Thus the counting problem is solved once we know both cycle indices. It is to be understood that the variables in these polynomials are indeterminates. Therefore we can differentiate formally and no questions of existence or convergence ever arise. Lemma 2. A term hi... ohr in Z gives rise to z t T1.Jt."' tt) 3 i J tsJr. Proof. We compute (hi...hr) azi This yields z / r 00 Zkt a- kexp= t=l k=l /.r x \ r oo = exp j Zkt... ~. tJt 5i kt t= k=l / t=l k=l 35

where 6i kt is the Kronecker delta function, i.e., 1 if i = kt i kt = 0 otherwise Taking all the z's equal to zero gives Za (h..h.rr) Z t zi tji III. APPLICATIONS We now specialize our approach to handle an arbitrary permutation group 0^ of degree 2 and order g. For Boolean functions D = [0,1. so d = 2 and R = (0,1]. If - is taken to be the negation group Y, then we note that the action of the negation group is to permute the elements of the range of the Boolean functions. So J! is really the symmetric group of degree (and order) two; hence 1 2 Z = 2 (h! + h2) Using De Bruijn's theorem and the lemma gives Theorem 3. if O is any permutation group on the 2n min-terms, then the number of equivalence classes of Boolean functions under / x i is (Z (2,2, o..,2) + Z (0,2,0,2,,..,0,2)) 2 Y We note that Z (2,2,...,2) is the total number of classes of functions under the group ^. Since it is necessary to construct Z~ in order to 4

count the classes under (., we see that no additional work is required to count the number of classes under i x We list the number of classes under Qx A, Ax n, and (x 2 n' The cycle indices for these groups were constructed in reference 4. The pertinent results are listed here without proof. Theorem 4, i 1 2nnZ - (fn 2 + (2n 1) f2 2n Xn 2 ^1 5 n: II f Z U —-?" ~ ~n:......i n( fed + d- f' e(d)J i An ( j) Jil...n n j,1 d d12i where the last two indices are summed over all partitions of n such that n > iji = n. The functions (x), e, and g are defined in reference 4, i=l n is the group of complementations of variables; is the group of permutations of variables, (n is the group of complementations and permutations of variables. It is shown in reference 4 that = n. The group n 2 j'x in has already been studied by Golomb who did not, however, count the number of classes. Since an explicit formula has been obtained for Z, we get the following result, 5

Theorem 5. The number of classes under glx is 1 (2n + (2n )22n-1+ 1) 2n+1 Theorem 6. The number of classes under 3x n is -Z n (2,.. 2) i.e., half the number of classes under Af. n The rest of the results are tabulated below. Number of Classes Under Groups Without Complementation of Functions n 4 ~~2 Yn 1 3 4 3 2 7 12 6 3 46 80 22 4 4,336 3,984 402 5 134,281,216 37,333,248 1,228,158 6 288,2380380,379,570,176 25,626,412,338,274,304 400,507,806,843,728 Number of Classes Under Groups With Complementation of Functions 2 n 2n X 1 2 2 2 2 6 4 3 30 4o 14 4 2,288 1,992 222 5 67,172,352 18,666,624 616,126 6 114,115,192,303,714,304 12,813,206,169,137,152 200,253,952,527,184 6

We may apply theorem I to obtain some information about groups without negation of functions. If ~ is taken to be just the identity alone, then the total number of equivalence classes under 0} is Z~ (2,...,2). Comparing this to theorem 3, we get the following result. Theorem 7o The number of classes of functions under (J which are equivalent to their complements, i.e,, self-complementary, is. (0,2,02,,...,0,2). We compute the following numbers, Number of Classes of Self-Complementary Functions n in 2 n 1 1 0 1 2 3 0 2 3 14 o 6 4 2400 42 5 63,488 0 4,094 6 4,227,858,432 0 98,210,640 The results in the last column (for n < 5) were obtained independently 2 by Elspas by a laborious method, It is easy to show that no function is n equivalent to its negation under d directly. For ), the number of selfcomplementary classes is (2n - 1)22 -n IV, THE DUALITY GROUP We can define a group Z5 having order two whose non-trivial element 6 7

has the property &: f(xl,...,xn) > fD(xl,...,x) = f(l,,...,n) for any Boolean function f. One would naturally ask about the number of classes under say75 x A and d x o In these cases it is easy to 2 prove that we get the same number of classes as with x and x ~, by constructing a one-to-one mapping between the classes under the different groups. The case of x is somewhat special; the disn cussion of this group is postponed until the sequel. Recently Toda5 has counted the number of classes under which consist of only self-dual functions. It is interesting to observe that Toda's results do not give the number of classes closed under the duality operation; this latter number is somewhat larger, namely Z (0,2,0,2,..,0,2). This ~n result may be seen by showing that the equivalence classes of the two groups are the same. Number of Cla s U r Number of Classes Number of Classes Under Number of Classes Under _ x n C lof Self-Dual Func- Closed Under the x _n __xV tions Under n * Duality Operation 1 2 1 1 2 4 1 2 3 14 3 6 4 222 7 42 5 616,126 83 4,094 6 200,253,952,527,184 109,958 98,210,640 *These results are quoted from Toda's paper,5 8

REFERENCES 1. N. G. De Bruijn, "Generalization of Polya's fundamental theorem in enumerative combinatorial analysis," Koninklijke Nederlandse Akademie Van Wetenschappen, Series A, Vol. LXII, No. 2 (1959), pp. 56-59. 2. B. Elspas, "Self-complementary symmetry types of Boolean functions," IRE Transactions of Electronic Computers, Vol. EC-9, No. 2 (1960), pp. 264-266. 3. S. Golomb, "On the classification of Boolean functions," IRE Transactions on Information Theory, Vol, IT-5 (1959), ppo 176-186. 4. M. Harrison, The Number of Transitivity Sets of Boolean Functions, The University of Michigan Technical Note 04879-3-T, June 1962. 5. I. Toda, "On the number of types of self-dual logical functions," IRE Transactions on Electronic Computers, Vol. EC-11, No. 2 (1962). 9

UNtvERSISi OF MlCH\SAN //3 9/!1 03026 8356 3 ~u~56