离散数学第四章二元关系和函数知识点总结

集合论部分第四章、二元关系和函数4.1集合的笛卡儿积与二元关系有序对定义由两个客体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=3定义一个有序n(n3)元组x1,x2,…,xn是一个有序对，其中第一个元素是一个有序n-1元组，即x1,x2,…,xn=x1,x2,…,xn-1,xn当n=1时,x形式上可以看成有序1元组.实例n维向量是有序n元组.笛卡儿积及其性质定义设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={,,{},}性质：不适合交换律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|=mn证明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).例3(1)证明A=BC=DAC=BD(2)AC=BD是否推出A=BC=D?为什么？解(1)任取x,yx,yACxAyCxByDx,yBD(2)不一定.反例如下：A={1}，B={2},C=D=,则AC=BD但是AB.二元关系的定义定义设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个不同的二元关系.设A为任意集合，是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：EA={x,y|x∈A∧y∈A}=A×AIA={x,x|x∈A}例如,A={1,2},则EA={1,1,1,2,2,1,2,2}IA={1,1,2,2}小于等于关系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是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.例如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}}二元关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若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上的关系A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},R的关系矩阵MR和关系图GR如下：4.2关系的运算基本运算定义：定义域、值域和域domR={x|y(x,yR)}ranR={y|x(x,yR)}fldR=domRranR例1R={1,2,1,3,2,4,4,3},则R={1,2,4}R={2,3,4}fldR={1,2,3,4}逆与合成R1={y,x|x,yR}R∘S=|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}R∘S={1,3,2,2,2,3}S∘R={1,2,1,4,3,2,3,3}定义F在A上的限制F↾A={x,y|xFyxA}A在F下的像F[A]=ran(F↾A)实例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}注意：F↾AF,F[A]ranF基本运算的性质定理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.定理2设F,G,H是任意的关系,则(1)(F∘G)∘H=F∘(G∘H)(2)(F∘G)1=G1∘F1证(1)任取x,y,x,y(F∘G)∘Ht(x,t∈F∘G∧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∈G∘H)x,y∈F∘(G∘H)所以(F∘G)∘H=F∘(G∘H)(2)任取x,y,x,y∈(F∘G)1y,x∈F∘Gt(y,t∈F∧(t,x)∈G)t(x,t∈G1∧(t,y)∈F1)x,y∈G1∘F1所以(F∘G)1=G1∘F1幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={x,x|x∈A}=IA(2)Rn+1=Rn∘R注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R性质：定理3设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证R为A上的关系,由于|A|=n,A上的不同关系只有个.当列出R的各次幂R0,R1,R2,…,,…,必存在自然数s和t使得Rs=Rt.定理4设R是A上的关系,m,n∈N,则(1)Rm∘Rn=Rm+n(2)(Rm)n=Rmn证用归纳法(1)对于任意给定的m∈N,施归纳于n.若n=0,则有Rm∘R0=Rm∘IA=Rm=Rm+0假设Rm∘Rn=Rm+n,则有Rm∘Rn+1=Rm∘(Rn∘R)=(Rm∘Rn)∘R=Rm+n+1,所以对一切m,n∈N有Rm∘Rn=Rm+n.(2)对于任意给定的m∈N,施归纳于n.若n=0,则有(Rm)0=IA=R0=Rm×0假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)n∘Rm=(Rmn)∘Rm=Rmn+m=Rm(n+1)所以对一切m,n∈N有(Rm)n=Rmn.4.3关系的性质自反性反自反性定义设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反自反关系：实数集上的小于关系幂集上的真包含关系例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既不是自反也不是反自反的对称性反对称性定义设R为A上的关系,(1)若xy(x,y∈A∧x,y∈R→y,x∈R),则称R为A上对称的关系.(2)若xy(x,y∈A∧x,y∈R∧y,x∈R→x=y),则称R为A上的反对称关系.实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA，空关系是A上的反对称关系.例2设A＝{1,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}R1对称、反对称.R2对称，不反对称.R3反对称，不对称.R4不对称、也不反对称.传递性定义设R为A上的关系,若xyz(x,y,z∈A∧x,y∈R∧y,z∈R→x,z∈R),则称R是A上的传递关系.实例：A上的全域关系EA,恒等关系IA和空关系小于等于关系,小于关系，整除关系，包含关系，真包含关系例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中R1＝{1,1,2,2}R2＝{1,2,2,3}R3＝{1,3}R1和R3是A上的传递关系R2不是A上的传递关系关系性质的充要条件设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当R∩IA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当R∩R1IA(5)R在A上传递当且仅当RRR证明模式证明R在A上自反任取x,xA……………..….…….x,xR前提推理过程结论例4证明若IAR，则R在A上自反.证任取x,xAx,xIAx,xR因此R在A上是自反的.证明模式证明R在A上对称任取x,yx,yR……………..….…….y,xR前提推理过程结论例5证明若R=R1,则R在A上对称.证任取x,yx,yRy,xR1x,yR因此R在A上是对称的.证明模式证明R在A上反对称任取x,yx,yRy,xR………..……….x=y前提推理过程结论例6证明若R∩R1IA,则R在A上反对称.证任取x,yx,yRy,xRx,yRx,yR1x,yR∩R1x,yIAx=y因此R在A上是反对称的.证明模式证明R在A上传递任取x,y，y,zx,yRy,zR…..……….x,zR前提推理过程结论例7证明若RRR,则R在A上传递.证任取x,y，y,zx,yRy,zRx,zR