2.2. 集合运算

两个或多个集合可以以许多不同的方式结合在一起。

并集（union）

令$A$和$B$为集合，集合$A$和$B$的并集，用$A\cup B$表示，是一个集合，它包含$A$或$B$中或同时在$A$和$B$中的元素。

一个元素$x$属于$A$和$B$的并集当且仅当$x$属于$A$或$x$属于$B$。这说明

$$A\cup B = \{x \enspace | \enspace x \in A \lor x \in B \}$$

交集（intersection）

令$A$和$B$为集合，集合$A$和$B$的交集，用$A\cap B$表示，是一个集合，它包含同时在$A$和$B$中的那些元素。

一个元素$x$属于集合$A$和$B$的交集当且仅当$x$属于$A$并且$x$属于$B$。这说明

$$A\cap B = \{x \enspace | \enspace x \in A \land x \in B \}$$

两个集合称为不相交的，如果它们的交集为空集。

集合基数的计算$|A \cup B| = |A| + |B| - |A \cap B|$。把这一结果推广到任意多个集合的并集就是所谓的包含排斥原理或简称容斥原理。容斥原理是枚举中的一项重要技术。

差集（difference）

令$A$和$B$为集合，集合$A$和$B$的差集，用$A - B$表示，是一个集合，它包含属于$A$而不属于$B$的元素。$A$和$B$的差集也称为B相对于A的补集。

集合$A$和$B$的差集有时也记为 $A \setminus B$

一个元素$x$属于$A$和$B$的差集当且仅当$x \in A$且$x \notin B$，这说明

$$A - B = \{x \enspace | \enspace x \in A \land x \notin B\}$$

对称差（symmetric difference）

集合$A$和$B$的对称差，用$A\oplus B$表示，是属于$A$或属于$B$但不同时属于$A$与$B$的元素组成的集合。

$$\begin{array}{ll} A\oplus B = \set{x | (x \in A \lor x \in B) \land x \notin A\cap B } \\ A\oplus B = A\cup B \setminus A\cap B \end{array}$$

例：$A = \set{0,1,2,3}, B=\set{1,3,5,7,9}. A\oplus B = \set{0,2,5,7,9}$

补集

令$U$为全集。集合$A$的补集，用$\overline{A}$表示，是$A$相对于$U$的补集。所以集合$A$的补集是$U-A$。补集也可以写成$\complement{_U}{A}$

一个元素x属于A当且仅当$x \notin A$。这说明

$$\complement{_U}{A} = \overline{A} = \{x \in U | x \notin A\}$$

$\{x \in U | x \notin A\}$是一个真值集，意为满足 $x \notin A$并且 $x \in U$的所有元素的集合。

集合恒等式

恒等式	名称
$A \cap U = A,\enspace A\cup\varnothing = A$	恒等率
$A \cup U = U,\enspace A\cap\varnothing = U$	支配率
$A \cap A = A,\enspace A\cup A = A$	幂等率
$\overline{(\overline{A})}$	补率
$A \cap B = B\cap A,\enspace A \cup B = B\cup A$	交换率
$A\cup(B\cup C)=(A\cup B)\cup C \\ A\cap(B\cap C)=(A\cap B)\cap C$	结合率
$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\\ A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$	分配率
$\overline{A\cap{B}}=\overline{A}\cup\overline{B}\\ \overline{A\cup{B}}=\overline{A}\cap\overline{B}$	德摩根率
$A\cup(A\cap B)=A\\A\cap(A\cup B)=A$	吸收率
$A\cup\overline{A}=U\\A\cap\overline{A}=\varnothing$	互补率

分配率证明：
$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$

此题证明主要用到了逻辑运算中的分配率$p \lor(q\land r) = (p \lor q)\land(p\lor r)$

$$\begin{array}{lll} A\cup(B\cap C) &=\{x \enspace | \enspace x \in A \lor x \in(B \cap C)\}\\ &= \{x \enspace | \enspace x \in A \lor (x \in B \land x\in C)\}\\ &= \{x \enspace | \enspace (x \in A \lor x \in B)\land(x\in A \lor x \in C) \}\\ &= \{x \enspace | \enspace x \in A\cup B \land x \in A\cup C\}\\ &= (A\cup{B})\land(A\cup{C}) \end{array}$$

$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$的证明与上面类似。

德摩根率证明：

$$\begin{array}{lll} \overline{A \cap B} &= \{x \enspace | \enspace x \notin A\cap B\} & \small\text{补集的定义}\\ &= \{x \enspace | \enspace \lnot( x \in A\cap B)\} & \small\text{不属于符号的含义}\\ &= \{x \enspace | \enspace \lnot( x \in A \land x \in B)\} & \small\text{交集的定义}\\ &= \{x \enspace | \enspace \lnot(x \in A) \lor \lnot(x \in B) \} & \small\text{逻辑等价式的第一德摩根率}\\ &= \{x \enspace | \enspace x \notin A \lor x \notin B\} & \small\text{不属于符号的含义}\\ &= \{x \enspace | \enspace x \in \overline{A} \lor x \in \overline{B}\} & \small\text{补集的定义}\\ &= \{x \enspace | \enspace x \in \overline{A}\cup\overline{B}\} & \small\text{并集的定义}\\ &=\overline{A}\cup\overline{B} & \small\text{集合构造器记号的含义} \end{array}$$

扩展的并集和交集

由于集合的交集和并集满足结合律，所以只要$A$、$B$、$C$为集合，则$A\cup{B}\cup{C}$和$A\cap{B}\cap{C}$均有定义，即这样的记号是无二义性的。我们不需要用括号来指明哪个运算在前。

• $A\cup{B}\cup{C}$包含那些至少属于$A$、$B$、$C$为中一个集合的元素。
• $A\cap{B}\cap{C}$包含那些属于$A$、$B$、$C$全部3个集合中的元素。

多个集合的并集

一组集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合。
我们用下列记号

$$A_1 \cup A_2 \cup ... \cup A_n = \bigcup_{i=1}^{n}A_i$$

表示集合$A_1 \cup A_2 \cup ... \cup A_n$的并集。

多个集合的交集

一组集合的交集是包含那些属于这组集合中所有成员集合的元素的集合。
我们用下列记号

$$A_1 \cap A_2 \cap ... \cap A_n = \bigcap_{i=1}^{n}A_i$$

表示集合$A_1 \cap A_2 \cap ... \cap A_n$的交集。

例题： 令 $A_i = \{i, i+i, i+2, ...\}$，$i=1,2,3,...$。那么,

$$\bigcup_{i=1}^{n}A_i=\bigcup_{i=1}^{n} \{i, i+i, i+2, ...\}=\{1,2,3,...\}$$

而

$$\bigcap_{i=1}^{n}A_i=\bigcap_{i=1}^{n}\{i, i+i, i+2, ...\}=\{n, n+1,n+2,...\}=A_n$$

我们可以将并集和交集的记号扩展到其他系列的集合。

$$A_1 \cup A_2 \cup ... \cup A_n\cup ... = \bigcup_{i=1}^{\infty}A_i\\ A_1 \cap A_2 \cap ... \cap A_n\cap ... = \bigcap_{i=1}^{\infty}A_i$$

更一般地，当$\;I\;$是一个集合时，可以用记号$\bigcap_{i\in{I}} A_i$和$\bigcup_{i\in{I}} A_i$分别表示对于$i \in I$ 的集合$A_i$的交集和并集。注意我们有

$$\textstyle\bigcap_{i\in{I}} A_i = \{x \enspace | \enspace \forall\: i \in I (x \in A_i)\} \text{和} \bigcup_{i\in{I}} A_i=\{x \enspace | \enspace \exist\: i \in I (x \in A_i)\}$$

例题： 假设对于$i=1,2,3,...$，集合 $A_i = \{1, 2, 3, ...,i\}$。那么，

$$\bigcup_{i=1}^{\infty}A_i=\bigcup_{i=1}^{\infty} \{1,2,3,\dots,i\} = \{1,2,3,\dots\} = Z^+$$ $$\bigcap_{i=1}^{\infty}A_i=\bigcap_{i=1}^{\infty} \{1,2,3,\dots,i\} = \{1\}$$

集合的计算机表示

利用二进制的位运算可以快速对集合进行各种运算。

如$U=\{1,2,3,4,5,6,7,8,9,10\}$，集合$A = \{1,3,5,7,9\}$，$B = \{2,4,6,8,10\}$，将集合元素在全集中的位置标记为A，不在的位置标记为0，则

$$\begin{array}{ll} A &= 10\: 1010\: 1010\\ B &= 01\: 0101\: 0101\\ A\cup{B} &= 10\: 1010\:1010 \lor01\: 0101\: 0101=11\: 1111\: 1111 = U\\ A\cap{B} &= 10\: 1010\:1010 \land01\: 0101\: 0101=00\: 0000\: 0000 = \varnothing\\ \overline{A} &= \lnot 10\: 1010\: 1010 = 01\: 0101\: 0101 = B \end{array}$$