离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。
“序”关系
Loading...
来自 Shanghai Jiao Tong University 的课程
离散数学
15 个评分
[音乐]
[音乐] [音乐]
[音乐] 大家好，本次讲解有关序理论的一些知识
我们首先看一些常见的序有关的例子 第一个是整数集合上的小于关系 我们显然都知道 -2
是小于 -1 小于 0 ，小于 1 小于 2 等等这样一些 大小之间的比较。
第二个是我们看实数上的 比较关系，我们知道实数当然包括有理数，也包括无理数
但是一旦给了两个实数，我们总是可以比较它们的大小 这里仍然是看的是实数上的严格小于，这样一个关系
我们看一个生活中的一个例子：我们现在 有三个，有冰箱的这样一个选择，冰箱有三个参数
我们用 V 呢表示冰箱的容积，用 E 来表示耗电量，而用 C
来表示冰箱的价格 并且假设我们总是喜欢容量大、
耗电量低，而价格又便宜的产品 那么我们现在有三个冰箱可选，我们问一下大家会选择哪一个冰箱呢？
我们首先看一下一号和第三号冰箱 注意到第一号冰箱它的容量更大、
耗电量更低 但是第一号冰箱的价格更贵，它是一千五百块，而第三号冰箱只要一千四百块
所以这两个冰箱相比较的话，我们似乎不能马上得出应该选哪一款冰箱
那么我们把角度换一下，我们首先比较第一号冰箱和第二号冰箱
可以看出第二号冰箱它的容量更大，耗电量和第一款冰箱一样，而它的价格更便宜
所以第一和第二号冰箱相比呢，我们肯定会选择第二号冰箱 我们再把第二号冰箱和第三号冰箱相比
我们注意到第二号冰箱同样地容量更大，耗电量更低 而价格更便宜，所以二和三相比，我们无疑会选择第二号冰箱
所以我们刚才得到一个重要的观察，虽然只给我们选一和三的
时候我们选不出来，但是一旦一二三放在一起，我们一定会选择第二号冰箱
好了，我们现在给出偏序的这样一个定义，偏序我们其实在导论中介绍过 我们给了集合
S 上的关系 R，如果它同时满足 自反性、
反对称性和传递性的话，那么这个关系 R 被称为一个偏序 我们回忆一下自反、
反对称和传递的 这样一个定义，自反是说对任意一个元素
x 那么 x 和 x 一定在元关系 R 中 就说从 x
到自身一定有一个自反 那么反对称性是说两个不同的元素
x、 y 一定不会有 xRy 和 yRx
同时成立 传递性是说，如果 xRy 并且 yRz
的话，那么我们能够 马上知道 xz 这个二元对
它一定也在关系 R 中
在后面呢我们固定地用这样一个有序二元组 S、 R 来表示 集合 S 以及集合
S 上的那个偏序关系 R 并且我们把它叫做一个偏序集。
常用地一些偏序符号，我们把它用这样两个符号
第一个我们在后面可能都，为了简便都把它叫做一个小于等于符号，但是写法可能不完全一样
那什么是严格地序关系，严格地序关系是说如果 x 严格地于
y ，或者是 x严格地在 y 前面 当且仅当 x 小于等于 y
，并且 x 和 y 不相等 那么逆序的定义也很自然，就说
x 在 y 的前面，或者叫做 x 大于等于 y 当且仅当 y 是小于等于 x
，或者是在序关系上 y 在 x 之前 如果我们对偏序增加要求
增加一个要求是说给了集合 S 中的任意两个元素 x、 y，x
和 y 都 相互可比较，也就是说一定有 xRy 成立或者是 yRx
成立的话 那么这样的一个特殊地偏序，我们把它叫做一个线性序
就是线性序相对于一般偏序来说，它最大的特点是任何两个元素都是互相可比较的
我们看几个线性序的例子：首先是自然数上的小于与等于关系，它当然是一个
线性序，因为任何两个自然数之间互相可比较 以及整数上的小于等于关系，以及实数上的小于等于关系都类似的可以
很容易地证明，它们确实是满足线性序的定义 我们再看一些非线性的偏序的例子
比如说自然数上的整除关系，什么是整除关系？我们说 a 整除
b ，用这样一个符号表示，当且仅当存在自然数 c ，使得 b 等于
a 乘以 c，换句话说 a 是 b 的一个因子。
我们说 这个整除关系它不是一个线性序，比如说我们是说 2
不能够整除 3 ，也就是在这个 线性序关系下，2
和 3 不可比较，类似地 3 也不能整除 2 第二个例子是集合上的子集关系，如果这个符号大家还记得的话
是集合上的幂集关系，它包含了 A 的所有子集，我们说集合 A 上的子集关系也不是一个线性序
我们考察比如说 A 中间包含了两个元素 a 和 b 那么我们说只包含了小
a 的 元素的集合是它的一个子集，只包含了小 b 元素的
集合呢，也是 A 的一个子集，但是这两个集合互相之间
在子集关系下，互相不可比较，所以它不是一个线性序 然后冰箱选择的例子我们也看到它
不是一个线性序，第一号冰箱和第三号冰箱它们互相不可比较 当然这三个例子也都是偏序，是可以去用偏序的定义去验证的
我们这里想介绍一个很重要的序是叫做字典序 字典序的首先呢，它的组成部分是由
n 个线性序，也就是说 s1 小于等于 1 是第一个偏序集，s2
小于等于 2 是第二个偏序集 sn 小于等于 n 是第 n 个偏序集，注意第
i 个偏序都一定是线性序 那么我们想定义的是有序
n 元组 上的这样的一个序关系，我们给了两个
n 元组 一个是 a1 到 an ，一个是 b1 到 bn。
它们是来自于 s1 乘以 s2 一直就说 n 个集合的笛卡尔集
那么我们定义字典序是怎么样定义的呢？我们是定义 a1
a2、 an 这个有序组在字典序上小于等于 b1、 b2 ，一直到
bn 这个有序组当且仅当 要不然这两个有序组它们完全相等，也就是 ai 等于
bi 第二个是说如果它们两个不相等的话那么是存在
一个下标 i，使得在 i 之前的所有的下标 也就说当
j 小于 i 的时候， aj 和 bj 相等 但是 ai
是严格地小于 bi，注意 ai 小于 bi 是用到的第 i 个 线性序关系。
我们想说这个 n 元字典序呢，它是一个线性序关系
当然我们需要验证，首先要验证它是一个偏序关系，我们也要验证，证给了两个 这样的
n 元的字符串集后，它们一定是可以比较
验证过程并不复杂，这里我们先看一个例子 就说 Sk ，也就说 s1、
s2 一直到 sn 每一个 这样的每一个序关系都是，首先它的集合是
26 个英文字母 xyz 然后小于等于 k
，也就是说第 k 个线性序都是字母序，我们规定 a 小于
b ，b 小于 c 这样 x 小于 y ，y 小于 z 这样一个序关系。
那么在上面的定义下我们 能够得到这样一个六元组 abcdf
在字典序上是小于 等于 abeaay 的，因为它们这里显然是两个
不同的字符串，而它们第一个不同的地方在第三号位置，而第一个是 c
第二个是 e，我们说在字母序下，c 在 e
之前所以 有我们的线性序的定义，就有前面
这个六位的字符串是小于后面这个六位的字符串 我们想证明就是刚刚我们所定义这个
n 元字典序它是一个线性序，我们刚刚也提了，就是要按照它的定义一点一点地去证
这里看一下，比如说证明它的 具有传递性，举一个例子：我们说假设我们已经知道
x 是小于等于 y ，也就在 n 元字典序下小于等于 y ，y 在 n
元字典序下小于等于 z，我们想要证明 x 是小于等于 z 的。
我们现在假设 x 和 y 是不同的，而它们不同的位置在第
i 这个 位置，我们也假设 y 和 z 不同，它们的位置在第
j 这个位置 当然了根据我们的定义我们知道 ai
是小于 bi，bj 是小于 cj 的 那么我们怎么样说明
x 在这个前提下它一定会小于 z 呢？我们会考察这是 ci
这个位置 我们会观察到 ai 是 严格地小于 bi
，但是 bi 和 ci 是相等的，就是作为我在这里用蓝色和红色
分别表示 i 和 j 的位置，也就是 i 和 j 的相对位置而言，
i 是小于 j 的 所以说，那么既然 bj 和 cj 是 y 和 z
第一次不同的地方，所以我马上知道 bi 和 ci 是相等的，然后又由于
ai 小于 bi 等于 ci ，由传递性因为我们说那个
每个既然是一个线性序的话，那它们一定是一个偏序，偏序一定是有传递关系，所以我能够得到 ai 是小于 ci 的。
而之前的位置 它们都是相等，因此我们能够得到 x 是小于 z
当然你完整的证明中，你还要考虑比如说 i 和 j 的位置不是我们刚才说的是 i
小于 j ，而是在另外一种情况下 y 和 z 不同的位置是在
x 和 y 不同的位置之前，也就现在的红色和蓝色这样一个关系
我们同样地要说明 x 一定是小于 z ，那是 怎么样说呢？我们还是要考虑
ai 这样一个元素 我们说 ai 和 bi 一定是相等的，在这种情况下
而 bi 又是小于 ci ，bi 小于 ci ，那么我们能够得到
ai 和 ci 之间的有这样一个偏序关系
还是我想强调说，我用红色和蓝色分别表示出了 y 和 z 的第一个不同的地方，以及
x 和 y 第一个不同的地方，当然完整的证明你还要说明如果
i 和 j 重合 但是证明的思路是一样的。
我想强调的是这个 序本身在不同的场合我们都会用到
就是质点序的这样一个概念。
好了，我们在定义了 定义了偏序关系之后，我们想要介绍一个新的概念，叫做"立即前元"
给了一个偏序集 S 小于等于关系 给了两个元素
x、 y，如果下面这两个条件都满足的话，我们称 x 是 y
的立即前元 第一个我们说是 x 是严格地小于 y ，或者是 x
是严格地排在 y 之前，在你给定的这个偏序下 第二个是说
x 和 y 之间不存在元素 z 使得 x 严格地小于
z ，并且 z 严格地小于 y，那么我们就说 x 是
y 的一个立即前元，这个时候立即前元关系我们用这样一个
x 这样一个小三角 y 的这样一个符号来表示 x、 y 的立即前元
从它这个名字的意思呢，也就说我一旦有了 x
是 y 的立即前元我们马上就知道，在 y 之前 到 x
到达 x 的中间不会出现一个中间的这样一个元素
我们看一个例子，我们是自然数上的整除关系 我们说 2
是 4 的立即前元，4 是 8 的立即前元。
这个是由 整除的定义很容易得到的，但是要注意的是 2 不是 8 的立即前元，因为 2 和 8
之间加了 4 换句话说你如果把立即前元理解成一个关系的话，那么这个关系不具有传递性
类似地在整除关系下， 3 是 6 的立即前元，3 也是 9 的立即前元
而对于任意一个素数 x ，我们都知道 1 一定是 x 的一个立即前元 所以这 2、
3 两条我们能够得到的是多个元素可能有同一个立即前元
而相对地我们说 2 是 10 的立即前元， 5 也是 10
的立即前元，换句话说 一个元素它可能有不止一个立即前元。
我们定义立即前元的目的是为了 介绍哈斯图，什么叫哈斯图？是说给了这样一个
偏序集之后，我们想用图形的方式来表示这个偏序集
我们这个图形表示有两个点，第一个是只保留立即前元关系所对应的边
这就会使得原始的偏序集所对应的图会得到大大化解 第二个是说如果
x 是 y 的立即前元的话，那么代表 y 的点是画在代表 x 点的上方
这个约定是为了一旦我们有了这个约定之后呢，我们就可以连箭头都省掉。
大家回忆我们一开始介绍那个 关系的图形表示的时候， xry 我们说是有一个从 x
到 y 的箭头 但是在哈斯图中我们规定了这样一个顺序关系之后，我们就可以把箭头省掉。
我们看一个例子 1，2，3，4，5 这个集合上的小于等于关系
我们首先用五个点来表示其中的元素 并且我们用直线来表示立即前元关系，我们知道
1 是小于 2 2 是小于 3 ，3 小于 4 ，4 小于 5
，那么这就是它的哈斯图，大家可以看到不但没有箭头 并且比如说我们当然知道
1 是小于 3 的，但是这条边就不用画出来，因为 我们说了只保留立即前元关系对应的边
而且在这里也有一个重要的观察是一旦给了哈斯图，实际上我们能够 恢复出原始的关系，因为我们只要对这个图做一个
传递的闭包的话，那么我们就能够得到原始的那个 所有的关系，所有的关系。
我们再看一个例子 1 到 10 这个 有限的自然数集合上的整除关系
我们说 1 是所有素数的立即前元 我们把剩下的那个立即前元关系补充上
大家可以看到，比如说我们说 2 是 能够整除
8 的，在这个关系中 因为有 4 ，2 是 4 的立即前元， 4
是 8 的立即前元，所以在这里我们 2 到 8 之间的这条边我们是没有画出来
这条边我们是不用画出来，只保留立即前元关系 但是类似的我们想说，最重要的一点是我们
一旦给了哈斯图之后，我们能够恢复出整个的原始的偏序关系，只需要对
它这个图做一个闭包 好了，在定义了序关系之后，我们想定义一些特别重要的对象
我们首先给定义偏序集上的极小元和极大元，什么是极小元？ 我们称
a 是这个偏序集上的极小元，如果不存在 元素比这个
a 要严格地小，就不存在这样的 x x 是严格地小于
a，那么从序的关系上来说，我们 把它叫做极小，而什么是极大呢？就说如果找不到元素比它严格地要大
找不到这样的 x ，x 严格地大于 a，那么我们说在这个序关系下
a 已经是极大的了 看还是看用例子来解释，包含十个自然数的整除关系，哈斯图我们之前已经给出来了
那么这个偏序集上的极小元和极大元是什么？极小元我们说是 1
没有任何元素严格地小于 1 ，而极大元我们说
其实在这个例子下它有五个极大元，包括 8、 6、 9、 10 和
7 这五个元素都找不到元素，在整除关系下严格地比它们大
我们把刚才的例子稍微做一点修改，就说 我们考虑这个集合是从 2 开始的，2、 4、 5、
6、 7、 8 9、 10 ，那么在还是考虑整除关系，我们重新得到一个哈斯图
我们说在这个改过之后的例子中，极小元 就有四个元素是
2、 3、 5、 7 ，极大元仍然是 8、 6、 9、 10 和 7
就是注意在这个例子中，极小元不止一个，极大元 不止一个，并且
7 这个元素很特别的，它既是极小元 又是极大元，没有元素比它小，也没有元素比它更大
在定义了极小元之后 极小元极大元之后，我们还想定义所谓的最大元和最小元
什么是最小元呢？就说如果这个元素 a 它比所有的
x 都要 小，它小于等于所有的 x 的话，那么我们称 a 是一个最小元
类似的什么是最大元，就说如果 a 在偏序关系下是排在所有的
其它元素的后面， x 大于等于 a 这样一个关系成立的话，那么我们把
a 叫做一个最大元 这就一定要小心的是极小元、 极大元和最小元、
最大元的区别 我们还是先看一个例子，理解什么是最小元、 最大元 包含
1 到 10 的自然数集上的整除关系，我们说在这个例子中
它有最小元是 1 ，1 比其它所有的元素都要小
而在这个例子中没有最大元，因为没有一个元素比其它所有的元素都要大 类似的我们把这个例子稍微改一下，把
1 去掉只考虑 2、 4、 5、 6、 7、 8、 9、 10 的集合上的整除关系的话
那么在这个例子中，它既没有最小元也没有最大元 这里就可以看出跟极小元、
极大元之间的区别，因为同样一个例子我们说它有 四个极小元，有五个极大元，但是在
考虑最大元最小元的时候，它最大元最小元都不存在 我们把它的极小元、
极大元和最大元 最小元的定义放在一起，大家可以看出来它们之间的区别
就是极小元是强调没有比它更小的，而最小元是强调它比所有的元素都要小
类似地最大元是说这个元素它比所有的元素都要大
而极大元是说，没有元素比它更大 就这两个之间的区别一定要看清楚
换句话说我们能够知道的是最大元一定是极大元 最小元如果存在的话，一定是极小元。
但是反过来不一定成立 这里我们总结极大元、 极小元、
最大元、 最小元的一个的性质 就是如果给了偏序集
S，如果偏序集中的集合 S 如果是无限的话，那么 极小、 极大、
最大、 最小元都不一定存在 我们通过例子来说明，我们说比如说整数上的小于等于关系
显然，整数中没有极大的整数、 没有极小的整数；相应没有最大的整数、
也没有最小的整数 而我们说，比如说第二个例子是自然数上的小于等于关系
我们说自然数上的小于等于关系，它确实是有最小元，也相应地有极小元，也就是 1 但是它没有极大元，也没有最大元。
那么 S 有限的时候呢，我们说情况 还就有一些不一样，就是说最大元、
最小元不一定存在，就通过我们刚才考查的那个整除的这个例子 我们马上能够举出一个例子，最大元最小元不存在。
但是我们说一旦 S 有限，极大元和极小元一定存在 但是一定要注意这两个的区别，这两段的区别
当 S 无限的时候，四个都可能不存在；但是 S 一旦有限了，我起码知道极大元、
极小元一定是存在的 我们看一下极小元的存在性的证明
我们这也是一个定理，就是任意有限的偏序集中，至少存在一个极小元 证明其实也比较简单，我们首先任意取
S 中的一个元素 x0 我们为什么能够取到 x0，因为我们知道它中间至少存在一个元素，因為它们有自反性嘛
如果 x0 已经是极小元了，那么定理就正好了，就说存在一个极小元
那么如果 x0 不是极小元呢？如果不是极小元，根据我们的定义，我们就说
那么一定能够找到一个 x1，是严格地小于 x0 那么我们现在就问
x1 是否是极小元？如果 x1 是极小元，那么 定理也证完了，如果
x1 不是极小元，我們能够找到 x2 ＜ x1 然后我们对 x2
考查它是否是极小元，就是重复之前的论证 但是因为 S 又是一个有限集合，所以我们知道情况
2 必然在有限步内就能 终止，就是有限步后情况 2 就不成立；换句话说
走了有限步之后，我们一定能找到一个元素，它就是 给定的偏序集中的极小元。
好了，关于偏序 我们想介绍一个相关的一个，一个很有意思的定理，叫做线性扩充定理
它说你任给了一个偏序集，S 小于等于 关系，它们一定存在另外一个线性续集(S,
≤') 注意，(S, ≤')是个线性序集
并且这个线性序集和原始的偏序集之间有什么关系呢 它说原始的如果有
x 是小于等于 y 的话，那么一定能够有在这个线性序中 x 是小于等于
'y 的，但是注意反过来不成立，反过来一般来说是不成立的
这个定理的的证明其实也比较有意思，我们看一下，这个证明呢，是用归纳法来证明 就说，归纳法是，怎么说，我们首先看
即使步然后看归纳步，然后再是说加 1
的情况是否成立 首先我们说即使步，当 S 的规模为 1
的时候 那么这个情况是很简单的，我们把这个所谓的线性序就定义为
原始的序关系就好，它必然是一个，就是只含有一个元素的 Pn 序
一定是一个线性序，当 S 的规模大于 1 的时候
那么根据刚才的定义，我们说它必然有一个，有限的 偏序集中必然有一个极小元
x0，然后我们从 S 中去掉 x0 得到一个集合是 S'，当然 S'
也一定是一个有限的集合 在这里我们给了一个图，注意我用黄色的点和蓝色的点都表示极小元，因为极小元，一般来-
说可能是 不止一个，那么，至少有一个，我们把这个黄色这个点，我们叫做
x0 剩下的这个虚线所包括的部分，我们叫做
S' 我们注意到，我们把原始，原始的偏序关系限制在
S' 上，它还是一个偏序集，这个需要一点证明，但是比较简单，大家课后可以练习一下
但最重要的是，S' 的规模是严格地小于 S，因为它比它少了一个元素
那么我们这个时候就可以利用归纳假设 归纳假设说，那么我对
S' 这个小一点的集合上的偏序关系，偏序集的话，那么它是存在一个线性扩充 这个线性扩充，我用小于等于 ''
来表示 那么我接下来要做的一件事情，因为就是我想要证的是，我是说
S 小于等于这个偏序集上，存在一个线性扩充，那么我现在已经找到了
S' 的线性扩充 那么我就是要把这个 S' 的线性扩充，我对它
放大一点，就得到原始整个集合的线性扩充，那么 我想找的那个
S 小于等于 ' 是什么呢，它是两部分并起来，第一个就是小于等于 ''
这是一个，这是 S' 上的一个线性序关系，它并上，比较有意思的是第二部分
(x0,y)，所有的 (x0,y)，y 是属于 x
的 注意这是，当然是有序对，我们从图象上来表示
我们把，我这里所加入的红色的箭头就是 x0
它跟所有的其他的点，都建立一个有序的这样一个关系 我们想说的是，S
小于等于 '，这是一个线性序，这个怎么样证明呢，我们比如说，要证明任意两个元素都可比较
首先两个元素都来自 S' 的话 两个元素都来自，x,y
都来自 S' 的话，那么因为 小于等于 '' 是一个线性序，所以我已经证好了
第二种情况是 x,y 有一个是 x0，比如说 x 有一个是等于
x0 而且 y 是另外一个元素，那么这个时候我们说，x 和 y
之间可以比较，因为我把 （x0,y）这个有序组放到了小于等于 '
这个集合中 当然我们还，要证明它的线性序，你还要完善比如说，它具有自反
反对称，传递性等等，但这些都是比较简单的部分 但我们想强调的是，一般来说线性扩充并不唯一
为什么呢？因为我们说，我们可以选，在这个例子中，我们可以选黄色的这个极小点 当然我们也，可以在，完全可以选蓝色这个点
作为 x0，那么可能会得到不同的那个线性扩充 好，总结一下本次课的内容，我们主要介绍了偏序
线性序的定义，我们给出了什么是哈斯图这样一个定义，是对原始 原始序关系的这个图上的一个极简表示
然后我们还定义了极大元、 极小元、 最大元、 最小元，要注意这两者的区别
并且我们看了极小元，有限集合极小元存在 性的一个应用，也就是说线性扩充定理的这样一个证明。
好了，谢谢大家 [音乐]
