异或

异或通常缩写为 XOR，是逻辑学中的一种二元运算：当两个输入的真值不同时，结果为真；当真值相同时，结果为假。若用 0 表示假、1 表示真，则仅当一个输入为 1、另一个输入不为 1 时，异或的结果才为 1。它不同于相容或，后者在两个输入都为真时也返回真。异或将逻辑推理与二进制计算及代数联系起来。(xlinux.nist.gov)

逻辑定义

在命题逻辑中，异或通常写作 $p\oplus q$。其真值表如下：

因此，异或是对布尔值进行的“不相等”运算。(xlinux.nist.gov)

利用布尔代数的标准运算，可以将其定义表示为

等价地，它也可以写作 $(p\land\neg q)\lor(\neg p\land q)$：要么只有第一个命题为真，要么只有第二个命题为真。逐一检查真值表的四行即可直接得到这些公式。异或的否定通常称为同或（XNOR），当两个输入相同时，其结果为真。(xlinux.nist.gov)

排他或与相容或的区别在于是否允许两个输入同时为真。例如，在两个选项之间进行排他选择时，可以单独选择其中任意一个，但不能同时选择两个。该运算本身只规定真值条件，并不要求输入之间存在任何时间先后顺序或因果关系。(xlinux.nist.gov)

代数结构

异或具有四项基本性质：

因此，异或满足交换律和结合律，以 0 为单位元，且每个元素都是自身的逆元。用群论的术语来说，两个布尔值在异或运算下构成一个阿贝尔群。对于等长比特串，逐位异或也满足这些性质。(web.stanford.edu)

由此，消去性质给出

这解释了为什么连续两次施加相同的异或变换会恢复原值。单个比特与 1 异或会取反，与 0 异或则保持不变。(web.stanford.edu)

对于比特 $a,b$，异或就是模算术中的加法：

将与运算作为乘法时，这两种运算就构成了二元有限域 $\mathbb F_2$ 的算术运算。因此，长度为 $n$ 的比特串可以视为向量空间 $\mathbb F_2^n$ 中的元素，异或则对应向量加法。这种代数解释是二进制编码和网络编码计算的基础。(doi.org)

结合律使得连续进行异或运算时无需指定括号。仅当输入中有奇数个 1 时，结果才为 1，因为每一对 1 都会相互抵消。需要注意，对于三个或更多输入，这并不意味着“恰有一个输入为真”。例如，$1\oplus1\oplus1=1$。这种奇数奇偶性特征是该二元运算的恒等式所决定的。(web.stanford.edu)

与集合的联系

在集合论中，异或对应于对称差：

一个元素属于 $A\triangle B$，当且仅当它属于其中一个集合，但不同时属于两个集合。与普通的并集不同，这种运算排除了两个集合的重叠部分。因此，一个元素是否属于对称差，等于它是否属于这两个集合的两个真值进行异或的结果。(doi.org)

对称差继承了异或的结合律和交换律。其单位元是空集，并且 $A\triangle A=\varnothing$。这些恒等式使集合运算能够与布尔值运算相对应。(doi.org)

按位计算与数字电路

按位异或对两个二进制数中对应的比特分别进行异或运算，各位之间不会传递进位。例如，直接逐位计算可得

输出中的 1 标示了两个输入中取值不同的位置。在 Python 编程语言中，运算符 ^ 对整数执行按位异或，并不是乘方符号。(web.stanford.edu)

异或逻辑门通过电子电路实现同一真值表。在半加器中，异或用于计算和位 $s=a\oplus b$，与运算则用于计算进位 $c=a\land b$。因此，$1+1$ 得到和位 0、进位 1，表示二进制结果 $10_2$。全加器还包含一个输入进位，其和位为 $a\oplus b\oplus c_{\mathrm{in}}$。(www-inst.eecs.berkeley.edu)

连续异或还可以提供纠错码所使用的奇偶校验信息。根据其奇数奇偶性规则，奇偶校验能够检测任意奇数个比特翻转，但偶数个比特翻转可能不会改变奇偶性。因此，仅靠奇偶校验无法识别所有可能的错误。(web.stanford.edu)

密码学中的应用

在密码学中，可以通过异或将明文比特串 $M$ 与密钥串 $K$ 结合：

消去性质保证了明文能够恢复。二进制一次一密采用这一构造，所用密钥必须保密、服从均匀随机分布、独立于消息、与消息等长，并且绝不重复使用。在这些条件下，它能够实现完美保密；异或本身并不能保证这些条件成立。(nvlpubs.nist.gov)

如果使用同一密钥加密两条消息，根据消去性质可得 $C_1\oplus C_2=M_1\oplus M_2$。这一推导出的恒等式表明，重复使用密钥会暴露两条明文之间的关系，因而无法维持一次一密的保密保证。(nvlpubs.nist.gov)

机器学习中的异或问题

在机器学习中，异或是不具有线性可分性的分类问题的典型例子。正类点 $(0,1)$ 和 $(1,0)$ 位于正方形的一对对角顶点，负类点则为 $(0,0)$ 和 $(1,1)$。不存在一条直线能够将这两类分开，因此，单个采用线性阈值的感知机无法表示异或。(cs.cmu.edu)

多层感知机可以利用带有非线性激活函数的隐藏层表示异或。一种构造方式是让隐藏单元分别检测或与与的结果，再组合它们的输出，排除两个输入同时激活的情况。这说明，中间表示能够使神经网络表达单个线性阈值单元无法表达的决策规则。(cs.cmu.edu)