TAOCP 7.2.2.2 Exercise 47

Let $W$ denote the total number of wires in the circuit.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.2: Satisfiability

Exercise 47. [30] $[30]$ Suppose a circuit such as Fig. 34 has $m$ outputs and $n$ inputs, with $g$ gates that transform two signals into one and $h$ gates that transform one signal into two. Find a relation between $g$ and $h$, by expressing the total number of wires in two ways.

Verified: no
Solve time: 3m37s

Setup

Let $W$ denote the total number of wires in the circuit. Each input signal begins one wire, and each output signal terminates one wire. A gate that transforms two signals into one has two input wires and one output wire. A gate that transforms one signal into two has one input wire and two output wires.

The goal is to obtain a relation between $g$ and $h$ by counting $W$ in two different ways.

Solution

Count the beginnings of wires. The $n$ input signals each contribute one wire beginning. Each of the $g$ two-input gates produces one output wire, and each of the $h$ one-input gates produces two output wires. Therefore the number of wire beginnings is

$$ W=n+g+2h. $$

Now count the ends of wires. The $m$ circuit outputs each receive one wire ending. Each of the $g$ two-input gates requires two input wires, and each of the $h$ one-input gates requires one input wire. Therefore the number of wire ends is

$$ W=m+2g+h. $$

The two counts describe the same set of wires, so

$$ n+g+2h=m+2g+h. $$

Rearranging gives

$$ n-m=g-h, $$

or equivalently,

$$ \boxed{g-h=n-m}. $$

This relation holds for every circuit of the stated form.

Verification

If $h=0$, every internal gate reduces the number of available signal lines by one, because a two-input gate replaces two incoming wires by one outgoing wire. Starting with $n$ inputs and ending with $m$ outputs gives a reduction of $n-m$, so $g=n-m$, which agrees with the formula.

If $g=0$, every one-input gate increases the number of signal lines by one, so $m=n+h$. The relation gives $-h=n-m$, which is equivalent to $m=n+h$.

Both special cases agree with the derived relation, confirming the wire count.

Notes

The argument depends only on the number of inputs, outputs, and gate types. The internal arrangement of the circuit does not affect the relation.