Lesson 1

A truth table specifies what a Boolean function does, but not how to compute it. The exact synthesis problem asks for a smallest circuit computing a given truth table. We use gates of fan-in two. A gate may compute any Boolean function of its two inputs, described by four bits \[b_{00}b_{01}b_{10}b_{11}.\] The bit \(b_{uv}\) is the output when the first input is \(u\) and the second is \(v\). Thus, \(\texttt{0001}\), \(\texttt{0111}\), and \(\texttt{0110}\) describe AND, OR, and XOR, respectively.

Inputs and earlier gates may be reused without cost. This sharing is what distinguishes circuits from formulas and makes exact synthesis interesting.