集合的异或运算（对称差）

1、集合的异或运算(AΔB)定义
属于A或属于B，但不同时属于A和B的元素的集合称为A和B的对称差，即A和B的异或。

注：草绿色部分即为 AΔB

2、对称差(异或)运算的定律
2.1 AΔB = (A-B)∪(B-A) = (A∪B)-(A∩B)
该公式的证明已在 集合的证明及相关习题 中证明了

2.2 对称差运算的交换律
(AΔB)ΔC = (AΔC)ΔB

注：图1中草绿色部分为 (AΔB) ，三角形区域为 C ，(AΔB)ΔC  = 仅含草绿色或仅含三角形的区域
注：图2中草绿色部分为 (AΔC) ，三角形区域为 B ，(AΔC)ΔB  = 仅含草绿色或仅含三角形的区域

证明：
(AΔB)ΔC
= [(A-B)∪(B-A)]△C         
= {[(A-B)∪(B-A)] - C} ∪ {C - [(A-B)∪(B-A)]}
转换全部 '-' 号
= {[(A∩～B)∪(～A∩B)] ∩ (～C)} ∪ {C∩～[(A∩～B)∪(～A∩B)]}
对大括号的2部分分别进行公式化解

左边部分：
{[(A∩～B)∪(～A∩B)] ∩ (～C)}
将(A∩～B)和(～A∩B)当整体，根据分配律
{[(A∩～B)∪(～A∩B)] ∩ (～C)}
= {[(A∩～B)∩(～C)]∪[(～A∩B)∩(～C)]}
根据结合律
= {(A∩～B∩～C)∪(～A∩B∩～C)}

右边部分：
{C∩～[(A∩～B)∪(～A∩B)]}
根据De.Morgen定律，将～移进去
= {C∩[～(A∩～B)∩～(～A∩B)]}
根据De.Morgen定律，继续将～移进去
= {C∩[(～A∪～～B)∩(～～A∪～B)]}
∵～～B = B，～～A = A
∴{C∩[(～A∪～～B)∩(～～A∪～B)]} = {C∩[(～A∪B)∩(A∪～B)]}
将(～A∪B)当作整体，继续用分配律处理[(～A∪B)∩(A∪～B)]
[(～A∪B)∩(A∪～B)]
= [(～A∪B)∩A]∪[(～A∪B)∩～B)]
继续分配律
= [(～A∩A)∪(B∩A)]∪[(～A∩～B)∪(B∩～B)]
= [φ∪(B∩A)]∪[(～A∩～B)∪φ]
= (B∩A)∪(～A∩～B)
∴{C∩[(～A∪B)∩(A∪～B)]} = {C∩(B∩A)∪(～A∩～B))
将(B∩A)和(～A∩～B)分别当作整体，根据分配律
= (A∩B∩C)∪(～A∩～B∩C)

∴(AΔB)ΔC = {(A∩～B∩～C)∪(～A∩B∩～C)} ∪ (A∩B∩C)∪(～A∩～B∩C)
根据以上步骤，将B看着C，同理可推得：
(AΔC)ΔB = {(A∩～C∩～B)∪(～A∩C∩～B)} ∪ (A∩C∩B)∪(～A∩～C∩B)
根据结合律：
(AΔC)ΔB = {(A∩～B∩～C)∪(～A∩B∩～C)} ∪ (A∩B∩C)∪(～A∩～B∩C)
∴(AΔB)ΔC = (AΔC)ΔB
点评：该证明过程重点在于将2个类似的式子转化为可用结合律移动位置的中间表达式，从而得证

3、集合的异或运算在计算机中的应用
3.1 证明：当 AΔB = C 时，AΔC = B

即典型的异或运算 A xor B = C，A xor C = B
在编程中常用该可逆运算对数据 B 异或一个常量 A 转换后进行加密保护，当要还原数据B时，再次用 C 异或常量 A 即可得到B

 
注:图1中草绿色部分即为 AΔB = C
    图2中草绿色部分即为 C，三角形区域为 A，AΔC = 仅有草绿色或仅有三角形的区域 = B

证明：
∵AΔB = C
∴C = (A∪B)-(A∩B)
将C代入到AΔC中
AΔC = AΔ[(A∪B)-(A∩B)]
= {A∪[(A∪B)-(A∩B)]} - {A∩[(A∪B)-(A∩B)]}
先处理左边式子
{A∪[(A∪B)-(A∩B)]}
= A∪{(A∪B)∩[～(A∩B)]}
将 (A∪B) 和 [～(A∩B)]看着整体，根据分配律
= [A∪(A∪B)] ∩ {A∪[～(A∩B)]}
= (A∪B) ∩ {A∪[～(A∩B)]}
根据De.morgen定律
= (A∪B) ∩ {A∪[～A∪～B)]}
= (A∪B) ∩ {(A∪～A)∪～B}
= (A∪B) ∩ {E∪～B}
= (A∪B) ∩ E
= (A∪B)

再处理右边式子
{A∩[(A∪B)-(A∩B)]}
= A∩{(A∪B)∩[～(A∩B)]}
= A∩(A∪B)∩[～(A∩B)]
根据吸收律反推
A∩(A∪B) = A
A∩(A∪B)∩[～(A∩B)] = A∩[～(A∩B)]

合并左右式子
AΔC = (A∪B) - {A∩[～(A∩B)]}
将[～(A∩B)]看着整体，根据De.morgen定律
(A∪B) - {A∩[～(A∩B)]} = (A∪B) ∩ {～ {A∩[～(A∩B)]}}
再次根据De.morgen定律
= (A∪B) ∩ {～A∪～[～(A∩B)]}
= (A∪B) ∩ {～A∪(A∩B)}
= (A∪B) ∩ {～A∪(A∩B)}
根据分配律
= (A∪B) ∩ {(～A∪A)∩(～A∪B)}
= (A∪B) ∩ {E∩(～A∪B)}
= (A∪B) ∩ (～A∪B)
根据分配律倒推
= B∪(A∩～A)
= B∪(φ)
= B
∴AΔC = B

3.2 《离散数学及其应用》第6版P83 21 题
证明：当 AΔB = AΔC时，是否有B = C
即如果2个数和同一个常量 A 进行异或后的结果相等，那么这两个数必定相等，这是 ∪∩ 等运算没有的性质

证明：
∵AΔB = AΔC = D
根据上面证明：当 AΔB = D 时，AΔD = B(将上面证明中的C换成D，以免歧义)
同理
∵AΔC = D
∴AΔD = C = B
∴C = B

3.3 《离散数学及其应用》第6版P83 19 题
证明：若A是全集E的子集，则:
a) AΔA= Φ  b) AΔΦ = A
c) AΔE= ～A d) AΔ(～A)= E

a) 证明：
AΔA= (A-A)∪(A-A) = Φ∪Φ = Φ
b) 证明：
AΔΦ = (A∪Φ)-(A∩Φ) = A-Φ = A
c) 证明：
AΔE= (A∪E)-(A∩E) = E-A = ～A
d) 证明：
AΔ(～A)= (A∪～A)-(A∩～A) = E-Φ = E

点评：此4组证明a和b是一组，互为可逆运算，c和d是一组，互为可逆运算，这也是异或运算的重要性质
a) AΔA= Φ 即表示 A xor A = 0
这在汇编中经常用来给寄存器清0操作：xor eax, eax（因为只需要1个字节的命令,其他指令都要2个以上的字节）
c) AΔE= ～A 给出了异或和补集的转换公式，即异或和反码的转换