date: 2025-06-14T15:31:00 aliases:

• 离散数学第六章

---

集合代数

集合基本概念

• 集合定义：具有某种特定性质的对象汇集的整体，对象称为元素
• 表示方法：
  • 列举法：$A = \{a, b, c\}$
  • 描述法：$B = \{x | P(x)\}$
• 特殊集合：
  • 空集 $\varnothing$
  • 全集 $E$
  • 自然数集 $\mathbb{N}$
  • 整数集 $\mathbb{Z}$
• 元素关系：
  • 属于 $a \in A$
  • 不属于 $b \notin A$
• 集合关系：
  • 包含 $A \subseteq B$
  • 真包含 $A \subset B$
  • 相等 $A = B \iff (A \subseteq B) \land (B \subseteq A)$

集合的运算

• 并集：$A \cup B = \{x | x \in A \lor x \in B\}$
• 交集：$A \cap B = \{x | x \in A \land x \in B\}$
• 差集：$A - B = \{x | x \in A \land x \notin B\}$
• 补集：$\sim A = E - A$
• 对称差：$A \oplus B = (A - B) \cup (B - A)$
• 笛卡尔积：$A \times B = \{(a,b) | a \in A \land b \in B\}$

笛卡尔积运算示例

基本示例

设集合：

• $A = \{1, 2\}$
• $B = \{a, b\}$ 则笛卡尔积：

$$A \times B = \{(1,a), (1,b), (2,a), (2,b)\}$$

有穷集的计数

• 基本计数原理：
  • 并集计数：$|A \cup B| = |A| + |B| - |A \cap B|$
  • 容斥原理：$|\bigcup_{i=1}^n A_i| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots + (-1)^{n+1}|\bigcap_{i=1}^n A_i|$
• 应用示例：
  • 文氏图辅助计算
  • 错位排列计数

集合恒等式

• 基本恒等式：
  • 幂等律：$A \cup A = A$, $A \cap A = A$
  • 交换律：$A \cup B = B \cup A$, $A \cap B = B \cap A$
  • 结合律：$(A \cup B) \cup C = A \cup (B \cup 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)$
  • 德摩根律：
    • $\sim (A \cup B) = \sim A \cap \sim B$
    • $\sim (A \cap B) = \sim A \cup \sim B$
• 证明方法：
  • 逻辑等值式法
  • 集合定义法
  • 成员表法
  • 文氏图法