第三章 关系 3.6偏序关系 小于等于关系“”的推广，最基本、最常用的一类序关系 按某方面比较事物并按“程度”确定事物之间的大小次序

Presentation on theme: "第三章 关系 3.6偏序关系 小于等于关系“”的推广，最基本、最常用的一类序关系 按某方面比较事物并按“程度”确定事物之间的大小次序"— Presentation transcript:

1 第三章 关系 3.6偏序关系 小于等于关系“”的推广，最基本、最常用的一类序关系 按某方面比较事物并按“程度”确定事物之间的大小次序
例： 实数集上的大小关系 人的年龄大小关系 字符串的大小关系 自然数集上的整除关系

2 3.6.1偏序关系 定义1 偏序关系 自反、反对称、传递的关系 偏序集：（S，R） 偏序关系R常表示为≤：a≤b，a≥b，a<b，a>b （偏序关系的逆≥也是偏序关系） 例 1 证明“大于或等于”关系(Z，≥）是整数集合上的偏序。 证明： 因为对所有整数a有a≥a，≥是自反的。如果a≥b且b≥a，那么a=b，因此≥是反对称的。最后，因为a≥b和b≥c推出a≥c，所以≥是传递的。从而≥是整数集合上的偏序且(Z, ≥)是偏序集。

3 例 2 证明包含关系是集合S的幂集上的偏序。
证明： 因为只要A是S的子集就有AA，是自反的。因为AB和BA推出A=B，所以它是反对称的。最后，因为AB和BC推出AC， 是传递的。因此，是P(S)上的偏序，且(P(S), )是偏序集。 例 ：（人的集合，长幼关系） （Z，<） （P(S)，） 偏序集中可能有没有关系的元素：（Z+，∣）

4 定义2 可比性 定义3 全序，全序集（链） 例 偏序集（Z，≤）是全序集，因为只要a和b是整数就有a≤b或b≤a。 例 偏序集（Z+ ，|）不是全序集，因为它包含着不可比的元素，例如5 和7。 定义4 良序集：全序集，任意非空子集有最小元 例 ：（Z，≤），（Z+，≤）

5 3.6.2字典序 A1×A2×…×An上的字典序： n个偏序集（A1，≤），（A2，≤），…，（An，≤） 在A1×A2×…×An上定义偏序关系： (a1,a2,…,an)<(b1,b2,…,bn)i，1≤i≤n-1，使a1=b1,a2=b2,…,ai=bi,且ai+1<bi+1 串上的字典序： 偏序集（S，≤），a1a2…am、b1b2…bn是S上的串，t=min(m,n) a1a2…am<b1b2…bn(a1,a2,…,at)<(b1,b2,…,bt)或(a1,a2,…,at)=(b1,b2,…,bt),且m<n

6 3.6.3 哈斯图 哈斯图：点表示元素，大的在上方，小的在下面 若x<y，且没有z，使x<z<y，则在x和y之间画连线 省略线上的箭头，隐含地从上指向下 例 11 画出表示{1，2，3，4，6，8，12}上的偏序{（a,b）|a整除b}的哈斯图。 解 由这个偏序的有向图开始，如图3-6(a)所示。移走所有的环，如图3-6(b)所示。然后删除所有由传递性导出的边。这些边是(1,4),(1,6),(1,8),(1,12),(2,8),(2,12)和（3，12）。排列所有的边使得方向向上，并且删除所有的箭头得到哈斯图。结果的哈斯图显示在图3-6(c). （接下页）

7 （接上页） 图3-6 构造（{1，2，3，4，6，8，12}，|）上的哈斯图

8 例 12 画出幂集P(S)上的偏序{(A,B)|AB}的哈斯图，其中S={a,b,c}.
解 关于这个偏序的哈斯图是由相关的有向图得到的，先删除所有的环和所有由传递性产生的边，即(Ф, {a,b}), (Ф, {a,c}), (Ф,{b,c})，(Ф,{a,b,c}),({a},{a,b,c}),({b},{a,b,c})和({c},{a,b,c})。最后，使所有的边方向向上，并删除箭头。结果的哈斯图如图3-7所示。 图3-7 (P({a,b,c}),) 的哈斯图 · 注意与普通关系的图形表 示的差异：没有画出所有 的二元组 省略了线上的箭头

9 3.6.4 极大和极小元 偏序集（S，≤），a∈S a是极大元：没有比a更大的元素 不b∈S，使a<b b∈S，a≤ba=b a是极小元：没有比a更小的元素 不b∈S，使b<a b∈S，b≤aa=b

10 例 13 偏序集（｛2，4，5，10，12，20，25.｝,|）的哪些元素是极大元素，哪些是极小元素？
解 图3-8关于这个偏序集的哈斯图显示了极大元素是12, 20和25，极小元素是2和5.。通过这个例子可以看出，一个偏序集可以有多于一个的极大元素和多于一个的极小元素。 图3-8 偏序集的哈斯图

11 a是最大元：a比其他所有元素都大 b∈S，b≤a
a是最小元：a比其他所有元素都小 b∈S，a≤b 例 14 确定图3-9的每个哈斯图表示的偏序集是否有最大元素和最小元素。 图3-9 四个偏序集的哈斯图 (接下页)

12 解 哈斯图a）的偏序集的最小元素是a。这个偏序集没有最大元素。哈斯图b）的偏序集既没有最小元素也没有最大元素。哈斯图c）的偏序集没有最小元素。它的最大元素是d。哈斯图d）的偏序集有最小元素a和最大元素d。 例 15 设S是集合。确定偏序集(P(S), )中是否存在最大元素与最小元素。 解 最小元素是空集，因为对于S的任何子集T有T。集合S是这个偏序集的最大元素，因为只要T是S的子集，就有TS。 例 在偏序集(Z+，|)中是否存在最大元素和最小元素。 解 1是最小元素，因为只要n是正整数，就有1|n。因为没有被所有正整数整除的整数，所以不存在最大元素。

13 一些结论： (1)最大（小）元是极大（小）元，反之不一定成立 (2)极大（小）元可以没有，也可以有多个 (3)最大（小）元可以没有，但至多只有一个 (4)有限偏序集一定有极大（小）元 证明：(4)设（X,≤）是偏序集，且X是有限集。 任取X中的元素x1，如果x1不是极小元，那么存在x2∈X，使得x2< x1。如果x2不是极小元，那么存在有限集，上述过程x3∈X，使得x3< x2 < x1。因为X是有限集，上述过程重复k次后（1≤k≤n）,得到xk∈X，使得xk< xk-1 < … < x2 < x1，而且xk是（X,≤）的极小元。同理可证，有限偏序集也一定有极大元。

14 上界：AS，a∈S 若x∈A，x≤a，则称a是A的上界 下界：AS，a∈S 若x∈A，a≤x，则称a是A的下界 例 17 找出在图3-10所示哈斯图的偏序集的子集｛a,b,c｝,{j,h}和｛a,c,d,f｝的下界和上界。 解 ｛a,b,c｝的上界是e,f,j和h，它的唯一的下界是a。{j,h}没有上界，它的下界是a,b,c,d,e和f。{a,c,d,f}的上界是f，h和j，它的下界是a。 图3-10 偏序集 的哈斯图

15 最小上界（上确界）：最小的上界，lub(A)
最大下界（下确界）：最大的上界，glb(A) 例 18 在图3-10所示偏序集中如果｛b,d,g｝的最大下界和最小上界存在，求出这个最大下界和最小上界。 解｛b,d,g｝的上界g和h。因为g<h, g是最小上界。｛b,d,g｝的下界是a和b。因为a≤b，b是最大下界。 例 19 在偏序集(Z+,|)中如果集合{3,9,12}和{1,2,4,5,10}的最大下界和最小上界存在，求出这些最大下界和最小上界。 解 如果3,9,12被一个整数整除，那么这个整数就是{3,9,12}的下界。这样的整数只有1和3。因为1|3，3是{3,9,12}的最大下界。集合{1,2,4,5,10}关系到|的下界只有1，因此1是{1,2,4,5,10}的最大下界。

16 一些结论： 上（下）界可以没有，也可以有多个 上（下）界可以在A中，也可以不在A中 即使有上（下）界，上（下）确界也可以没有 上（下）确界至多只有一个 若某上（下）界在A中，则它必为上（下）确界

17 3.6.5 拓扑排序 例：课程安排 工程任务的安排 与偏序（≤）相容的全序R：R  ≤ 拓扑排序：从偏序求相容的全序的过程 算法：从小到大，每次找出一个极小元，删除；再重复 例 25 找出偏序集({1，2，4，5，12，20}，|)的一个相容的全序。 解 第一步是选择一个极小元素。这个元素一个是1，因为它是唯一的极小元素。下一步选择({2,4,5,12,20}，|)的一个极小元素。在这个偏序集中有两个极小元素，即2和5。我们选择5 。剩下的元素是{2,4,12,20}。在这一步唯一的极小元素是2。下一步选择4，因为它是{4,12,20}的唯一极小元素。因为12和20都是({12,20},|)的极小元素，下一步选哪一个都可以。我们选20，只剩下12作为最后的元素。这产生了全序 1<5<2<4<20<12

18 3.6.6 格 定义 格 偏序集，任意两个元素都有上、下确界。 例 20 确定图3-11的每个哈斯图表示的偏序集是否是格。 解 在a）和c）中的哈斯图表示的偏序集是格，因为在每个偏序集中每对元素都有最小上界和最大下界，读者应该能验证这一点。另一方面，b）所示的哈斯图的偏序集不是格，因为元素b 和c没有最小上界。为此只要注意到d，e和f中每一个都是上界，但这3个元素的任何一个关于这个偏序集中的序都不大于其他2个。 图3-11 三个偏序集 的哈斯图

19 例 21 偏序集(Z+,|)是格吗？ 解 设a和b是两个正整数。这两个整数的最小下界和最大下界分别是他们的最小公倍数和最大公约数，读者应能验证这一点。因此这个偏序集是格。 例 22 确定偏序集({1,2,3,4,5},|)和({1,2,4,8,16},|)是否为格. 解 因为2和3在({1,2,3,4,5},|)中没有上界，它们当然没有最小上界，因此第一个偏序集不是格。 第二个偏序集的每两个元素都有最小上界和最大下界。在这个偏序集中两个元素的最小上界是他们中间较大的元素，而两个元素的最大下界是它们中间较小的元素，读者应能验证这一点。因此第二个偏序集是格。 例 确定(P(S), )是否是格，其中S是集合。 解 设A和B是S的两个子集。A和B的最小上界和最大下界分别是AB和AB，因此(P(S), )是格。

20 习题 1.确定由下面的0-1矩阵表示的关系是否是偏序。 a) b) c) 2.对偏序集({2,4,6,9,12,18,27,36,48,60,72},|)回答下列问题。 a)找出极大元素。 b)找出极小元素。 c)存在最大元素吗？ d)存在最小元素吗？ e)找出{2,9}的所有上界。 f)如果存在，找出{2,9}的最小上界。 g)找出{60,72}的所有下界。 h)如果存在，找出{60,72}的最大下界。 3.给出满足下述性质的偏序集。 a)有一个极小元素但没有极大元素。 b)有一个极大元素但没有极小元素。 c)既没有极大元素也没有极小元素。