离散数学-二元关系和函数

1第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数24.1集合的笛卡儿积和二元关系有序对笛卡儿积及其性质二元关系的定义二元关系的表示3有序对定义由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作x,y实例：点的直角坐标(3,4)有序对性质有序性x,yy,x（当xy时）x,y与u,v相等的充分必要条件是x,y=u,vx=uy=v例12,x+5=3y4,y，求x,y.解3y4=2,x+5=yy=2,x=34有序n元组定义一个有序n(n3)元组x1,x2,…,xn是一个有序对，其中第一个元素是一个有序n-1元组，即x1,x2,…,xn=x1,x2,…,xn-1,xn当n=1时,x形式上可以看成有序1元组.实例n维向量是有序n元组.5笛卡儿积定义设A,B为集合，A与B的笛卡儿积记作AB，即AB={x,y|xAyB}例2A={1,2,3},B={a,b,c}AB={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}BA={a,1,b,1,c,1,a,2,b,2,c,2,a,3,b,3,c,3}A={},P(A)A={,,{},}6笛卡儿积的性质不适合交换律ABBA(AB,A,B)不适合结合律(AB)CA(BC)(A,B)对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)若A或B中有一个为空集，则AB就是空集.A=B=若|A|=m,|B|=n,则|AB|=mn7性质的证明证明A(BC)=(AB)(AC)证任取x,yx,y∈A×(B∪C)　x∈A∧y∈B∪C　x∈A∧(y∈B∨y∈C)　(x∈A∧y∈B)∨(x∈A∧y∈C)　x,y∈A×B∨x,y∈A×C　x,y∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).8例题解(1)任取x,yx,yACxAyCxByDx,yBD例3(1)证明A=BC=DAC=BD(2)AC=BD是否推出A=BC=D?为什么？(2)不一定.反例如下：A={1}，B={2},C=D=,则AC=BD但是AB.9二元关系的定义定义如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如x,y∈R,可记作xRy；如果x,yR,则记作xy实例：R={1,2,a,b},S={1,2,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.10从A到B的关系与A上的关系定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例4A={0,1},B={1,2,3},R1={0,2},R2=A×B,R3=,R4={0,1}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.计数|A|=n,|A×A|=n2,A×A的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.22n22n11A上重要关系的实例设A为任意集合，是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：　EA={x,y|x∈A∧y∈A}=A×A　IA={x,x|x∈A}例如,A={1,2},则　EA={1,1,1,2,2,1,2,2}　IA={1,1,2,2}12A上重要关系的实例（续）小于等于关系LA,整除关系DA,包含关系R定义：LA={x,y|x,y∈A∧x≤y},AR，R为实数集合DB={x,y|x,y∈B∧x整除y},BZ*,Z*为非0整数集R={x,y|x,y∈A∧xy},A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.13实例例如A={1,2,3},B={a,b},则　LA={1,1,1,2,1,3,2,2,2,3,3,3}　DA={1,1,1,2,1,3,2,2,3,3}A=P(B)={,{a},{b},{a,b}},则A上的包含关系是R={,,,{a},,{b},,{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}14关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A={a1,a2,…,am}，B={b1,b2,…,bn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij=1ai,bjR.关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=A,R,其中A为结点集，R为边集.如果xi,xj属于关系R，在图中就有一条从xi到xj的有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系15实例A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},R的关系矩阵MR和关系图GR如下：0010000011000011RM16基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2关系的运算17关系的基本运算定义定义域、值域和域domR={x|y(x,yR)}ranR={y|x(x,yR)}fldR=domRranR例1R={1,2,1,3,2,4,4,3},则　domR={1,2,4}　ranR={2,3,4}fldR={1,2,3,4}18关系的基本运算定义（续）逆与合成R1={y,x|x,yR}RS=|x,z|y(x,yRy,zS)}例2R={1,2,2,3,1,4,2,2}S={1,1,1,3,2,3,3,2,3,3}R1={2,1,3,2,4,1,2,2}RS={1,3,2,2,2,3}SR={1,2,1,4,3,2,3,3}19合成运算的图示方法利用图示（不是关系图）方法求合成RS={1,3,2,2,2,3}SR={1,2,1,4,3,2,3,3}20限制与像定义F在A上的限制FA={x,y|xFyxA}A在F下的像F[A]=ran(FA)实例R={1,2,2,3,1,4,2,2}R{1}={1,2,1,4}R[{1}]={2,4}R=R[{1,2}]={2,3,4}注意：FAF,F[A]ranF21关系基本运算的性质定理1设F是任意的关系,则　(1)(F1)1=F　(2)domF1=ranF,ranF1=domF证(1)任取x,y,由逆的定义有　x,y∈(F1)1y,x∈F1x,y∈F所以有(F1)1=F(2)任取x,x∈domF1y(x,y∈F1)y(y,x∈F)x∈ranF所以有domF1=ranF.同理可证ranF1=domF.22定理2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1证(1)任取x,y,　x,y(FG)Ht(x,t∈FG∧t,y∈H)t(s(x,s∈F∧s,t∈G)∧t,y∈H)ts(x,s∈F∧s,t∈G∧t,y∈H)s(x,s∈F∧t(s,t∈G∧t,y∈H))s(x,s∈F∧s,y∈GH)x,y∈F(GH)所以(FG)H=F(GH)关系基本运算的性质（续）23(2)任取x,y,　　　x,y∈(FG)1　　y,x∈FG　　t(y,t∈F∧(t,x)∈G)　　t(x,t∈G1∧(t,y)∈F1)　　x,y∈G1F1所以(FG)1=G1F1关系基本运算的性质（续）24A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={x,x|x∈A}=IA(2)Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R25幂的求法对于集合表示的关系R，计算Rn就是n个R右复合.矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.例3设A={a,b,c,d},R={a,b,b,a,b,c,c,d},求R的各次幂,分别用矩阵和关系图表示.解R与R2的关系矩阵分别为0000100001010010M0000000010100101000010000101001000001000010100102M26同理，R0=IA,R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此可以得到　　　R2=R4=R6=…,R3=R5=R7=…0000000010100101,000000000101101043MM10000100001000010M幂的求法（续）27R0,R1,R2,R3,…的关系图如下图所示幂的求法（续）R0R1R2=R4=…R3=R5=…28幂运算的性质定理3设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证R为A上的关系,由于|A|=n,A上的不同关系只有个.当列出R的各次幂R0,R1,R2,…,,…,必存在自然数s和t使得Rs=Rt.22n29定理4设R是A上的关系,m,n∈N,则(1)RmRn=Rm+n(2)(Rm)n=Rmn证用归纳法　(1)对于任意给定的m∈N,施归纳于n.若n=0,则有　　　　RmR0=RmIA=Rm=Rm+0假设RmRn=Rm+n,则有　　　　RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1,所以对一切m,n∈N有RmRn=Rm+n.幂运算的性质（续）30(接上页证明)(2)对于任意给定的m∈N,施归纳于n.若n=0,则有　　(Rm)0=IA=R0=Rm×0假设(Rm)n=Rmn,则有　　(Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1)所以对一切m,n∈N有(Rm)n=Rmn.幂运算的性质（续）14.3关系的性质自反性反自反性对称性反对称性传递性2自反性与反自反性定义设R为A上的关系,(1)若x(x∈A→x,xR),则称R在A上是自反的.(2)若x(x∈A→x,xR),则称R在A上是反自反的.实例：反关系：A上的全域关系EA,恒等关系IA小于等于关系LA,整除关系DA反自反关系：实数集上的小于关系幂集上的真包含关系3实例例1A={1,2,3},R1,R2,R3是A上的关系,其中　　R1＝{1,1,2,2}　　R2＝{1,1,2,2,3,3,1,2}　　R3＝{1,3}R2自反,R3反自反,R1既不是自反也不是反自反的4对称性与反对称性定义设R为A上的关系,(1)若