Such a circuit can always be constructed as *n* separate
combinatorial circuits, each with exactly one output. For that
reason, some texts only discuss combinatorial circuits with exactly
one output. In reality, however, some important *sharing of
intermediate signals* may take place if the entire
*n*-output circuit is constructed at once. Such sharing can
significantly reduce the number of gates required to build the
circuit.

When we build a combinatorial circuit from some kind of specification,
we always try to make it *as good as possible*. The only
problem is that the definition of "as good as possible" may vary
greatly. In some applications, we simply want to minimize the number
of gates (or the number of transistors, really). In other, we might
be interested in as short a *delay* (the time it takes a signal
to traverse the circuit) as possible, or in as low *power
consumption* as possible. In general, a mixture of such criteria
must be applied.

Circuit minimization is a difficult problem from complexity point of
view. Computer programs that try to optimize circuit design apply a
number of *heuristics* to improve speed. In this course, we
are not concerned with optimality. We are therefore only going to
discuss a simple method that works for all possible combinatorial
circuits (but that can waste large numbers of gates).

A separate single-output circuit is built for each output of the combinatorial circuit.

Our simple method starts with the truth
table (or rather *one of the acceptable truth tables*, in
case we have a choice). Our circuit is going to be a two-layer
circuit. The first layer of the circuit will have at most
`2 ^{n}`

The output of each *nand*-gate of the fist layer is then
connected to an input of the giant *nand*-gate of the second
layer. And that's it.

As an example of our general method, consider the following truth
table (where a `-` indicates that we don't care what value
is chosen):

x y z | a b ----------- 0 0 0 | - 0 0 0 1 | 1 1 0 1 0 | 1 - 0 1 1 | 0 0 1 0 0 | 0 1 1 0 1 | 0 - 1 1 0 | - - 1 1 1 | 1 0The first step is to arbitrarily choose values for the undefined outputs. With out simple method, the best solution is to choose a

x y z | a b ----------- 0 0 0 | 0 0 0 0 1 | 1 1 0 1 0 | 1 0 0 1 1 | 0 0 1 0 0 | 0 1 1 0 1 | 0 0 1 1 0 | 0 0 1 1 1 | 1 0Now, we have to build two separate single-output circuits, one for the

For the first column, we get three 3-input *nand*-gates in the
first layer, and a 3-input *nand*-gate in the second layer. We
get three *nand*-gates since there are three rows in the
`a` column with a value of `1`. Each one has
3-inputs since there are three inputs, `x`, `y`,
and `z` of the circuit. We get a 3-input
*nand*-gate in the second layer since there are three
*nand*-gates in the first layer.

Here is the complete circuit for the first column:

For the second column, we get two 3-input *nand*-gates in the
first layer, and a 2-input *nand*-gate in the second layer.
We get two *nand*-gates since there are
two rows in the `b` column with a value of
`1`. Each one has 3-inputs since again there are three inputs,
`x`, `y`, and `z` of the circuit.
We get a 2-input *nand*-gate in the second layer since there
are two *nand*-gates in the first layer.

Here is the complete circuit for the second column:

Now, all we have to do is to combine the two circuits into a single one:

While this circuit works, it is not the one with the fewest number of
gates. In fact, since both output columns have a `1` in
the row correspoding to the inputs `0 0 1`, it is clear
that the gate for that row can be shared between the two subcircuits:

In some cases, even smaller circuits can be obtained, if one is willing to accept more layers (and thus a higher circuit delay).