- 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:
- 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.