Making Three NOT Gates from Two

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