AN APPLICATION OF GROUP THEORY TO THE ANALYSIS OF SYMMETRIC GATES
Peter Michael Maurer · 2009
A method for determining the symmetries of the inputs of a logic gate either from its truth table or from facts obtained by inspection of its circuit is presented. The symmetry rule of a gate with n inputs is defined in terms of a subgroup of the symmetric group of degree n. This technique leads to an expanded and more complete definition of partial symmetry than has previously appeared. This definition of symmetry is used to show that the set of boolean expressions that represent non-totally-symmetric functions is NP-complete. The group-theoretic concept of conjugate sets is used to identify symmetry rules that are fundamentally the same but applied to different sets of inputs. A complete analysis of all forms of symmetry for 2-input, 3-input and 4-input gates is provided. An example is given to show how this theory was applied to a problem in VLSI design verification. This paper was originally written in 1985 while I was a member of technical staff at the now defunct Bell Laboratories. Although I had high hopes for a publication, I spent many years attempting to publish this work without success. The theorists considered it too trival, while the practitioners considered it too theoretical. I disagree with both, but I wasn’t able to convince anyone. While it is less sophisticated than any paper I would write today, I believe that the material is worth knowing and not available in any other form. Thus I am releasing this paper as a Baylor Technical Report.