Simple proof $XOR$ with $0,1$ is not universal

Question

$XOR(x,y)=x'y+xy'$ and so $XOR(x,1)=x'=NOT(x)$. Howver $XOR$ cannot create $AND(x,y)$. Is there simple proof of this? We are allowed $XOR$ gate and $0,1$ constants.

Answer 1

Observe $XNOR(x,y) = XOR(x',y) = XOR(x,y') = XOR(x,y)'$ and $XOR(x,y) = XOR(x',y')$ so this greatly limits your options of what can be produced.

Answer 2

Note:

1. Every boolean function has CNF(conjumctive normal form) form as well as an ANF(algenraic normal form).

2. ANF form is nothing but expressing n- input boolean function as n variable boolean polynomial.

3. In the ANF form, addition corresponds to XOR and multiplication corresponds to AND.

Now consider any n- input boolean function f formed by using XOR gates and 0, 1, so this function f looks like $f(X_{1}, \cdots, X_{n}) = \sum_{i = 1}^{t} b_{i}Y_{i}$, where $Y_{i} \in \{ X_{j}\}_{j=1}^{n} \cup \{0, 1\}$ and $b_{i} \in \{0, 1\}$. Since addition is associative and commutative, so $f(X_{1}, \cdots, X_{n}) =\sum_{i=1}^{n} a_{i} X_{i}+ c$, for some $a_{i}$ and c. So any boolean function formed by only xor gates and 0 and 1 is a degree 1 polynomial. So for any such $f$, either $f+1$ or $f$ will be a linear function.

But neither AND+1 nor AND is a linear function. So we can't get AND gate using XOR gates and $0$ and $1$.

Thus XOR gate along with $0$ and $1$ is not universal.