集合论

约定

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

集合基本概念

集合表示

离散结构大厦的地基！

  • 集合是若干元素的无序聚集，且元素不重复
  • 集合构造法：V={x ∣ P(x),Q(x),⋯ }V=\{x\ |\ P(x),Q(x),\cdots\}，其中谓词P,QP,Q表示xx的性质
  • 属于：x∈Vx\in V表示一个元素属于一个集合，在构造法限定元素所属父集时可写在竖线左方
  • 包含关系：
    • V1⊆V2V_1\subseteq V_2表示集合**V1V_1包含于V2V_2，或V2V_2包含V1V_1，称V1V_1是V2V_2的子集**，与V2⊇V1V_2\supseteq V_1等价
    • 逻辑表示：V1⊆V2⇔∀x(x∈V1→x∈V2)V_1\subseteq V_2\Leftrightarrow\forall x(x\in V_1\rightarrow x\in V_2)
    • 所有集合都包含空集和它本身
    • 包含是严格区分离散结构的，变元即变元，集合即集合，例如{1}⊈{{1}}\{1\}\nsubseteq\{\{1\}\}
  • 相等：
    • 若V1⊆V2V_1\subseteq V_2且V2⊆V1V_2\subseteq V_1，称V1=V2V_1=V_2
    • 逻辑表示：V1=V2⇔∀x(x∈V1↔x∈V2)V_1=V_2\Leftrightarrow\forall x(x\in V_1\leftrightarrow x\in V_2)
  • 基数：∣V∣|V|表示集合的基数，即集合中元素的个数
  • 常用集合约定记号：
    • NN：所有自然数的集合
    • ZZ：所有整数的集合
    • Z+Z^+：所有正整数的集合，和{x∈N ∣ x≠0}\{x\in N\ |\ x\ne0\}相等
    • QQ：{p/q ∣ p∈Z∧q∈Z∧q≠0}\{p/q\ |\ p\in Z\wedge q\in Z\wedge q\ne0\}，即所有有理数的集合
    • RR：所有实数的集合
    • R+R^+：所有正实数的集合
    • CC：所有复数的集合

集合分类及特殊集合

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

集合运算

  • 集合运算的结果也是集合
  • 并集：V1∪V2={x ∣ x∈V1∨x∈V2}V_1\cup V_2=\{x\ |\ x\in V_1\vee x\in V_2\}
  • 交集：V1∩V2={x ∣ x∈V1∧x∈V2}V_1\cap V_2=\{x\ |\ x\in V_1\wedge x\in V_2\}，V1∩V2=∅⇔V1和V2不相交V_1\cap V_2=\varnothing\Leftrightarrow V_1和V_2不相交
  • 相对补集：V1−V2={x ∣ x∈V1∧x∉V2}V_1-V_2=\{x\ |\ x\in V_1\wedge x\notin V_2\}，称为V2V_2相对于V1V_1的补集，也称V1V_1和V2V_2的差集
  • 对称差集：V1⊕V2=(V1−V2)∪(V2−V1)V_1\oplus V_2=(V_1-V_2)\cup(V_2-V_1)，即V1∪V2−V1∩V2V_1\cup V_2-V_1\cap V_2
  • 绝对补集：
    • 通常假定所有集合都包含于一个称为全集UU的大集合，通常所说VV的补集就是VV相对于UU的补集，记为∼V\sim V或Vˉ\bar{V}
    • x∈Vˉ⇔x∉Vx\in\bar V\Leftrightarrow x\notin V
  • 集合的并集、交集运算满足布尔和、布尔积的各种恒等式，其中空集∅\varnothing对应FF，全集UU对应TT

恒包含及补集恒等式

  • V1∩V2⊆ V1V2⊆V1∪V2V_1\cap V_2\subseteq\ \begin{matrix}V_1\\V_2\end{matrix}\subseteq V_1\cup V_2
  • V1−V2=V1∩V2ˉ=V1−V1∩V2⊆V1V_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)V_1\cap V_2-V_1\cap V_3=V_1\cap(V_2-V_3)，即相对补集和交集满足分配律
  • V1∪V2−V1∪V3⊆V1∪(V2−V3)V_1\cup V_2-V_1\cup V_3\subseteq V_1\cup(V_2-V_3)
  • V1⊕V1=∅V_1\oplus V_1=\varnothing，自身对称补集为空集
  • V1⊆V2⇔V1−V2=∅V_1\subseteq V_2\Leftrightarrow V_1-V_2=\varnothing

二元关系

元组

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

笛卡尔积

笛卡尔积从多个集合中构造出能够反映聚集顺序的元素全为元组的新集合，不满足交换律

V1×V2×⋯×Vn={(x1,x2,⋯ ,xn) ∣ x1∈V1∧x2∈V2∧⋯∧xn∈Vn} V_1\times V_2\times\cdots\times V_n=\{(x_1,x_2,\cdots,x_n)\ |\ x_1\in V_1\wedge x_2\in V_2\wedge\cdots\wedge x_n\in V_n\}

二元笛卡尔积即构造出以V1V_1元素为第一元素，以V2V_2元素为第二元素的所有序偶，并放在一个新集合里

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

不难得到，

∣V1×V2×⋯×Vn∣=∏1≤i≤n∣Vi∣\begin{align}|V_1\times V_2\times\cdots\times V_n|=\prod_{1\le i\le n}|V_i|\end{align}

映射函数