感觉在学习计算机的过程中，碰到位运算大多涉及异或，又碰巧学离散数学提及与非门是完备集。就疑惑异或这么常用，怎么证明不是完备集呢？
刚学计算机，希望捞捞。
别说，这问题确实挺难的🤨证明它是完全集很容易，证明不是又挺难的。
但当然还是有方法的。
通常说单个联结符号构成完全集，就是指可以用 x,y,1,0 的若干次该联结运算的累积，表示任意的基本逻辑符号。
我们尝试用 XOR 表示 AND。
注意到 x XOR y 同余 x + y (mod 2)，所以
x AND y 同余 ax+by+c×1+d×0 (mod 2) 同余 ax+by+c (mod 2).
我们根据将所有可能的取值代入：
| x | y | AND 值 | 异或值 |
|---|---|---|---|
| 1 | 1 | 1 | a+b+c (mod2) |
| 1 | 0 | 0 | a+c (mod 2) |
| 0 | 1 | 0 | b+c (mod 2) |
| 0 | 0 | 0 | c (mod 2) |
令 第二行 + 第三行 - 第四行，我们得到异或值为 a+b+c (mod 2)，但是 AND 值却是 0，与第一行不符。
由此得出矛盾。