离散数学 关系PPT课件

.,1,第2章关系,.,2,考察日常生活和科学技术中的“关系”：人与人之间有：父子关系兄弟关系师生关系两数之间有：大于关系等于关系小于关系,.,3,集合之间有：包含关系相等关系元素与集合之间有：属于关系函数之间有：调用关系,.,4,关系联系:事物间的多值对应。本章讨论的是：用集合理论刻画这些“联系”所建立的最一般的数学模型关系，这也是计算机科学中数据描述和信息处理的最常用的数学模型。,.,5,2.1关系的概念2.1.1n元关系,设A1,A2,An是集合，则称A1A2An的任意一个子集R为A1,A2,An间的n元关系。,集合A1,A2,An叫做关系的域,n叫做它的阶。若RAn,则称R为A上的n元关系。,.,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，其笛卡儿积AB的任意一个子集R称为从A到B的一个二元关系（relationfromAtoB）。即:RAB特别地，当AB时，R称为A上的关系（relationonA）,这时RA2,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)是从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且yA3)若R(x,x)|xA,则称R是A上的恒等关系,用A表示。,.,13,【例】设A1,2,3,4,5，R是A上的二元关系，其定义为：当a，bA且a能整除b时，(a,b)R（R称为A上的整除关系），求R。,.,14,【例】设A1,2,3,4,5,6，R是A上的二元关系，其定义为：当a，bA且a和b被3除后余数相同时，(a,b)R（R也称为A上的模3同余关系,记为3），求R。,.,15,设R是一个二元关系，(1)R中所有序偶的第一元素构成的集合称为R的定义域（domain），记做domR。(2)R中所有序偶的第二元素构成的集合称为R的值域（range），记做ranR。,2.1.3关系的定义域、值域,例如：A=a,b,c,d，B=1,2,3，R(a,2),(b,2),(c,1)，则：domR=a,b,c，ranR=1,2,.,16,2.1.4关系表示1、关系图2、关系矩阵,.,17,1.关系图情形1：R是从A到B的关系,采用如下的图示:1）用大圆圈表示集合A和B，里面的小圆圈（或实心圆）表示集合中的元素;2）若aA，bB，且(a,b)R，则在图中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。,.,18,例如：A=a1,a2,a3,a4B=b1,b2,b3,b4,b5R=(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,a3)。求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】A=a,b,c,B=1,2,3,f:AB,f(a)=2,f(b)=3,f(c)=3.注意：一般来说,A到B的关系不是A到B的函数.,.,25,A到B的关系f满足:(1)domf=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的学生;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的必修课，或者课程b是a的必修课，但是a没有选修它。,.,31,如何用关系矩阵实现关系的集合运算?,记关系R的关系矩阵为MR=(uij)mn，关系S的关系矩阵为MS=(vij)mn，则1)RS的关系矩阵MRS是MR与MS的按位或(布尔和):MRS=MR+MS=(uij+vij)mn=(uijvij)mn,布尔和,逻辑或,布尔和,.,32,2)RS的关系矩阵MRS是MR与MS的按位与(按位布尔积):MRS=(uijvij)mn=(uijvij)mn3)的关系矩阵M是MR的按位取反:把每个1改为0，每个0改为14)利用ABA,可计算MR-S及MRS,布尔积,逻辑与,.,33,2.2.2关系的逆运算,设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的关系矩阵为MR，则MR的转置矩阵MRT就是逆关系R-1的关系矩阵。,.,36,【定理2-2】【定理2-3】(1)(2)(3)R是A上的关系,则,.,37,R是集合A到B的二元关系，S是集合B到C的二元关系，R和S的复合RS定义为RS=(x,z)|yB使得(x,y)R且(y,z)S它是A到C的二元关系。,2.2.3关系的复合运算1.关系R和S的复合,.,38,例:R表示“教师-课程”关系，S表示“课程-学生”关系，则RS是“教师-学生”关系。例:R表示“父子”关系，则RR是“祖孙”关系。,.,39,例:R表示“教师-课程”关系，S表示“课程-学生”关系，T表示“学生-家长”关系，则(RS)T是“教师-学生家长”关系。例: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)求RS。解:R(1,3),(2,2)S(2,1),(3,2),(4,3),(2,3)RS(1,2),(2,1),(2,3)复合关系RS的图示如图所示。,.,41,复合关系,RS,.,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的二元关系，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或或uinvnj=1时wij=1；当ui1v1j=0且ui2v2j=0且且uinvnj=0时wij=0；,.,45,引入布尔加法(逻辑或)（即0+0=0，1+0=0+1=1，1+1=1），则：w11=1当且仅当u11v11+u12v21+u1nvn1=1；一般地wij=1当且仅当ui1v1j+ui2v2j+uinvnj=1；这说明：复合关系RS的关系矩阵MRS=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,3)则有：,.,48,设R是A到B的二元关系，S是B到C的二元关系，T是C到D的二元关系，则：(RS)T=R(ST),二元关系与其关系矩阵是一一对应的，复合关系RS的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法运算满足结合律，所以关系的复合也满足结合律，即：,.,49,设RAB，则：(1)IAR=R(2)RIB=R,设R是A到B的二元关系，S是B到C的二元关系，则(RS)-1=S-1R-1。,.,50,设R是A上的关系，n为自然数，则R的n次幂定义为：(1)R0=(x,x)|xA=IA(2)Rn+1=RnR,由于二元关系的复合满足结合律，所以二元关系的幂运算是有意义的。,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就包含(a,b)。,.,53,设R是A上的关系，m,nN，则(1)RmRn=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,恒等关系A是A上的自反关系;小于等于关系A,整除关系DA是A上的自反关系;小于关系A是反自反关系。,.,57,分析上述关系的关系图和关系矩阵，可得出结论:若关系R是自反的,当且仅当其关系图中每个结点都有自回路(环),其关系矩阵中,主对角线上的元素均为;若关系R是反自反的,当且仅当其关系图中每个结点都没有自回路(环),其关系矩阵中,主对角线上的元素全为。注意,一个关系不是自反的,不一定就是反自反的。,.,58,设RAA，则：(1)R自反IAR.(2)R反自反IAR=.,.,59,设R是A上的关系，(1)若对于任意的x,yA,每当(x,y)R时就有(y,x)R,则称R是对称的(symmetric)。(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的边,其关系矩阵是一个对称矩阵。若关系R是反对称的,当且仅当其关系图中,若有顶点a到顶点b的边,则一定没有顶点b到顶点a的边,其关系矩阵关于主对角线对称的元素不同时为,即当rij=(ij)时,必有rji=。,.,63,设RAA，则：(1)R对称R=R-1.(2)R反对称RR-1IA.,.,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)R2(1,1),(2,2),(2,3),(3,2)说明它们是否为A上的传递关系。,.,66,【例】全域关系EA,恒等关系A，小于等于关系A,整除关系DA，包含关系是传递的。,.,67,设RAA，则：R传递RRR,.,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(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,A20,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上的关系，如果满足：(1)R是自反的（对称的或传递的）(2)RR(3)对A上任何包含R的自反（对称或传递）关系R”，均有：RR，则称R是R的自反（对称或传递）闭包。,2.4.1闭包的定义,.,77,一般的，R的自反(reflexive)闭包记为r(R)对称(symmetric)闭包记为s(R)传递(transitive)闭包记为t(R),.,78,例1R表示中山市所有居民组成的集合上“父母-子女”的亲子关系，问t(R)是什么关系？先辈-后代关系例2设R是广州市所有地铁站的集合上的关系。如果可以从站a不换车就旅行到站b，那么R包含对(a,b)。问t(R)是什么?可达关系,.,79,2.4.2闭包的构造【定理2-14,15,16】设R为集合A上的关系,则有1)r(R)RIA2)s(R)RR-13)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,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=R3R2n=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，RAA，则：t(R)RR2Rn.,.,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是等价关系。,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且x3y可以验证R为等价关系。,若把A中元素按除3后的余数进行分组，则可以得到3,6,1,4,7,2,5,8。可见一个等价关系一定可以确定一种分组，等价关系就是分组后的同组关系。,.,94,2.5.2等价类(equivalenceclasses),设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且xy(mod3)则A中各元素关于R的等价类分别为：1R=4R=7R=1,4,72R=5R=8R=2,5,83R=6R=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的一个划分。,前例中，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:2，4，8,.,103,设R是A上的关系,且满足：（1）自反性；（2）反对称性；（3）传递性；则称R是A上的一个偏序关系,简称为偏序(partialorder),常记为“”并读作“小于等于”。,2.7偏序关系,2.7.1偏序关系的定义,.,104,集合A和A上的偏序一起称为一个偏序集(partiallyorderedset,poset),用(A,)表示。【示例】小于等于关系LA,整除关系DA是偏序关系；P(A)上的“”关系是偏序关系。,.,105,设（A,）是偏序集,若对任意的x,yA,有xy或yx,则称是线性序关系(linearorder)，又称全序关系。,注：全序关系的哈斯图是一条直线，故称为线性序关系。,.,106,例：小于等于关系LA是全序关系；整除关系DA一般不是全序关系；P(A)上的“”关系一般不是全序关系。,.,107,设（A,）是偏序集，x,yA，若下列三个条件同时成立，则称元素y盖住x：（1）xy（2）xy（3）不存在异于x和y的元素zA，使得xzy。,y盖住x意味着y比x只“高（大）”一层（级）。,2.7.2偏序集的哈斯图,.,108,记COV(A)=(x,y)|x,yA且y盖住x.,.,109,【例】设A=1,2,3,4,6,12，R是A上的整除关系。则R的关系图如下图（a）所示。,.,110,为了更清楚地表示偏序集中元素间的一种层次关系,我们引入哈斯图(Hasse图)。,哈斯(Hasse,1898-1979),生于德国。高中毕业后在海军服役。后在大学学习数论。对代数数论作出了基础性的贡献。二战时曾为德国海军从事应用数学研究。,.,111,哈斯图是一种简化的关系图：1)只画相邻层间的有向弧，自反性不在图中表示出来;2)“大”的元素画在较“小”元素的上方（如果y盖住x，则在x和y之间连一条线）;3)有向弧简化为无向线段（方向性由上、下方体现）。,.,112,哈斯图的画法：方法1:从关系图开始，1）去掉环；2）去掉由传递性形成的有向弧；3）重新排列顶点，使每条有向弧的始点在终点的下边；4）去掉有向弧的箭头。,.,113,.,114,方法2:1)求出A上的盖住关系COV(A)=(x,y)|x,yA且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偏序集中的特殊元素从前面例子的哈斯图可以看出,偏序集中元素的结点层次清楚,有的结点在哈斯图的最上层,有的在最下层;有的最上（下）层只有一个结点,有的有多个结点。下面我们将着重研究哈斯图中这些特殊位置上的结点。,.,118,设(A,)是偏序集,SA,bS。1）b是S的最大元（greatestelement):xS，都有xb。2）b是S的最小元（leastelement):xS，都有bx。,.,119,【例】,.,120,在(A,)偏序集中,SA，若S存在最大(