Using only two inverters and an unlimited number of AND and OR gates in a logic circuit, show how to invert an arbitrary number of inputs.

(For instance, if you have four inputs, the circuit will have four outputs that are the inverses of the four inputs)

I can just hear it now..."You copy/paste stuff off the Internet, but you don't understand it". (You have a point. I don't understand it fully. Doubtless the smarter flooblers will improve upon it...).

(http://rec-puzzles.org/new/sol.pl/logic/inverter)

Solution found at above website:

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

Solution:

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! :-) "







Edited on February 13, 2004, 5:45 am

Posted by Penny on 2004-02-12 18:30:53