# 基本结构：集合，函数，序列，求和与矩阵

离散数学的许多内容主要研究离散结构，用以表示离散对象。

# 集合

这一节我们将研究最基本的离散结构—集合，所有其他离散结构都建立于集合之上。集合可用于把对象聚集在一起。

通常我们用大写字母来表示集合。用小写字母表示集合中的元素。

# 描述集合的方式

花名册方法：在一对花括号之间，列出集合中的所有元素。

例子：

使用 “集合构造器” 符号：我们通过描述作为集合的成员必须具有的性质来刻画集合中的那些元素。

例子：

# 一些常用的集合

# 相等的集合

两个集合相等当且仅当它们拥有同样的元素。如何 A 和 B 是相等的集合，就记为 A = B。

# 空集

# 单元素集

# 文氏图 Venn Diagram

文氏图常用于表示集合之间的关系。

在文氏图中全集（universal set）U，包含所考虑的全部对象，用矩形框来表示。（注意全集随着我们所关注的对象会有所不同。）

在矩形框内部，圆形或其他几何图形用于表示集合。有时候用点来表示集合中特定的元素。

# 子集

上面定理（i）的证明：

# 集合的大小

例子：

例子：

# 幂集

许多问题涉及要检查一个集合的元素的所有可能组合看它们是否满足某种性质。为了考虑集合 S 中元素所有可能的组合，我们构造一个以 S 的所有子集作为其元素的新集合。

例子：

# 笛卡尔集

有时候元素聚集中其次序是很重要的。由于集合是无序的，所以就需要用一种不同的结构来表示有序的聚集。这就是『 有序 n 元组 』。

::: details-open 例子： :::

例子：

# 带量词的集合符号

例子：

# 真值集 & 量词

例子：

# 集合运算



# 集合恒等式

下面列出了最重要的集合恒等式：

证明集合相等的一种方法是证明每一个是另一个的子集。回想一下为了证明一个集合是另一个集合的子集，可以通过证明一个元素如果属于第一个集合，必定属于第二个集合。

下面给出些证明恒等式的例子：

例子：

# 扩展的并集和交集

例子：

# 函数

::: theorem 定义：

:::

当定义一个函数的时候，我们需要指定它的定义域、陪域、定义域中元素到陪域的映射。当两个函数有相同的定义域、陪域，定义域中的每个元素映射到陪域中相同的元素时，这两个函数是相等的。

例子：

例子：

例子：

# 一对一函数 & 映上函数

# 反函数 & 函数组合

如果函数 f 不是一一对应的，就无法定义反函数。

一一对应关系称为可逆的（invertible），因为可以定义这个函数的反函数。如果函数不是一一对应关系，就说它是不可逆的（not invertible），因为这样的函数不存在反函数。

例子：

例子：

# 函数的图

例子：

# 一些重要的函数

例子：

# 部分函数

用于计算一个函数的程序可能不会对这个函数定义域中所有的元素产生正确的函数值。例如，由于在计算函数时可能导致无限循环或溢出，所以一个程序可能不会产生一个正确的值。

要研究这种情形，我们需要用到部分函数的概念。

例子：

# 序列和求和

# 序列

序列是一种用来表示有序列表的离散结构。例如 1，2，3，5，8 是一个含有五项的序列。

例子：

# 递推关系

例子：

# 斐波那契数列

例子：

#  闭公式

当我们为序列的项找到一个显式公式，称为『 闭公式 』（closed formula）时，我们就说解决了带有初始条件的递推关系。

我们有两种方法去求解递推关系：

『 正向替换 』：我们从初始条件出发找到连续的项直到 $an$ 为止

『 反向替换 』：因为我们从 $an$ 开始迭代时将其表示为序列中前面的项直到可以用 $a1$ 来表示

例子：

例子：

# 求和

例子：

例子：

# 集合的基数

前面我们把 “有限集合的基数” 定义成该集合中的元素个数。有限集合诉我们什么时候两个有限集合大小相同，什么时候一个比另一个大。本节我们将这个概念扩展到无限集合。即如果能有一种方法来衡量无限集的相对大小，我们就能定义什么是两个无限集合有相同的基数了。

# 可数集

无限集是可数的当且仅当可以把集合中的元素排列成序列（下标是正整数）。这是因为从正整数集合到集合 S 的一一对应关系 f 可以用序列 a1，a2，…，an，…表示，其中 a1 ＝ f（1），a2 ＝ f（2），…，an ＝ f（n），…

::: details-open 例子：

:::

# 不可数集

下面使用 “ 康托尔对角线法” 来证明实数集合是不可数的：

# 矩阵

离散数学中用矩阵表示集合中元素之间的关系。

# 矩阵算数

# 矩阵相加

相同大小的两个矩阵的和是将它们对应位置上的元素相加得到的。不同大小的矩阵不能相加，因为两个矩阵的和只对行数和列数都一样的两个矩阵才有定义。

例子：

# 矩阵相乘

例子：

# 矩阵的转置 & 幂

# 单位矩阵

# 矩阵转置

# 0 - 1 矩阵

所有元素非 0 即 1 的矩阵称为 0-1 矩阵。0-1 矩阵经常用来表示各种离散结构。

例子：

例子：

例子：