离散数学: 集合论

Posted on Edited on In , Word count in article: 1.1k Reading time ≈ 4 mins.

集合论

约定

  • 小写字母表示元素，大写字母表示集合
  • 元素可指代变元、集合、元组等任何离散结构

集合基本概念

集合表示

离散结构大厦的地基！

  • 集合是若干元素的无序聚集，且元素不重复
  • 集合构造法：V = {x | P(x), Q(x), ⋯}，其中谓词P, Q表示x的性质
  • 属于：x ∈ V表示一个元素属于一个集合，在构造法限定元素所属父集时可写在竖线左方
  • 包含关系：
    • V1 ⊆ V2表示集合V1包含于V2，或V2包含V1，称V1是V2的子集，与V2 ⊇ V1等价
    • 逻辑表示：V1 ⊆ V2 ⇔ ∀x(x∈V1→x∈V2)
    • 所有集合都包含空集和它本身
    • 包含是严格区分离散结构的，变元即变元，集合即集合，例如{1} ⊈ {{1}}
  • 相等：
    • 若V1 ⊆ V2且V2 ⊆ V1，称V1 = V2
    • 逻辑表示：V1 = V2 ⇔ ∀x(x∈V1↔︎x∈V2)
  • 基数：|V|表示集合的基数，即集合中元素的个数
  • 常用集合约定记号：
    • N：所有自然数的集合
    • Z：所有整数的集合
    • Z+：所有正整数的集合，和{x ∈ N | x ≠ 0}相等
    • Q：{p/q | p ∈ Z ∧ q ∈ Z ∧ q ≠ 0}，即所有有理数的集合
    • R：所有实数的集合
    • R+：所有正实数的集合
    • C：所有复数的集合

集合分类及特殊集合

  • 元素个数分类：有限集、无限集
  • 空集：⌀，表示不含任何元素的集合
    • 空集不显式写在集合内，但若出现在集合内，证明是一个结构是集合的元素
    • 区分：空集单独作为集合写作⌀，作为其它集合的一个元素写作{..., ⌀, ...}
    • 逻辑表示：{x | P(x) ∧ ¬P(x)}
  • 幂集：𝒫(V)表示集合V的幂集，是V所有子集的集合
    • |𝒫(V)| = 2|V|，若一个集合每取一次幂集，基数就取一次2的幂
    • 所有集合一定包含空集和本身，而⌀ = ⌀，故𝒫(⌀) = {⌀}
    • 空集作为元素的边缘情况：𝒫(𝒫(⌀)) = 𝒫({⌀}) = {⌀, {⌀}}

集合运算

  • 集合运算的结果也是集合
  • 并集：V1 ∪ V2 = {x | x ∈ V1 ∨ x ∈ V2}
  • 交集：V1 ∩ V2 = {x | x ∈ V1 ∧ x ∈ V2}，V1 ∩ V2 = ⌀ ⇔ V1和V2不相交
  • 相对补集：V1 − V2 = {x | x ∈ V1 ∧ x ∉ V2}，称为V2相对于V1的补集，也称V1和V2的差集
  • 对称差集：V1 ⊕ V2 = (V1−V2) ∪ (V2−V1)，即V1 ∪ V2 − V1 ∩ V2
  • 绝对补集：
    • 通常假定所有集合都包含于一个称为全集U的大集合，通常所说V的补集就是V相对于U的补集，记为 ∼ V或V̄
    • x ∈ V̄ ⇔ x ∉ V
  • 集合的并集、交集运算满足布尔和、布尔积的各种恒等式，其中空集⌀对应F，全集U对应T

恒包含及补集恒等式

  • $V_1\cap V_2\subseteq\ \begin{matrix}V_1\\V_2\end{matrix}\subseteq V_1\cup V_2$
  • $V_1-V_2=V_1\cap\bar {V_2}=V_1-V_1\cap V_2\subseteq V_1$，相对补集满足吸收律，且最终包含于前集合
  • V1 ∩ V2 − V1 ∩ V3 = V1 ∩ (V2−V3)，即相对补集和交集满足分配律
  • V1 ∪ V2 − V1 ∪ V3 ⊆ V1 ∪ (V2−V3)
  • V1 ⊕ V1 = ⌀，自身对称补集为空集
  • V1 ⊆ V2 ⇔ V1 − V2 = ⌀

二元关系

元组

  • 单纯的集合结构聚集的元素是无序的，无法表示元素的聚集顺序，故通过元组来反映次序
  • 元组表示：用圆括号或尖括号括起具有固定排列顺序的元素，称为一个元组
  • 二元组：含有两个元素的元组，也称序偶，第一个元素称为第一元素
  • 元组相等：两个元组的所有元素对应相等

笛卡尔积

笛卡尔积从多个集合中构造出能够反映聚集顺序的元素全为元组的新集合，不满足交换律 V1 × V2 × ⋯ × Vn = {(x1,x2,⋯,xn) | x1 ∈ V1 ∧ x2 ∈ V2 ∧ ⋯ ∧ xn ∈ Vn} 二元笛卡尔积即构造出以V1元素为第一元素，以V2元素为第二元素的所有序偶，并放在一个新集合里

边缘情况：若其中一个参数集合是空集，那么新集合为空集

不难得到，$\begin{align}|V_1\times V_2\times\cdots\times V_n|=\prod_{1\le i\le n}|V_i|\end{align}$

映射函数