Gateways To Joy
Puzzles

## Three NOT Gates from Two NOT Gates

### Puzzle

Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates.

### Source

Heard from a fellow student at UC Berkeley in 1996.

### Solution

The construction below is more insightful if we work with a general n, instead of n = 3. We will show that n NOT gates are sufficient to invert 2^n - 1 signals. But please keep Philip Martel's comment in mind:

Once you have n = 2 NOT gates generating 2^n-1 = 3 inversions, you do not need any more NOT gates for any number of inversions. The same set of AND and OR gates that is around the two NOT gates can be placed around two of the three inversions, yielding 3 inversions, plus the one inversion that was not used.

This can be done interatively, or once you have 4 inversions, you could apply the set of gates around two pairs of inversions yielding 6 inversions. In any case no more than two NOT gates is required.

Let the input signals be s0, s1, s2, s3, ... We define 3 functions:

Q(k) is simply the OR of all combinations of k signals AND-ed together. For example, with 3 input signals:

Q(0) = 1
Q(1) = s0 +s1 + s2
Q(2) = s0.s1 + s1.s2 + s2.s0
Q(3) = s0.s1.s2.

Thus, for k ∈ [0, 2^n - 1], Q(k) = 1 iff at least k input signals are 1.

R(k, i) is obtained by removing all terms containing the i-th signal from Q(k). For example, for 3 input signals: R(1, 0) = s1 + s2
R(1, 1) = s0 + s2
R(1, 2) = s0 + s1
R(2, 0) = s1.s2
R(2, 1) = s2.s0
R(2, 2) = s0.s1

Thus, for k ∈ [0, 2^n - 1), i ∈ [0, 2^n - 1), R(k, i) = 1 iff at least k input signals are 1, ignoring the i-th input signal.

Finally, let us define the third function: For k ∈ [0, 2^n - 1], P(k) = 1 iff exactly k input signals are 1. Assuming we manage to construct P's, the inversion of the i-th signal is the expression P(0) + P(1).R(1, i) + P(2).R(2, i) + P(3).R(3, i) + ...

Note that so far, we have not used any NOT gates.

Constructing P's from Q's is the heart of the puzzle — NOT gates are used for doing so. We explain the procedure with an example: we show how to invert seven signals with three NOT gates. Let us "visualize" the Q's by writing them in short-hand as bit-masks: the i-th bit from the left denotes that exactly i signals are on, and concatenation of bits denotes the OR operation.

Our goal is to produce the P's, whose bit-masks are:

00000001
00000010
00000100
00001000
00010000
00100000
01000000
10000000