Generalized symmetries in Boolean functions

In this paper we take a fresh look at the notion of symmetries in Boolean functions. Our studies are motivated by the fact that the classical characterization of symmetries based on invariance under variable swaps is a special case of a more general invariance based on unrestricted variable permutations. We propose a generalization of classical symmetry that allows for the simultaneous swap of ordered and unordered groups of variables, and show that it captures more of a function's invariant permutations without undue computational requirements. We apply the new symmetry definition to analyze a large set of benchmark circuits and provide extensive data showing the existence of substantial symmetries in those circuits. Specific case studies of several of these benchmarks reveal additional insights about their functional structure and how it might be related to their circuit structure.