离散数学特殊关系课件.ppt

资源描述

《离散数学特殊关系课件.ppt》由会员分享，可在线阅读，更多相关《离散数学特殊关系课件.ppt（92页珍藏版）》请在三一文库上搜索。

1、离散数学,2021年5月26日星期三,电子科技大学计算机科学与工程学院,2021/5/26,第7章特殊关系,2021/5/26,7.1 本章学习要求,2021/5/26,判定下列关系具有哪些性质,在全体中国人所组成的集合上定义的“同姓”关系；对任何非空集合A，A上的全关系；三角形的“相似关系”、“全等关系”；直线的“平行关系”； “朋友”关系。,解：1, 2, 3都具有自反性，对称性和传递性；具有反自反和，对称性，不具有自反和传递性；具有自反和对称性，不具有传递性。,等价关系,2021/5/26,7.2 等价关系,定义7.2.1 设R是定义在非空集合A上的关系，如果R是自反

2、的、对称的、传递的，则称R为A上的等价关系。,由定义7.2.1知：（1）关系R是等价关系当且仅当R同时具备自反性、对称性和传递性；（2）关系R不是等价关系当且仅当R不具备自反性或对称性或传递性。,2021/5/26,例7.2.1,不具有对称性,不具有对称性，自反性,是等价关系,判定下列关系是否是等价关系? 幂集上定义的“”关系；整数集上定义的“”关系；全体中国人所组成的集合上定义的“同性别”关系。,2021/5/26,例7.2.2,在时钟集合A0,1,2,23上定义整除关系： R|x,yA)(x-y)被12所整除)。（1）写出R中的所有元素；（2）画出R的关系图；（3）证明R是一

3、个等价关系。,2021/5/26,解,（1）R=, , , , （2）此关系的关系图：,2021/5/26,对任意xA， R，即R是自反的。对任意x,yA，若R， R，即R是对称的。对任意x,y,zA，若R且R， R，即R是传递的。由1,2,3知R是等价关系。,解 (续),有(x-x)被12所整除，所以有(x-y)被12整除，则(y-x)-(x-y)被12整除，所以，有(x-y)被12所整除且(y-z)被12所整除，所以(x-z)(x-y)(y-z)被12所整除，所以，,2021/5/26,从例7.2.2可以看出,关系R将集合A分成了如下的12个子集： 0,12，1,13，2,14，

5、-y)+(y-z)得n|(x-z)，所以，R，即R是传递的。由(1)、(2)、(3)知，R是Z上的等价关系。,事实上，对任意正整数n，整数集合Z的任意非空子集A上的关系 R=|x,yA(n|(x-y) 都是等价关系。,2021/5/26,以n为模的同余关系,上述R称为Z上以n为模的同余关系(Congruence Relation)，记xRy为 xy(mod n) 称为同余式。如用resn(x)表示x除以n的余数，则 xy(mod n) resn(x)resn(y)。此时，R将Z分成了如下n个子集： ,-3n,-2n,-n,0,n,2n,3n, ,-3n+1,-2n+1,-n+1,1,n+1

6、,2n+1,3n+1, , -3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2, ,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1,2021/5/26,说明,这n个Z的子集具有如下特点：在同一个子集中的元素之间都有关系R；不同子集的元素之间没有关系R；不同子集的交集是空集；所有这些子集的并集就构成集合Z。,称为集合Z的一个划分,2021/5/26,7.2.2 集合的划分,定义7.2.2 给定非空集合A，设有集合S=S1,S2,S3,Sm。如果满足 SiA且Si，i1,2,m； SiSj，ij，i,j1,2,m；。,则集合S称作集合A的一个划分(Part

7、ition)，而S1, S2,Sm叫做这个划分的块(Block)或类(Class)。,2021/5/26,例7.2.4,试给出非空集合A上2个不同的划分解（1）在A中设定一个非空真子集A1，令A2=A-A1，则根据集合划分的定义，A1,A2就构成了集合A的一个划分，见图(a)；（2）在A中设定两个不相交非空真子集A1和A2，令A3=A-(A1A2)，则根据集合划分的定义，A1,A2,A3就构成了集合A的一个划分，见图(b)。,2021/5/26,例7.2.5,设设A=0,1,2,4,5,8,9， 1、写出R是A上的以4为模的同余关系R的所有元素； 2、求分别与元素1,2,4有关系R的所有元

8、素所作成的集合。,解：1、R=, , ,。显然，R是A的一个等价关系。,2021/5/26,集合1,5,9称为元素1关于等价关系R的等价类，记为1R，即1R =1,5,9；,解,2、与元素1有关系R的所有元素所作成的集合1,5, 9；与元素2有关系R的所有元素所作成的集合2；与元素4有关系R的所有元素所作成的集合0,4, 8。,2R= 2， 4R = 0,4,8。,2021/5/26,7.2.3 等价类与商集,定义7.2.3 设R是非空集合A上的等价关系，对任意xA，称集合 xRy|yAR 为x关于R的等价类(equivalence class)，或叫作由x生成的一个R等价类，其中x称为

9、xR的生成元(或叫代表元，或典型元)(generator) 。,2021/5/26,由定义7.2.3可以看出：,等价类产生的前提是A上的关系R必须是等价关系； A中所有与x有关系R的元素y构成了xR； A中任意一个元素一定对应一个由它生成的等价类； R具有自反性意味着对任意xA，xR； R具有对称性意味着对任意x,yA，若有yxR，则一定有xyR。,2021/5/26,例7.2.5(续),设A=0,1,2,4,5,8,9，R是A上的以4为模的同余关系。求（1）R的所有等价类；（2）画出R的关系图。解：（1）1R1,5,95R9R； 4R0,4,8=0R8R。（2）,2R=2；,2021/

10、5/26,定理7.2.1,设R是非空集合A上的等价关系，则有下面的结论成立： 1)对任意xA，xR； 2)对任意x,yA， a)如果yxR，则有xR=yR， b)如果y xR，则有xRyR。 3) A；,2021/5/26,证明 1）,对任意xA，因为R是等价关系，所以R是自反的，因此R，即xxR，故xR。,2021/5/26,证明 2),对任意x,yA， a)若yxR，则R。对任意zxR，则有：R，又R，由R的对称性有：R，由R的传递性有：R。所以zyR，即：xRyR。对任意zyR，则有：R，又R，由R的传递性有：R。所以，zxR，即： yRxR。所以，xRyR。,b)若

11、yxR，设xRyR，则存在zxRyR。即zxR，zyR，则有：R，R，由R的对称性，R。由R的传递性有：R，即yxR，矛盾。所以xRyR。,2021/5/26,因为对任意xA，xR A，所以 A。对任意xA，因R是自反的，所以R，即xxR。所以x，即A 。故=A。,证明 3),2021/5/26,商集,定义7.2.4 设R是非空集合A上的等价关系，由R确定的一切等价类为元素构成的集合，称为集合A关于R的商集(Quotient Set)，记为A/R，即 A/RxR|(xA),例7.2.6 设集合A=0,1,2,4,5,8,9，R为A上以4为模的同余关系。求A/R。解根据例7

12、.2.5，商集 A/R=0R,1R,2R=0,4,8,1,5,9,2。,2021/5/26,例7.2.7,设集合A=1,2,3,4,5,8，R为A上以3为模的同余关系。求A/R。解根据例7.2.3知，A上以3为模的同余关系R是等价关系。因为1R=1,4=4R，2R=5R=8R=2,5,8， 3R=3，所以根据商集的定义， A/R=1R,2R,3R=1,4,2,5,8,3。,2021/5/26,计算商集A/R的通用过程,任选A中一个元素a，计算aR；如果aRA，任选一个元素 bA-aR，计算bR；如果aRbRA，任选一个元素 cA-aR-bR，计算cR；以此类推，直到A中所有元素都

13、包含在计算出的等价类中。,2021/5/26,7.2.4 等价关系与划分,定理7.2.2 设R是非空集合A上的等价关系，则A对R的商集A/R是A的一个划分，称之为由R所导出的等价划分。定理7.2.3 给定集合A的一个划分=A1,A2,An，则由该划分确定的关系 R=(A1A1)(A2A2)(AnAn) 是A上的等价关系。我们称该关系R为由划分所导出的等价关系。,2021/5/26,定理7.2.3的证明,证明 1）R是自反的对任意xA，因为(A)是A的一个划分，所以存在一个划分块Ai(A)，使得xAi，显然x和x同属于(A)的一个划分块Ai，故 R，所以R是自反的。 2)R是对称的对任

14、意x,yA，若R，则x和y同属于(A)的一个划分块Ai，因此y和x同属于(A)的一个划分块Ai，故 R，所以R是对称的。,2021/5/26,定理7.2.3的证明(续),3) R是传递的对任意x,y,zA，若R，R，则x和y同属于(A)的一个划分块Ai，y和z同属于(A)的一个划分块Aj，因此yAiAj，由于不同的划分块交为空，所以Ai=Aj，因此x和z同属于(A)的一个划分块Ai，即 R，所以R是传递的。综上，由1)、2)、3)知，R是A上的等价关系。,说明：集合A上的等价关系和A的划分是一一对应的。,2021/5/26,例7.2.8,设A=1,2,3，求A上所有的等价关系及其对应的

15、商集。解只有1个划分块的划分为S1，见图(a)；具有2个划分块的划分为S2、S3和S4，见图(b)、(c)和(d)，具有3个划分块的划分为S5，见图(e)。,2021/5/26,例7.2.8(续）,假设由Si导出的对应等价关系为Ri，i=1,2,3,4,5，则有 R1=S1S1=AA， A/R1=1,2,3； R2=1,21,233 =, A/R2=1,2,3； R3=1,31,322 =, A/R3=1,3,2；,2021/5/26,例7.2.8(续）,R4=2,32,311 =,， A/R4=1,2,3； R5=112233 =,=IA， A/R5=1,2,3。,2021/5/26,例

16、7.2.9,设R是A上的自反和传递关系，S也是A上的关系，且满足：对任意x,yA， S (RR) 证明 S是A上的等价关系。证明（1）S是自反的：对任意aA，因R是自反的，所以R，由R并且R和S的定义得 S，即S是自反的。,2021/5/26,例7.2.9 (续),（2）S是对称的：对任意a,bA，若S，则由S的定义得R并且R，即有R并且R，所以有 S，即S是对称的。,2021/5/26,例7.2.9 (续),（3）S是传递的：对任意a,b,cA，若S，S，则由S的定义得R且R和R且R。因为R是传递的，所以有R和R。从而， S，即S是传递的。由(1),(2)和(3)知，S是A

17、上的一个等价关系。,2021/5/26,例7.2.10,设R是集合A上的关系。对任意a,b,cA，若R并且R，则有R，则R称为A上的循环关系。试证明R是A上的等价关系的充要条件是R是A上的循环关系和自反关系。,2021/5/26,证明“”,若R是等价关系。 1) 显然R是自反的。 2) 对任意a,b,cA，若R，R，则由R是对称的，有R并且R，由R是传递的，所以， R。即R是A上的循环的关系。由1)，2)知R是自反的和循环的。,2021/5/26,若R是自反的和循环的。 1) 显然R是自反性的； 2) 对任意a,bA，若R，则由R是自反的，有R，因R是循环的，所以 R且R，故 R，

18、即R是对称的。 3) 对任意a,b,cA，若R，R，由R对称的，有R并且R；由R是循环的，所以由R和R得 R，即R是传递的。由1)、2)、3)知R是A上的等价关系。,证明“”,2021/5/26,7.2.6等价关系的应用,例7.2.11 在图7.2.5中，点i和j之间有路当且仅当从结点i通过图中的边能够到达结点j。规定对任意结点i，i和i之间一定有路。定义R如下： Ri和j之间有路。试说明该关系R是否可以给定结点集A=1,2,3,4,5, 6,7,8一个划分？如果能，请给出具体的划分。,2021/5/26,解,（1）由于规定任意结点i与他自身之间一定有路，因此R，即R具有自反性；（2

19、）若R，则两个结点i和j之间存在路，当然也存在j和i之间的路，所以R，即R具有对称性；（3）若R，R，则结点i和j之间有路，j和k之间也有路，从而i到k之间存在经过j的路，即有R，因此得到R具有传递性。由(1)、(2)和(3)知，R是等价关系。,2021/5/26,解(续),于是所有不同的等价类为： 1R=1,2,3,4，5R=5,6,7，8R=8。根据定理7.2.2知， A/R=1R,5R,8R=1,2,3,4,5,6,7,8 就是A的一个划分。,2021/5/26,例7.2.12,信息检索系统中的信息有离散数学，高等数学，计算机操作系统，计算机网络，数据结构，编译原理，软件工程，计算

20、机组成原理。试给该信息检索系统指定三种不同的划分。解设A=离散数学，高等数学，计算机操作系统，计算机网络，数据结构，编译原理，软件工程，计算机组成原理，则,2021/5/26,解（续）,划分1：含关键词离散数学，则 A=离散数学,高等数学,计算机操作系统,计算机网络,数据结构,编译原理,软件工程,计算机组成原理；划分2：含关键词数学，则 A=离散数学,高等数学,计算机操作系统,计算机网络,数据结构,编译原理,软件工程,计算机组成原理；划分3：含关键词计算机，则 A=离散数学，数据结构,编译原理,软件工程,高等数学,计算机操作系统,计算机网络,计算机组成原理。,2021/5/26,总结,

21、熟记等价关系的定义；利用等价关系的定义证明一个关系是等价关系；给定A上的等价关系R，会求所有的等价类和商集A/R；并求出对应的集合的划分；给定集合A上的划分，会求对应的等价类。,2021/5/26,判定下列关系具有哪些性质,对任何非空集合A，A上的恒等关系；多边形的“相似关系”、“全等关系”；集合A的幂集P(A)上定义的“包含关系”；集合A的幂集P(A)上定义的“真包含关系”。,解：1，2都具有自反性，对称性和传递性，是等价关系； 3 具有自反性，反对称性和传递性； 4 具有反自反性，反对称性和传递性。,偏序关系,拟序关系,2021/5/26,7.3 次序关系,拍摄一张室内闪光灯照

22、片，需要完成如下任务： 1、打开镜头盖； 2、照相机调焦； 3、打开闪光灯； 4、按下快门按钮。这些任务中有的必须在其他任务之前完成。例如，任务1必须在任务2之前完成，任务2，3必须在任务4之前完成，即任务之间存在“先后”关系，即次序关系。,2021/5/26,7.3.1 拟序关系,定义7.3.1 设R是非空集合A上的关系，如果R是反自反和传递的，则称R是A上的拟序关系(Quasi-Order Relation)，简称拟序，记为“”，读作“小于”，并将“”记为“ab”。序偶称为拟序集(Quasi-Order Set)。,2021/5/26,由定义7.3.1知：,R是拟序关系 R同时具有反自

23、反性和传递性； R不是拟序关系 R不具有反自反性或者传递性；拟序“”的逆关系“-1”也是拟序，用“”表示，读作“大于”。,2021/5/26,例7.3.1,设R是集合A上的拟序关系，则R是反对称的。证明用反证法。假设R不是反对称的关系，则存在x,yA，且xy，满足R并且R。因为R是A上的拟序关系，所以R具有传递性，从而有R。这与R是反自反的矛盾，从而假设错误，即R一定是反对称的。,2021/5/26,例7.3.2,判断下列关系是否为拟序关系（1）集合A的幂集P(A)上定义的“”；（2）实数集R上定义的“小于”关系()；解（1）集合A的幂集P(A)上定义的“”具有反自反性和传递

24、性，所以是拟序集。（2）实数集合R上定义的“小于”关系()具有反自反性和传递性，所以是拟序集。,2021/5/26,7.3.2偏序关系,定义7.3.2 设R是非空集合A上的关系，如果R是自反的、反对称的和传递的，则称R是A上的偏序关系(Partial Order Relation)，简称偏序，记为“”，读作“小于等于”，并将“”记为ab。序偶称为偏序集(PartialOrder Set)。常将ab且ab记为ab。,2021/5/26,由定义7.3.2知,（1）R是偏序关系 R同时具有自反性、反对称性和传递性；（2）R不是偏序关系 R不具备自反性或反对称性或传递性；（3）偏序“”的逆关

25、系“-1”也是一个偏序，我们用“”表示，读作“大于等于”；（4）(-IA)为A上的拟序关系，(IA)为A上的偏序关系。,2021/5/26,试判断下列关系是否为偏序关系 (1) 集合A的幂集P(A)上的包含关系“”； (2) 实数集合R上的小于等于关系“”； (3) 自然数集合N上的模m同余关系； (4) 自然数集合N上的整除关系“|”； (5) 正整数集合Z+上的整除关系“|”； (6) ALGOL或PL/I等都是块结构语言，设B=b1,b2,bn是这种语言的一个程序中的块的集合。对所有i和j，定义关系“”如下： bibj当且仅当bi被bj所包含。,例7.3.3,2021/5/26,解,根

26、据偏序关系的定义知， (1)，(2)，(5)，(6)所对应的关系同时具有自反性，反对称性和传递性，所以都是偏序集； (3)所对应的关系不具有反对称性，所以它不是偏序关系； (4)所对应的关系不具有自反性，所以它不是偏序关系。,2021/5/26,例7.3.4,设X是所有4位二进制串的集合，在X上定义关系R：如果s1的某个长度为2的子串等于s2的某个长度为2的子串，则R，例如因为0111和1010中都含有子串01，所以R。试判断R是否是一个偏序关系。,2021/5/26,解,对任意s,tX，如果R，则s的某个长度为2的子串等于t的某个长度为2的子串，也可以说t的某个长度为2的子串等于s的某个长

27、度为2的子串，即有R，从而R是对称的。根据对称性，存在0111，1010X，有R且R ，但是01111010，从而R不是反对称的，从而R不是偏序关系。,2021/5/26,例7.3.5,考虑任务集T，它包含了拍摄一张室内闪光照片必须按顺序完成的任务： 1、打开镜头盖； 2、照相机调焦； 3、打开闪光灯； 4、按下快门按钮。在T上定义关系R如下： R如果i=j或者任务i必须在任务j之前完成。试判断R是T上的偏序关系并画出它的关系图。,2021/5/26,根据R的定义，有 R=, ,。根据自反、反对称和传递的定义知，关系 R具有自反性，对称性和传递性。从而R是偏序关系，其关系图如右图所

28、示。,解,2021/5/26,2 哈斯图,用小圆圈或点表示A中的元素，省掉关系图中所有的环；（因自反性) 对任意x,yA，若xy，则将x画在y的下方，可省掉关系图中所有边的箭头；（因反对称性）对任意x,yA，若xy，且不存在zA，使得 xz, zy，则x与y之间用一条线相连，否则无线相连。（因传递性）,2021/5/26,例7.3.6,画出例7.3.5中关系R的哈斯图。解例7.3.5中关系R的哈斯图如下图所示。,2021/5/26,例7.3.7,设A=2,3,6,12,24,36，“”是A上的整除关系R，画出其一般的关系图和哈斯图。解由题意可得 R=, , , ,，从而得出该偏

29、序集的一般关系图和哈斯图如下：,2021/5/26,例7.3.7 （续）,关系图,哈斯图,2,3,6,12,36,24,2,3,6,12,36,24,2021/5/26,3 特殊元素,定义7.3.3 设是偏序集，B是A的任何一个子集，若存在元素bB，使得对任意xB，都有xb，则称b为B的最大元素，简称最大元；都有bx，则称b为B的最小元素，简称最小元；满足bx x=b，则称b为B的极大元素，简称极大元；满足xb x=b，则称b为B的极小元素，简称极小元。,2021/5/26,定义7.3.3可以符号化为,2021/5/26,注意,（1）B的最大元、最小元、极大元和极小元如果存在，一定在B

30、中；（2）b是B的最大元 B中所有其它元素都比b小； b是B的最小元 B中所有其它元素都比b大； b是B的极大元 B中没有比b大的元素； b是B的极小元 B中没有比b小的元素。,2021/5/26,例7.3.8,在例7.3.7中，设B1=6,12，B2=2,3，B3=24, 36，B4=2,3,6,12是集合A的子集，试求出B1,B2, B3和B4的最大元，最小元，极大元和极小元。解见下表。,12,6,12,6,无,无,无,无,无,2,3,2,3,24,36,24,36,12,12,2,3,2021/5/26,定义7.3.4,设是偏序集，B是A的任何一个子集。若存在元素aA，使得对任意

31、xB，都有xa，则称a为B的上界；对任意xB，都有ax，则称a为B的下界；若元素aA是B的上界，元素aA是B的任何一个上界，若均有aa，则称a为B的最小上界或上确界。记a=SupB；若元素aA是B的下界，元素aA是B的任何一个下界，若均有aa，则称a为B的最大下界或下确界。记a=InfB。,2021/5/26,由定义7.3.4知,子集B的上、下界和上、下确界必须在集合A中寻找；子集B的上、下界不一定存在，如果存在，可以不唯一的；子集B的上、下确界不一定存在，如果存在，则一定唯一；子集B有上(下)确界，一定有上(下)界；反之不然。,2021/5/26,例7.3.9,在例7.3.7中，

32、设B1=6,12，B2=2,3是集合A的子集，试求出B1，B2的上界、下界、上确界和下确界。解见下表。,12,24,36,2,3,6,12,6,6,12,24,36,无,6,无,2021/5/26,例7.3.10,A=x1,x2,x3,x4，A上定义偏序集的哈斯图如下图所示。求B=x1,x2和C=x3,x4上界、下界、上确界和下确界。解见右表。,无,x3,x4,无,无,x1,x2,无,无,无,2021/5/26,例7.3.11,设集合A=a,b,c,d,e,f,g,h，对应的哈斯图见右图。令B1=a,b，B2=c,d,e。求出B1，B2的最大元、最小元、极大元、极小元、上界、下界、上确

33、界、下确界。,无,无,a,b,a,b,c,d,e,f,g,h,无,c,无,无,c,d,e,c,h,c,a,b,h,c,2021/5/26,结论,(设是一偏序集，B是A的子集) （1）若b是B的最大元，则b一定是B的极大元，上界和上确界；反之，则不然；（2）若b是B的最小元，则b一定是B的极小元，下界和下确界；反之，则不然。,2021/5/26,定理7.3.1,设是一偏序集，B是A的子集。则： b是B的最大元 b是B的极大元、上界、上确界； b是B的最小元 b是B的极小元、下界、下确界； a是B的上确界且aB a是B的最大元； a是B的下确界且aB a是B的最小元。,2021/5/26,定理7

34、.3.2,设是一偏序集，B是A的子集。则：若B存在最大元，则B的最大元是惟一的；若B存在最小元，则B的最小元是惟一的； b是B的最大元 b是B的惟一极大元； b是B的最小元 b是B的惟一极小元；若B存在上确界，则B的上确界是惟一的；若B存在下确界，则B的下确界是惟一的。,2021/5/26,设集合X=x1,x2,x3,x4,x5上的偏序关系如下图所示，求X的最大元、最小元、极大元、极小元。求子集X1=x2,x3,x4，X2=x3,x4,x5，X3=x1, x3,x5的上界、下界、上确界、下确界、最大元、最小元、极大元和极小元。,例7.3.12,2021/5/26,例7.3.1

35、2 解,X1，X2和X3的各种特殊元见下表。,2021/5/26,7.3.3全序关系,定义7.3.5 设为偏序集，若对任意x,yA，总有xy或yx，二者必居其一，则称关系“”为全序关系(Total Order Relation)，简称全序，或者线序关系，简称线序。称为全序集(Total Order Set)，或者线序集，或者链(Chain)。从定义7.3.5可以看出：全序关系是偏序关系，反之则不然。,2021/5/26,例7.3.13,试判断下列关系是否为全序关系，如果是，请画出其哈斯图。设集合A=a,b,c，其上的关系“”=, , , 实数集R上定义的小于等于关系“”；实数集R上定义

36、的小于关系“”；集合A的幂集P(A)上定义的包含关系“”。,2021/5/26,例7.3.13 解,是全序集，其哈斯图见图(a)；是全序集，其哈斯图是数轴，见图(b)，其中x,y,zR；不是全序关系；当|A|是全序集，其哈斯图见图(c)；当|A|2，则不是全序集。,2021/5/26,7.3.4 良序关系,定义7.3.6 设是一偏序集，若A的任何一个非空子集都有最小元素，则称“”为良序关系，简称良序，此时称为良序集。从定义7.3.6可以看出：（1）R是良序关系 R是偏序关系和A的任何非空子集都有最小元；（2）良序关系一定是偏序关系，反之则不然；（3）良序关系一定是全序关系，反之

37、则不然。,2021/5/26,例7.3.14,试判断例7.3.13的(1)和(2)是否为良序关系。解（1）是良序集；（2）是不良序集。注： 1、 “”是良序关系 “”是全序关系 “”是偏序关系； 2、有限全序集一定是良序集。,2021/5/26,7.3.6次序关系的应用,例7.3.15 计算机科学中常用的字典排序如下：设是一有限的字母表。上的字母组成的字母串叫上的字；*是包含空字“”的所有字组成的集合，建立*上的字典次序关系L：设x=x1x2xn，y=y1y2ym，其中xi,yj(i=1,2,n；j=1,2,m)，则x,y*。,2021/5/26,例7.3.15 （续）,（1）当x

38、1y1时，若x1y1，则xLy；若y1x1，则yLx。（2）若存在最大的k且kmin(n,m),使xi=yi(i=1,2, k)，而xk+1yk+1，若xk+1yk+1，则xLy；若yk+1xk+1，则yLx。（3）若存在最大的k且k=min(n,m)，使xi=yi(i=1,2,3,k)，此时，若nm，则xLy；若mn，则yLx。证明 L是*上的一个偏序关系且是一个全序关系。,2021/5/26,例7.3.15 证明,首先证明L是偏序关系。（1）L是自反的。对任意x*，令x=x1x2xn，其中xi，显然有xixi(i=1,2,n)，从而有xLx；（2）L是反对称的。对任意x，y*

39、，令x=x1x2xn, y=y1y2ym，其中xi,yj(i=1,2,n；j=1,2,m)。若xLy且yLx，根据L的定义有x=y；,2021/5/26,例7.3.15 证明（续）,（3）L是传递的。对任意x,y,z*，令x=x1x2xn, y=y1y2ym，z=z1z2zp，其中xi,yj,zk(i=1,2,n；j=1,2,m；k=1,2,p)。若xLy且yLz，根据L的定义和“”的传递性，有xLz。综上所述，L是*上的一个偏序关系。对任意x,y*，由x和y的表示形式知，xi和yi(i=1,2,n)总能进行比较，所以一定有xLy和yLx之一成立，从而L是*上的一个全序关系。,2021/

40、5/26,例7.3.16,一个计算机公司开发的项目需要完成7个任务，其中的某些任务只能在其他任务结束之后才能开始。考虑如下建立任务上的偏序，如果任务Y在任务X介绍之后才能开始，则XY。这7个任务的关于偏序的哈斯图如右图，求一个全序执行这些任务以完成这个项目。,2021/5/26,例7.3.16 解,可以通过执行一个排序得到7个任务的一种排序，排序的步骤见下图(a)到(g),2021/5/26,7.4 本章总结,等价关系的概念及证明、等价类和商集的计算；集合划分的定义、求给定集合的划分；等价关系与集合划分的关系；偏序关系、拟序关系、全序关系和良序关系的定义，它们之间的异同；哈斯图的画法；八个特殊元的定义和基本性质。,2021/5/26,习题类型,基本概念题：涉及寻找偏序关系的8个特殊元；判断题：涉及对证明过程正误的判断，集合的划分，关系特殊性的保持以及特殊关系的判定；计算题：涉及等价类和商集的计算和给定集合的划分，计算对应的等价关系；证明题：涉及特殊关系的证明；画图题：涉及等价关系的关系图、偏序关系的哈斯图。,2021/5/26,习题,217219页 1.2.6. 8.9.11. 13 (1),(3),(5) 15.16.18 22.24 (2),(5),Thank You !,

展开阅读全文