SYMMETRIC FANOUT-FREE FUNCTIONS

Abstract

We show that symmetric Boolean fanout-free functions or cascade functions realizable by networks of AND's, OR's and inverters are only the functions 0,1 x//1x//2. . . x//n, x//1 plus x//2 plus . . . plus x//n, x OVER BAR //1x OVER BAR //2. . . x OVER BAR //n, x OVER BAR //1 plus x OVER BAR //2 plus . . . plus x OVER BAR //n(n greater than equivalent to 1). If we add exclusive OR gates as the elements of the networks, only the functions x//1 DIR SUM x//2 DIR SUM . . . DIR SUM x//n and x//1 DIR SUM x//2 DIR SUM . . . DIR SUM x//n plus 1 are realizable in addition to the above functions.