Circuit with 2 not gates

1. Apr 30, 2010

implet

Hi,

1. The problem statement, all variables and given/known data
You are trying to design a circuit with 3 inputs and 3 outputs. The circuit should negate each of its inputs. e.g. A-> not A, B-> not B, C-> not C. Clearly we can do this using 3 'not' gate. Is it possible to do this using 2 'not' gates and an unlimited number of 'and' and 'or' gates?

2. Relevant equations
None I know of.

3. The attempt at a solution
I'm not sure whether this is true.
To prove it's true: Find a circuit. I've tried many with no success.
To prove it's false: Use an information based argument? Use properties of the different gates?

Thanks :)

P.S. This is an OCW question from 6.080

2. Apr 30, 2010

story645

3. Apr 30, 2010

willem2

try to make a two bit signal that represents the number of 1 bits in the 3 inputs.
these are the two bits you have to invert.

the high bit of this is easy, that is a 3-way majority circuit.

you can use the inverted high bit to compute the low bit.

Once you have that, you can make a decoder that produces 4 outputs
that are 1 if 0,1,2 or 3 of the input bits are equal to 1.

finally to calculate a' you can comtine the cases for 0,1 and 2 1-bits in the input.

if there are 0 1-bits in the input then a must be 0, so a' = 1
if there is 1 1-bit in the input then a is 0 if b and c are 1.
if there are 2 1-bits in the input then ................

and then you can do the same for b' and c'

Finally. What is the problem you run into, if you try to embed this circuit in to another copy of it to get more than 2 nots from 2 not gates?