算法和数据结构笔记

集合

1. 集合

1.1 集合的定义

定义 集合 是一组对象的全体。集合在数学中是不定义概念，最基本概念之一。

集合常用大写字母表示，如 A, B, C⋯A,\,B,\,C\cdots。

定义 集合内的每个对象叫做这个集合的 元素，集合与元素的关系用属于（∈\in）和不属于（∉\notin）描述，元素通常使用小写字母 a, b, c⋯a,\,b,\,c\cdots 表示。

下面出现的 A, BA,\,B 等大写字母，若不解释均为集合，小写字母 a, b, ca,\,b,\,c 等若不解释均为集合内元素。

定义 集合相等 被定义为集合内的每一个元素都对应相等，即

(∀ a∈A, a∈B), (∀ b∈B, b∈A)⇔A=B \left(\forall\, a \in A,\, a \in B\right),\, \left(\forall\, b \in B,\, b \in A\right) \Leftrightarrow A = B

集合内的元素是 确定的，下面的条件只有一个成立

a∈A, A∉A a \in A,\, A \notin A

集合内的元素是 无序的，且集合内的元素是 互异的

∀ a, b∈A, a≠b \forall \,a,\,b \in A,\, a \neq b

定义 有限集：元素个数是有限，否则是 无限集。

定义 若 ∀ a∈A\forall\, a \in A，均有 a∈Ba \in B，则称为 AA 是 BB 的 子集，记为 A⊆BA \subseteq B。此时如果 A≠BA \neq B，则 AA 是 BB 的真子集，记为 A⫋BA \subsetneqq B。

1.2 集合的表示

集合的表示在数学上并无严格定义，一般来说有下面几种：

  1. 列举法
  2. 描述法
  3. 图示法

列举法使用大括号包含集合内的元素，适用于集合元素有限且比较少的情况，例如

{1, 2}, {π, 23} \left\{1,\,2\right\},\,\left\{\pi,\,\frac{\sqrt{2} }{3}\right\}

描述法使用 {x∣P(x)}\left\{x\mid P(x)\right\} 格式来表示集合，用处较广，其中 P(x)P(x) 表示具有某性质的描述，xx 是描述符，例如

{x∣x∈R, x>π} \left\{x \mid x \in \R,\, x > \sqrt{\pi}\right\}

图示法一般用于形象化的描述，一般用 Venn 图在新窗口打开 来表示。在不太严格的意义下用以表示集合（或类）的一种图解。

1.3 常见的集合

定义 点集 是只包含点元素的集合，数集 是只包含数字的集合，复数集 是只包含复数的集合，其中上述集合也可以为空集。

一般地，如果集合内的元素都属于类 A\text{A}，那么这个集合可以称为 A\text{A} 集，如 点集、数集，复数集 等。

定义几个最常用的集合：

  • 定义 全集 UU（有时也表示为 II）表示为在某范围内某些对象的全体，具体取决定义于上下文
  • 定义 空集 是不含元素的集合，表示为 ∅\emptyset
  • 定义 自然数集 N\mathbf{N}，有时也写为 N\mathbb{N}
  • 定义 正整数集 N+\mathbf{N}_+ 或 N∗\mathbf{N}^*，也可写为 N+, N∗\mathbb{N}_+,\,\mathbb{N}^*
  • 定义 整数集 Z\mathbf{Z} 或者 Z\mathbb{Z}
  • 定义 有理数集 Q\mathbf{Q} 或者 Q\mathbb{Q}
  • 定义 实数集 R\mathbf{R} 或者 R\mathbb{R}
  • 定义 复数集 C\mathbf{C} 或者 C\mathbb{C}

符号规范

在本文档中，所有和数集有关的符号均使 Blackboard Bold 字体表示，即 Z, Q, R, C\mathbb{Z},\,\mathbb{Q},\,\R,\,\mathbb{C} 等，不使用一些教材等广泛定义的粗体。

Blackboard Bold 字体的 LaTeX 代码为 \mathbb{}。

有一类特殊的集合，用于表示从 aa 到 bb 范围内的所有整数（a, b∈Za,\,b \in \mathbb{Z}），记为 a, b‾\overline{a,\,b}，其定义为

a, b‾={x∣x∈Z, a⩽x⩽b} \overline{a,\,b} = \left\{x \mid x \in \mathbb{Z},\, a \leqslant x \leqslant b \right\}

且 a, b∈Za,\,b \in \mathbb{Z}。例如 1, 2, 3⋯ , n1,\,2,\,3\cdots,\,n 可以表示为 1, n‾\overline{1,\,n}。

2. 区间

定义 区间 表示范围内的所有实数构成的集合，在无歧义的情况下，区间可以使用括号包含的一对实数来表示。不同的括号的区别是是否包含边界，定义如下

[a, b]={x∣a⩽x⩽b, x∈R}[a, b)={x∣a⩽x<b, x∈R}(a, b]={x∣a<x⩽b, x∈R}(a, b)={x∣a<x<b, x∈R} \begin{aligned} \left[a,\,b\right] &= \left\{x \mid a \leqslant x \leqslant b,\,x \in \R \right\} \\ \left[a,\,b\right) &= \left\{x \mid a \leqslant x < b,\,x \in \R \right\} \\ \left(a,\,b\right] &= \left\{x \mid a < x \leqslant b,\,x \in \R \right\} \\ \left(a,\,b\right) &= \left\{x \mid a < x < b,\,x \in \R \right\} \\ \end{aligned}

3. 集合的运算

定义 集合的加法即集合的 并集，其定义如下

A+B=A∪B={x∣x∈A or x∈B} A + B = A \cup B = \left\{x \mid x \in A \text{ or } x \in B\right\}

定义 集合的减法即集合的 差集，其定义如下

A−B=A\B={x∣x∈A, x∉B} A - B = A \backslash B = \left\{x \mid x \in A,\, x \notin B\right\}

定义 集合的乘法即集合的 交集，其定义如下

A⋅B=A∩B={x∣x∈A, x∈B} A \cdot B = A \cap B = \left\{x \mid x \in A,\, x \in B\right\}

对多个集合依次取并集记为

A=⋃i=1nAi A = \bigcup_{i=1}^n A_i

对多个集合依次取交集记为

A=⋂i=1nAi A = \bigcap_{i=1}^n A_i

定义 有限集内元素的个数也称为 集合的大小，或称为 集合的基，记为

N=∣A∣ N = \left| A \right|

定义 对集合取反也称为取集合的 补集，AA 相对于全集 UU 的补集为

A‾=∁UA={x∣x∉A, x∈U} \overline{A} = \complement_U A = \left\{x \mid x \notin A,\, x \in U\right\}

定义 集合的 对称差 定义如下

A⊕B=A△B={x∣x∈A∪B, x∉A∩B} A \oplus B = A \triangle B = \left\{ x \mid x \in A \cup B,\, x \notin A \cap B \right\}

根据定义，存在下面的结论

A⊕B=A△B=A+B−AB A \oplus B = A \triangle B = A + B - AB

4. 集合运算的性质

4.1 基础结论

根据上述运算，容易得到下面的结论

∣∅∣=0∣A+B∣=∣A∣+∣B∣−∣AB∣∑i=1n∣Ai∣⩾∣⋃i=1nAi∣⩾∣⋂i=1nAi∣ \begin{aligned} \left| \emptyset \right| &= 0 \\ \left|A+B\right| &= \left|A\right| + \left|B\right| - \left|AB\right| \\ \sum_{i=1}^{n} \left| A_i \right| & \geqslant \left| \bigcup_{i=1}^{n} A_i \right| \geqslant \left| \bigcap_{i=1}^{n} A_i \right| \end{aligned}

4.2 运算性质

下面的性质我们不加以证明：

  1. 集合的交运算满足交换律和结合律

    A+B=B+A(A+B)+C=A+(B+C) \begin{aligned} A + B =& B + A \\ (A + B) + C =& A + (B + C) \end{aligned}

  2. 集合的并运算满足交换律和结合律

    AB=BA(AB)C=A(BC) \begin{aligned} AB &= BA \\ (AB)C &= A(BC) \end{aligned}

  3. 集合的补集满足等幂律

    A‾‾=A \overline{\overline{A} } = A

  4. 常元律、同一律

    A+∅=AA⋅∅=∅A+U=UAU=AA+A=AAA=A \begin{aligned} A + \emptyset &= A \\ A \cdot \emptyset &= \emptyset\\ A + U &= U \\ AU &= A \\ A + A &= A \\ AA &= A \end{aligned}

  5. 分配律

    A(B+C)=AB+ACA+BC=(A+B)(A+C) \begin{aligned} A(B + C) &= AB + AC \\ A +BC &= (A + B)(A + C) \end{aligned}

  6. 摩根定律

    A+B‾=A‾⋅B‾AB‾=A‾+B‾ \begin{aligned} \overline{A + B} &= \overline{A} \cdot \overline{B} \\ \overline{AB} &= \overline{A} + \overline{B} \end{aligned}

  7. 引申的公式

    A+AB=AA(A+B)=A \begin{aligned} A + AB &= A \\ A(A + B) &= A \end{aligned}

  8. 摩根定律的一般情况

    ⋂i=1nAi‾=⋃i=1nAi‾⋃i=1nAi‾=⋂i=1nAi‾ \begin{aligned} \overline{\bigcap_{i=1}^n A_i} &= \bigcup_{i=1}^n \overline{A_i} \\ \overline{\bigcup_{i=1}^n A_i} &= \bigcap_{i=1}^n \overline{A_i} \end{aligned}

递归地，对于一个集合，将交集和并集关系互换，将每一个集合符号都改为它的补集，那么得到的集合是原式的补集。