Equivalence classes of boolean functions

Abstract

There are 22ν switching functions on n variables. Even for moderate values of n, this is a large number. To handle this complexity, n-variable switching functions are ivided into classes under a set of selected classification rules. The rules are such that, once a representative function of a class is realized, the transformation to any other function in the class corresponds to modifications that are natural for the chosen technology. To be most useful, the classifications should have as few classes as possible, and the set of rules should be simple. In this chapter, we review a few classifications including the classifications based on manipulation with Boolean expressions (NPN-classification), through LP-classification,SD-classification, and classification byWalsh spectra andWalsh decision diagrams.