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.)
Hints/Tips Inverting seven inputs with three inverters Comment 19 of 19 |

Let A,B,C,D,E,F,G be the seven independent inputs to invert.
The standard convention of AND taking higher precedence over OR will be used.

Also, define function J(n,{list of booleans}) to return true if at least n elements in the boolean list are true.  For any specific number n and boolean list, the boolean equivalent to J can be constructed out of AND and OR gates.  For example J(2,{A,B,C,D,E}) = A and B or A and C or A and D or A and E or B and C or B and D or B and E or C and D or C and E or D and E.  Note that J(1,{list}) is all the members of the list OR'ed together and J(n,{list of size n}) is all the members of the list AND'ed together.

Then make the following calculations:
T4567 = J(4,{A,B,C,D,E,F,G})
T0123 = NOT T4567

T67 = J(6,{A,B,C,D,E,F,G})
T23 = T0123 AND J(2,{A,B,C,D,E,F,G})
T0145 = NOT (T23 AND T67)
T01 = T0123 AND T0145
T45 = T4567 AND T0145

T7 = J(7,{A,B,C,D,E,F,G})
T5 = T45 AND J(5,{A,B,C,D,E,F,G})
T3 = T23 AND J(3,{A,B,C,D,E,F,G})
T1 = T01 AND J(1,{A,B,C,D,E,F,G})
T0246 = NOT (T1 AND T3 AND T5 AND T7)
T6 = T67 AND T0246
T4 = T45 AND T0246
T2 = T23 AND T0246
T0 = T01 AND T0246

Exactly one of T0, T1, T2, T3, T4, T5, T6, and T7 is true for any true/false combination of {A,B,C,D,E,F,G}.  The number in each T# denotes exactly how many of the variables are true.

Now the inverse of A can be calculated as:
NOT A = T0 OR T1 AND J(1,{B,C,D,E,F,G}) OR T2 AND J(2,{B,C,D,E,F,G}) OR T3 AND J(3,{B,C,D,E,F,G}) OR T4 AND J(4,{B,C,D,E,F,G}) OR T5 AND J(5,{B,C,D,E,F,G}) 0R T6 AND J(6,{B,C,D,E,F,G})
This works because: first at most one of T0-T6 is true; second: any T# term is ANDed with a matching J() term with value 0 if A is true and 1 if A is false.

For completeness, inversions for B-G
NOT B = T0 OR T1 AND J(1,{A,C,D,E,F,G}) OR T2 AND J(2,{A,C,D,E,F,G}) OR T3 AND J(3,{A,C,D,E,F,G}) OR T4 AND J(4,{A,C,D,E,F,G}) OR T5 AND J(5,{A,C,D,E,F,G}) 0R T6 AND J(6,{A,C,D,E,F,G})
NOT C = T0 OR T1 AND J(1,{A,B,D,E,F,G}) OR T2 AND J(2,{A,B,D,E,F,G}) OR T3 AND J(3,{A,B,D,E,F,G}) OR T4 AND J(4,{A,B,D,E,F,G}) OR T5 AND J(5,{A,B,D,E,F,G}) 0R T6 AND J(6,{A,B,D,E,F,G})
NOT D = T0 OR T1 AND J(1,{A,B,C,E,F,G}) OR T2 AND J(2,{A,B,C,E,F,G}) OR T3 AND J(3,{A,B,C,E,F,G}) OR T4 AND J(4,{A,B,C,E,F,G}) OR T5 AND J(5,{A,B,C,E,F,G}) 0R T6 AND J(6,{A,B,C,E,F,G})
NOT E = T0 OR T1 AND J(1,{A,B,C,D,F,G}) OR T2 AND J(2,{A,B,C,D,F,G}) OR T3 AND J(3,{A,B,C,D,F,G}) OR T4 AND J(4,{A,B,C,D,F,G}) OR T5 AND J(5,{A,B,C,D,F,G}) 0R T6 AND J(6,{A,B,C,D,F,G})
NOT F = T0 OR T1 AND J(1,{A,B,C,D,E,G}) OR T2 AND J(2,{A,B,C,D,E,G}) OR T3 AND J(3,{A,B,C,D,E,G}) OR T4 AND J(4,{A,B,C,D,E,G}) OR T5 AND J(5,{A,B,C,D,E,G}) 0R T6 AND J(6,{A,B,C,D,E,G})
NOT G = T0 OR T1 AND J(1,{A,B,C,D,E,F}) OR T2 AND J(2,{A,B,C,D,E,F}) OR T3 AND J(3,{A,B,C,D,E,F}) OR T4 AND J(4,{A,B,C,D,E,F}) OR T5 AND J(5,{A,B,C,D,E,F}) 0R T6 AND J(6,{A,B,C,D,E,F})

  Posted by Brian Smith on 2013-10-26 11:47:17
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information