集合

集合的定义

• 集合（集）：一些对象的全体作为一个整体
• 集合的元素： 构成整体（集合）的个体
• 集合具有：无序性，无重复性

集合的表示法

列举法

• 把集合的元素一一列举出来
• $\{1,2,3\}$
• $\{1,\{0,1\},f(x)\}$

谓词法

• $\{x|p(x)\}$:为满足性质$p$的所有$x$的集合

文氏图

• 用来示意集合的图形，可直观地表示集合间的关系
• 矩形(全覆盖)表示全集，圆表示其他集合，点表示元素

集合的术语

• $x\in A$, $x$是集合$A$的元素,反之，$x\not \in A$
• 空集$\phi$，不包含任何元素的集合
• 全集$U/E$：考虑的问题领域中所有对象组成的集合
• 有限集/无限集：集合的元素是有限/无限

集合与集合的关系

• $A=B$: 集合相等 $\Leftrightarrow$ 集合中每一个元素相同
• 若集合A中的元素均属于集合B，则称A是B的子集(subset)，$A\subseteq B$
• 若$A\subseteq B$,$A\not = B$,则$A$是$B$的真子集，记作$A\subset B$
• 任意(非空)集合A都有两个平凡子集：$A$和$∅$

集合包含关系的性质

• 自反性：$A\subseteq A$
• 反对称性：$A\subseteq B$，$B\subseteq A$ $\Rightarrow$ $A=B$
• 传递性：$A\subseteq B$, $B \subseteq C$ $\Rightarrow$ $A\subseteq C$

集合族

• 定义：集合的集合，集合中的每个元素都是集合
• 下标集：集合族中的元素用带下标的字母表示，所有下标组成的集合称为该集合族的下标集 (subscript set)

集合的运算

• 并集union：A和B的所有元素组成的集合，记为$A\cup B$

• 交集intersection：A和B的公共元素组成的集合，记为$A \cap B$

• 差集difference：属于A但不属于B的元素组成的集合，记为$A-B$

• 补集complement：不属于A的元素组成的集合，即$U-A$，记为$\overline A$

• $A\cup B$=$\{x|x∈A或x∈B\}$

• $A\cap B$=$\{x|x∈A且x∈B\}$

• $A-B$=$\{x|x∈A且x\not \in B\}$

• $U-A$=$\{x|x\not \in A\}$

• 集合A和B互不相交 disjoint:$A\cap B = \phi$

幂集

• 集合A的所有子集组成的集合称A的幂集(power set)，记为$P(A)$
• 显然有$\phi \in P(A)$, $A\in P(A)$
• $X\in P(A) \Leftrightarrow X\subseteq A$
• 若$a\in A,a\not \in B,A=B\cup \{a\}$，则$$P(A)=P(B)\cup{X\cup{a}|X\in P(B)}$$

n元组与笛卡尔乘积

• 集合：若干对象组合成的整体，无序组合
• 序列：若干对象组合成的整体，有序组合
• n元组：由$n$个对象组成的序列(串)$a_1a_2…a_n$称为n元组 (ordered n-tuple) ，记为$(a_1, a_2,…, a_n)$.
• $a_i(i=1,2,…,n)$称为该n元组的第i个坐标 (coordinate)
• 二元组也称有序偶(ordered pair)
• 如果两个n元组对应的坐标均相同，那么称这两个n元组相等$$(a_1,a_2,…a_n)=(b_1,b_2,…,b_n)\Leftrightarrow a_i=b_i(i=1,2,…n)$$
• 笛卡尔乘积: $$A\times B = {(a,b)|a\in A,b\in B}$$$$D_1\times D_2\times … \times D_n = {(d_1,d_2,…d_n)|d_i\in D_i,(i=1,2,…n)}$$

广义并&广义交

• A的广义并：所有A的元素中的元素所组成的集合，记为$∪A$

$$∪A=\{x| ∃ X\in A，x\in X\}$$

• A的广义交：A中所有集合的公共元素组成的集合，记为$∩A$

$$∩A=\{x| ∀ X\in A，x\in X\}$$

• 带下标集的形式($B$为下标记且$\beta \in B$,$A_{\beta} \in A$)：$${x| ∃ X\in A，x\in X}=\bigcup_{\beta\in B} A_{\beta}$$$${x| ∀ X\in A，x\in X}=\bigcap_{\beta\in B} A_{\beta}$$

集合恒等式

• $A\cap A = A$，$A\cup A = A$
• $A\cap \phi = \phi$，$A\cup U = U$
• $A \cap U = A$，$A \cup \phi = A$
• $A \cap \overline A =\phi$，$A \cup \overline A = U$
• $\overline{\overline A} = A$
• $A\cap B =B\cap A$，$A\cup B = B\cup A$
• $A\cap (B \cap C) = (A \cap B) \cap C$
• $A\cup (B\cup C) = (A\cup B)\cup C$
• $A\cap (B \cup C)=(A\cap B) \cup (A\cap C)$
• $A\cup (B\cap C) = (A\cup B)\cap (A\cup C)$
• $A\cup (A \cap B) = A$，$A\cap (A \cup B) = A$
• $\overline{A\cap B} = \overline A \cup \overline B$，$\overline{A\cup B} = \overline A \cap \overline B$
• $A-B = A\cap \overline B$

对偶原理

• 若P是关于集合的命题，其中至多包含并、交和补三种集合运算（不含差运算），P’是将P中的$\cap$、$\cup$、∅、U分别替换为$\cup$、$\cap$、U、∅而得到的命题，则称P’与P互为对偶命题。若P=P’，则称P为自对偶命题。
• $P \Leftrightarrow P'$

有限集的计数

• 容斥原理：$$|A\cup B| =|A|+|B|-|A\cap B|$$$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B \cap C|$$

• $$|A\times B| = |A||B|$$

• $$|P(A)| = 2^{|A|}$$