离散数学II笔记(2)

week 3

集合的运算（续）

集合的基本定义

• 集合表示：集合通常用大写字母表示，如A、B、C等，元素用小写字母表示，如x、y、z等。
• 集合的基本运算：
  • 并集（$\cup$）：A ∪ B 表示所有属于A或B的元素。
  • 交集（$\cap$）：A ∩ B 表示所有既属于A又属于B的元素。
  • 差集（$−$）：A − B 表示属于A但不属于B的元素。
  • 补集（ ~ ）：~A 表示不属于A的所有元素。

集合的基本定律

1. 幂等律：
   • $A ∪ A = A$
   • $A ∩ A = A$
2. 交换律：
   • $A ∪ B = B ∪ A$
   • $A ∩ B = B ∩ A$
3. 结合律：
   • $(A ∪ B) ∪ C = A ∪ (B ∪ C)$
   • $(A ∩ B) ∩ C = A ∩ (B ∩ C)$
4. 分配律：
   • $A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)$
   • $A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)$
5. 同一律：
   • $A \cup \varnothing = A$
   • $A \cap U = A$
6. 零律：
   • $A \cup U = U$
   • $A \cap \varnothing =\varnothing $
7. 吸收律：
   • $A ∪ (A ∩ B) = A$
   • $A \cap (A \cup B) = A$
8. 德·摩根律：
   • $\sim (A ∪ B) =\sim A ∩\sim B$
   • $\sim (A ∩ B) =\sim A ∪\sim B$
9. 对合律：
   • $ \sim (\sim A) = A$
   • $\sim \varnothing = U$
   • $\sim U =\varnothing $
10. 否定律：
    • $A ∪ \sim A = U$
    • $A \cap \sim A = \empty $

在不含 ~ 的集合恒等式中，将$∪$和$\cap$互换 ，$\varnothing$和$U$互换，得到的仍是集合恒等式。—— 对偶原理
将不含$\rightarrow $和 $\leftrightarrow$的命题逻辑等值式中的$\vee$ 换为$\cup$ ，$\wedge$ 换为$\cap$ ，$\lnot $换为$\sim$ ，0 换为 $\varnothing$ ，1 换为 $U$，$\Leftrightarrow$换为 = ，就得到集合恒等式。

集合运算的性质

• 定理7：设 A 和 B是全集U的子集，$B =\sim A$ 当且仅当$A ∪ B = U $和$ A ∩ B = \varnothing $。
• 定理 8：设 A 和 B是全集U的子集，则下列命题等价：
  (1)$A \subseteq B$；(2)$A∪B = B$; (3)$ A ∩ B = A$; (4)$ A – B =\varnothing $

证明两个集合相等常用以下两种方法：
（1）集合相等定义 （元素分析法）
（2）集合运算的基本定律（等式推理）

交、并的推广

广义并与广义交

设 A₁, A₂, ……, A_n 为集合，则：

• $$A_1 \cap A_2 \cap \cdots \cap A_n = \{x \,|\, x \in A_1 \land x \in A_2 \land \dots \land x \in A_n\}$$

• $$A_1 \cup A_2 \cup \cdots \cup A_n = \{x \,|\, x \in A_1 \lor x \in A_2 \lor \dots \lor x \in A_n\}$$

分别记作：$ \bigcap_{i=1}^{n} A_i $ 和$\bigcup_{i=1}^{n} A_i $

对于无穷多个集合的交集和并集，则分别记为：

• $ \bigcap_{i=1}^{\infty} A_i = A_1 \cap A_2 \cap \dots \cap A_n \cap \dots $
• $ \bigcup_{i=1}^{\infty} A_i = A_1 \cup A_2 \cup \dots \cup A_n \cup \dots $
• 定义 (集类或集合族) : 如果一个集合的所有元素都是集合，则称该集合为集类。
• 定义（广义并、广义交）：设 ( \mathcal{B} ) 为任意集类，则

1. 集合 $ { x ,|, \exists X (X \in \mathcal{B} \land x \in X) } $ 称为 $\mathcal{B} $ 的广义并，记为 $ \cup \mathcal{B} $。
2. 若 $ \mathcal{B} \neq \varnothing $，则集合 $ { x |, \forall X (X \in \mathcal{B} \rightarrow x \in X) } $ 称为 $ \mathcal{B} $ 的广义交，记为 $ \cap \mathcal{B} $。

若 $ B = \varnothing $，则 $ \cap B $ 无意义，因为对于任意 $ X \in B $，条件 $ X \in B \rightarrow x \in X $ 的前件为假，因此结论为真，导致 $ \cap B $ 等于全集 $ U $。

• 定理9：广义的交、并运算设 ( A ) 为任意集合，( \mathcal{B} ) 为任意集合族，则有：
  (1) 若 ( B \neq \varnothing )，则 $ A \cup (\cup B) = \cup { A \cup X ,|, X \in B } $
  (2) 若 ( B \neq \varnothing )，则 $ A \cap (\cap B) = \cap { A \cap X ,|, X \in B } $
  (3) 若 ( B \neq \varnothing )，则 $ A \cup (\cap B) = \cap { A \cup X ,|, X \in B } $
  (4) $ A \cap (\cup B) = \cup { A \cap X ,|, X \in B } $
  (5) 若 ( B \neq \varnothing )，则 $ \sim (\cap B) = \cup { \sim X ,|, X \in B } $
  (6) 若 ( B \neq \varnothing )，则 $ \sim (\cup B) = \cap { \sim X ,|, X \in {B} } $

• 定理10：设$A$为任意集合，$\mathcal{B}$ 为任意集合族，则，
  (1) $B\in \mathcal {B}$，则$\cap B \in B$且$B \in \cup B$
  (2) 若对任意$B \in \mathcal B$ 都有$B \subseteq A$，则$\cap B \subseteq A$
  (3) 若对任意$B \in \mathcal B$ 都有$A \subseteq B$，则$A \subseteq \cap B$

---

有穷集的计数原理

• 引理1：若$A$和$B$是有穷集合，且$A∩B＝\varnothing$，则
  $＃(A∪B) = ＃A+＃ B$

• 定理：若 A 和 B 是有穷集合，则
  $＃( A∪B ) = ＃A＋＃B －＃(A∩B)$
  证明：
  

• 推论：若$A$，$B$ 和 $C$是有穷集合，则
  $＃(A∪B ∪C), ＝, ＃A＋＃B＋＃C － ＃(A∩B) －＃(A∩C)－＃(B∩C)＋ ＃(A∩B ∩C) $

集合的归纳定义法

归纳定义法

1. 基本项：非空集 $S_0 \subseteq A$； （规定A的一些生成元）
2. 归纳项：一组规则，从 A 中元素出发，依据这些规则所获得的元素仍然是 A 中的元素；
3. 极小化：
   (a) A 中的每个元素都是通过有限次使用1) 或 2)获得的。
   (b) 如果集合 $S \subseteq A$ 也满足 1)和 2)，则 S = A 。

有序偶和笛卡尔乘积

有序偶

定义：1（有序偶）任给两个对象 x 和 y，将它们按规定的顺序构成的序列，称之为有序偶，记为$< x, y >$。其中，x 称为有序偶的第一元，y 称为第二元。

注意：有序偶≠二元集，有序偶是有顺序的

有序偶的集合定义：$<x,y>=\{\, \{ x\},\{ x,y\}\,\}$

有序偶的唯一性定理：若$<x,y>=<u,v>$，则$x=u$且$y=v$。

n元序偶定义：：$<x_1,x_2,...,x_n>=<<x_2,...,x_n>,x_1>，n>2$。
定理：$<x_1,x_2,...,x_n>=<y_1,y_2,...,y_n>$当且仅当$x_i=y_i$，$i=1,2,...,n，n>2$。

笛卡尔乘积

定义：设 A，B 是任意两个集合，则称集合 $A×B=\{<x,y>\,|\,x\in A \wedge y\in B\}$ 为集合 A 和 B 的笛卡尔乘积。
性质：

1. 不满足交换律
2. 不满足结合律
3. 当$A=\varnothing 或B=\varnothing 时，A\times B = \varnothing$
4. $\#(A×B)=\#A·\#B$（A，B为任意有限集）

定理：$A\times B = \varnothing $当且仅当$A=\varnothing$或$B=\varnothing$。

定理：若$A×B \subseteq C×D$，当且仅当$A\subseteq C$且$B\subseteq D$。
定理：若$A×B = C×D$，当且仅当$A=C$且$B=D$。

定理 设 A，B 和 C 为任意三个集合，则
$A×(B∪C) = (A×B)∪(A×C)$；
$(A∪B)×C = (A×C)∪(B×C)$；
$A×(B∩C) = (A×B)∩(A×C)$；
$(A∩B)×Ｃ= (A×C)∩(B×C)$；
$A×(B – C) = (A×B) – (A×C)$；
$(A – B)×C = (A×C) – (B×C)$。

n个集合的笛卡尔乘积：设$A_1,A_2,...,A_n$为任意n个集合，则称集合$A_1×A_2×...×A_n=\{<x_1,x_2,...,x_n>\,|\,x_i\in A_i,i=1,2,...,n\}$为n个集合的笛卡尔乘积，特别的，将$A_1×A_2×...×A_n$记为$A^n$。