Foundations of Combinational Circuits
In this chapter, we define and study combinational circuits. The underlying graph of a combinational circuit is more general than the underlying graph of a Boolean formula. In a formula, the underlying graph is a rooted tree. However, in a combinational circuit, the underlying graph is a directed acyclic graph.
We focus on the representation of Boolean functions by combinational circuits, a representation that is different from tables and formulas. Our goal is to prove two theorems: (i) every Boolean function can be implemented by a combinational circuit and (ii) every combinational circuit implements a Boolean function.
We introduce an efficient algorithm for simulating a combinational ...