Enumeration of Fanout-Free Boolean Functions

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.

REFERENCES

• 1: ARMSTRONG, D B On finding a nearly minimal set of fault detection tests for combinational logic nets. IEEE Trans Electrontc Computers EC-15 (Feb 1966), 66-73
• 2: BUTLER, J T On the number of functions reahzed by cascades and disjunctive networks. IEEE Trans. Computers C-24 (July 1975), 681-690
• 3: GILBERT, E N Lattice theoretic properties of frontal switching functions J Math. and Physzcs 33 (1954), 57-67
• 4: GRAHAM, R L A mathematical study of a model of magnetic domain interactions Bell Sys, Tech J 49 (Oct 1970), 1627-1644
• 5: HART, C M , AND SLOB, A Integrated mlect~on logic (PL) Ph:ltps Tech Rev 33 (Feb 1973), 76-85
• 6: HAVES, J P Minimization of fanout m switching networks Proc 15th Symp Switching and Automata Theory, New Orleans, 1974, pp 133-139
• 7: John P. Hayes, The Fanout Structure of Switching Functions, Journal of the ACM (JACM), v.22 n.4, p.551-571, Oct. 1975 [doi>10.1145/321906.321918]
• 8: HAVES, J P A NAND model for fault d~agnds~s m combinational logic networks IEEE Trans Computers C-20 (Dec 1971), 1496-1506
• 9: MINNICK, R C, ET AL. Magnetic bubble computer systems. Proc AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N J , pp 1279-1298
• 10: MUROGA, S , TSUBOI, T, AND BAUGH, C R Enumeration of threshold functions of eight variables IEEE Trans Computers C-19 (Sept 1970), 818-825
• 11: MUROGA, S Threshold Log:c and tts Apphcattons Wdey, New York, 1971
• 12: SH^NrqON, C E The synthesis of two-terminal switching c~rcmts Bell Sys Tech J 28 (Jan 1949), 59- 98
• 13: SKLANSKY, J , KORENJAK, A J,, aND STONE, H S Canomcal tributary networks, IEEE Trans Electrontc Computers EC-14 (Dec 1965), 961-963
• 14: WARD, M Note on the order of the free d~stnbut~ve lattice (abstract) Bull Amer. Math Soc 52 (May 1946), 423

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Measurement, Performance, Theory, Verification