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)
(In reply to
Circuits acrobatics !! (Solution) by Penny)
After composing what I show below, I noticed on the original post copied from the internet, that the description says:
"N inverters can invert 2^N-1 independent inputs"
Substitute N=2, and that says that 2 inverters can invert 3 independent inputs. In the below, I was trying to invert 4 independent inputs. According to the quoted source, this is not part of the possibility, though the current puzzle asks us to let 2 inverters work for an arbitrarily large number of bit streams.
The following program works fine as given for three inputs and three outputs:
CLS
FOR i1 = 0 TO -1 STEP -1
FOR i2 = 0 TO -1 STEP -1
FOR i3 = 0 TO -1 STEP -1
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
PRINT i1, i2, i3
PRINT o1, o2, o3
PRINT
NEXT
NEXT
NEXT
The programming language uses -1 for true (on) and 0 for false (off). The results come out fine:
0 0 0
-1 -1 -1
0 0 -1
-1 -1 0
0 -1 0
-1 0 -1
0 -1 -1
-1 0 0
-1 0 0
0 -1 -1
-1 0 -1
0 -1 0
-1 -1 0
0 0 -1
-1 -1 -1
0 0 0
where the input line is above the output line.
In my first attempt to scale this up to four inputs and outputs, I assumed that all possible pairwise ANDed inputs were to be ORed together for negation in n1, and in n2 there'd be an ORing of all the inputs as well as an ANDing:
CLS
FOR i1 = 0 TO -1 STEP -1
FOR i2 = 0 TO -1 STEP -1
FOR i3 = 0 TO -1 STEP -1
FOR i4 = 0 TO -1 STEP -1
n1 = NOT (i1 AND i2 OR i1 AND i3 OR i2 AND i3 OR i1 AND i4 OR i2 AND i4 OR i3 AND i4)
n2 = NOT ((i1 OR i2 OR i3 OR i4) AND n1 OR i1 AND i2 AND i3 AND i4)
o1 = (i2 OR i3 OR i4 OR n2) AND n1 OR i2 AND i3 AND i4 AND n2
o2 = (i1 OR i3 OR i4 OR n2) AND n1 OR i1 AND i3 AND i4 AND n2
o3 = (i1 OR i2 OR i4 OR n2) AND n1 OR i1 AND i2 AND i4 AND n2
o4 = (i1 OR i2 OR i3 OR n2) AND n1 OR i1 AND i2 AND i3 AND n2
PRINT i1, i2, i3, i4
PRINT o1, o2, o3, o4
PRINT
NEXT
NEXT
NEXT
NEXT
This did not work out:
0 0 0 0
-1 -1 -1 -1
0 0 0 -1
-1 -1 -1 0
0 0 -1 0
-1 -1 0 -1
0 0 -1 -1
0 0 0 0 BAD
0 -1 0 0
-1 0 -1 -1
0 -1 0 -1
0 0 0 0 BAD
0 -1 -1 0
0 0 0 0 BAD
0 -1 -1 -1
-1 0 0 0 BAD
-1 0 0 0
0 -1 -1 -1
-1 0 0 -1
0 0 0 0 BAD
-1 0 -1 0
0 0 0 0 BAD
-1 0 -1 -1
0 -1 0 0
-1 -1 0 0
0 0 0 0 BAD
-1 -1 0 -1
0 0 -1 0
-1 -1 -1 0
0 0 0 -1
-1 -1 -1 -1
0 0 0 0
---------
Then I tried putting all the triplets this time in making up n1, rather than pairs, figuring that this might have to scale up with the number of inputs, but this didn't work either:
CLS
FOR i1 = 0 TO -1 STEP -1
FOR i2 = 0 TO -1 STEP -1
FOR i3 = 0 TO -1 STEP -1
FOR i4 = 0 TO -1 STEP -1
n1 = NOT (i1 AND i2 AND i3 OR i1 AND i2 AND i4 OR i1 AND i3 AND i4 OR i2 AND i3 AND i4)
n2 = NOT ((i1 OR i2 OR i3 OR i4) AND n1 OR i1 AND i2 AND i3 AND i4)
o1 = (i2 OR i3 OR i4 OR n2) AND n1 OR i2 AND i3 AND i4 AND n2
o2 = (i1 OR i3 OR i4 OR n2) AND n1 OR i1 AND i3 AND i4 AND n2
o3 = (i1 OR i2 OR i4 OR n2) AND n1 OR i1 AND i2 AND i4 AND n2
o4 = (i1 OR i2 OR i3 OR n2) AND n1 OR i1 AND i2 AND i3 AND n2
PRINT i1, i2, i3, i4
PRINT o1, o2, o3, o4
PRINT
NEXT
NEXT
NEXT
NEXT
0 0 0 0
-1 -1 -1 -1
0 0 0 -1
-1 -1 -1 0
0 0 -1 0
-1 -1 0 -1
0 0 -1 -1
-1 -1 -1 -1
0 -1 0 0
-1 0 -1 -1
0 -1 0 -1
-1 -1 -1 -1
0 -1 -1 0
-1 -1 -1 -1
0 -1 -1 -1
-1 0 0 0
-1 0 0 0
0 -1 -1 -1
-1 0 0 -1
-1 -1 -1 -1
-1 0 -1 0
-1 -1 -1 -1
-1 0 -1 -1
0 -1 0 0
-1 -1 0 0
-1 -1 -1 -1
-1 -1 0 -1
0 0 -1 0
-1 -1 -1 0
0 0 0 -1
-1 -1 -1 -1
0 0 0 0
-------
So we still lack a general way of doing this for more than three inputs/outputs.
Edited on February 13, 2004, 11:26 am
|
|
Posted by Charlie
on 2004-02-13 11:21:31 |
re: Circuits acrobatics !! (Solution)-- does not scale up.
