This is a hard puzzle about using two NOT gates to build three.

Making Three NOT Gates from Two

Here is an old and interesting logic puzzle.

Background

Recall an AND gate takes in two inputs A and B, and has one output X. The truth table looks like

A AND B	0	1
0	0	0
1	0	1

Similarly, OR looks like

A OR B	0	1
0	0	1
1	1	1

And NOT simply inverts its input:

A	NOT A
0	1
1	0

Level 1

Design a circuit using AND gates, OR gates, and at most TWO NOT gates, that inverts three inputs.

Level 2

For each positive integer N, design a circuit using AND gates, OR gates, and at most two NOT gates, that inverts N inputs. Note the circuit may be different for different values of N (but you can make one circuit that inverts any number of inputs for

Solution

Here is a solution, there are many.

Level 1

Let the inputs be A,B,C, and we want outputs NOT A, NOT B, NOT C. Write AB for A AND B, and A + B for A OR B (common uses). Then:

X = NOT (AB + BC + CA) Y = NOT (XA + XB + XC)

This uses up the two NOT gates we’re allowed.

Then you can check

NOT A = X(Y+B+C) + YBC NOT B = X(Y+C+A) + YCA NOT C = X(Y+A+B) + YAB

Giving three inverted values.

If you don’t know how to check this is true, a simple way is to make the entire truth table (best automated, but doing it by hand is instructive if you’ve never done such a thing).

Level 2

Surprisingly, this is easier than level 1 (once level 1 is solved).

Fix a positive integer N. Using level 1, take three values, and invert them using two NOT gates. Now you effectively have 3 NOT gates to work with. Use one to invert one input, and use the remaining two to invert three more using the construction in level 1. Repeat as desired until all N are inverted.