如何证明异或门不构成逻辑门的完全集？

Question

感觉在学习计算机的过程中，碰到位运算大多涉及异或，又碰巧学离散数学提及与非门是完备集。就疑惑异或这么常用，怎么证明不是完备集呢？
刚学计算机，希望捞捞。

Answer 1

别说，这问题确实挺难的🤨证明它是完全集很容易，证明不是又挺难的。
但当然还是有方法的。
通常说单个联结符号构成完全集，就是指可以用 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，与第一行不符。
由此得出矛盾。