《离散数学关系》PPT课件.ppt

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

1、1,第2章 关 系,2,考察日常生活和科学技术中的“关系”：人与人之间有：父子关系兄弟关系师生关系两数之间有：大于关系等于关系小于关系,3,集合之间有：包含关系相等关系元素与集合之间有：属于关系函数之间有：调用关系,4,关系联系:事物间的多值对应。本章讨论的是：用集合理论刻画这些“联系”所建立的最一般的数学模型关系，这也是计算机科学中数据描述和信息处理的最常用的数学模型。,5,2.1 关系的概念 2.1.1 n元关系,设A1,A2,An是集合，则称A1A2An的任意一个子集R为A1,A2,An间的n元关系。,集合A1,A2,An叫做关系的域,n叫做它的阶。若R An,则称R为A上的n元关系。,

2、6,可以利用n元关系表示计算机的数据库:数据库由记录组成，这些记录是由字段构成的n元组。字段是n元组的数据项。,7,例 设R是ANSDT 的子集，其中A是所有航空公司的集合，N是航班号的集合，S是出发地的集合，D是目的地的集合，T是起飞时间的集合。则R是由5元组(a,n,s,d,t)组成的表示飞机航班的关系。例如，设R表示由国内航空公司飞机航班构成的关系，如果南方航空公司在15:00有从广州到北京的2963航班，那么(南方航空，2963，广州，北京，15:00)属于R。,8,若(a,b)R,则称a与b有关系R,记为aRb;若(a,b)R,则称a与b没有关系R,记为aRb。,设有两个集合A和B，

3、其笛卡儿积AB的任意一个子集R称为从A到B的一个二元关系（relation from A to B）。即:R AB特别地，当AB时，R称为A上的关系（relation on A）,这时 R A2,2.1.2 二元关系,9,直观地看，二元关系就是反映“多值对应”的二维表，例如，学生选课表：,10,把学生选课表用集合来表示：R=（张三,离散数学）,（李四,微积分）,（张三,高级语言）,序偶的集合R同样也刻画了学生集合A=张三，李四，与课程集合B=离散数学，微积分，高级语言，之间“多值对应”的联系。,11,【例】设A1,2,3,4,5,Ba,b,c,则R1(1,a),(1,b),(2,b),(3,a

4、)是从A到B的关系,而R2(a,2),(c,4),(c,5)是从B到A的关系。,12,【定义】设RAA,1)当R 时,称R为A上的空关系;2)当RAA=A2时,称R为集合A上的全域关系,用EA表示。显然EA(x,y)|xA 且 yA 3)若R(x,x)|xA,则称R是A上的恒等关系,用A表示。,13,【例】设A1,2,3,4,5，R是A上的二元关系，其定义为：当a，b A且a能整除b时，(a,b)R（R称为A上的整除关系），求R。,14,【例】设A1,2,3,4,5,6，R是A上的二元关系，其定义为：当a，b A且a和b被3除后余数相同时，(a,b)R（R也称为A上的模3同余关系,记为3），求

5、R。,15,设R是一个二元关系，(1)R中所有序偶的第一元素构成的集合称为R的定义域（domain），记做dom R。(2)R中所有序偶的第二元素构成的集合称为R的值域（range），记做ran R。,2.1.3 关系的定义域、值域,例如：A=a,b,c,d，B=1,2,3，R(a,2),(b,2),(c,1)，则：dom R=a,b,c，ran R=1,2,16,2.1.4 关系表示 1、关系图 2、关系矩阵,17,1.关系图 情形1：R是从A到B的关系,采用如下的图示:1）用大圆圈表示集合A和B，里面的小圆圈（或实心圆）表示集合中的元素;2）若aA，bB，且(a,b)R，则在图中将表示a和

6、b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。,18,例如：A=a1,a2,a3,a4 B=b1,b2,b3,b4,b5 R=(a1,b1),(a2,b3),(a3,b2),(a4,b4),(a4,b5),19,情形2：R是A上的关系,其画法如下:1)集合A中的每一个元素a用带有元素符号的顶点(称作顶点a)表示。2)若a,bA,且(a,b)R,则将顶点a和顶点b用一条带有箭头的有向边连接起来,其方向由顶点a指向顶点b。,20,【例】A=a1,a2,a3,a4,a5，R=(a1,a1),(a1,a2),(a2,a3),(a3,a4),(a4,a1),(a4,a5),(a5,a

7、3)。求R的关系图。,21,2.关系矩阵：由表格法抽象而来【定义】设集合Ax1,x2,xm,By1,y2,yn,R是从A到B的关系,则mn矩阵MR(mij)mn叫R的关系矩阵,其中:,22,【例】设A1,2,3,4,5,Ba,b,c,求下面两个关系的关系矩阵。A到B的关系:R1(1,a),(1,b),(2,b),(3,a)B到A的关系:R2(a,2),(c,4),(c,5),23,设集合Aa1,a2,an,对于A上的关系R,其关系矩阵MR(mij)nn是nn的,其中:,【例】求A1,2,3,4上的关系、EA和IA的关系矩阵。,24,2.1.5 函数的关系定义 函数如何转换成关系?【例2-15】

8、A=a,b,c,B=1,2,3,f:A B,f(a)=2,f(b)=3,f(c)=3.注意：一般来说,A到B的关系不是A到B的函数.,25,A到B的关系f 满足:(1)dom f=A;（像的存在性）(2)对任意xA，若(x,y1)f 且(x,y2)f,则y1=y2；（像的唯一性）则称f 为A到B的函数。,关系如何转换成函数?,26,作业：P44:1,3,7，13(1)(2),27,2.2 关系的运算,2.2.1.关系的集合运算 设 注意：,28,可以用n元关系上的集合运算构造新的n元关系。例 设A和B分别是学校的所有学生和所有课程的集合。假设:R1由所有有序对(a,b)组成，其中a是选修课程b

9、的学生;R2由所有的有序对(a,b)构成，其中课程b是a的必修课。问关系R1R2，R1R2，R1R2，R2R1，R1R2是什么?,29,解 关系R1R2由所有的有序对(a,b)组成，其中a是一个学生，他或者选修了课程b，或者课程b是他的必修课。R1R2是所有有序对(a,b)的集合，其中a是一个学生，他选修了课程b并且课程b也是a的必修课。,30,R1R2是所有有序对(a,b)的集合，其中a已经选修了课程b，但b不是a的必修课。R2R1是所有有序对(a,b)的集合，其中b是a的必修课，但a没有选它。R1R2由所有的有序对(a,b)组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程

10、b是a的必修课，但是a没有选修它。,31,如何用关系矩阵实现关系的集合运算?,记关系R的关系矩阵为MR=(uij)mn，关系S的关系矩阵为MS=(vij)mn，则1)RS 的关系矩阵M RS 是MR与MS的按位或(布尔和):M RS=MR+MS=(uij+vij)mn=(uij vij)mn,布尔和,逻辑或,布尔和,32,2)RS 的关系矩阵M RS 是MR与MS的按位与(按位布尔积):M R S=(uij vij)mn=(uij vij)mn3)的关系矩阵M 是MR的按位取反:把每个1改为0，每个0改为14)利用AB A,可计算MR-S 及MRS,布尔积,逻辑与,33,2.2.2 关系的逆运

11、算,设R是A到B的二元关系，如果把R中的每一个有序对中的元素顺序互换，所得到的B到A的二元关系称为R的逆关系，记作R-1。,例:R表示“课程-学生”关系，则R-1是“学生-课程”关系。,34,【例】A=a,b,c，B=x,y,z，R是A到B的二元关系，且有：R=(a,x),(b,y),(c,y)，则R-1是B到A的二元关系，且有：R-1=(x,a),(y,b),(y,c)【例】A=1,2,3，R是A上的二元关系，且有：R=(1,2),(2,3),(3,1)则其逆关系为：R-1=(2,1),(3,2),(1,3),35,逆关系R-1的关系矩阵与关系R的关系矩阵有何联系？,如果二元关系R的关系矩阵

12、为MR，则MR的转置矩阵MRT就是逆关系R-1的关系矩阵。,36,【定理2-2】【定理2-3】(1)(2)(3)R是A上的关系,则,37,R是集合A到B的二元关系，S是集合B到C的二元关系，R和S的复合R S 定义为R S=(x,z)|y B使得(x,y)R且(y,z)S 它是A到C的二元关系。,2.2.3 关系的复合运算 1.关系R和S的复合,38,例:R表示“教师-课程”关系，S表示“课程-学生”关系，则RS 是“教师-学生”关系。例:R表示“父子”关系，则RR 是“祖孙”关系。,39,例:R表示“教师-课程”关系，S表示“课程-学生”关系，T表示“学生-家长”关系，则(R S)T 是“教

13、师-学生家长”关系。例:R表示“父子”关系，则(RR)R是什么关系?,40,例:设A1,2,3,4,B2,3,4,C1,2,3,R(a,b)|(a,b)AB 且(ab4)S(b,c)|(a,b)BC 且(|bc|1)求R S。解:R(1,3),(2,2)S(2,1),(3,2),(4,3),(2,3)R S(1,2),(2,1),(2,3)复合关系R S的图示如图所示。,41,复合关系,R S,42,2.复合关系的矩阵表示 设A=a1,a2,am，B=b1,b2,bn，C=c1,c2,cs，R是A到B的二元关系，R的关系矩阵为：,其中：,1(ai,bj)R0(ai,bj)R,43,S是B到C的

14、二元关系，S的关系矩阵：,其中：,1(bi,cj)S0(bi,cj)S,44,令：,则有：当u11v11=1 或 u12v21=1 或 或 u1nvn1=1 时 w11=1；当u11v11=0 且 u12v21=0 且 且 u1nvn1=0 时 w11=0；一般地有：当ui1v1j=1 或 ui2v2j=1 或 或 uin vnj=1 时 wij=1；当ui1v1j=0 且 ui2v2j=0 且 且 uin vnj=0 时 wij=0；,45,引入布尔加法(逻辑或)（即0+0=0，1+0=0+1=1，1+1=1），则：w11=1 当且仅当 u11v11+u12v21+u1nvn1=1；一般地

15、wij=1 当且仅当 ui1v1j+ui2v2j+uin vnj=1；这说明：复合关系R S 的关系矩阵MR S=MRMS 其中是矩阵的布尔乘法（矩阵的逻辑乘法）。,46,【例】A=1,2,3，B=a,b,c,d，C=x,y,z，R是A到B的二元关系，R=(1,a),(1,b),(2,b),(3,c)，S是B到C的二元关系，S=(a,x),(b,x),(b,y),(b,z)。则有：,47,【例】A=1,2,3,4，R和S都是A上的二元关系 R=(1,1),(1,2),(1,3),(2,3),(2,4),(4,3),(4,4)S=(1,2),(1,3),(2,3),(2,4),(3,1),(4,

16、3)则有：,48,设R是A到B的二元关系，S是B到C的二元关系，T是C到D的二元关系，则：(R S)T=R(S T),二元关系与其关系矩阵是一一对应的，复合关系RS的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法运算满足结合律，所以关系的复合也满足结合律，即：,49,设 R AB，则：(1)IA R=R(2)R IB=R,设R是A到B的二元关系，S是B到C的二元关系，则(R S)-1=S-1 R-1。,50,设R是A上的关系，n为自然数，则R 的n 次幂定义为：(1)R0=(x,x)|x A=IA(2)Rn+1=Rn R,由于二元关系的复合满足结合律，所以二元关系的幂运算是有意义的

17、。,3.关系的幂运算,51,【例】设R是世界上所有人的集合上的关系，如果a认识b，那么R包含(a,b)。问Rn是由怎样的序偶构成的?其中n是大于等于2的正整数。解如果存在人c，使得(a,c)R且(c,b)R，即存在人c使得a认识c，c认识b，那么关系R2包括(a,b)。类似地，如果存在人x1，x2，xn-1使得a认识x1，x1认识x2，xn-1认识b，那么Rn包含对(a,b)。,52,【例】设R是广州市所有地铁站的集合上的关系。如果可以从站a不换车就旅行到站b，那么R包含对(a,b)。当n是正整数时，Rn是由怎样的序偶构成的?解 如果经过至多n-1次换车就可以从站a旅行到站b，关系Rn就包含(

18、a,b)。,53,设R是A上的关系，m,n N，则(1)Rm Rn=Rm+n(2)(Rm)n=Rmn(3)(Rm)-1=(R-1)m,54,作业：P51:1,3,11,55,设R是A上的关系,(1)若对于所有的xA,都有(x,x)R,则称R是自反的(reflexive)。(2)若对于所有的xA,都有(x,x)R,则称R是反自反的(irreflexive)。,2.3 关系的性质,56,【例】设A1,2,3,R1,R2,R3 是A上的关系，其中 R1(1,1),(2,2)R2(1,1),(2,2),(3,3),(1,2)R3(1,3)说明它们是否为A上的自反关系或反自反关系。【例】全域关系EA,恒

19、等关系A是A上的自反关系;小于等于关系A,整除关系DA是A上的自反关系;小于关系 A是反自反关系。,57,分析上述关系的关系图和关系矩阵，可得出结论:若关系R是自反的,当且仅当其关系图中每个结点都有自回路(环),其关系矩阵中,主对角线上的元素均为;若关系R是反自反的,当且仅当其关系图中每个结点都没有自回路(环),其关系矩阵中,主对角线上的元素全为。注意,一个关系不是自反的,不一定就是反自反的。,58,设 R AA，则：(1)R自反 IA R.(2)R反自反 IAR=.,59,设R是A上的关系，(1)若对于任意的x,yA,每当(x,y)R 时就有(y,x)R,则称R 是对称的(symmetric

20、)。(2)若(x,y)R 且xy时,必有(y,x)R,则称R是反对称的(antisymmetric)。,60,【例】设A1,2,3,R1,R2,R3,R4是A上的关系，其中 R1(1,1),(2,2)R2(1,1),(1,2),(2,1)R3(1,2),(1,3)R4(1,2),(2,1),(1,3)说明它们是否为A上的对称关系或反对称关系。,61,【例】全域关系EA,恒等关系A是A上的对称关系;小于等于关系 A,整除关系DA是A上的反对称关系。,62,分析这些关系的关系矩阵和关系图，可得出结论:若关系R是对称的,当且仅当其关系图中,若有顶点a到顶点b的边,则一定有顶点b到顶点a的边,其关系矩

21、阵是一个对称矩阵。若关系R是反对称的,当且仅当其关系图中,若有顶点a到顶点b的边,则一定没有顶点b到顶点a的边,其关系矩阵关于主对角线对称的元素不同时为,即当rij=(ij)时,必有rji=。,63,设 R AA，则：(1)R对称 R=R-1.(2)R反对称 RR-1 IA.,64,设R是A上的关系,若对任意x,y,zA,每当(x,y)R且(y,z)R时，就有(x,z)R,则称R是传递的(transitive)。,关系图上传递的特征：如果顶点x到y有边，y到z有边，则x到z也有边。,65,【例】设A1,2,3,R1,R2 是A上的关系，其中 R1(1,1),(1,2),(1,3),(2,3)R

22、2(1,1),(2,2),(2,3),(3,2)说明它们是否为A上的传递关系。,66,【例】全域关系EA,恒等关系A，小于等于关系 A,整除关系DA，包含关系是传递的。,67,设 R AA，则：R传递 RR R,68,【示例】判断下列关系的性质:1)实数集上的“”关系,2)实数集上的“”关系,3)实数集上的“”关系。解:1)“”关系是自反、对称、传递的。2)“”关系是自反、反对称、传递的。3)“”关系是反自反、反对称、传递的。,69,【例】若Aa,b,c,d,A上的3个关系为：R1(a,a),(a,b),(c,b),(d,a),(d,b)R2(a,a),(a,b),(a,d),(c,b)R3(

23、a,a),(a,b),(a,d),(b,c),(d,b)说明它们是否为A上的传递关系。,70,分析它们的关系图：则可判断出R1和R2是传递的,R3不是传递的（(a,b),(b,c)）。,71,练习：作出下列关系的关系图和关系矩阵,并判断其性质:1)A1,2,3,4,5,R是A上关系,R=(a,b)|(a,b)A2且,2)A0,1,R是集合2A上的“”关系。,72,解 1)R=(1,1),(1,4),(2,2),(2,5),(3,3),(4,1),(4,4),(5,2),(5,5)画出关系图，写出关系矩阵。由关系图可知,R是自反、对称、传递的。,73,解 2)2A,0,1,0,1 令 A1,A2

24、0,A31,A40,1 则 R=(A1,A1),(A1,A2),(A1,A3),(A1,A4),(A2,A2),(A2,A4),(A3,A3),(A3,A4),(A4,A4)画出关系图，写出关系矩阵。由关系图可知,R是自反、反对称、传递的。,74,作业：P58:8，9,75,2.4 关系的闭包,任给一个A上的关系R,R不一定具有自反、对称或传递等性质。希望在R中增加一些序偶，得到一个包含R的新关系R:1)R具有自反(对称、传递)性质2)R同原关系R尽可能接近(亦即增加的序偶尽可能少)这就是闭包的思想，即：闭包具有某种性质（如对称性）的最小扩充关系。,76,设R、R是集合A上的关系，如果满足：(

25、1)R是自反的（对称的或传递的）(2)R R(3)对A上任何包含R的自反（对称或传递）关系R”，均有：R R，则称R是R的自反（对称或传递）闭包。,2.4.1 闭包的定义,77,一般的，R的自反(reflexive)闭包记为r(R)对称(symmetric)闭包记为s(R)传递(transitive)闭包记为t(R),78,例1 R表示中山市所有居民组成的集合上“父母-子女”的亲子关系，问t(R)是什么关系？先辈-后代关系 例2 设R是广州市所有地铁站的集合上的关系。如果可以从站a不换车就旅行到站b，那么R包含对(a,b)。问t(R)是什么?可达关系,79,2.4.2 闭包的构造【定理2-14

26、,15,16】设R为集合A上的关系,则有 1)r(R)RIA 2)s(R)RR-1 3)t(R)RR2R3,80,【例】设A1,2,3,4,5,R是A上的关系,R(2,1),(2,4),(2,5),(3,4),(4,4),(5,2),求r(R),s(R),t(R),并作出它们及R的关系图。解:r(R)RIA(2,1),(2,4),(2,5),(3,4),(4,4),(5,2),(1,1),(2,2),(3,3),(5,5),81,R1(1,2),(4,2),(5,2),(4,3),(4,4),(2,5)s(R)RR1(1,2),(2,1),(2,4),(2,5),(3,4),(4,2),(4,

27、3),(4,4),(5,2),82,R2(2,2),(2,4),(3,4),(4,4),(5,1),(5,4),(5,5)R3(2,1),(2,4),(2,5),(3,4),(4,4),(5,2),(5,4)R4(2,2),(2,4),(3,4),(4,4),(5,1),(5,4),(5,5)R2 继续做下去显然有 R2n+1=R3 R2n=R2(n1,2,)t(R)=RR2R3=RR2R3=(2,1),(2,4),(2,5),(3,4),(4,4),(5,2),(2,2),(5,1),(5,4),(5,5),83,图 R,r(R),s(R),t(R)的关系图,84,设|A|=n1，R AA，

28、则：t(R)RR2 Rn.,85,2.4.3 闭包的矩阵计算设关系R的关系矩阵为M,r(R)、s(R)和 t(R)的关系矩阵分别为Mr、Ms和Mt，则Mr=M+IMs=M+MTMt=M+M2+M3+其中“”为布尔加。,86,【例2-44】P62,87,作业：P64:2,3,10,88,2.5 等价关系,实数集R上的“”关系,三角形集合中的全等关系等同时具有自反、对称和传递的特性,这是一种重要而常见的关系。,89,设R是A上的关系,若R具有：（1）自反性（2）对称性（3）传递性则称R是A上的等价关系。若有(a,b)R,则称a与b等价。,显然,对任何集合A,A上的恒等关系IA 和全域关系EA 是等

29、价关系。,2.5.1 等价关系的定义,90,【例】设Aa,b,c,d,e,f,g，A中元素分别表示7位大学生，其中a，b，c都姓张，d和e都姓李，f和g都姓王。如果同姓氏的大学生认为是相关的，不同姓氏的大学生是无关的，那么这种同姓关系R是等价关系。,91,【例】设Aa,b,c,d,e,f,g，A中元素分别表示7位大学生，其中a，c，d，f 都是20岁，b，e，g都是23岁。如果年龄相同的大学生认为是相关的，不同年龄的大学生是无关的，那么这种同龄关系R是等价关系。,92,“血缘关系”是否是等价关系?,解：否,93,【例】设A=1,2,8，定义A上的关系R如下：R=(x,y)|x,yA 且 x 3

30、 y可以验证R为等价关系。,若把A中元素按除3后的余数进行分组，则可以得到3,6,1,4,7,2,5,8。可见一个等价关系一定可以确定一种分组，等价关系就是分组后的同组关系。,94,2.5.2 等价类(equivalence classes),设R是A上的等价关系,aA,称集合 x|xA 且 aRx为元素a关于R的等价类,记为 aR。,由定义知,aR是A中所有与a等价的元素x组成的集合。,95,【例】设A=1,2,8，定义A上的关系R如下：R=(x,y)|x,yA 且 x y(mod 3)则A中各元素关于R的等价类分别为：1R=4R=7R=1,4,7 2R=5R=8R=2,5,8 3R=6R=

31、3,6,96,【例】设A是全院学生构成的集合,R为A上的关系：如果x与y是主修同一专业的学生，则xRy。那么(1)R是等价关系(2)R将A中的学生分为不相交的子集（等价类），其中每个子集包含了某个特定专业的所有学生。例如，一个子集（等价类）包含了所有（主修）软件工程专业的学生，另一个子集（等价类）包含了所有网络工程专业的学生。,97,设R是A上的等价关系,则等价类的集合xR|xA称为A关于R的商集,用A/R表示(读作A模R)。,前例中，A/R分别是：A/R=1,4,7，2,5,8，3,6A/R=软件工程专业的学生，网络工程专业的学生，.,98,设R是集合A上的等价关系,则商集A/R构成A的一个

32、划分。,前例中，A/R=1,4,7，2,5,8，3,6A/R=软件工程专业的学生，网络工程专业的学生，.分别构成A的划分。,99,等价关系导出的等价划分是唯一的;反之,给出集合A的一个划分,存不存在相应的等价关系呢？,100,设A1,A2,Am是集合A的一个划分,定义R为:R(a,b)|a,b属于同一划分块Ai,i1,2,m则R是A上的等价关系且A/R。,所以,A上的等价关系与集合A的划分是一一对应的。等价关系实质上是同组关系。,101,【思考题】在你们班所有同学构成的集合上定义3个等价关系，并确定关于这些等价关系的等价类。,同龄，同桌，同性，同乡，同舍，同社团（非社团）,102,作业：P68

33、:2，4，8,103,设R是A上的关系,且满足：（1）自反性；（2）反对称性；（3）传递性；则称R是A上的一个偏序关系,简称为偏序(partial order),常记为“”并读作“小于等于”。,2.7 偏序关系,2.7.1 偏序关系的定义,104,集合A和A上的偏序一起称为一个偏序集(partially ordered set,poset),用(A,)表示。【示例】小于等于关系LA,整除关系DA是偏序关系；P(A)上的“”关系是偏序关系。,105,设（A,）是偏序集,若对任意的x,yA,有xy或yx,则称是线性序关系(linear order)，又称全序关系。,注：全序关系的哈斯图是一条直线，

34、故称为线性序关系。,106,例：小于等于关系LA 是全序关系；整除关系DA一般不是全序关系；P(A)上的“”关系一般不是全序关系。,107,设（A,）是偏序集，x,y A，若下列三个条件同时成立，则称元素y盖住x：（1）xy（2）xy（3）不存在异于x和y的元素zA，使得x z y。,y盖住x意味着y比x只“高（大）”一层（级）。,2.7.2 偏序集的哈斯图,108,记 COV(A)=(x,y)|x,y A且y盖住x.,109,【例】设A=1,2,3,4,6,12，R是A上的整除关系。则R的关系图如下图（a）所示。,110,为了更清楚地表示偏序集中元素间的一种层次关系,我们引入哈斯图(Hass

35、e图)。,哈斯(Hasse,1898-1979),生于德国。高中毕业后在海军服役。后在大学学习数论。对代数数论作出了基础性的贡献。二战时曾为德国海军从事应用数学研究。,111,哈斯图是一种简化的关系图：1)只画相邻层间的有向弧，自反性不在图中表示出来;2)“大”的元素画在较“小”元素的上方（如果y盖住x，则在x和y之间连一条线）;3)有向弧简化为无向线段（方向性由上、下方体现）。,112,哈斯图的画法：方法1:从关系图开始，1）去掉环；2）去掉由传递性形成的有向弧；3）重新排列顶点，使每条有向弧的始点在终点的下边；4）去掉有向弧的箭头。,113,114,方法2:1)求出A上的盖住关系COV(A

36、)=(x,y)|x,y A且y盖住x；2)按盖住关系COV(A)分层画出顶点，并用直线连接。,115,【例】设A=1,2,3,4,6,8,12,24，R是A上的整除关系，画出R的哈斯图。COV(A)=(1,2),(1,3),(2,4),(3,6),(4,8),(6,12),(8,24),(12,24),116,【例】设集合S=1,2,3，其幂集P(S)上的包含关系为偏序关系，请画出其哈斯图。,117,2.7.3 偏序集中的特殊元素 从前面例子的哈斯图可以看出,偏序集中元素的结点层次清楚,有的结点在哈斯图的最上层,有的在最下层;有的最上（下）层只有一个结点,有的有多个结点。下面我们将着重研究哈斯

37、图中这些特殊位置上的结点。,118,设(A,)是偏序集,S A,b S。1）b是S的最大元（greatest element):x S，都有 x b。2）b是S的最小元（least element):x S，都有 b x。,119,【例】,120,在(A,)偏序集中,S A，若S存在最大(小)元,则是唯一的。,证明 若a1,a2都是集合S的最大元素,由定义可知a1a2,a2a1，根据偏序的反对称性,有a1a2。同理可证,S的最小元素如果存在也必唯一。,121,设(A,)是偏序集，如果A中任何非空子集都有最小元，则称是A上的良序，称(A,)为良序集。,【例】(N,)是良序集，但(Z,)不是良序集

38、。,122,设(A,)是偏序集,S A,b S。1）b是S的极大元（maximal element):x S，若b x，有 xb。2）b是S的极小元（minimal element):x S，若 x b，有 xb。,123,【例】,124,显然,在偏序集（A,）中:A的极大元是哈斯图中的一个上端点 A的极小元是哈斯图中的一个下端点它们不一定唯一,不同的极大元(极小元)之间没有线连接起来。,125,特殊元的几何特征（哈斯图）：1）集合A的极小元a是A的一个下端点；2）集合A的极大元a是A的一个上端点；3）集合A的最小元a“小于等于”A中所有的元（与A中所有的元都可比）；4）集合A的最大元a“大于

39、等于”A中所有的元（与A中所有的元都可比）。,126,设(A,)是偏序集,S A。(1)若有元素aA,使得xS,都有ax,则称a是子集S的下界(lower bound);(2)若有元素aA,使得xS,都有xa,则称a是子集S的上界(upper bound)。,127,【例】,128,设(A,)是偏序集,S A。1)子集S的最小上界称为S的上确界(least upper bound),记作sup(S)。2)子集S的最大下界称为S的下确界(greatest lower bound),记作inf(S)。,129,【例】,130,设(A,)是偏序集,S A。若S的上（下）确界存在，则唯一。,注意:子集

40、S的极小(大)元和最小(大)元都必须是S中的元素,而S的下(上)界和最大下界(最小上界)都不一定是S中的元素。,131,作业：P76:1,2,8,132,上机编程题:1.写一个程序，读入一个集合A及A上的关系R，判断R是否是自反关系、反自反关系、对称关系、反对称关系、传递关系。同时指出R是否是等价关系、偏序关系。2.写一个程序，读入一个集合A及A上的等价关系R，求A/R。3.写一个程序，读入一个集合A及A的一个划分S，求等价关系R，使得A/R=S。4.写一个程序，读入一个集合A及A上的偏序关系，求集合A的极小元、极大元、最小元、最大元。,133,练习：设 A0,1,2,3,A上有如下两个关系求R-1,S R,R S,R2.,R(0,0),(0,1),(1,2),(2,3),(2,1)S(2,0),(3,1)R-1(0,0),(1,0),(2,1),(3,2),(1,2)S R(1,0),(2,1)R S(2,0),(2,1),(3,2)R2(0,0),(0,1),(0,2),(1,3),(2,2),(1,1),