离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
导论
Loading...
來自 Shanghai Jiao Tong University 的課程
离散数学
17 個評分
[音乐]
[音乐] [音乐]
各位大家好，本次介绍
离散数学导论，主要会介绍我们后面会用到的一些基本的符号和定义 首先是常用的数集符号。
我们在后面会用 N 来表示自然数集，包括 {1,2,4,5}等等
而整数集是用大写字母 Z 表示 有理数集是用 Q
表示，而实数集用 R 表示 我们对实数
定义了两个特殊的函数，分别叫做向上取整函数和向下取整函数
其中向下取整函数是取小于等于 x 的最大的整数
而相应的向上取整函数是大于等于 x 的最小的整数 我们看几个例子。
我们说对 [0.9999] 这样一个 实数，我们向下取整的话，那么
会输出 0 ，而对负的 3/4 向下取整，我们说
小于等于 -3/4 的最大的正数是 -1 所以输出 -1
，类似地 当输入为 π 的时候，我们向上取整。
那么大于等于 π 的最大的 最小的整数是 4，所以它输出的是 4，类似地，
[5.778] 大于等于这个实数的最小的整数是 6 ，所以输出 自然数 6。
我们还会用到两个 符号，一个是连续求和的符号，一个是连续求乘积的符号
分别用大写的 Σ 和大写的 Π 表示 大家一旦看到这两个符号，比如说第一个
Σ i 等于 1 到 nai 的话表示我们去 a1 加到 a2 一直加到
an 而连续的乘，大写的 Π i 从 1 到 nai 的话表
示 a1 乘以 a2 一直乘到 an ，这两个符号在后面的课程中会反复的用到
那么我们这里还会用到的一个重要的符号，类似集合相关的一些符号 我们用小 x
∈ 大 A 表示 x 是集合 A 中的一个元素 那么
A 集合怎么样表示呢？一种比较常见的方式是我们 把大
A 集合中的元素列出来，而在集合的两边用花括弧表示
当然我们说另外一种常见的方式是用 大 A 集合中的元素满足的性质来描述集合大
A 有一个特别重要而又特殊的集合是空集，我们用
这里的这个符号来表示，∅ 来表示 空集是表示不含有任何元素的这样一个集合
那么给了一个集合之后，如果我们想要表示这个集合的大小 用什么符号呢？用大
A 两边加两个竖线，也就类似于绝对值函数的这样一个符号来表示
看一个例子，我们说包含有 丨{1,5,7}丨这三个元素的集合呢 它的大小是 3。
那么集合之间的关系常见的符号有集合的 相等，比如说
A 和 B 相等是什么意思？我们是说所有集合 A 中的元素 都在集合
B 中，并且集合 B 中的元素也都在集合 A 中 那么相应地，我们可以定义
A 是 B 的子集或者说 A 是 B 的真子集 第一个说 A 是 B 的子集是说：凡是
A 的元素都一定在集合 B 中 而 A 是 B 的真子集是说：不但
A 的元素 都在 B 中，并且 B 中必然含有至少一个元素它不在
A 中 我们想强调一点就是集合中的元素的顺序是没有关系的 并且集合中的元素是不具重复的。
也就是说比如说大 A 中出现了两次 小 x
的话，那么我们在最后的表达中它等价于只出现了一次 x
这里我们想介绍两个在 后面也会一直用到的对象。
一个是无序二元组，一个是有序二元组 无序二元组其实就是一个含有两个元素的这样 一个集合。
我们说用这里的 花括号包含了 {x，y}
来表示，要注意它 因为它本身是一个集合，所以 {x，y}
集合等于 {y，x} 这样的一个集合 当然如果 x 和 y
相等的话，我们刚才提到了重复的元素 它会等价于只含有一个元素
x 这样的一个集合 那什么是有序二元组呢？有序二元组注意我们不再用花括弧表示，这里是用了圆括弧
有序二元组的一个重要特点是说：我们说一个 有序二元组 {x，y}
与另外一个有序二元组 {x´，y´} 相等 当且仅当它们的第一个元素也就是
x 和 x´ 相等，并且它们的第二个元素也就是 y 和 y´ 相等
注意在这里，一般来说 {x，y} 的有序二元组和 {y，x}
所对应的有序二元组就不再一样 我们想提一句的是实际上有序二元组可以通过集合来定义出来
但是对于本课程而言，我们仍然把有序二元组作为一个单独的对象，在这里给出了它的这样- 一个定义
好了我们接下来想介绍一下集合上的一些操作 我们看一个例子，比如说大
A 是包含 {1，2，4} 三个元素，大 B 集合是包括 {2，3} 两个元素
我们首先想看的第一个操作是两的 A 次方 这样一个符号，它表示的集合的幂集。
什么是幂集？就是说我们取大 A 集合的所有子集 把它在这里列出来，我们说空集是任何集合的子集
接着我们考虑了只包含 A 中一个元素所形成的集合，分别是 包含只包含
{1} 的集合、 只包含 {2} 的集合和只包含 {4} 的集合 接着第三行列出来的是包含了
A 中两个元素所形成的集合，分别是 {1，2}、 {1，4} 和
{2，4} 子集 然后最后一行也就是第四行的这个
集合呢，就是大 A 集合本身，任何集合都是它本身的一个子集
接着我们看集合间的第二个操作，是 A 并上 B A 并上
B 的意思是我们把 A 和 B 中的元素放在一起
大家可以看到对于我们给出这个例子放在一起 就得到一个新的集合，是
{1，2，3，4} 含有四个元素的集合 接着我们第，集合的交
A 交上 B 是说我们取两个集合中的共同的部分
那么在这个例子中，它是生成一个集合是只包含元素 2 那么什么是接下来这个操作是
A 减去 B 呢？ 就是在 A 集合中除掉也在 B 集合中的元素
对我们这个特殊的例子来说，我们说 2 这个元素在 A 中也在
B 中，所以说我们在 A 减去 B 的时候就得到了 {1，4}
这样一个集合 那么最后一个集合操作我们把它叫做笛卡尔积，表现写成是两个集合相乘的这样一个形式
它会输出什么呢？它会输出一个有序二元组所组成的集合 这里面有序二元组的第一元素都是来自
A ，而第二个元素都来自 B 比如说我们看第一行，我们说 1
是来自 A 的，2 是来自 B 类似地，1 是来自 A ，3
是来自 B 那么我们说它第一个元素一共有三种取法，而第二项元素一共有两种取法
所以它的笛卡尔积中间的元素的大小，元素的个数一共是有六个
好了我们说关于集合 有一些基本的等式，比如说并集的交换
律，交集的交换律以及并和交之间的分配律 以及在这里最后两行，是那 著名的德摩根律。
因为这门课程不是一门专门的集合 论课程，所以我们在这里只是简单地罗列了一下这些等式关系
还有一个在本课程中会很重要的概念是函数 小
f（x）→y 它表示一个定义域有大 X ，值域为
Y 的这样一个函数 我们说函数的重要的特点是说 对大
X 中的每个函数都有大 Y 中唯一的一个值 与这个输入所对应
那么我们定义函数的复合就说给了两个函数，我们已经知道小 f 是 从
X 到 Y 的这样一个函数，小 g 是从 Y 到 Z 的一个函数，那么复合函数是什么呢？我们说
g 复合 f 定义域为，我们先使用小 f 函数 得到小
f（x） ，然后再把小 f（x） 的值通过 g 函数映射到 Z
上的一个值 我们看一个例子，我们说小 f 是从实数到实数的一个函数，它是定义为
sinx 而 g 是从实数到整数的一个函数，它是定义为 x 的向上取整
那么这两个函数复合简单地推导就它是 sinx 函数向上取整。
它就是一个从 实数到整数的这样一个函数
有一些特殊而重要的函数 就说什么是单射函数？就是说如果不同的
输入，它一定会对应不同的输出的话，那么我们称这样的函数具有单射性质 比如说自然数到自然数所定义的
f(x) = x + 1 这个函数 它显然是一个单射函数。
第二个重要的函数是满射函数 就是我们说一般来讲，给了一个函数，它的定义域
定义域中的每一个输入都一定有一个值，但是值域中的每一个元素不一定在 大
X 中有一个对应的原像，但是满射函数是说，如果对大 Y
中的 任何一个值都一定能够找到一个原像小 x，使得小 f(x)
= y 的话 那么这就是一个满射函数，我们看一个例子，是从
去掉零的整数集合映射到自然数的取 绝对值的这样一个函数，我们说，很显然这是一个满射函数
那什么是双射函数呢？就是说一个函数如果 它既是一个单射函数，也就是说不同的输入对应到不同的输出
它又是一个满射函数，也就对每一个值，它都能找到一个原像的话，那么我们称这样的函数是- 一个双射函数
双射函数在我们后续课程中会变得非常重要 我们看一个例子，就说还是实数到实数的这样一个函数
f(x) = x³ 可以验证它确实是一个单射函数，也是一个满射函数
我们把函数的概念推广就可以得到关系 什么是集合 A 上的一个关系
R？我们说 R 是 A x A，也就是 A 的笛卡尔积的一个子集
我们用 xRy 这个符号来表示 (x,y)
这个有序对是属于 R 的，要特别注意的是，我们这里现在 使用的是有序对。
关系经常我们会用图形 来表示它，以增强我们对它的理解，直观的理解
xRy 经常是用 x，用一个点来表示，y 也用一个点来表示，然后
一个有像编也就是 x 到 y 的这样一个箭头表示这个有序对 (x,y)
在 R 关系中，那么当 x 和 y 相等的时候呢，我们经常是用这样一个
字环，就是从这个点到本身的一个箭头来表示 xRx
我们说关系也有一些特殊的性质 对 A 上的关系
R，我们说 R 具有，第一个是自反性，自反性是说 对任意的
A 中一个元素小 x，如果 (x,x) 这个有序对它都在关系
R 中，那我们称它为一个自反的关系，用图象来表示的话，就是对每一点
x 它都有到自己的一个环 我们看一个例子，就是自然数上的小于等于关系，我们说它满足自反性，因为每一个
自然数都小于等于它本身，第二个是对称性 对称性是定义为对任意的两个
x,y 属于 A，如果 (x,y) 这个有序对在关系 R
中，那么 (y,x) 也一定在关系 R 中，如果这个 y 是满足这个性质的话，我们就称
关系具有对称性，从图形的表示，如果x,y 之间有一个箭头，那么
y 到 x 也必然有一个箭头 我们看一个例子，我们说自然数上的等于关系它是一个自反的关系
因为如果 x,y 都是自然数，x 等于 y 的话，那么显然 y 也是等于 x
的 那么什么是反对称性？反对称性是说对任意两个元素
x,y 如果我既有 xRy，又有 yRx 的话，那么唯一的可能性是 x
和 y 必然相等 换句话说，就说如果 x 和 y 不相等的话
它们之间不可能有 x 到 y 的箭头以及 同时有 y
到 x 的箭头，我们看一个反对称性的一个例子，我们说
自然数上的小于等于关系是一个反对称关系，因为如果 x 小于等于 y，又有
y 小于等于 x 的话 在自然数上一定能够推出 x 和 y 一定是相等
最后一个重要的性质是传递性，我们说对三个元素 x,y,z
传递性说，如果 xRy 和 yRz 同时成立，那么我们一定能够得到
(x,z) 这个有序对它也在关系 R 中 从图像来讲，如果
x 到 y 有一个箭头，y 到 z 有一个箭头 那么我们应该能够得到 x
到 z 也有一个箭头 一个简单的例子，还是自然数上的小于等于关系，三个自然数
x 小于等于 y，y 小于等于 z 的话，那么自然数上能够推出 x 一定是小于等于 z
的 我们从关系的特殊的性质能够进一步导出一些
重要关系的定义，第一个是等价关系 就是说，如果这个关系同时具有自反性、
对称性 和传递性的话，那么我们称这样的一个关系是等价关系
还是看一个例子，这里是说自然数上的 ≡6 相等的关系，我们说它是一个等价关系
≡6 相等的定义是说两个自然数 x 和 y 如果它们除以 6
的余数是相等的话，那么我们就说它是 ≡6 相等，比如说 6 和 12
除以 6 的余数都是 0，那么它们 ≡6 相等 类似的 1 和 7 除以 6 都是余数为
1，那么也是 ≡6 相等 可以证明它是自反、 对称并且是传递
那么什么是偏序关系？偏序关系我们说一个关系 R
它如果同时具有自反性 反对称性和传递性，那么我们称它为一个 偏序关系。
注意等价和偏序关系的区别就在于 一个是用对称性来定义，另外一个是用反对称性
我们同样的看一个，一个偏序的例子，我们说自然数上的小于等于关系就是一个偏序关系
显然它满足自反，任何自然数小于等于它本身，第二个是反对称性，我们刚才讲了，x 小于等于
y，y 也小于等于 x 的话 那么 x 和 y 必然相同，我们讲了等价关系
之后，我们想要引入一个重要的概念，是所谓的等价类 就说我们已经知道
R 是一个等价关系，那么我们定义 R[x] R[x]
被定义为什么呢？定义为一个集合，它是所有的 y x 和
y 这个有序对在关系 R 中 用 R[x] 来表示元素 x 在关系
R 下的等价类 我们还是看一个例子，我们说自然数上的那个
≡6 相等的关系，刚才我们 讲了它是一个等价关系，那么这个 ≡6
相等的关系，它所定义出来的等价类是什么样子呢？ 我们说元素
0 在≡6 相等这个关系下的包含
所有除以 6 余数为 0 的这些数，比如说 0,6,12
等等，再比如说看最后一个 当我们输入为 5 的时候
它是，这个等价类中包含了所有的除 6 余 5 的数，那么就是
5,11,17 等等 这样一些数。
我们 说关于等价类，它有一个，有一些比较重要的性质，第一个性质是说
如果我们找到了这个等价类，那么对任意的小 x 属于 A，R[x] 都一定是为 非空的。
第二个性质是说，对任意的两个 x,y 元素 要不然
R[x] 和 R[y] 完全相等，要不然它们相交为空
我们看一下这个性质的证明，第一个性质是比较显然的，我们说大 A 中的每一个元素小 x
它一定是在 R[x] 中，这是由 关系
R 它因为是一个等价关系，所以它一定具有自反性，所以
x 一定是 R[x]，所以 x 一定在 R[x] 中，第二个我们证明
两个等价类它们要不然完全重合，要不然完全不相交，是怎么样证呢 就说如果它们相交为空，那么结论已经成立了
现在我们假设它相交不为空，我们假设有一个小 z，是在 R[x] 交上 R[y]
里面 那么根据定义这说明什么呢？这是说明 xRz 和 yRz
同时成立 那么根据对称性，我们从 xRz 我们能够得到
zRx，类似的我们也可以得到zRy 但这个时候我们考虑
R[x] 这个等价类中的任何一个元素 x'
x' 在 R[x] 中也就是说明了xRx'
成立 那么根据传递性，我们从 xRx'
和 zRx 这两个马上可以得到 zRx'
那么我们这次，再一次使用传递性，我们是使用了 yRz
和 zRx'，我们用传递性马上可以得到
yRx'，yRx' 根据定义来讲我们就
马上知道 x' 是在 R[y] 中 那么注意到 x' 是 R[x]
中的任意一个元素 前面的推论又说明了x' 也一定在
R[y] 中，所以我们马上得到 R[x] 一定是 R[y] 的一个子集 但这个证明也可以类似地对
R[y] 来进行这样一个推导，我们可以得到 R[y] 也是 R[x]
的一个子集 所以我们把这两部分，这两个子集关系合起来，我们马上就得到了
R[x] 和 R[y] 相等，换句话说，R[x] 和 R[y]
它们如果有一个 相交的元素，那么它们一定是完全重合的，这就得到了我们原始的这样一个性质
等价类，它们要不然相交为空，要不然是完全重合
一个相关的重要概念叫做划分，就是给了一个集合
A，如果我们把它的一些子集放在一起 把它记成 π，π中间的元素
B1，B2 一直到Bn 每一个都是 A 的一个子集，并且这个 π
中的每一个元素它们满足什么性质？满足不相交性，也就说 i
和 j 不相等的时候 Bi 和 Bj 的交一定为空，但是它
同时又满足第三个条件覆盖性，也就说我把所有的这些 B1，B2
一直到 Bn 并起来的话，它得到所有 A 中的元素，那么 这样的一个 π
叫做原始 A 的一个划分 大家可以看到划分这个定义本身是简单的，但是
我们想强调的是有一个重要的划分是什么 是给了集合
A 上的一个等价关系之后，那么我们说等价类集合实际上形成了一个划分
注意我们这里用大 Π，大写的 Π 表示， 大 Π 等于所有的 R[x]
的集合 注意 R[x] 就是我们刚刚定义的，x 元素在关系
R 下的那个等价类 我们说大 Π 一定是一个划分，为什么呢？这个就是我们刚刚所证明的那个一个性质
每一个 R[x] 都一定非空，并且
x 和 y R[x] 和 R[y] 要不然相等，要不然相交为空
并且所有的并起来的话，显然就是得到了整个 A 的这样一个集合 我们要注意这个大
Π 我们在后面，不同的场合都会用到这个定义 好了，我们对那个划分有一个直观的
描述，这里是，我们用一个大圆表示大 A 中所有的元素
那什么，同时又给了 A 上的一个关系 R
它，假设它是一个等价关系，那么我们可以用 等价关系对原始的集合 A 中的元素做划分
比如说第一个扇，第一个扇面中，我们说它放入的是所有跟 R[x] 在关系
R 下相等的那些元素，比如说 R[y] 是另外一些元素，R[z]
是另外一些元素，我们说这些扇面，它们要不然是完全重合，要不然是 完全不相交。
好了，这门课程中我们 还会用到一些逻辑符号，比如说对任意
x，存在 x，否定 合取，析取，还有条件，双向条件以及蕴含，当且仅当关系等
关于这门课中用到的更多的一些基础知识呢，在我们的这两本主要的参考书中都能够
找到，第一章的部分都有详细的介绍。
好了，谢谢大家 [音乐]
