对称差

维基百科,自由的百科全书
跳转至: 导航搜索
A ΔB的文氏圖。對稱差標為紅色。

数学上,两个集合对称差是只属于其中一个集合,而不属于另一个集合的元素组成的集合。 集合论中的这个运算相当于布尔逻辑中的异或运算。

集合AB的对称差通常表示为AΔB,对称差的符号在有些图论书籍中也使用\oplus符号来表示。例如:集合{1,2,3}和{3,4}的对称差为{1,2,4}。所有学生的集合和所有女性的集合的对称差为所有男性学生和所有女性非学生组成的集合。

定义[编辑]

对称差是集合间的运算,两个集合A和B,其对称差AΔB有几种等价的定义方式:

  1. AΔB = (A - B)∪(B - A)
  2. AΔB = (A∪B) - (A∩B)

性质[编辑]

对称差运算的主要性质包括:

交换律
AΔB = BΔA
结合律
(AΔB)ΔC = AΔ(BΔC)
单位元
∅ΔA = A(空集是单位元)
逆元
AΔA = ∅
分配律
A∩(BΔC) = (A∩B)Δ(A∩C)
注意:AΔ(B∩C) ≠ (AΔB)∩(AΔC)
注意:A∪(BΔC) ≠ (A∪B)Δ(A∪C)
注意:AΔ(B∪C) ≠ (AΔB)∪(AΔC)
布尔环

以对称差作为加法,交集为乘法,任何集合X的幂集P(X)构成一个布尔环,并可以诱导一个同构的布尔代数

综上可得,采用对称差运算,任意集合 X幂集阿贝尔群。由于该群中所有元素都是其自身的负元, 这个群实际上是二元域 Z2 上的向量空间。若 X 有限,则以其为元素的单元素集合构成这个向量空间的,那么向量空间的维数等于 X 的元素个数。这种构造方法用于图论,可定义图的圈空间

对称差满足的恒等式有:

A\oplus \phi =A

A \oplus A= \phi

A \oplus B=B \oplus A

(A \oplus B)\oplus C =A\oplus(B\oplus C)

A \oplus B=A\oplus C \Rightarrow B=C

与逻辑和布尔代数的关系[编辑]

或者用 XOR 运算表示:

A Δ B = { x : (xA) XOR (xB) }.

对称差可以在任意布尔代数中定义,写作

x Δ y = (xy) ∧ ¬(xy) = (x ∧ ¬y) ∨ (y ∧ ¬x)。

参考[编辑]