离散数学第四章二元关系和函数PPT讲稿.ppt

《离散数学第四章二元关系和函数PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《离散数学第四章二元关系和函数PPT讲稿.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学第四章二元关系和函数第1页，共80页，编辑于2022年，星期一2第第4章章 二元关系与函数二元关系与函数4.1 集合的笛卡儿积与二元关系集合的笛卡儿积与二元关系4.2 关系的运算关系的运算4.3 关系的性质关系的性质4.4 关系的闭包关系的闭包4.5 等价关系和偏序关系等价关系和偏序关系4.6 函数的定义和性质函数的定义和性质4.7 函数的复合和反函数函数的复合和反函数第2页，共80页，编辑于2022年，星期一34.1 集合的笛卡儿积和二元关系集合的笛卡儿积和二元关系 有序对有序对 笛卡儿积及其性质笛卡儿积及其性质 二元关系的定义二元关系的定义 二元关系的表示二元关系的表示第3页，共8

2、0页，编辑于2022年，星期一4 有序对的性质：有序对的性质：1）有序性有序性 （当（当x y时）时）2）与与 相等的充分必要条件是相等的充分必要条件是 =x=u y=v例例4.1 =，求，求 x,y.解解 3y 4=2,x+5=y y=2,x=3 4.1 4.1 二元关系的概念二元关系的概念1.有序对有序对有序对有序对/序偶序偶：由两个元素由两个元素x和和y按一定顺序按一定顺序排成二元组，记作：排成二元组，记作：。其中。其中x称作称作第第一个元素一个元素；y称作称作第二个元素第二个元素。第4页，共80页，编辑于2022年，星期一5 实例实例：1.空间直角坐标系中的坐标空间直角坐标系中的坐标

3、是有序三元组是有序三元组2.图书馆记录图书馆记录是一个是一个有序六元组有序六元组.2.有序有序有序有序n n元组元组元组元组：一个有序一个有序 n(n 3)元组元组 是一个有序对，其中是一个有序对，其中第一个元第一个元素素是一个有序是一个有序 n-1元组，即元组，即 ,xn=。我们将来的研究重点为有序二元组，即有序对/序偶第5页，共80页，编辑于2022年，星期一6例例4.2 A=1,2,3,B=a,b,c,C=A B=,B A=,A A=,A C=C A=3.笛卡儿积笛卡儿积：设设A,B为集合，用为集合，用A中元素中元素为为第一第一个元素个元素，B中元素中元素为为第二个元素第二个元素，构成有

4、序对构成有序对.所有这样的有序对组所有这样的有序对组成的集合叫做成的集合叫做 A与与B 的笛卡儿积的笛卡儿积 记作记作A B,即即 A B=|x A y B。第6页，共80页，编辑于2022年，星期一7笛卡儿积的性质：笛卡儿积的性质：1.不适合交换律不适合交换律 A B B A (A B,A,B)2.若若A或或B中有一个为空集，则中有一个为空集，则A B就是空集就是空集.A=B=3.若若|A|=m,|B|=n,则则|A B|=mn 4.不适合结合律不适合结合律 (A B)C A(B C)(A,B,C)例：例：A=1,B=2,C=3A B=,(A B)C=,3=B C=,A(B C)=1,第7页

5、，共80页，编辑于2022年，星期一8二元关系二元关系：集合中两个元素之间的某种关系：集合中两个元素之间的某种关系例例3 甲、乙、丙甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：比赛结果可表示为：，其中，其中表示表示x胜胜y，它，它表示了集合表示了集合甲甲,乙乙,丙丙中元素之间的一种胜负关系中元素之间的一种胜负关系.例例4 有有A、B、C3个人和四项工作个人和四项工作G1、G2、G3、G4，已知，已知A可以从事工作可以从事工作G1和和G4，

6、B可以从事工作可以从事工作G3，C可以从事工作可以从事工作G1和和G2.那么，人和工作之间的对应关系可以记作那么，人和工作之间的对应关系可以记作 R,C,G2 它表示了工人集合它表示了工人集合A,B,C到工作集合到工作集合G1,G2,G3,G4之间的关系之间的关系第8页，共80页，编辑于2022年，星期一如如R,可记作可记作 xRy；如果；如果 R,则记作则记作xR y实例：实例：R1=,R2=,R3=,3,4，R4=|xNy ZR1,R2,R4是二元关系；是二元关系；R3不是二元关系。不是二元关系。4.二元关系二元关系：如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非

7、空）集合非空,且它的元素都是有序对且它的元素都是有序对(以有序对为以有序对为 元素的集合元素的集合)（2）集合是空集）集合是空集则称该集合为一个则称该集合为一个二元关系二元关系,简称为简称为关系关系，记作，记作R.第9页，共80页，编辑于2022年，星期一105.从从A到到B的关系与的关系与A上的关系上的关系设设A,B为集合为集合,AB的任何子集所定义的二元的任何子集所定义的二元关系叫做关系叫做从从A到到B的二元关系的二元关系,当当A=B时则叫做时则叫做 A上上的二元关系的二元关系.例例5 A=0,1,B=1,2,3,R1=,R2=AB,R3=,R4=.那么那么 R1,R2,R3,R4是从是从

8、 A 到到 B 的二元关系的二元关系,R3和和R4同时也是同时也是 A上的二元关系上的二元关系.计数：计数：|A|=n,|B|=m,|AB|=nm,AB的子集有的子集有 个个.所以所以 A到到B上有上有 个不同的二元关系个不同的二元关系.|A|=n,|AA|=,AA的子集有的子集有 个个.所以所以 A上有上有 个不同的二元关系个不同的二元关系.例如例如|A|=3,则则 A上有上有512个不同的二元关系个不同的二元关系.第10页，共80页，编辑于2022年，星期一11A上重要关系的实例上重要关系的实例设设 A 为任意集合，为任意集合，是是 A 上的关系，称为上的关系，称为空关系空关系EA,IA

9、分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下：EA=|xAyA=AA IA=|xA例如例如,A=1,2,则则 EA=,IA=,注：注：IA;IA第11页，共80页，编辑于2022年，星期一12A上重要关系的实例（续）上重要关系的实例（续）小于等于关系小于等于关系 LA,整除关系整除关系DA,包含关系包含关系R 定义：定义：LA=|x,yAxy,DA=|x,yAx整除整除y,R=|x,yP(A)x y,A是某集合是某集合.类似的还可以定义大于等于关系类似的还可以定义大于等于关系,小于关系小于关系,大于关系大于关系,真真包含关系等等包含关系等等.第12页，共80页，编

10、辑于2022年，星期一13实例实例例如例如 A=1,2,3,B=a,b,则则 LA=,DA=,P(B)=,a,b,a,b,则则 B上的包含关系是上的包含关系是 R=,第13页，共80页，编辑于2022年，星期一14关系的表示关系的表示表示方式：关系的集合表达式、关系矩阵、关系图表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵关系矩阵：若：若A=x1,x2,xm，B=y1,y2,yn，R是是从从A到到B的关系，以的关系，以A元素为元素为行行，B元素为元素为列列，MR=rij m n,其中其中 rij=1 R，否则，否则rij=0。关系图关系图：若：若A=x1,x2,xm，R是从是从A上的关

11、系，上的关系，R的关的关系图是系图是GR=,以以A中元素为结点，如果中元素为结点，如果 R，则从则从 xi 到到 xj 有一条有向边有一条有向边.注意：注意：A,B为有穷集，关系矩阵适于表示从为有穷集，关系矩阵适于表示从A到到B的关的关系或者系或者A上的关系，关系图仅适于表示上的关系，关系图仅适于表示A上的关系上的关系 第14页，共80页，编辑于2022年，星期一15 实例实例A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下：习题：习题：4.1第15页，共80页，编辑于2022年，星期一 练习练习1.令令A=1,2,3;B=a,b,求求R1=,的关系矩阵。的关

12、系矩阵。2.令令A=1,2,3;求求R2=,的关的关系图。系图。3.令令F=,，G=,求求F G,G F,F F。（方法自选）（方法自选）第16页，共80页，编辑于2022年，星期一17基本运算定义基本运算定义定义域、值域、域定义域、值域、域逆、合成、限制、像逆、合成、限制、像基本运算的性质基本运算的性质幂运算幂运算定义定义求法求法性质性质4.2 关系的运算关系的运算第17页，共80页，编辑于2022年，星期一4.2 4.2 关系的运算关系的运算关系关系R的定义域：的定义域：domR=x|(y)R(即即R中有序组的中有序组的第一个元素第一个元素构成的集合构成的集合)关关系系R的的值值域域：ra

13、nR=y|(x)R(即即R中中有有序序组组的的第第二二个个元元素素构构成的集合成的集合)一、关系的定义域与值域关系关系R的域：的域：fldR=domR ranR 第18页，共80页，编辑于2022年，星期一19关系的基本运算定义关系的基本运算定义例例1 R=,则则 domR=1,2,4 ranR=2,3,4 fldR=1,2,3,4 第19页，共80页，编辑于2022年，星期一20关系的基本运算定义（续）关系的基本运算定义（续）R 1=|R R S=|z(S R)例例2 R=,S=,R 1=,R S=,S R=,第20页，共80页，编辑于2022年，星期一21合成运算的图示方法合成运算的图示方

14、法 利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R=,S=,R S=,S R=,RSSRS RR S第21页，共80页，编辑于2022年，星期一22实实例例 R=,R 1=,R1=2,4 R 1,2=,R=R1,2=2,4 三三 限制和像：限制和像：已知二元关系已知二元关系F F 和集合和集合A A F 在在A上的上的限制限制 F A=|xFy x A A 在在F下的下的像像 FA=ran(F A)注意：注意：F A F,FA ranF第22页，共80页，编辑于2022年，星期一23四四.关系运算的基本性质关系运算的基本性质(1)(2)(3)不满足交换律：不满足交换律：F

15、 GG F(4)满足结合律：满足结合律：F G H=F(G H)(5)第23页，共80页，编辑于2022年，星期一第24页，共80页，编辑于2022年，星期一25五五.A上关系的幂运算上关系的幂运算设设R为为A上的关系上的关系,n为自然数为自然数,则则 R 的的 n次幂次幂定义为：定义为：(1)R0=|xA=IA (2)Rn+1=Rn R 注意：注意：对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10=R20=IA 对于对于A上的任何关系上的任何关系 R 都有都有 R1=R 第25页，共80页，编辑于2022年，星期一26(1)定义法：定义法：对于集合表示的关系对于集合表示的关系R

16、，计算，计算 Rn 就是就是n个个R左复合左复合.(2)矩阵乘法：矩阵乘法：矩阵表示就是矩阵表示就是n个矩阵相乘个矩阵相乘,其中相加采用逻辑加其中相加采用逻辑加.（线性代数，逻辑乘法）（线性代数，逻辑乘法）(3)关系图法：关系图法：若点若点a经经k(k=1,2,n)条线可到达点条线可到达点b，则在，则在 的关系图上，的关系图上，a到到b有线相连。有线相连。例例3 设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R与与R2的关系矩阵分别为的关系矩阵分别为第26页，共80页，编辑于2022年，星期一27同理，同理，R0=IA,R3和和R4的

17、矩阵分别是：的矩阵分别是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=,R3=R5=R7=第27页，共80页，编辑于2022年，星期一28R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示关系图法关系图法结论：结论：仅当仅当A有回路时，上述结论成立。有回路时，上述结论成立。第28页，共80页，编辑于2022年，星期一当图中没有回路时：当图中没有回路时：第29页，共80页，编辑于2022年，星期一30(1)当关系图有回路时：当关系图有回路时：(2)(3)第30页，共80页，编辑于2022年，星期一31证明（证明（2）：用数学归纳法）：用数学归纳法 若若

18、n=0,则有则有 RmR0=RmIA=Rm=Rm+0 假设假设RmRn=Rm+n,则有则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1。幂运算的性质（续）幂运算的性质（续）证明（证明（3）：）：若若n=0,则有则有 假设假设 则有则有课后习题：课后习题：4.2，4.3，4.13第31页，共80页，编辑于2022年，星期一第32页，共80页，编辑于2022年，星期一第33页，共80页，编辑于2022年，星期一第34页，共80页，编辑于2022年，星期一4.3 4.3 关系的性质关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性：x A 有R (R是A上的关系

19、)关系矩阵：主对角线元素全是0关系图：每个顶点都没有环反自反性：x A R第35页，共80页，编辑于2022年，星期一例1：A=1,2,3,R1=,R2=,R3=,R4=,R5=,既不是自反的也不是非自反的自反的自反的既不是自反的也不是非自反的反自反的例1：是自反的一定不是反自反的；是反自反的一定不是自反的是自反的一定不是反自反的；是反自反的一定不是自反的！在自反性方面在自反性方面R有有3种可能：自反的；反自反的；既非自种可能：自反的；反自反的；既非自反又非反自反的反又非反自反的第36页，共80页，编辑于2022年，星期一对称性：若 R，则 R 关系矩阵：对称阵(aij=aji)关 系 图：如

20、果两个顶点之间有边，一定是一对方向相反的边。反对称性：反对称性：若 R且x y，则 R 关系矩阵：如果rij=1，且 i j，则rji=0 关系图：如果两个顶点之间有边，一定是只有一条有向边。！R=|xR=|x R既是对称关系又是反对称关系既是对称关系又是反对称关系第37页，共80页，编辑于2022年，星期一例2：A=1,2,3,R1=,R2=,R3=,R4=,R5=,反对称的既对称又反对称的对称的反对称的既非对称又非反对称的！在对称性方面在对称性方面R有有4种可能：对称的；反对称的；既对称又反种可能：对称的；反对称的；既对称又反对称的；既非对称又非反对称的对称的；既非对称又非反对称的第38页

21、，共80页，编辑于2022年，星期一传递性：传递性：若 R且 R，则 R 关系图：如果顶点xi到xj有边，xj到xk有边，则从xi到xk有边！若若a可经过两条或两条以上的线到达可经过两条或两条以上的线到达b，则，则 R 第39页，共80页，编辑于2022年，星期一例3：A=1,2,3,4,R1=,R2=,R3=,R4=,R5=,传递的传递的非传递的传递的非传递的！在传递性方面，在传递性方面，R有两种可能：传递的；非传递的。有两种可能：传递的；非传递的。第40页，共80页，编辑于2022年，星期一练习：自反的对称的反对称的传递的自反的对称的传递的反自反的反对称的反对称的传递的课后习题：课后习题：

22、4.4，4.12根据关系图判断关系的综合性质：第41页，共80页，编辑于2022年，星期一4.4 4.4 关系的闭包运算关系的闭包运算闭包：设RAA，自反闭包 记作 r(R)对称闭包 记作 s(R)传递闭包 记作 t(R)那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包自反闭包；包含R而使之具有传递性质的最小关系，称之为R的传递闭包传递闭包。一、定义包含R而使之具有对称性质的最小关系，称之为R的对称闭包闭包。第42页，共80页，编辑于2022年，星期一幂运算：设RAA，kN，约定(1)R0=IA=|xA(2)R1=R(3)Rk+1=Rk R二、计算方法为了有效地计算关系R的各种闭包

23、，先引进关系的幂运算概念。第43页，共80页，编辑于2022年，星期一逻辑运算方法：逻辑运算方法：设R是A上的任一关系，则(1)r(R)=RIA(2)s(R)=RR(3)t(R)=RR2R3 Rn-1第44页，共80页，编辑于2022年，星期一矩阵形式矩阵形式：(M为R的关系矩阵)(1)Mr=M+E（单位矩阵）(2)Ms=M+M (M 是M的转置)(3)Mt=M+M2+.+Mn-1其中“+”均表示“逻辑加”第45页，共80页，编辑于2022年，星期一关系图法：关系图法：(1)自反闭包图：对没有加环的点加环(2)对称闭包图：单边的加方向相反的边(3)传递闭包图：若Ai经过两条或两条以 上的边可到

24、达Aj，且无 边则加边第46页，共80页，编辑于2022年，星期一例例4.10 设A=a,b,c,d，A上的关系求 r(R)，s(R)和 t(R)解：解：1.逻辑求法：逻辑求法：r(R)=RIA=,R=,=R,三、实例第47页，共80页，编辑于2022年，星期一=,=R,s(R)=RRt(R)=RR2R3 Rn-1=R,=,R=,第48页，共80页，编辑于2022年，星期一2.矩阵运算：矩阵运算：R=,第49页，共80页，编辑于2022年，星期一3.关系图方法：关系图方法：课后习题：课后习题：4.14Rr(R)t(R)s(R)第50页，共80页，编辑于2022年，星期一第51页，共80页，编辑

25、于2022年，星期一4.5 4.5 等价关系和偏序关系等价关系和偏序关系等价关系：集A上的关系R是自反的,对称的和传递的。一、等价关系及用途例4.5.1：A=1,2,3,8，R=|x y(mod 3)则 147，258，36设设 R 是一个等价关系是一个等价关系,若若R,称称 x 等价于等价于y,记做记做 xy.第52页，共80页，编辑于2022年，星期一相容关系：R是集A上的关系，且R是自反的，对称的(1)在一群人的集合上在一群人的集合上年龄，姓名相同的关系年龄，姓名相同的关系是等价关系是等价关系,而而朋友关系朋友关系是相容关系，因为它可能不是传递的是相容关系，因为它可能不是传递的.(2)动

26、物是按种属分类的；动物是按种属分类的；“具有相同种属性具有相同种属性”的关系的关系是动是动物集合上的等价关系物集合上的等价关系.(3)集合上的集合上的恒等关系恒等关系和和全域关系全域关系都是等价关系都是等价关系.(4)在同一平面上在同一平面上三角形之间的相似关系三角形之间的相似关系是等价关系是等价关系,但但直直线间的平行关系线间的平行关系不是等价关系也不是相容关系不是等价关系也不是相容关系,因为它不因为它不是自反的是自反的.例子：！等价关系一定是相容关系；相容关系不一定是等价关系等价关系一定是相容关系；相容关系不一定是等价关系第53页，共80页，编辑于2022年，星期一等价类：R是集A上的等价

27、关系，对于任一aA，aR=x|aRx,xA被称为a的等价类。即：xR=y|xy在例4.5.1中：1R=4R=7R=1,4,7;2R=5R=8R=2,5,8;3R=6R=9R=3,6,9;第54页，共80页，编辑于2022年，星期一等价类的性质：等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：(1)xR 且xR A (等价类为A的子集)(2)若xy则xR=yR，反之成立。(3)若xRy，则xR yR=第55页，共80页，编辑于2022年，星期一集A在等价关系R下的商集：设R为非空集A上的等价关系，A在R下的商集记作A/R，A/R=xR|x A.(集合的集合）例例4.5.1的商集为：

28、的商集为：A/R=1,4,7,2,5,8,3,6,9注意：注意：A/EA=A A/IA=x|xA第56页，共80页，编辑于2022年，星期一集A的划分：令=A/R，满足以下性质：(1)(2)中任意两个元素不交(3)中所有元素的并集为A则 为A的划分。集合集合A上的划分是不唯一的上的划分是不唯一的第57页，共80页，编辑于2022年，星期一 对于集合A，若给定一个等价关系，则我们可唯一确定一个商集集合A上的等价关系与划分是一一对应的。集合A上的一个商集可唯一确定A上的一个划分第58页，共80页，编辑于2022年，星期一例例4.5.2 设A=1,2,3，求出A上所有的等价关系：解：解：先求A的各种

29、划分：只有1个划分块的划分1，具有两个划分块的划分2，3，和4，具有3个划分块5。第59页，共80页，编辑于2022年，星期一设对应于划分i 的等价关系 Ri，i=1,2,5，则有R5=，R1=，R2=，R3=，R4=，第60页，共80页，编辑于2022年，星期一偏序关系：偏序关系：集合集合A上的关系上的关系R是是自反的自反的，反对称反对称的的和和传递的传递的，记作，记作“”。二、偏序关系及用途设设R为偏序关系为偏序关系,如果如果 R,则记作则记作x y,读作读作“x小于小于等于等于y”.注意注意:这里的这里的“小于等于小于等于”不是指数的大小不是指数的大小,而是在偏序关而是在偏序关系中的顺序

30、性系中的顺序性.第61页，共80页，编辑于2022年，星期一例例4.5.3 设A=1,2,3，求出A上的大于等于关系：解：解：=,其中：其中：1 1,2 1,2 2,3 1,3 2,33第62页，共80页，编辑于2022年，星期一偏序关系例子：（1）任何集合）任何集合A上的恒等关系上的恒等关系（2）集合）集合A的幂集的幂集P(A)上的包含关系上的包含关系（4）正整数集上的整除关系都是偏序关系）正整数集上的整除关系都是偏序关系.（3）实数集上的小于等于，大于等于关系）实数集上的小于等于，大于等于关系,第63页，共80页，编辑于2022年，星期一相关概念：相关概念：偏序集：偏序集：集合A和偏序关系

31、R 构成一个偏序集，记作。如：,等可比：可比：对于任意两个元素x和y，若xy或y x，则x与y是可比的全序关系与全序集：全序关系与全序集：若A中任意两个元素都是可比的，则R为全序关系；为全序集。第64页，共80页，编辑于2022年，星期一盖住：盖住：如果xy，且不存在z使x z y(不是间接的),则称y能盖住x。例：锅，笼屉，锅盖火车卧铺的下铺，中铺，上铺第65页，共80页，编辑于2022年，星期一例例4.5.4 设A=1,2,3,4，求出A上的整除关系：解解:R整除=,则：则：2,3能盖住能盖住1；4能盖住能盖住2；4不能盖住不能盖住1第66页，共80页，编辑于2022年，星期一(1)去掉箭

32、头；（盖住）(2)去掉间接关系；（传递）(3)去掉环。（自反的）第67页，共80页，编辑于2022年，星期一哈斯图实例哈斯图实例例例4.5.5：画出画出 和和第68页，共80页，编辑于2022年，星期一全序关系的哈斯图：全序集中全部元素可以排序，它的哈斯图为一条直线。也称为线序集。集合A上的偏序关系与哈斯图是一一对应的。课后习题：课后习题：4.16第69页，共80页，编辑于2022年，星期一第70页，共80页，编辑于2022年，星期一(2)若yA，使得 (x)(xA yx)，则称y是A的极大元极大元(没有比我大的)(1)若yA，使得 (x)(xA xy)，则称y是A的极小元极小元(没有比我小的

33、)设是偏序集极小元与极大元一定存在，不一定唯一第71页，共80页，编辑于2022年，星期一(3)如果yA，使得(x)(xAyx)为真，则y是A的最小元最小元(比谁都小)(4)如果yB，使得(x)(xB xy)为真，则y是B的最大元最大元(比谁都大)最小元与最大元或唯一或不存在第72页，共80页，编辑于2022年，星期一例子：左图：左图：极小元为1;极大元为5,9,6,8,7 最小元为1;没有最大元。右图：右图：极小元为;极大元为a,b,c 最小元为;最大元为a,b,c。第73页，共80页，编辑于2022年，星期一上图：上图：极小元为a,b,c,g;极大元为a,f,h 没有最小元也没有最大元。结

34、论(1):最小元一定是极小元；最大元一定是极大元.(2):孤立点既是极小元又是极大元第74页，共80页，编辑于2022年，星期一(6)若yA，使得(x)(xB yx)为真，则称y是B的下界下界（比B中每一个都小）(7)令C=y|y为B的上界，则称C的最小元为B的上上确界或最小上界确界或最小上界（上界的最小元）(8)令D=y|y为B的下界，则D的最大元为B的下下确界或最大下界确界或最大下界（下界的最大元）(5)若yA，使得(x)(xB xy)为真，则称y是B的上界上界（比B中每一个都大）设是偏序集,B A第75页，共80页，编辑于2022年，星期一对以下哈斯图，令对以下哈斯图，令B=2，3，6,

35、则则B的上界为的上界为6,12;B的下的下界为界为1;B的上确界为的上确界为6;下确界为下确界为1.例子：令令C=2,4,则则C的上界为的上界为4,8,12;C的下界为的下界为1,2;C的上确的上确界为界为4;下确界为下确界为2.第76页，共80页，编辑于2022年，星期一考虑下图中的偏序集考虑下图中的偏序集.令令B=b,c,d,则则B的下界和最大下界的下界和最大下界都不存在都不存在,上界有上界有d和和f,最小上界为最小上界为d.结论(1):上界和下界不一定存在，不一定唯一。(2):上确界和下确界或者不存在或者唯一。(3):集合的最小元就是它的最大下界，最大元 就是它的最小上界；反之不对.课后

36、习题：课后习题：4.6第77页，共80页，编辑于2022年，星期一第78页，共80页，编辑于2022年，星期一了了解解二二元元关关系系的的定定义义和和表表示示方方法法；熟熟练练掌掌握握关关系系的的性性质质和和运运算算；特特别别是是幂幂，合合成成和和三三种种闭闭包包运运算算;理理理理解解解解等等等等价价价价关关关关系系系系和和和和偏偏偏偏序序序序关关关关系系系系，明明明明确确确确它它它它们们们们在在在在描描描描述述述述研研研研究究究究对对对对象象象象的的的的结结结结构构构构和和和和特特特特点点点点时时时时重重重重要要要要作作作作用用用用 (即即即即分分分分类类类类和和和和覆覆覆覆盖盖盖盖)。它它

37、们们在在计计算算机科学中有重要应用。机科学中有重要应用。重重重重点点点点：关关关关系系系系的的的的表表表表示示示示方方方方法法法法；关关关关系系系系的的的的合合合合成成成成，幂幂幂幂运运运运算算算算；关关关关系系系系性性性性质质质质判判判判断断断断；闭闭闭闭包包包包求求求求法法法法；哈哈哈哈斯斯斯斯图图图图画画画画法法法法；哈哈哈哈斯斯斯斯图图图图的的的的八八八八个特殊元素的求法。个特殊元素的求法。个特殊元素的求法。个特殊元素的求法。第79页，共80页，编辑于2022年，星期一作业二作业二课后习题：课后习题：课后习题：课后习题：4.14.1，4.24.2，4.34.3，4.44.4，4.64.6，4.124.12，4.134.13，4.144.14，4.164.16第80页，共80页，编辑于2022年，星期一