Can a Circuit with 2 Not Gates Negate 3 Inputs?

[implet]

Hi,

Homework Statement

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?

Homework Equations

None I know of.

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

 

[story645]

Someone previously asked the same question on this forum: link

 

[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 into another copy of it to get more than 2 nots from 2 not gates?