离散数学第四章二元关系和函数课件.ppt

1、2023年1月5日星期四离散数学第四章二元关离散数学第四章二元关系和函数系和函数内容提纲内容提纲1.集合的笛卡尔积与二元关集合的笛卡尔积与二元关系系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数序偶序偶定义定义4.1:由两个元素由两个元素x和和y（允许（允许x=y）按一定的）按一定的顺序排列成的二元组叫作顺序排列成的二元组叫作有序对有序对(也称也称序偶序偶),记作记作(也可记作也可记作(x,y).其中其中x是它的是它的第一元素第一元素,y是是它的它的第二

2、元素第二元素.例如平面直角的坐标例如平面直角的坐标:,他的特性他的特性是是:当当xy时时,=等充分必要条件是等充分必要条件是x=u,y=v.序偶与集合的关系序偶与集合的关系,但但x,y=y,x有序有序n元组元组定义定义4.2:一个有序一个有序n元组元组(3n)是一个有序对是一个有序对,其其中第一个元素是一个中第一个元素是一个有序有序n-1元组元组，一个有序，一个有序n元组记作元组记作x1,x2,xn,即即 x1,x2,xn,=,xn 例如例如:,是三元组是三元组.例如例如:n维空间中的点的坐标维空间中的点的坐标.例如例如:n维向量是维向量是n元组元组笛卡儿积笛卡儿积定义定义4.3:设设A,B为

3、集合为集合,用用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,y AxB,则则x A或或y B笛卡儿积运算具有的性质笛卡儿积运算具有的性质(1)若

4、若A,B中有一个空集中有一个空集,则它们的笛卡儿积是空集则它们的笛卡儿积是空集,即即 xB=Ax=当当AB且且A,B都不是空集时都不是空集时,有有 AxBBxA 笛卡儿积不适合交换律笛卡儿积不适合交换律当当A,B,C都不是空集时都不是空集时,有有 (AxB)xCAx(BxC)笛卡儿积不适合结合律笛卡儿积不适合结合律,z(AxB)xC,x,Ax(BxC),x,(AxB)xC.笛卡儿积运算具有的性质笛卡儿积运算具有的性质(2)笛卡儿积运算对笛卡儿积运算对 或或 运算满足分配律运算满足分配律,Ax(B C)=(AxB)(AxC)(B C)xA=(BxA)(CxA)Ax(B C)=(AxB)(AxC)

5、(B C)xA=(BxA)(CxA)证明证明:对任意的对任意的 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)成立成立.例题例题(1)设设A=1,2,求求P(A)xA P(A)xA=,1,2,1,2 x1,2 =,判断下列命题的真假判断下列命题的真假若若A C且且B D,则有则有AxB CxD;(真真)若若AxB CxD,则有则有A C且且B D.(假假)n阶笛卡儿积阶笛卡儿积定义定义4.4 设设A1,A2,An,是集合是集合(n 2),它们的它们的n阶阶笛卡儿

6、积记作笛卡儿积记作A1x A2x xAn,其中其中 A1x A2x xAn|x1 A1,x2 A2,.,xn An 当当A1 A2 An A时可记为时可记为An例题例题:A=a,b,c,则则A3=,二元关系二元关系定义定义4.5:如果一个集合为空集或者它的元素都是如果一个集合为空集或者它的元素都是有序对有序对,则称这个集合是一个则称这个集合是一个二元关系二元关系,一般记作一般记作R,对于二元关系对于二元关系R,如果如果 R,则记作则记作xRy;R,记作记作x y.本书涉及二元关系，（其它本书涉及二元关系，（其它n元关系不在本书之列），元关系不在本书之列），书中涉及的关系全为二元关系书中涉及的关

7、系全为二元关系A到到B的二元关系的二元关系 定义4.6：设A,B为集合，AxB的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时,则叫做A上的二元关系.如果|A|=n,则|AxA|=n2.AxA的子集有 个,每一个子集代表一个A上的关系.其中之一是空集,称做空关系.另外两种就是全域关系EA和恒等关系IA.定义4.7:对任何集合A,EA=|xAyA=AxA.IA=|xA.例如,A=0,1,2,则 EA=,IA=,关系实例关系实例设设A为实数集为实数集R的某个子集的某个子集,则则A上的小于等于关系定义为上的小于等于关系定义为 LA=|x,y A,x y.例例4.4 设设A=a,b,R

8、是是P(A)上的包含关系上的包含关系,R=|x,y P(A),x y,则有则有 P(A)=,a,b,A.R=,.关系矩阵关系矩阵设设 A=x1,x2,.,xn,R是是A上的关系上的关系,令令ri,j=1 若若xiRxj0 若若xiRxjri,j=r11 r12 .r1n.r21 r22 .r2nrn1 rn2 .rnnri,j=是关系矩阵是关系矩阵例题例题设设A=1,2,3,4,R=,的关系图和关系矩阵为的关系图和关系矩阵为:1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0关系图关系图设设V是顶点的集合是顶点的集合,E是有向边的集合是有向边的集合,令令V=x1,x2,.,xn,如

9、果如果xiRxj,则有则有 E,那么那么G=就是就是R的的关系图关系图.例题例题 设设A=1,2,3,4,R=,的关系图和关系矩阵为的关系图和关系矩阵为:1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 01243内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数关系的定义域和值域关系的定义域和值域定义定义4.8:关系关系R的定义域的定义域domR,值域值域ranR和域和域fldR

10、分别是分别是:domR=x|y(R).ranR=y|x(R).fldR=domR ranR.例题例题例题例题4.8:下列关系都是整数集下列关系都是整数集Z上的关系上的关系,分别求出它们分别求出它们的定义域和值域的定义域和值域.R1=|x,y Z x y;R2=|x,y Z x2+y2=1;domR1=ranR1=Z.R=,domR2=ramR2=0,1,-1图解方法图解方法10-110-1R2domR2ranR2逆、合成、限制和象逆、合成、限制和象定义定义4.9:设设F,G为任意的关系为任意的关系,A为集合为集合,则则F的逆记作的逆记作F-1,F-1=|yFx;F与与G的合成记作的合成记作Fo

11、G=|z（xGz zFy）;F在在A上的限制记作上的限制记作F A=|xFy x A;A在在F下的象下的象FA=ran(F A).例题例题设设F,G是是N上的关系上的关系,其定义为其定义为F=|x,y N y=x2;G=|x,y N y=x+1,求求G-1,FoG,F 1,2,F1,2解解:G-1=,.,.;z(z=x+1)y=z2)FoG=|x,y N y=(x+1)2F 1,2=,F1,2=ran(F 1,2)=1,4等式等式(1)定理定理4.1:设设F,G,H是任意的关系是任意的关系,则有则有(F-1)-1=FdomF-1=ranF,ranF-1=domF;(FoG)OH=Fo(GoH)

12、;(FoG)-1=G-1oF-1证明证明(4)任取任取,(FoG)-1 (FoG)z(G)(F)z(G-1)(F-1)G-1 O F-1 等式等式(2)定理定理4.2 设设F,G,H为任意的关系为任意的关系,则有则有Fo(G H)=FoG FoH;Fo(G H)FoG FoH;(G H)Of=GoF HoF;(G H)oF GoF HoF;证明证明(1)取取 Fo(G H)z(G H F)z(G H)F)z(G F)(H F)FoG FoH FoG FoHn次幂次幂定义定义4.10 设设R为为A上的关系上的关系,n为自然数为自然数,则则R的的n次幂次幂规定如下规定如下:R0=|x A;Rn=R

13、n-1oR,n 1.由上可知由上可知:RoR0=R=R0oR例题例题(关系图法关系图法)设设 A=a,b,c,d,R=,求求R0,R1,R2,R3,R4,R5.解解:abcdabcdabcdabcdR0R=R1R2=R4R3=R5例题例题(关系矩阵运算法关系矩阵运算法)设设 A=a,b,c,d,R=,求求R0,R1,R2,R3,R4,R5.解解: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

14、 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=.等式等式(3)定理定理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)

15、0=R0=Rm.0.假设假设(Rm)n=Rmn,则则(Rm)n+1=(Rm)noRm =RmnoRm =Rm(n+1)内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数关系的性质关系的性质自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性定义定义自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性定义定义 x A,有有 R x A,有有 R若若 R则则 R若

16、若 R,且且x y,则则 R若若 R 且且 R 则则 R关系矩阵特关系矩阵特点点主对角线的主对角线的元素全为元素全为1主对角线的主对角线的元素全为元素全为0矩阵为对称矩阵为对称矩阵矩阵如果如果rij=1,且且x y则则rji=0关系图特点关系图特点图中每个节图中每个节点都有环点都有环图中每个节图中每个节点都没有环点都没有环如果两个顶如果两个顶点之间有边点之间有边,一定是一对一定是一对方向相反的方向相反的边边.如果两个顶如果两个顶点之间有边点之间有边,一定是一条一定是一条有向边有向边.如果如果xi到到xj有有边，边，xj到到xk有有边，则边，则xi到到xk一定有边一定有边例题（）例题（）设设A为

17、非空集合，为非空集合，A上的关系可以是自反的，反上的关系可以是自反的，反自反的，或则两者都不是自反的，或则两者都不是A=1,2,3 R1=,(自反自反)R2=,(反自反反自反)R3=,(两者都不是两者都不是)例题（）例题（）设设A为非空集合，为非空集合，A上的关系可以是对称的，反上的关系可以是对称的，反对称的，或则两者都是对称的，或则两者都是,两者都不是两者都不是A=1,2,3 R4=,(对称对称)R5=,(反对称反对称)R6=(两者都是两者都是)R7=,(两者都不是两者都不是)性质性质自反自反/反自反反自反自反关系包含着恒等关系自反关系包含着恒等关系.即即IA R.反自反关系反自反关系R一定

18、与一定与IA不交不交,即即IA R=如果如果IA R 且且IA R,则两者都不是则两者都不是.对称对称/反对称反对称A上的对称关系满足上的对称关系满足R-1=R.反对称关系满足反对称关系满足R R-1 IA.如果两者都是如果两者都是R IA传递传递满足满足RoR R例题例题(3)判断下面关系的性质判断下面关系的性质123123123关系演算后的性质关系演算后的性质自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R-1 R1 R2 R1 R2 R1-R2 R1oR2 运算原有性质证明证明(1)设设R1,R2为为A上的对称关系上的对称关系,证明证明R1 R2也是也是A上上的对称

19、关系的对称关系.证明证明:对任意的对任意的,R1 R2 R1 R2 R1 R2 R1 R2证明证明(2)R1,R2是是A上的反对称关系上的反对称关系,则则R1 R2不一定是不一定是A上的反对称关系上的反对称关系,例如例如A=x1,x2,R1=,R2=.R1 R2=,.内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系6.函数的定义和性质函数的定义和性质7.函数的复合和反函数函数的复合和反函数自反闭包自反闭包,对称闭包对称闭包,传递闭包传递闭包定义定义4.11:设设R

20、是非空集合是非空集合A上的关系上的关系,R的的自反闭自反闭包包(对称闭包或传递闭包对称闭包或传递闭包)是是A上的关系上的关系R,且且R满满足以下条件足以下条件:R是自反的是自反的(对称的或传递的对称的或传递的);R R;对对A上的任何包含上的任何包含R的自反关系的自反关系(对称或传递关系对称或传递关系)R都有都有R R.一般将一般将R的自反闭包记作的自反闭包记作r(A),对称闭包对称闭包s(A),传递闭包传递闭包t(A)例题例题例例4.10 设设A=a,b,c,d,R=,则则R和和r(A),s(A),t(A)的关系图如下的关系图如下:abcdabcdabcdabcdRr(R)s(R)t(R)定

21、理定理定理定理4.4:设设R为非空集合为非空集合A上的关系上的关系,则有则有r(R)=R R0;s(R)=R R-1;t(R)=R R2 R3 .求各种闭包求各种闭包R=,求求r(A),s(A),t(A)r(A)=R R0=,=,s(A)=R R-1=,=,t(A)=R R2 R3=,=,采用关系矩阵求闭包采用关系矩阵求闭包设设R的关系矩阵为的关系矩阵为M,求相应的自反、对称、传递求相应的自反、对称、传递闭包的矩阵为闭包的矩阵为Mr，Ms，Mt，则有，则有Mr=M+E；Ms=M+MMt=M+M2+M3+.E表示同阶的单位矩阵表示同阶的单位矩阵,M为为M的转置的转置,而而+均表示矩阵中对均表示矩

22、阵中对应元素的逻辑加应元素的逻辑加.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 0 0 1+=Mr =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 =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

23、 1 10 0 0 10 0 0 0=内容提纲内容提纲1.集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系2.关系的运算关系的运算3.关系的性质关系的性质4.关系的闭包关系的闭包5.等价关系和偏序关系等价关系和偏序关系等价关系等价关系定义定义.12 设设 R为非空集合为非空集合A上的关系上的关系,如果如果R是是自反的、对称的和传递的，则称自反的、对称的和传递的，则称R为为A上的上的等价等价关系关系。对任何。对任何x，y A，如果，如果 等价关系等价关系R，则记作则记作x y。例题例题(1)例例 4.11:A=1,2,.,8,R=|x,y A x y(mod 3),其中其中x y(mod 3)为

24、为x-y被被3整除整除.R为为A上的等价关系上的等价关系.14725836 推广推广:对任何正整数对任何正整数n,可以给定整数集合可以给定整数集合Z上的模上的模n的等价关系的等价关系:R=|x,y Z x y(mod n).例题例题(2),相容关系相容关系在一群人的集合上在一群人的集合上,年龄相等是等价关系年龄相等是等价关系,而朋友而朋友关系不一定是等价关系关系不一定是等价关系,因为它可能不是传递的因为它可能不是传递的.一般这种自反的对称的关系为一般这种自反的对称的关系为相容关系相容关系.显然等显然等价关系都是相容关系价关系都是相容关系.动物是按种属分类的动物是按种属分类的,”具有相同种属具有

25、相同种属”的关系是的关系是动物集合上的等价关系动物集合上的等价关系.集合上的集合上的恒等关系恒等关系和和全域关系全域关系是等价关系是等价关系.等价类等价类定义定义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等价类的性质等价类的性质(1)定理4.5:设R是非空集合A上的等价关系,对任意的x,yA,下面的结论成立.x,且xA;若xRy,则x=y;若x

26、Ry,则xy=;.商集商集定义定义4.14:设设R为非空集合为非空集合A上的等价关系上的等价关系,以以R的的不交的等价类为元素的集合叫做不交的等价类为元素的集合叫做A在在R下的商集下的商集,记作记作A/R,即即 A/R=xR|x A.A/R=1,4,7,2,5,8,3,6.例题例题非空集合非空集合A上的全域关系上的全域关系EA是是A上的等价关系上的等价关系,对对任意任意x A有有x=A,商集商集A/EA=A.非空集合非空集合A上的恒等关系上的恒等关系IA是是A上的等价关系上的等价关系,任任意意x A有有x=x,商集商集A/IA=x|x A.在整数集合在整数集合Z上模上模n的等价关系的等价关系,

27、其等价类是其等价类是0=.,-2n,-n,0,n,2n,.=nz|z Z=Nz,.划分划分,划分块划分块定义定义4.15:设设A是非空集合是非空集合,如果存在一个如果存在一个A的子集的子集族族(P(A)满足以下条件满足以下条件,中任意两个元素不交中任意两个元素不交;中所有元素的并集等于中所有元素的并集等于A;则称则称为为A的一个的一个划分划分,且称且称中的元素为中的元素为划分块划分块.例题例题考虑集合考虑集合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的划分的

28、划分a,b,c;不是不是A的划分的划分R是是A上的等价关系上的等价关系,则则A/R是一个划分是一个划分,等价关系等价关系和划分是一一对应的和划分是一一对应的.例题例题例题例题4.15:设设A=1,2,3,求出求出A上所有的等价关系上所有的等价关系.解解:先求先求A的各种划分的各种划分:1划分块的划分块的,2划分块的划分块的,3划分划分块的块的.21312132213321342135求等价关系求等价关系R5=,=IAR1=,IA=EA.R2=,IA R3=,IA R4=,IA偏序关系偏序关系(偏序偏序)定义定义4.16:设设R为非空集合为非空集合A上的关系上的关系,如果如果R是自反的是自反的,

29、反对称的和传递的反对称的和传递的,则称则称R为为A上的上的偏序关系偏序关系,简称简称偏序偏序,记作记作.任何集合任何集合A上的恒等关系上的恒等关系,集合的幂集集合的幂集P(A)上上的包含关系的包含关系,实数集上的小于等于关系实数集上的小于等于关系,正整数正整数集上的整除关系都是偏序关系集上的整除关系都是偏序关系.=,3 2,2 2,3 1偏序集偏序集定义定义4.17:一个集合一个集合A与与A上上偏序关系偏序关系R一起叫做一起叫做偏序集偏序集,记作记作.例如例如,都是偏序集都是偏序集.可比可比,盖住盖住定义定义4.18:设设为为偏序集偏序集,对于任意的对于任意的x,y A,如果如果x y或者或者

30、y x成立成立,则称则称x与与y是是可比可比的的,如果如果xy(即即x y x y),且不存在且不存在z A使得使得xzy,则称则称y盖住盖住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.全序关系全序关系,全序集全序集定义定义4.19:设设为偏序集为偏序集,若对任意的若对任意的x,y A,x和和y都可比都可比,则

31、称则称 为为A上的上的全序关全序关系系,且称且称为为全序集全序集.如如1,2,3,4,5上的小于等于关系上的小于等于关系.哈斯图哈斯图画出画出和和的哈的哈斯图斯图.171193612248510cabb,ca,ba,ca,b,c例题例题设偏序集设偏序集的哈斯图如图的哈斯图如图4.10所示所示,求出集合求出集合A的偏序的偏序.解解 A=a,b,c,d,e,f,g,h =,IA.由哈斯图可以看出全序集是一条直线由哈斯图可以看出全序集是一条直线.abcdefgh最小元最小元,最大元最大元,极小元极小元,极大元极大元定义定义4.20:设设为偏序集为偏序集,B A.若若 y B,使得使得 x(x By

32、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的的极大元极大元.例题例题:说出最大说出最大/小元和极大小元和极大/小元小元abcdefgh171193612248510cabb,ca,ba,ca,b,c上界上界,下界下界,最小上界最小上界,最大下界最大下界定义定义4.21:设设为偏序集为偏序集,B A.若若 y A,使得使得 x(x Bx y)成立成立,则称则称y是是B的的上界上界;若若 y A,使得使得 x(x By x)成立成立,则称则称y是是B的的下界下界;令令C=y|y为为B的上界的上界,则称则称C的最小元为的最小元为B最小上界最小上界,或或上确界上确界.令令C=y|y为为B的下界的下界,则称则称C的最大元为的最大元为B最大下界最大下界,或或下确界下确界.例题例题:说出上界说出上界/下界等下界等abcdefgh171193612248510cabb,ca,ba,ca,b,c