Enumeration of Fanout-Free Boolean Functions

Publisher Website
Google Scholar
Abstract
A solution to the problem of counting the number of fanout-free Boolean functions of n variables is presented. The relevant properties of fanout-free functions and circuits are summarized. The AND and OR ranks of a fanout-free function are defined. Recursive formulas for determining the number of distinct functions of specified rank are derived. Based on these, expressions are obtained for @@@@ D ( n ), @@@@ ND ( n ), and @@@@( n ), which denote the number of degenerate, nondegenerate, and all n -variable fanout-free functions, respectively. Simple nonrecursive bounds on the various @@@@ functions are also computed and are used to determine some asymptotic properties of the @@@@ functions. It is shown that for large n almost all fanout-free functions are nondegenerate, and that almost all unate functions are not fanout-free. The relationship between the fanout-free function enumeration problem and other function enumeration problems in switching theory is discussed.

This publication has 7 references indexed in Scilit: