All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
Triple Negative (Posted on 2004-02-12) Difficulty: 4 of 5
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)

No Solution Yet Submitted by DJ    
Rating: 4.1250 (8 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re: Circuits acrobatics !! (Solution)-- does not scale up. | Comment 12 of 19 |
(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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information