Gurmeet.Net
Gurmeet.Net
Puzzles
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.

Bitmask(7) = 00000001 (denotes Q(7))
Bitmask(6) = 00000011 (denotes Q(6))
Bitmask(5) = 00000111 (denotes Q(5))
Bitmask(4) = 00001111 (denotes Q(4))
Bitmask(3) = 00011111 (denotes Q(3))
Bitmask(2) = 00111111 (denotes Q(2))
Bitmask(1) = 01111111 (denotes Q(1))
Bitmask(0) = 11111111 (denotes Q(0))

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

00000001
00000010
00000100
00001000
00010000
00100000
01000000
10000000

Step 1: Complement Bitmask(4) to get 11110000. Then replace Bitmask(3), Bitmask(2), Bitmask(1) and Bitmask(0) by AND-ing them with 11110000 to get:

Bitmask(7) = 00000001
Bitmask(6) = 00000011
Bitmask(5) = 00000111
Bitmask(4) = 00001111
Bitmask(3) = 00010000
Bitmask(2) = 00110000
Bitmask(1) = 01110000
Bitmask(0) = 11110000

Step 2: Complement the expression Bitmask(2) OR Bitmask(6) to get 11001100. Then replace Bitmask(5), Bitmask(4), Bitmask(1) and Bitmask(0) by AND-ing them with 11001100 to get:

Bitmask(7) = 00000001
Bitmask(6) = 00000011
Bitmask(5) = 00000100
Bitmask(4) = 00001100
Bitmask(3) = 00010000
Bitmask(2) = 00110000
Bitmask(1) = 01000000
Bitmask(0) = 11000000

Step 3: Complement the expression Bitmask(1) OR Bitmask(3) OR Bitmask(5) OR Bitmask(7) to get 10101010. Then replace Bitmask(6), Bitmask(4), Bitmask(2) and Bitmask(0) by AND-ing them with 10101010 to get:

Bitmask(7) = 00000001
Bitmask(6) = 00000010
Bitmask(5) = 00000100
Bitmask(4) = 00001000
Bitmask(3) = 00010000
Bitmask(2) = 00100000
Bitmask(1) = 01000000
Bitmask(0) = 10000000

which are exactly the P's that we wanted! One NOT gate was used in each step. The procedure can be generalized for higher powers of two.

The problem was first studied in On Maximum Inversion with Minimum Inverters by S B Akers, IEEE Transactions on Computers, Vol 17, Issue 2, Feb 1968, pages 134-135. A modern writeup is here: An Intriguing Digital Logic Problem: How fundamental is an inverter? by Srinivasan Ramasubramanian, 2007.

There are n+1 processors named 0, 1, ..., n. Processor i has a counter C(i) that takes values in the range [0, n]. Its initial value is arbitrarily chosen from [0, n]. Processor 0 is said to be privileged if C(0) = C(n). Processor i, where i > 0, is said to be privileged if C(i) ≠ C(i-1). At successive clock ticks, exactly one out of possibly several privileged processors is arbitrarily chosen and its counter is updated as follows: If processor 0 is chosen, we set C(0) ← (C(0) + 1) mod (n+1). Otherwise, we set C(i) ← C(i-1). Prove that after a bounded number of clock ticks, exactly one processor will be privileged. And that this will continue to hold forever.

Next Puzzle: Chameleons

On an island live 13 purple, 15 yellow and 17 maroon chameleons. When two chameleons of different colors meet, they both change into the third color. Is there a sequence of pairwise meetings after which all chameleons have the same color?

25 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.