集合代数

集合的基本概念

集合的定义

由一些个体构成的整体称为集合。称为集合的个体为元素。

集合的表示

• 枚举法：列举出集合中的所有元素。

• 谓词表示法：通过谓词概括集合中的元素。 例如：

• 枚举法：自然数集合：$\mathbb{N}=\{1,2,3,\cdots \}$

• 谓词表示法：偶数集合：$A=\{x|x=2k,k\in \mathbb{N}\}$

• 集合的树形结构表示：

          A
         /|\
        / | \
       /  |  \
      /   |   \
     /    |    \
  {a, b}{{b}}   d
   /  \   |
  a    b {b}
          |
          b

集合的元素具有的性质

• 无序性：集合中的元素之间没有先后次序之分。
• 相异性：集合中的元素各不相同。
• 确定性：一个元素要么属于一个集合，要么不属于一个集合。
• 任意性：集合中的元素可以是任意的，也可以是集合。

元素和集合的关系

$\in$：元素属于集合。 $\notin$：元素不属于集合。

集合与集合的关系

$$A\subseteq B\iff \mathrm{\forall }x(x\in A\Rightarrow x\in B)$$$$A=B\iff A\subseteq B\wedge B\subseteq A$$$$A⫋B\iff A\subseteq B\wedge A\ne B$$$$A⊈B\iff \mathrm{\exists }x(x\in A\wedge x\notin B)$$

空集

不包含任何元素的集合称为空集，记作 $\varnothing$ 空集是任何集合的子集，即 $\varnothing \subseteq A$ 空集是唯一的。

全集

包含一切可能元素的集合称为全集，记作 $E$。

全集具有相对性，与讨论的问题有关，不存在绝对的全集。

幂集

$$P(A)=\{x|x\subseteq A\}$$

例如：$A=\{a,b\}$，则 $P(A)=\{\varnothing ,\{a\},\{b\},\{a,b\}\}$

集合的运算

$$\begin{array}{rlrl}\mathrm{并}& & A\cup B& =\{x|x\in A\vee x\in B\}\\ \mathrm{交}& & A\cap B& =\{x|x\in A\wedge x\in B\}\\ \mathrm{相}\mathrm{对}\mathrm{补}/\mathrm{差}& & A-B& =\{x|x\in A\wedge x\notin B\}\\ \mathrm{绝}\mathrm{对}\mathrm{补}& & \bar{A}& =A=E-A\\ \mathrm{对}\mathrm{称}\mathrm{差}& & A\oplus B& =(A-B)\cup (B-A)\\ \\ \mathrm{广}\mathrm{义}\mathrm{并}& & \bigcup _{i=1}^n{A}_i& =\{x|\mathrm{\exists }z(z\in A\wedge x\in z)\}\\ \mathrm{广}\mathrm{义}\mathrm{交}& & \bigcap _{i=1}^n{A}_i& =\{x|\mathrm{\forall }z(z\in A\to x\in z)\}\end{array}$$

1. ${\displaystyle \bigcup \varnothing =\varnothing }$，${\displaystyle \bigcap \varnothing }$ 无意义
2. 广义运算减少集合的层次（括弧减少一层）
3. 广义运算的计算：一般情况下可以转变成初级运算

运算顺序

一类运算：广义并，广义交，幂集，绝对补，运算由右向左进行 二类运算：初级运算 $\cup$，$\cap$，$-$，$\oplus$，运算由左向右进行 混合运算：一类运算优先于二类运算

有穷集合的计数

1. 文氏图法
2. 包含排斥原理（容斥原理）

$$\begin{array}{rl}|\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_n}|=& \left|E\right|\\ & -\sum _{i=1}^n\left|A_i\right|\\ & +\sum _{1\le i<j\le n}|A_i\cap A_j|\\ & -\cdots \\ & +(-1{)}^n|A_1\cap A_2\cap \cdots \cap A_n|\end{array}$$

推论：$n$ 个集合的并的元素个数

$$\begin{array}{rl}|A_1\cup A_2\cup \cdots \cup A_n|=& \sum _{i=1}^n\left|A_i\right|\\ & -\sum _{1\le i<j\le n}|A_i\cap A_j|\\ & +\cdots \\ & +(-1{)}^{n-1}|A_1\cap A_2\cap \cdots \cap A_n|\end{array}$$$$|A_1\cup A_2\cup \cdots \cup A_n|=\left|E\right|-|\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_n}|$$

集合恒等式

只涉及一个运算符的恒等式

运算律	$\cup$	$\cap$	$\oplus$
交换律	$A\cup B=B\cup A$	$A\cap B=B\cap A$	$A\oplus B=B\oplus A$
结合律	$(A\cup B)\cup C=A\cup (B\cup C)$	$(A\cap B)\cap C=A\cap (B\cap C)$	$(A\oplus B)\oplus C=A\oplus (B\oplus C)$
幂等律	$A\cup A=A$	$A\cap A=A$	$A\oplus A=\varnothing$

涉及两个不同运算符的恒等式

运算律	$\cup$ 与 $\cap$	$\cap$ 与 $\oplus$
分配律	$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$	$A\cap (B\oplus C)=(A\cap B)\oplus (A\cap C)$
吸收律	$A\cup (A\cap B)=A$ $A\cap (A\cup B)=A$

涉及补运算的恒等式

运算律	$-$	$\sim$
DM律	$A-(B\cup C)=(A-B)\cap (A-C)$ $A-(B\cap C)=(A-B)\cup (A-C)$	$\overline{A\cup B}=\bar{A}\cap \bar{B}$ $\overline{A\cap B}=\bar{A}\cup \bar{B}$ $\sim (B\cup C)=\sim B\cap \sim C$ $\sim (B\cap C)=\sim B\cup \sim C$
双重否定律		$\overline{\stackrel{―}{A}}=A$, $\sim \sim A=A$

涉及空集和全集的恒等式

	$\varnothing$	$E$
补元律	$A\cap \sim A=\varnothing$	$A\cup \sim A=E$
零律	$A\cap \varnothing =\varnothing$	$A\cup E=E$
同一律	$A\cup \varnothing =A$	$A\cap E=A$
否定律	$\sim \varnothing =E$	$\sim E=\varnothing$

集合等式的证明

命题演算法

例3 证明 $A\cup (A\cap B)=A$ （吸收律）

$$\begin{array}{r}\text{证：任取 }x\\ x\in A\cup (A\cap B)\iff & x\in A\vee x\in A\cap B\\ \iff & x\in A\vee (x\in A\wedge x\in B)\\ \iff & (x\in A\wedge x\in E)\vee (x\in A\wedge x\in B)\\ \iff & x\in A\wedge (x\in E\vee x\in B)\\ \iff & x\in A\\ \text{因此得 }A\cup (A\cap B)=A.\end{array}$$

等式置换法

直接运用集合恒等式演算。