# 333 logic/inverter.p

Can a digital logic circuit with two inverters invert N independent inputs?
The circuit may contain any number of AND or OR gates.

logic/inverter.s

It can be shown that N inverters can invert 2^N-1 independent inputs,
given an unlimited supply of AND and OR gates. The classic version of
this puzzle is to invert 3 independent inputs using AND gates, OR
gates, and only 2 inverters.

This is solved by:

```        n1 = not(i1 and i2 or i1 and i3 or i2 and i3);
n2 = not((i1 or i2 or i3) and n1  or  i1 and i2 and i3);
o1 = (i2 or i3 or n2) and n1  or  i2 and i3 and n2;
o2 = (i1 or i3 or n2) and n1  or  i1 and i3 and n2;
o3 = (i1 or i2 or n2) and n1  or  i1 and i2 and n2;
```

i1, i2, and i3 are the inputs, n1 and n2 are the inverted signals, and
o1, o2, and o3 are the outputs. "and" has higher precedence than "or".

Keep doing that until you're down to 2 inverters.

I was skeptical at first, because such a design requires so much feedback
that I was sure the system would oscillate when switching between two
particular states. But after writing a program to test every possible state
change (32^2), it appears that this system settles after a maximum of
3 feedback logic iterations. I did not include gate delays in the simulation,
however, which could increase the number of iterations before the system
settles.

In any case, it appears that the world needs only 2 inverters! :-)

Continue to: