IBM Research | Ponder This | August 2009 solutions
Skip to main content

August 2009

<<July August September>>

The way to compute three inverters with only two is to first compute the majority function:
maj(a,b,c) = (a AND b) or (a AND c) or (b AND c);

then compute the xor function using the first NOT:
xor(a,b,c) = (a AND b AND c) or (NOT(maj(a,b,c)) AND (a OR b OR c));

and lastly we can compute NOT(a) without additional NOT gates by multiplexing on the two computed functions maj and xor (shorthand for maj(a,b,c) and xor(a,b,c) respectively):
NOT(a) = (NOT(maj) AND NOT(xor)) OR (NOT(maj) AND xor AND (b OR c)) OR (maj AND NOT(xor) AND b AND c); and similarly compute the other two NOT(b) and NOT(c).

After some optimization this can all fit into 23 gates:

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: