Logic Gate Puzzle

[Itu]

So, I came accross this puzzle about logic gates, and I've been trying for a while without success.

• Can you compute the NOT’s of 3 input variables, using as many AND/OR gates as you like but only 2 NOT gates?

In other words, from an input of 3 boolean variables X, Y, and Z, you need to output NOTX, NOTY and NOTZ using only 2 NOT gates and as many AND/OR gates as you like. No IFs or any other gate.

The normal rules apply for the logic gates, sorry if this is redundant:

• AND takes 2 or more inputs, and it will output TRUE (or 1) iff all inputs are TRUE (or 1).
• OR takes 2 or more inputs, and it will output FALSE (or 0) iff all inputs are FALSE (or 0).
• NOT takes 1 input, and it will output FALSE (or 0) if the input is TRUE (or 1) and TRUE (or 1) if the input is FALSE(or 0).

Here's what I have so far:

Spoiler:

• You can see this as truth tables. For example, for Y, you need 1 for 000,001,100,101 and 0 for 111,110,011,010. I write this as needing 1111,0000.
• NOT[(XANDY)OR(YANDZ)OR(ZANDX)] seems very useful. It will output 1110,0001 for X, Y or Z.
• You can combine these outputs as if they were binary numbers, and AND and OR as bitwise operators.
• Or, you can take them as sets, 1 means they have that element and 0 that they don't. You can use union and intersection.
• These binary numbers or sets can be built from any logic gates applied to all the 8 possibilities.

[Tirian]

http://www.azillionmonkeys.com/qed/hints.html

[mfb]

A different hint:

Spoiler:

Construct variables which are invariant under an exchange of the inputs. They can be used for all 3 outputs.

[taggedjc]

As far as I can tell, this is not possible.

First, looking at X.

X AND P
If X is 1, then P
If X is 0, then 0

X OR P
If X is 1, then 1
If X is 0, then P

In both cases, the result is either not what we want (ie is X) or is dependant on some other structure (P).

P can only be made up of AND/OR gates as well. In addition, since we want the output to actually depend on X, P would have to include X as well. And as shown, each of the options available don't work if you include X as one of the inputs.

You need NOT in order to change this:
NOT X
If X is 1, then 0
If X is 0, then 1

This obviously just gives you what you need right away. But you can only do two of these total, so you can only tweak up to two variables, not all three.

I'm not sure if there's a way I could better formalize this, haha.



Although, looking at that first link, it looks like it is actually possible? I'll have to look at it closer to figure out why. Maybe not five minutes before bed

[mfb]

It is possible, and I have a solution. Therefore, your argument is flawed.
While the final outputs are made out of OR gates, the corresponding inputs are not directly connected to these OR gates, but hidden behind one or two NOT gates.

Spoiler:

My final output for not A looks like this: (L AND NOT P) OR (B AND C AND NOT P) OR (P AND L AND (B OR C)) - where L and P are some functions symmetric between A,B,C. Therefore, the two NOT gates required to get (L, P and NOT P) are sufficient.