《离散数学第四章二元关系和函数.ppt》由会员分享，可在线阅读，更多相关《离散数学第四章二元关系和函数.ppt（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学第四章二元关系和函数离散数学第四章二元关系和函数现在学习的是第1页，共66页内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数现在学习的是第2页，共66页序偶序偶1.定义定义4.1:由两个元素由两个元素x和和y（允许（允许x=y）按一定的）按一定的顺序排列成的二元组叫作顺序排列成的二元组叫作有序对有序对(也称也称序偶序偶),记作记作(也可记作也可记作(x,y).其中其中x是它的是它的
2、第一元素第一元素,y是是它的它的第二元素第二元素.例如平面直角的坐标例如平面直角的坐标:,他的特性他的特性是是:当当xy时,=等充分必要条件是等充分必要条件是x=u,y=v.序偶与集合的关系序偶与集合的关系,但但x,y=y,x现在学习的是第3页，共66页有序有序n元组元组1.定义定义4.2:一个有序一个有序n元组元组(3n)是一个有序对是一个有序对,其其中第一个元素是一个中第一个元素是一个有序有序n-1元组元组，一个有序，一个有序n元元组记作组记作x1,x2,xn,即即 x1,x2,xn,=,xn 例如例如:,是三元组是三元组.例如例如:n维空间中的点的坐标维空间中的点的坐标.例如例如:n维向
3、量是维向量是n元组元组现在学习的是第4页，共66页笛卡儿积笛卡儿积1.定义定义4.3:设设A,B为集合为集合,用用A中的元素为第一元素中的元素为第一元素,B中元素为第二元素，构成有序对，所有这样的中元素为第二元素，构成有序对，所有这样的有序对组成的集合叫做有序对组成的集合叫做A和和B的的笛卡尔积笛卡尔积，记作，记作AxB,符号化表示符号化表示为 AxB=|x Ay B。例如例如:A=a,b,B=0,1,2,则 AxB=,;BxA=,.如果如果A中的元素中的元素为m个元素，个元素，B中的元素中的元素为n个元素，个元素，则AxB和和BxA中有中有mn个元素个元素x,y AxB,则x A,y B,x
4、,y AxB,则x A或或y B现在学习的是第5页，共66页笛卡儿积运算具有的性质笛卡儿积运算具有的性质(1)1.若若A,B中有一个空集中有一个空集,则它们的笛卡儿积是空集则它们的笛卡儿积是空集,即即 xB=Ax=2.当当AB且且A,B都不是空集都不是空集时,有有 AxBBxA 笛卡儿笛卡儿积不适合交不适合交换律律3.当当A,B,C都不是空集都不是空集时,有有 (AxB)xCAx(BxC)笛卡儿笛卡儿积不适合不适合结合律合律,z(AxB)xC,x,Ax(BxC),x,(AxB)xC.现在学习的是第6页，共66页笛卡儿积运算具有的性质笛卡儿积运算具有的性质(2)1.笛卡儿积运算对笛卡儿积运算对
5、或或 运算满足分配律运算满足分配律,Ax(B C)=(AxB)(AxC)(B C)xA=(BxA)(CxA)Ax(B C)=(AxB)(AxC)(B C)xA=(BxA)(CxA)2.证明明:对任意的任意的 Ax(B C)x Ay(B C)x A(y B y C)(x A y B)(x A y C)(AxB)(AxC)(AxB)(AxC)所以：所以：Ax(B C)=(AxB)(AxC)成立成立.现在学习的是第7页，共66页例题例题(1)1.设设A=1,2,求求P(A)xA P(A)xA=,1,2,1,2 x1,2 =,2.判断下列命判断下列命题的真假的真假若若A C且且B D,则有有AxB C
6、xD;(真真)若若AxB CxD,则有有A C且且B D.(假假)现在学习的是第8页，共66页n阶笛卡儿积阶笛卡儿积1.定定义4.4 设A1,A2,An,是集合是集合(n 2),它它们的的n阶笛卡儿积记作阶笛卡儿积记作A1x A2x xAn,其中其中 A1x A2x xAn|x1 A1,x2 A2,.,xn An 当当A1 A2 An A时可可记为An例题例题:A=a,b,c,则则A3=,现在学习的是第9页，共66页二元关系二元关系1.定义定义4.5:如果一个集合为空集或者它的元素都是如果一个集合为空集或者它的元素都是有序对有序对,则称这个集合是一个则称这个集合是一个二元关系二元关系,一般记作
7、一般记作R,对于二元关系对于二元关系R,如果如果 R,则记作则记作xRy;R,记作记作xRy.本书涉及二元关系，（其它本书涉及二元关系，（其它n元关系不在本书之列），元关系不在本书之列），书中涉及的关系全为二元关系书中涉及的关系全为二元关系现在学习的是第10页，共66页A到到B的二元关系的二元关系定义定义4.6：设：设A,B为集合，为集合，AxB的任何子集所定的任何子集所定义的二元关系称作的二元关系称作从从A到到B的二元关系的二元关系，特，特别当当A=B时,则叫做叫做A上的二元关系上的二元关系.如果如果|A|=n,则|AxA|=n2.AxA的子集有的子集有 个个,每一个子集代表一个每一个子集代
8、表一个A上的关系上的关系.其中之一是其中之一是空集空集,称做空关系称做空关系.另外两种就是另外两种就是全域关系全域关系EA和恒等关系和恒等关系IA.定定义4.7:对任何集合任何集合A,EA=|x A y A=AxA.IA=|x A.例如例如,A=0,1,2,则 EA=,IA=,现在学习的是第11页，共66页关系实例关系实例1.设设A为实数集为实数集R的某个子集的某个子集,则则A上的小于等于关系定义为上的小于等于关系定义为 LA=|x,y A,x y.2.例例4.4 设设A=a,b,R是是P(A)上的包含关系上的包含关系,R=|x,y P(A),x y,则有则有 P(A)=,a,b,A.R=,.
9、现在学习的是第12页，共66页关系矩阵关系矩阵1.设设 A=x1,x2,.,xn,R是是A上的关系上的关系,令令ri,j=1 若若xiRxj0 若若xiRxjri,j=r11 r12 .r1n.r21 r22 .r2nrn1 rn2 .rnnri,j=是关系矩阵是关系矩阵现在学习的是第13页，共66页例题例题1.设设A=1,2,3,4,R=,的关系图和关系矩阵为的关系图和关系矩阵为:1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0现在学习的是第14页，共66页关系图关系图1.设设V是顶点的集合是顶点的集合,E是有向边的集合是有向边的集合,令令V=x1,x2,.,xn,如果如果xi
10、Rxj,则有则有 E,那么那么G=就是就是R的的关系图关系图.现在学习的是第15页，共66页例题例题1.设设A=1,2,3,4,R=,的关系图和关系矩阵为的关系图和关系矩阵为:1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 01243现在学习的是第16页，共66页内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数现在学习的是第17页，共66页关系的定义域和值域关系的定义域和值域1
11、.定义定义4.8:关系关系R的定义域的定义域domR,值域值域ranR和域和域fldR分别是分别是:domR=x|y(R).ranR=y|x(R).fldR=domR ranR.现在学习的是第18页，共66页例题例题1.例题例题4.8:下列关系都是整数集下列关系都是整数集Z上的关系上的关系,分别求出它们的定义域分别求出它们的定义域和值域和值域.R1=|x,y Z x y;R2=|x,y Z x2+y2=1;2.domR1=ranR1=Z.R=,domR2=ramR2=0,1,-13.图解方法图解方法10-110-1R2domR2ranR2现在学习的是第19页，共66页逆、合成、限制和象逆、合成
12、、限制和象1.定义定义4.9:设设F,G为任意的关系为任意的关系,A为集合为集合,则则F的逆记作的逆记作F-1,F-1=|yFx;F与与G的合成记作的合成记作FoG=|z（xGz zFy）;F在在A上的限制记作上的限制记作F A=|xFy x A;A在在F下的象下的象FA=ran(F A).现在学习的是第20页，共66页例题例题1.设设F,G是是N上的关系上的关系,其定义为其定义为F=|x,y N y=x2;G=|x,y N y=x+1,求求G-1,FoG,F 1,2,F1,22.解解:G-1=,.,.;z(z=x+1)y=z2)FoG=|x,y N y=(x+1)2F 1,2=,F1,2=r
13、an(F 1,2)=1,4现在学习的是第21页，共66页等式等式(1)1.定理定理4.1:设设F,G,H是任意的关系是任意的关系,则有则有(F-1)-1=FdomF-1=ranF,ranF-1=domF;(FoG)OH=Fo(GoH);(FoG)-1=G-1oF-12.证明证明(4)任取任取,(FoG)-1 (FoG)z(G)(F)z(G-1)(F-1)G-1 O F-1 现在学习的是第22页，共66页等式等式(2)1.定理定理4.2 设设F,G,H为任意的关系为任意的关系,则有则有Fo(G H)=FoG FoH;Fo(G H)FoG FoH;(G H)Of=GoF HoF;(G H)oF G
14、oF HoF;2.证明证明(1)取取 Fo(G H)z(G H F)z(G H)F)z(G F)(H F)FoG FoH FoG FoH现在学习的是第23页，共66页n次幂次幂1.定义定义4.10 设设R为为A上的关系上的关系,n为自然数为自然数,则则R的的n次幂次幂规定如下规定如下:R0=|x A;Rn=Rn-1oR,n 1.2.由上可知由上可知:RoR0=R=R0oR现在学习的是第24页，共66页例题例题(关系图法关系图法)1.设设 A=a,b,c,d,R=,求求R0,R1,R2,R3,R4,R5.2.解解:abcdabcdabcdabcdR0R=R1R2=R4R3=R5现在学习的是第25
15、页，共66页例题例题(关系矩阵运算法关系矩阵运算法)1.设设 A=a,b,c,d,R=,求求R0,R1,R2,R3,R4,R5.2.解解:rij=ri1.r1j+ri2.r2j+ri3.r3j+ri4.r4j0+0=0;0+1=1,1+0=1,1+1=10 1 0 01 0 1 00 0 0 10 0 0 00 1 0 01 0 1 00 0 0 10 0 0 00 1 0 01 0 1 00 0 0 10 0 0 0.1 0 1 00 1 0 10 0 0 00 0 0 00 1 0 01 0 1 00 0 0 10 0 0 00 1 0 11 0 1 00 0 0 00 0 0 0=.现在
16、学习的是第26页，共66页等式等式(3)1.定理定理4.3:设设R为为A上的关系上的关系,m,n是自然数是自然数,则下面的等式成立则下面的等式成立.RmoRn=Rm+n(Rm)n=Rmn证明证明 任意给定任意给定m,对对n进行归纳进行归纳.(1)n=0,RmoR0=Rm=Rm+0假设假设 RmoRn=Rm+n,则则RmoRn+1=Rmo(RnoR)=(RmoRn)oR =Rm+noR =Rm+n+1(2)n=0,(Rm)0=R0=Rm.0.假设假设(Rm)n=Rmn,则则(Rm)n+1=(Rm)noRm =RmnoRm =Rm(n+1)现在学习的是第27页，共66页内容提纲内容提纲1.集合的笛
17、卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数现在学习的是第28页，共66页关系的性质关系的性质1.自反性自反性2.反自反性反自反性3.对称性对称性4.反对称性反对称性5.传递性传递性现在学习的是第29页，共66页定义定义自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性定义定义 x A,有有 R x A,有有 R若若 R则则 R若若 R,且且x y,则则 R若若 R 且且 R 则则 R关系矩阵特
18、关系矩阵特点点主对角线的主对角线的元素全为元素全为1主对角线的主对角线的元素全为元素全为0矩阵为对称矩阵为对称矩阵矩阵如果如果rij=1,且且x y则则rji=0关系图特点关系图特点图中每个节图中每个节点都有环点都有环图中每个节图中每个节点都没有环点都没有环如果两个顶如果两个顶点之间有边点之间有边,一定是一对一定是一对方向相反的方向相反的边边.如果两个顶如果两个顶点之间有边点之间有边,一定是一条一定是一条有向边有向边.如果如果xi到到xj有有边，边，xj到到xk有有边，则边，则xi到到xk一定有边一定有边现在学习的是第30页，共66页例题（）例题（）1.设设A为非空集合，为非空集合，A上的关系
19、可以是自反的，反上的关系可以是自反的，反自反的，或则两者都不是自反的，或则两者都不是A=1,2,3 R1=,(自反自反)R2=,(反自反反自反)R3=,(两者都不是两者都不是)现在学习的是第31页，共66页例题（）例题（）1.设设A为非空集合，为非空集合，A上的关系可以是对称的，反上的关系可以是对称的，反对称的，或则两者都是对称的，或则两者都是,两者都不是两者都不是A=1,2,3 R4=,(对称对称)R5=,(反对称反对称)R6=(两者都是两者都是)R7=,(两者都不是两者都不是)现在学习的是第32页，共66页性质性质1.自反自反/反自反反自反自反关系包含着恒等关系自反关系包含着恒等关系.即即
20、IA R.反自反关系反自反关系R一定与一定与IA不交不交,即即IA R=如果如果IA R 且且IA R,则两者都不是则两者都不是.2.对称对称/反对称反对称A上的对称关系满足上的对称关系满足R-1=R.反对称关系满足反对称关系满足R R-1 IA.如果两者都是如果两者都是R IA3.传递传递满足满足RoR R现在学习的是第33页，共66页例题例题(3)1.判断下面关系的性质判断下面关系的性质123123123现在学习的是第34页，共66页关系演算后的性质关系演算后的性质自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R-1 R1 R2 R1 R2 R1-R2 R1oR2 运
21、算原有性质现在学习的是第35页，共66页证明证明(1)1.设设R1,R2为为A上的对称关系上的对称关系,证明证明R1 R2也是也是A上的上的对称关系对称关系.证明证明:对任意的对任意的,R1 R2 R1 R2 R1 R2 R1 R2现在学习的是第36页，共66页证明证明(2)1.R1,R2是是A上的反对称关系上的反对称关系,则则R1 R2不一定是不一定是A上上的反对称关系的反对称关系,例如例如A=x1,x2,R1=,R2=.R1 R2=,.现在学习的是第37页，共66页内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的
22、闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数现在学习的是第38页，共66页自反闭包自反闭包,对称闭包对称闭包,传递闭包传递闭包1.定义定义4.11:设设R是非空集合是非空集合A上的关系上的关系,R的的自反闭自反闭包包(对称闭包或传递闭包对称闭包或传递闭包)是是A上的关系上的关系R,且且R满满足以下条件足以下条件:R是自反的是自反的(对称的或传递的对称的或传递的);R R;对对A上的任何包含上的任何包含R的自反关系的自反关系(对称或传递关系对称或传递关系)R都有都有R R.一般将一般将R的自反闭包记作的自反闭包
23、记作r(A),对称闭包对称闭包s(A),传递闭包传递闭包t(A)现在学习的是第39页，共66页例题例题1.例例4.10 设设A=a,b,c,d,R=,则则R和和r(A),s(A),t(A)的关系图如下的关系图如下:abcdabcdabcdabcdRr(R)s(R)t(R)现在学习的是第40页，共66页定理定理1.定理定理4.4:设设R为非空集合为非空集合A上的关系上的关系,则有则有r(R)=R R0;s(R)=R R-1;t(R)=R R2 R3 .现在学习的是第41页，共66页求各种闭包求各种闭包1.R=,求求r(A),s(A),t(A)r(A)=R R0=,=,s(A)=R R-1=,=,
24、t(A)=R R2 R3=,=,现在学习的是第42页，共66页采用关系矩阵求闭包采用关系矩阵求闭包1.设设R的关系矩阵为的关系矩阵为M,求相应的自反、对称、传递求相应的自反、对称、传递闭包的矩阵为闭包的矩阵为Mr，Ms，Mt，则有，则有Mr=M+E；Ms=M+MMt=M+M2+M3+.E表示同阶的单位矩阵表示同阶的单位矩阵,M为为M的转置的转置,而而+均表示矩阵中对均表示矩阵中对应元素的逻辑加应元素的逻辑加.现在学习的是第43页，共66页Mr0 1 0 010 1 00 0 0 10 0 0 01 0 0 00 1 0 00 0 1 00 0 0 11 1 0 01 1 1 00 0 1 10
25、 0 0 1+=Mr =现在学习的是第44页，共66页Ms0 1 0 010 1 00 0 0 10 0 0 00 1 0 01 0 0 00 1 0 00 0 1 00 1 0 01 0 1 00 1 0 10 0 1 0+=Ms =现在学习的是第45页，共66页Mt0 1 0 010 1 00 0 0 10 0 0 01 0 1 00 1 0 10 1 0 00 0 0 00 1 0 11 0 1 00 0 0 00 0 0 0+Mt =1 1 1 11 1 1 10 0 0 10 0 0 0=现在学习的是第46页，共66页内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关
26、系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系现在学习的是第47页，共66页等价关系等价关系1.定义定义.12 设设 R为非空集合为非空集合A上的关系上的关系,如果如果R是是自反的、对称的和传递的，则称自反的、对称的和传递的，则称R为为A上的上的等价等价关系关系。对任何。对任何x，y A，如果，如果 等价关系等价关系R，则记作，则记作x y。现在学习的是第48页，共66页例题例题(1)1.例例 4.11:A=1,2,.,8,R=|x,y A x y(mod 3),其中其中x y(mod 3)为为x-y被被3整除整除.R为为A上
27、的等价关系上的等价关系.14725836 推广推广:对任何正整数对任何正整数n,可以给定整数集合可以给定整数集合Z上的模上的模n的等的等价关系价关系:R=|x,y Z x y(mod n).现在学习的是第49页，共66页例题例题(2),相容关系相容关系1.在一群人的集合上在一群人的集合上,年龄相等是等价关系年龄相等是等价关系,而朋友而朋友关系不一定是等价关系关系不一定是等价关系,因为它可能不是传递的因为它可能不是传递的.一般这种自反的对称的关系为一般这种自反的对称的关系为相容关系相容关系.显然等显然等价关系都是相容关系价关系都是相容关系.2.动物是按种属分类的动物是按种属分类的,”具有相同种属
28、具有相同种属”的关系是的关系是动物集合上的等价关系动物集合上的等价关系.3.集合上的集合上的恒等关系恒等关系和和全域关系全域关系是等价关系是等价关系.现在学习的是第50页，共66页等价类等价类1.定义定义4.13:设设R是非空集合是非空集合A上的等价关系上的等价关系,对任对任意的意的x A,令令xR=y|y A xRy,则称为则称为x关于关于R的等价类的等价类,简称简称xR为为x关于关于R的等价类的等价类,简记为简记为x.147258361=4=7=1,4,72=5=8=2,5,83=6=3,6现在学习的是第51页，共66页等价类的性质等价类的性质(1)定理定理4.5:设设R是非空集合是非空集
29、合A上的等价关系上的等价关系,对任意的对任意的x,y A,下面的结论成立下面的结论成立.x,且且x A;若若xRy,则则x=y;若若xRy,则则x y=;.现在学习的是第52页，共66页商集商集1.定义定义4.14:设设R为非空集合为非空集合A上的等价关系上的等价关系,以以R的的不交的等价类为元素的集合叫做不交的等价类为元素的集合叫做A在在R下的商集下的商集,记作记作A/R,即即 A/R=xR|x A.A/R=1,4,7,2,5,8,3,6.现在学习的是第53页，共66页例题例题1.非空集合非空集合A上的全域关系上的全域关系EA是是A上的等价关系上的等价关系,对对任意任意x A有有x=A,商集
30、商集A/EA=A.2.非空集合非空集合A上的恒等关系上的恒等关系IA是是A上的等价关系上的等价关系,任任意意x A有有x=x,商集商集A/IA=x|x A.3.在整数集合在整数集合Z上模上模n的等价关系的等价关系,其等价类是其等价类是0=.,-2n,-n,0,n,2n,.=nz|z Z=Nz,.现在学习的是第54页，共66页划分划分,划分块划分块1.定义定义4.15:设设A是非空集合是非空集合,如果存在一个如果存在一个A的子集的子集族族(P(A)满足以下条件足以下条件,中任意两个元素不交中任意两个元素不交;中所有元素的并集等于中所有元素的并集等于A;则称称为A的一个的一个划分划分,且称且称中的
31、元素中的元素为划分划分块.现在学习的是第55页，共66页例题例题1.考虑集合考虑集合A=a,b,c,d的下列子集族的下列子集族a,b,c,d;(A的划分的划分)a,b,c,d;(A的划分的划分)a,b,c,a,d;不是不是A的划分的划分,a,b,c,d;不是不是A的划分的划分a,b,c;不是不是A的划分的划分2.R是是A上的等价关系上的等价关系,则则A/R是一个划分是一个划分,等价关系等价关系和划分是一一对应的和划分是一一对应的.现在学习的是第56页，共66页例题例题1.例题例题4.15:设设A=1,2,3,求出求出A上所有的等价关系上所有的等价关系.解解:先求先求A的各种划分的各种划分:1划
32、分块的划分块的,2划分块的划分块的,3划分划分块的块的.21312132213321342135现在学习的是第57页，共66页求等价关系求等价关系1.R5=,=IA2.R1=,IA=EA.3.R2=,IA 4.R3=,IA 5.R4=,IA现在学习的是第58页，共66页偏序关系偏序关系(偏序偏序)1.定义定义4.16:设设R为非空集合为非空集合A上的关系上的关系,如果如果R是自反的是自反的,反对称的和传递的反对称的和传递的,则称则称R为为A上的上的偏序关系偏序关系,简称简称偏序偏序,记作记作.任何集合任何集合A上的恒等关系上的恒等关系,集合的幂集集合的幂集P(A)上上的包含关系的包含关系,实数
33、集上的小于等于关系实数集上的小于等于关系,正整数正整数集上的整除关系都是偏序关系集上的整除关系都是偏序关系.=,3 2,2 2,3 1现在学习的是第59页，共66页偏序集偏序集1.定义定义4.17:一个集合一个集合A与与A上上偏序关系偏序关系R一起叫做一起叫做偏序集偏序集,记作记作.例如例如,都是偏序集都是偏序集.现在学习的是第60页，共66页可比可比,盖住盖住1.定义定义4.18:设设为为偏序集偏序集,对于任意的对于任意的x,y A,如果如果x y或者或者y x成立成立,则称则称x与与y是是可比可比的的,如果如果xy(即即x y x y),且不存在且不存在z A使得使得xzy,则称则称y盖住
34、盖住x.是是A=1,2,3,4,5上的整除关系上的整除关系,1和任意元素和任意元素有整除关系有整除关系,所以所以1和和1,2,3,4,5是可比的是可比的.但但2不能整除不能整除3,所以所以2和和3是不可比的是不可比的.1 2并且不存在一个并且不存在一个z使得使得1z2,所以所以2盖住盖住1,同样同样4盖住盖住2,但但4不盖住不盖住1.现在学习的是第61页，共66页全序关系全序关系,全序集全序集1.定义定义4.19:设设为偏序集为偏序集,若对任意的若对任意的x,y A,x和和y都可比都可比,则称则称 为为A上的上的全序关全序关系系,且称且称为为全序集全序集.如如1,2,3,4,5上的小于等于关系
35、上的小于等于关系.现在学习的是第62页，共66页哈斯图哈斯图1.画出画出和和的哈的哈斯图斯图.171193612248510cabb,ca,ba,ca,b,c现在学习的是第63页，共66页例题例题1.设偏序集设偏序集的哈斯图如图的哈斯图如图4.10所示所示,求出集求出集合合A的偏序的偏序.解解 A=a,b,c,d,e,f,g,h =,IA.由哈斯图可以看出全序集是一条直线由哈斯图可以看出全序集是一条直线.abcdefgh现在学习的是第64页，共66页最小元最小元,最大元最大元,极小元极小元,极大元极大元1.定义定义4.20:设设为偏序集为偏序集,B A.若若 y B,使得使得 x(x By x)成立成立,则称则称y是是B的的最小元最小元;若若 y B,使得使得 x(x Bx y)成立成立,则称则称y是是B的的最大元最大元;若若 y B,使得使得 x(x B xy)成立成立,则称则称y是是B的的极小极小元元.若若 y B,使得使得 x(x B yx)成立成立,则称则称y是是B的的极大极大元元.现在学习的是第65页，共66页例题例题:说出最大说出最大/小元和极大小元和极大/小元小元abcdefgh171193612248510cabb,ca,ba,ca,b,c现在学习的是第66页，共66页