How to create AND with XOR and NOT

1.3k Views Asked by At

I can only create XOR and NOT gates, can I use them to create an AND gate?

I was expecting this to be easy to find, but I was unable to do so. I´m quite unsure of what the answer might be, since unlike AND and OR gates, XOR has no output that is generated by only one input (true is returned for both 1+0 and 0+1, while falste for 1+1 and 0+0).

1

There are 1 best solutions below

0
On BEST ANSWER

It's not possible. If you look at the truth table for $p\land q$, it has an odd number of $1$'s (three, to be precise). We can inductively show that any combination of NOT and XOR produces a column with an even number of $1$'s.

Certainly, this holds for the expression $p$ and the expression $q$. Further, say we have some expression $\varphi$ which has an even number of $1$'s on a truth table. Then so do $p \oplus \varphi, q\oplus \varphi$, and $\lnot \varphi$. The latter case should be clear, convince yourself of the first two.