Detection of Group Invariance or Total Symmetry of a Boolean Function

A method is presented for determining whether a Boolean function possesses any group invariance; that is, whether there are any permutations or primings of the independent variables which leave the f unction unchanged. This method is then extended to the detection of functions which are totally symmetric. 1 GROUP INVARIANCE For some Boolean transmission functions (transmissions, for short) it is possible to permute the variables, or prime some of the variables, or both permute and prime variables without changing the transmission. The following material presents a method for determining, for any given transmission, which of these operations (if any) can be carried out without changing the transmission. The permutation operations will be represented symbolically as follows: Sm-.-nT will represent the transmission T with no variables permuted Sm...nT will represent the transmission T with the xi and x2 variables interchanged, etc. Thus SunT(xi, x2, x3, x4) = T(xi , x4 , x3, x2) The symbolic notation for the priming operation will be as follows: Noooa-.-oT will represent the transmission T with no variables primed Nom...oT will represent the transmission T with the x2 and x3 variables primed, etc. Thus NmoT(xi , x2, x3, x4) = T(xi, x2, x3', xA). The notation for the priming operator can be shortened by replacing the binary subscript on N by its decimal equivalent. Thus N9T is equiv* This paper is derived from a thesis submitted to the Massachusetts Institute of Technology in partial fulfillment of the requirements for the degree of Doctor of Science on April 30, 1956.