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).
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.
A bit late, but this is another reason: If you create an algebra over the field $Z/2Z$, with as multiplication AND, then the addition is XOR and $\neg p$ is simply $1 + p$, which uses addition.
It should be obvious that multiplication can’t be defined through addition, which means you can’t form AND with only XOR and NOT.
