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)

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