离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
导论
Loading...
來自 Shanghai Jiao Tong University 的課程
离散数学
20 個評分
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
[音乐]
[音乐] [音乐]
各位大家好，本次介绍
离散数学导论，主要会介绍我们后面会用到的一些基本的符号和定义 首先是常用的数集符号。
我们在后面会用 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，否定 合取，析取，还有条件，双向条件以及蕴含，当且仅当关系等
关于这门课中用到的更多的一些基础知识呢，在我们的这两本主要的参考书中都能够
找到，第一章的部分都有详细的介绍。
好了，谢谢大家 [音乐]
