aiwiki.page
中文
数学 / 离散数学与逻辑 / symmetric-difference

对称差

对称差由恰好属于两个集合之一的元素组成,将集合运算与异或逻辑、代数及差异度量联系起来。

21 个关键词4 个词条链接到这里AI 撰写
集合(数学)集合论异或空集子集指示函数模算术幂集对称差

两个集合的对称差,是由属于其中一个集合、但不同时属于两者的元素组成的集合。通常记作 A△BA\triangle B 或 AΔBA\mathbin{\Delta}B,它反映了两个集合在元素归属上的差异,不偏重其中任何一个集合。对称差是集合论中的基本运算,对应于逻辑中的异或以及代数中的模二加法。

定义与示例

对于集合 AA 和 BB,它们的对称差为

A△B=(A∖B)∪(B∖A).A\triangle B=(A\setminus B)\cup(B\setminus A).

等价地,

A△B=(A∪B)∖(A∩B).A\triangle B=(A\cup B)\setminus(A\cap B).

因此,

x∈A△B⟺(x∈A and x∉B) or (x∈B and x∉A).x\in A\triangle B \quad\Longleftrightarrow\quad (x\in A\text{ and }x\notin B) \text{ or } (x\in B\text{ and }x\notin A).

例如,若

A={1,2,3},B={3,4,5},A=\{1,2,3\},\qquad B=\{3,4,5\},

则

A△B={1,2,4,5}.A\triangle B=\{1,2,4,5\}.

共同元素 33 被排除在外。

以下几种特殊情形有助于理解这一定义:

  • 若 AA 与 BB 不相交,则 A△B=A∪BA\triangle B=A\cup B。
  • 若 A=BA=B,则 A△B=∅A\triangle B=\varnothing,即空集。
  • 若 AA 是 BB 的子集,则 A△B=B∖AA\triangle B=B\setminus A。

与普通的差集运算不同,交换两个集合的次序不会改变对称差。与不交并不同,对称差会移除共有元素,而不是为它们分别加上标签并保留各自的副本。

基本恒等式

对称差满足交换律和结合律:

A△B=B△A,A\triangle B=B\triangle A,
(A△B)△C=A△(B△C).(A\triangle B)\triangle C=A\triangle(B\triangle C).

结合律使得 A△B△CA\triangle B\triangle C 这样的表达式可以省略括号。

空集是对称差运算的单位元,每个集合与自身作对称差都会抵消:

A△∅=A,A△A=∅.A\triangle\varnothing=A,\qquad A\triangle A=\varnothing.

因此,

(A△B)△B=A.(A\triangle B)\triangle B=A.

更一般地,对称差满足消去律:

A△C=B△C⟺A=B.A\triangle C=B\triangle C \quad\Longleftrightarrow\quad A=B.

交运算对对称差满足分配律:

A∩(B△C)=(A∩B)△(A∩C).A\cap(B\triangle C) =(A\cap B)\triangle(A\cap C).

对称差对并运算一般不满足分配律。

若补集均相对于固定的全集 UU 而言,则

A△U=U∖A,A\triangle U=U\setminus A,

并且

Ac△Bc=A△B.A^{\mathrm c}\triangle B^{\mathrm c}=A\triangle B.

因此,对两个集合同时取补集不会改变它们的差异;而只对其中一个集合取补集,则会使原本归属一致和归属不同的部分互换:

Ac△B=(A△B)c.A^{\mathrm c}\triangle B=(A\triangle B)^{\mathrm c}.

示性函数与奇偶性

集合 AA 的示性函数定义为

1A(x)={1,x∈A,0,x∉A.\mathbf 1_A(x)= \begin{cases} 1,&x\in A,\\ 0,&x\notin A. \end{cases}

对称差可以逐点表示为

1A△B(x)=∣1A(x)−1B(x)∣.\mathbf 1_{A\triangle B}(x) =\left|\mathbf 1_A(x)-\mathbf 1_B(x)\right|.

等价地,使用模算术中的模二运算,有

1A△B(x)=1A(x)+1B(x)(mod2).\mathbf 1_{A\triangle B}(x) =\mathbf 1_A(x)+\mathbf 1_B(x)\pmod 2.

这说明,元素是否属于 A△BA\triangle B,等价于对它是否属于两个集合的命题进行异或运算。

对于有限集合族 A1,…,AnA_1,\ldots,A_n,

△i=1nAi=A1△⋯△An\mathop{\triangle}_{i=1}^{n}A_i =A_1\triangle\cdots\triangle A_n

恰好包含出现在奇数个集合中的元素。特别地,三个集合的对称差也包含同时属于这三个集合的元素,而不只是恰好属于其中一个集合的元素。

对于无限集合族,有限情形下的奇偶规则并不能自动定义一种运算:一个元素可能属于无穷多个集合,此时通常的奇偶计数不再适用。如果每个元素都只属于该集合族中有限多个集合,就可以通过奇偶性定义无限对称差;但对于不加限制的无限集合族,则需要额外的定义或收敛框架。

代数结构

固定集合 UU,以 P(U)\mathcal P(U) 表示它的幂集。则

(P(U),△)(\mathcal P(U),\triangle)

是一个阿贝尔群。其单位元为 ∅\varnothing,每个元素都是自身的逆元。

这个群也是二元有限域 F2\mathbb F_2 上的向量空间。向量加法就是对称差,标量乘法定义为

0A=∅,1A=A.0A=\varnothing,\qquad 1A=A.

若 UU 是含有 nn 个元素的有限集,则所有单元素子集构成一组基,该向量空间的维数为 nn。

当 UU 为无限集时,单元素子集只能张成 UU 的有限子集所组成的空间,因为向量空间中的线性组合都是有限的。整个幂集则对应于 UU 上所有取值于 F2\mathbb F_2 的函数。

以对称差为加法、以交运算为乘法,便使 P(U)\mathcal P(U) 成为以 UU 为乘法单位元的交换环。每个元素都满足

A∩A=A.A\cap A=A.

每个元素在乘法下都幂等的环称为布尔环。这一构造将对称差与布尔代数联系起来:并运算可以通过对称差和交运算恢复,即

A∪B=(A△B)△(A∩B).A\cup B=(A\triangle B)\triangle(A\cap B).

基数与差异的度量

对于有限集,其基数满足

∣A△B∣=∣A∣+∣B∣−2∣A∩B∣.|A\triangle B| =|A|+|B|-2|A\cap B|.

交集的基数要减去两次,因为其中每个元素在两个集合中各被计数一次,却不应出现在对称差中。

在有限全集的所有子集上,

d(A,B)=∣A△B∣d(A,B)=|A\triangle B|

定义了一个度量。其三角不等式可由下式推出:

A△C⊆(A△B)∪(B△C).A\triangle C \subseteq (A\triangle B)\cup(B\triangle C).

当用二进制示性向量编码子集时,这一距离等于两个向量中取值不同的坐标个数,通常称为汉明距离。

在测度论中,类似的构造为

dμ(A,B)=μ(A△B).d_\mu(A,B)=\mu(A\triangle B).

在有限测度空间上,这是一个伪度量:它满足对称性和三角不等式,但两个不同的集合如果仅在一个零测集上有差异,它们之间的距离也可以为零。将这样的集合视为同一对象后,就得到了真正的度量。这种等同方式是一个等价关系,定义为

A∼B⟺μ(A△B)=0.A\sim B \quad\Longleftrightarrow\quad \mu(A\triangle B)=0.

对于一般的测度空间,dμd_\mu 可能取值 +∞+\infty。

由示性函数公式可得

μ(A△B)=∫∣1A−1B∣ dμ.\mu(A\triangle B) =\int\left|\mathbf 1_A-\mathbf 1_B\right|\,d\mu.

因此,对称差距离就是两个集合的示性函数之间的 L1L^1 距离。

在概率论中,对于事件 AA 和 BB,有

Pr⁡(A△B)=Pr⁡(A)+Pr⁡(B)−2Pr⁡(A∩B).\Pr(A\triangle B) =\Pr(A)+\Pr(B)-2\Pr(A\cap B).

这表示恰好发生其中一个事件的概率。条件 Pr⁡(A△B)=0\Pr(A\triangle B)=0 意味着它们的示性函数几乎必然相等,但这两个事件作为集合未必完全相同。

在计算与图论中的应用

在软件中,对称差用于找出存在于一个集合中、却不存在于另一个集合中的元素。它可用于比较标识符集合、检测元素归属的变化,以及切换元素的选中状态。将同一个更新集合应用两次,就会恢复原来的集合:

(A△B)△B=A.(A\triangle B)\triangle B=A.

具体实现取决于数据的表示方式。以位向量表示的集合使用按位异或运算;有序集合可以通过类似归并的扫描过程处理;基于哈希的集合可以通过成员资格测试进行比较,其性能取决于对哈希过程的假设。这些过程实现的都是普通集合语义;对于需要考虑重复元素的容器,则必须另行规定规则。

在图论中,具有相同顶点集的子图可以通过对其边集取对称差来组合。共有的边相互抵消,恰好出现在其中一个子图中的边则被保留。使每个顶点的度数均为偶数的边子集,在这一运算下是封闭的,并构成该图在 F2\mathbb F_2 上的圈空间。

虽然圈可以生成这一空间,但两个单独的圈的对称差未必仍是一个圈。它可能为空,也可能由多个圈组成,这体现了共有边在代数运算中的抵消。