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:

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.

© Copyright 2008—2018, Gurmeet Manku.