# Can I get the NOT of 3 inputs using as many and/or gates but only 2 NOT gates?

Came across this question in an online course. I think it belongs to electronics and logic alike.

EDIT: To clarify, if I have A, B, C as inputs, I need ~A, ~B, ~C as outputs, separately.

EDIT-2: So what I did was constructing a XOR off the inputs A and B. When either one of them is set as 1, then the other one is automatically reversed. But won't be able to get simultaneous results.

• What do you mean by "the NOT of 3 inputs"? NOT is a unary operation, so for 3 inputs you would have three outputs. Jan 31 '14 at 11:50
• Which reduces the question to "can you get the NOT of a signal using only AND and OR gates?". The answer is NO. Jan 31 '14 at 11:56
• @WoutervanOoijen: Are you sure? A reference somewhere to confirm this would be nice. I just imagine that if you connect all the combination of the 3 inputs to both a AND and OR gate that maybe there could be a unique pattern? Which also can be combined with logic further to give the ~A, ~B and ~C? Jan 31 '14 at 16:56
• @Phataas: Proof is simple. First: if it were possible with AND it would be possible with OR and vice versa. Hence we need to investigate only one. Proof up to you. (Hint: AND for positive logic is a OR for negative logic.) Now look at the truth table for AND. There is no line that produces the inverse of one input when the other input is held constant. QED. Jan 31 '14 at 21:16
• @WoutervanOoijen: It is possible using N inverters along with a combination of AND and OR gates to build a combinatorial circuit with (2^N)-1 inputs and (2^N)-1 outputs whose steady-state condition will have each output show the inverse of the state of a corresponding input. Your attempted reduction to show it's impossible is fallacious, since it presumes that an ability to "simulate" three inverters using two should imply the possibility of simulating two with one or one with none. Jan 31 '14 at 23:11

It is possible to construct a purely-combinatorial three-input circuit consisting of a number of AND and OR gates along with exactly two independent inverters, with three outputs whose steady-state condition will be the inverse of the inputs. Note that the input to the second inverter will be affected by the output from the first, and that all three outputs are affected by the signals from both inverters. Consequently, one cannot use two of the inputs and outputs of one such circuit to serve as the "inverters" for another.

Assume the inputs are A, B, C and the outputs are X,Y, Z. Using AND and OR gates, determine whether at least two of the inputs are high. Invert that to get a signal which would indicate that at least two are low. Feeding that signal along with the original signals into AND and OR gates, generate a signal which would indicate that an odd number of inputs are high. Invert that to get a signal saying that an odd number are low.

Once one has generated the aforementioned signals, output X should be high if either all three inputs are low (both inverters outputting true), at least two are low and either B or C is true (which would imply that A must be false), or at least one is low and both B and C are true. Outputs Y and Z should be computed similarly.

The principle can be extended to produce a seven I/O combinatorial circuit using three independent inverters and a lot of AND/OR gates. First determine if there are four or more inputs high. Invert that to say there are four or more low. Then determine if the number is 2, 3, 6, or 7. Invert that to say there are 0, 1, 4, or 5. Then determine if the number is odd, and invert it to say it's even.

After having done all that, each output Q should be high if all three inverters output high (all seven inputs low), or if the first two inverters are high and at least one input not associated with Q is high, or the first and last inverters are high and at least two inputs not associated with Q are high, or the first inverter is high and at least three inputs not associated with Q are high, or at the second and third inverters are high and at least four inputs not associated with Q are high, or the second inverter is high and at least five inputs not associated with Q are high, or the first inverter is high and all six inputs not associated with Q are high.

Theoretically, one could design a circuit for 15 I/O's using four inverters, or 31 using five, or 63 using six, etc. but the number of AND and OR gates required would be mind-blowing.

I wanted to post this as a comment, but don't have enough reputation. Here is a solution, found here (EE Times)

R    = (A & B) | (A & C) | (B & C)
notR = !R
S    = (notR & (A | B | C)) | (A & B & C)
notS = !S
------------------------------------------
notA = (notR & notS) | (notR & S & (B | C)) | (R & notS & (B & C))
notB = (notR & notS) | (notR & S & (A | C)) | (R & notS & (A & C))
notC = (notR & notS) | (notR & S & (A | B)) | (R & notS & (A & B))


Edit: I tried it out in matlab to be sure:

A   B   C    R   S   !A  !B  !C
0 | 0 | 0 || 0 | 0 || 1 | 1 | 1
0 | 0 | 1 || 0 | 1 || 1 | 1 | 0
0 | 1 | 0 || 0 | 1 || 1 | 0 | 1
0 | 1 | 1 || 1 | 0 || 1 | 0 | 0
1 | 0 | 0 || 0 | 1 || 0 | 1 | 1
1 | 0 | 1 || 1 | 0 || 0 | 1 | 0
1 | 1 | 0 || 1 | 0 || 0 | 0 | 1
1 | 1 | 1 || 1 | 1 || 0 | 0 | 0


I do not have enough reputation to comment under Ryan Johnson's answer. Basically, I found a redundancy in Ryan's answer. The solution can be simplified as:

R    = (A & B) | (A & C) | (B & C)
notR = !R
S    = (notR & (A | B | C)) | (A & B & C)
notS = !S
------------------------------------------
notA = (notR & notS) | (notR & S & (B | C)) | (notS & (B & C))
notB = (notR & notS) | (notR & S & (A | C)) | (notS & (A & C))
notC = (notR & notS) | (notR & S & (A | B)) | (notS & (A & B))