333 logic/inverter.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
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".
So, start with N inverters. Replace 3 of them with 2.
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:
My Books
