2

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

Valent
  • 3,228
  • 1
  • 15
  • 28
Turbo
  • 6,221
  • 2
    HINT do an inductive proof to show that if you create the truth-table for any function created from XOR, 0, and 1 alone, and involving at least two variables, then you will find that the function will always be true in an even number of cases. – Bram28 Nov 02 '18 at 03:24
  • @Bram28 I see that but how will you make a formal case? – Turbo Nov 02 '18 at 04:53
  • See https://math.stackexchange.com/questions/2340622/prove-a-set-is-not-a-complete-set-of-connectives/2341090#2341090 – Bram28 Nov 02 '18 at 19:38

2 Answers2

1

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.

awCwa
  • 483
  • 3
  • 7
  • 1
    Nice idea, but it's not yet complete. The problem is that the mere fact than an AND gate is of degree two is not enough to conclude that it is not equal-as-a-function to the expression for XOR of degree one. (E.g., $X_1^2$ is not equal to $X_1$, but they are equal considered as functions). – Magdiragdag Jan 11 '23 at 07:12
  • 1
    @Magdiragdag Agreed, f+1 or f will be linear, neither AND+1 nor AND is linear, so xor along with 0 or 1 isn't universal. – awCwa Jan 12 '23 at 09:14
0

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.

qwr
  • 10,716