离散数学与概率论

# 0 集合与数学记号

# 0.1 集合

# 0.1.1 基本概念

一个 集合(set) 是一些定义良好的对象的全体，这些对象称之为集合的 元素(elements) 或者 成员(members) ，并且一个它们可以是任何东西，包括数字、字母、人、城市，甚至是其它的集合。

一般，我们会用大写字母来表示集合，通过列举集合的元素并用花括号括起的方式来定义或者描述一个集合。比如说，我们可以描述集合A为前5个质数组成的集合，或者，我们可以显式地这样写：

A={2,3,5,7,11} A = \{2, 3, 5, 7, 11\}

如果x是集合A的一个元素，我们写作 x∈Ax \in A ，类似的，如果y不是集合A的一个元素，我们写作 y∉Ay \not\in A 。

如果两个集合A和B的元素相同，我们称这两个集合 相等(equal) ，写作 A=BA = B 。

集合中元素的顺序以及重复性并不影响集合本身，所以：

{red,white,blue}={blue,white,red}={red,white,white,blue} \{red, white, blue\} = \{blue, white, red\} = \{red, white, white, blue\}

有时，一些复杂的集合我们会用一种不同的记号来表示。比如说所有有理数组成的集合，记为 Q\mathbb{Q} ，可以写作

{ab∣a,b∈Z∧b≠0} \{\frac{a}{b} | a, b \in \mathbb{Z} \wedge b\ne 0\}

其中， Z\mathbb{Z} 表示整数集， ∧\wedge 表示且。这个表示方法读作“所有分子分母都是整数且分母不为0的分数组成的集合”。

# 0.1.2 集合的势

我们也会讨论一个集合的大小，也叫做集合的 势(cardinality) 。如果 A={1,2,3,4}A = \{1, 2, 3, 4\}，那么集合A的势为4，可以用 ∣A∣=4|A| = 4 来表示。

一个集合的势也可能是0，有一个独特的这样的集合，我们称之为 空集(empty set) ，记为 ∅\emptyset 。

一个集合也可能有无限个元素，比如说整数集、质数集或者奇数集。

# 0.1.3 子集与真子集

如果集合A中的每一个元素都在集合B中，我们称A是B的一个 子集(subset) ，写作 A⊆BA \subseteq B 。与之等价地，我们也可以写作 B⊇AB \supseteq A ，读作B是A的一个超集(superset)。

如果集合A严格包含在集合B中，我们称A是B的 真子集(proper subset) ，记作 A⊂BA \subset B ，说明B中至少有一个元素是不在A中的。

比如说，考虑集合 B={1,2,3,4,5}B = \{1, 2, 3, 4, 5\} ，集合 {1,2,3}\{1, 2, 3\} 既是B的子集，也是B的真子集，而集合 {1,2,3,4,5}\{1, 2, 3, 4, 5\} 是B的子集，但不是B的真子集。

关于子集，有如下的一些简单性质：

  • 空集，用 {}\{\} 或 ∅\emptyset 表示，是任何非空集合A的真子集： ∅⊂A\emptyset \subset A；

  • 空集是任何集合B的子集：∅⊆B\emptyset \subseteq B ；

  • 每个集合A都是它本身的子集：A⊆AA \subseteq A 。

# 0.1.4 交集和并集

集合A与集合B的 交集(intersection) 是所有同时在A和B中的元素组成的集合，记作 A∩BA \cap B 。

如果 A∩B=∅A\cap B = \emptyset ，我们称这两个集合是 不相交的(disjoint) 。

集合A与集合B的 并集(union) 是所有在A或者B中的元素组成的集合，记作 A∪BA \cup B 。

例如，假设集合A是所有正奇数组成的集合，集合B是所有正偶数组成的集合，那么 A∩B=∅A \cap B = \emptyset ， A∪B=Z+A \cup B = \mathbb{Z}^{+} ，其中 Z+\mathbb{Z}^{+} 是正整数集。

关于交集和并集，有如下的一些简单性质：

  • A∪B=B∪AA \cup B = B \cup A
  • A∪∅=AA \cup \emptyset = A
  • A∩B=B∩AA \cap B = B \cap A
  • A∩∅=∅A \cap \emptyset = \emptyset

# 0.1.5 补集

考虑集合A与集合B，所有在集合B中，但是不在集合A中的元素组成的集合为A在B中的 相对补集(relative complement) ，或者B和A的 差集(set difference) ，记作 B−AB - A 或者 B\AB \backslash A ：

B−A={x∈B∣x∉A} B - A = \{x \in B | x \not\in A\}

比如说 B={1,2,3},A={3,4,5}B = \{1, 2, 3\}, A =\{3, 4, 5\} ，则 B−A={1,2}B - A = \{1, 2\} 。

再比如说记 R\mathbb{R} 是实数集， Q\mathbb{Q} 是有理数集， 则 R−Q\mathbb{R} - \mathbb{Q} 就是无理数集。

关于补集，有如下一些性质：

  • A−A=∅A - A = \emptyset
  • A−∅=AA - \emptyset = A
  • ∅−A=∅\emptyset - A = \emptyset

# 0.1.6 重要集合

在数学中，有一些集合非常常用，所以我们会用一些特殊的符号表示它们，包括：

  • N\mathbb{N} 表示自然数集： {0,1,2,3,...}\{0, 1, 2, 3, ...\} ；

  • Z\mathbb{Z} 表示整数集： {...,−2,−1,0,1,2,...}\{..., -2, -1, 0, 1, 2, ...\} ；

  • Q\mathbb{Q} 表示有理数集： {ab∣a,b∈z∧b≠0}\{\frac{a}{b} | a, b \in \mathbb{z} \wedge b \ne 0\} ；

  • R\mathbb{R} 表示实数集；

  • C\mathbb{C} 表示复数集。

# 0.1.7 积与幂集

两个集合的 笛卡尔积(Cartesian product) （也叫做 叉乘(cross product) ），写作 A×BA \times B ，指的是所有的A中的元素作为第一个部分，B中的元素作为第二个部分的有序对组成的集合。用集合表示法写作：

A×B={(a,b)∣a∈A,b∈B} A\times B = \{(a, b) | a \in A, b\in B\}

比如说，若 A={1,2,3},B={u,v}A = \{1, 2, 3\}, B = \{u, v\} ，则

A×B={(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)} A\times B = \{(1, u), (1, v), (2, u), (2, v), (3, u), (3, v)\}

再比如说自然数集和自然数集的笛卡尔积就是所有的自然数有序对：

N×N={(0,0),(1,0),(0,1),(1,1),(2,0),...} \mathbb{N}\times\mathbb{N}=\{(0, 0), (1, 0), (0, 1), (1, 1), (2, 0), ...\}

给定一个集合S，S的 幂集(power set) 指的是S的所有的子集组成的集合，记为 P(S)\mathcal{P}(S)，集合记号表示为：

P(S)={T∣T⊆S} \mathcal{P}(S) = \{T | T \subseteq S\}

例如，对于集合 S={1,2,3}S = \{1, 2, 3\} ，其幂集为：

P(S)={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} \mathcal{P}(S) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}

幂集有一个性质，若 ∣S∣=k|S| = k ，则 ∣P(S)∣=2k|\mathcal{P}(S)| = 2^k ，其实就是在说势为k有限集的有 2k2^k 个子集。

# 0.2 数学记号

# 0.2.1 求和与累积

在书写很多东西求和或者累积的时候，我们有一套比直接书写更加紧凑的表示法。比如说，写 1+2+...+n1 + 2 + ... + n ，不一定非得说“点点点”，我们可以更简单的写作 ∑i=1ni\sum_{i = 1}^{n} i。

更一般地，求和符号的含义如下：

f(m)+f(m+1)+...+f(n)=∑i=mnf(i) f(m) + f(m + 1) + ... + f(n) = \sum_{i = m}^{n} f(i)

例如， ∑i=5n=52+62+...+n2\sum_{i = 5}^{n} = 5^2 + 6^2 + ... + n^2 。

类似的，累积的符号定义如下：

f(m)⋅f(m+1)⋅...⋅f(n)=∏i=mnf(i) f(m)\cdot f(m + 1)\cdot ... \cdot f(n) = \prod_{i = m}^{n} f(i)

例如， ∏i=1n=1⋅2⋅...⋅n\prod_{i = 1}^{n} = 1\cdot 2\cdot ...\cdot n 就是前n个正整数的积。

# 0.2.2 全称量词和存在量词

考虑语句：对于所有的自然数n， n2+n+41n^2 + n + 41 是质数。这里，n的数量范围是自然数集 N\mathbb{N} 内的任意元素。

用数学记号写作

(∀n∈N)(n2+n+41isprime) (\forall n \in \mathbb{N})(n^2 + n + 41\ is\ prime)

这里，我们使用了 全称量词(universal quantifier) ∀\forall (任意(for all))。

这句话是真的吗？如果你尝试将一些较小的n代进去，你会发现 n2+n+41n^2 + n + 41 对于这些n来说确实是质数。

这个式子其实是高斯想出来的，高斯当时想着寻找一个质数的通项或者递推公式，能够生成不少的质数，也不知道他是怎么想出来的。当然，最终他证明了不存在这样的式子。

但是，如果你思考得更深入一些，你会发现一些更大的n代入使得这个式子的值并不是质数。因此这句话其实是错的。

和全称量词相对的， 存在量词(existential quantifier) ∃\exists (存在(there exists)) 可以被用在这样的语句中：

(∃x∈Z)(x<2andx2=4) (\exists x \in \mathbb{Z})(x < 2\ and\ x^2 = 4)

这个语句是说存在一个小于2的整数，其平方为4。这是一个真的语句，因为存在 x=−2x = -2 满足 x<2x < 2 且 x2=4x^2 = 4。

我们也可以写一些同时使用这两个量词的语句：

  1. (∀x∈Z)(∃y∈Z)(y>x)(\forall x \in \mathbb{Z})(\exists y \in \mathbb{Z})(y > x)
  2. (∃y∈Z)(∀x∈Z)(y>x)(\exists y \in \mathbb{Z})(\forall x \in \mathbb{Z})(y > x)

第一条语句时是在说给定一个整数，我们总能找到一个更大的。第二条语句说了一件非常不同的事情：存在一个最大的整数。第一句话是真的，而第二句话是假的。因此，全称量词和存在量词的使用顺序会对语句表达的含义产生影响。

这一讲是对于之后会使用到的一些集合知识以及数学记号的复习，因为这些东西之后会经常用，所以单独抽出一节来讲。

进度

恭喜完成离散数学与概率论第0讲《集合与数学记号》所有内容的学习！

← 1 命题逻辑 →