Consider the problem of designing a circuit that computes the OR of n bits. A natural approach for solving this problem is to partition the bits into pairs, compute the OR of each pair, and continue recursively until we are left with one bit—the result. The underlying graph, or topology, of the combinational circuit we obtain is a rooted tree. Is this the best design? In this chapter, we prove that indeed, this is the case.
We consider this question in a more general setting. First, we define a class of functions for which the preceding problem can be easily formulated. This is the class of associative Boolean functions. Second, we define a combinational circuit with a topology of a rooted tree, all gates of which are ...