复合关系、逆关系.ppt

1,第二部分集合论,主要内容集合3-1集合的概念和表示法3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分与覆盖,3-10等价关系与等价类3-11相容关系3-12序关系函数4.1函数的基本概念4.2复合函数与逆函数,2,第一部分数理逻辑,上节内容回顾,3-5关系及其表示3-5.1关系关系：序偶的集合定义域、值域、域3-5.2一些特殊关系空关系、恒等关系、全域关系关系的交并补差还是关系3-5.3关系的表示序偶集合形式关系矩阵MR关系图GR,3-4序偶和笛卡尔积序偶的概念和表示=,z,z笛卡尔积AB=|xAyB不满足交换律、结合律与、满足分配率,3,第二部分集合论,主要内容集合3-1集合的概念和表示法3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分与覆盖,3-10等价关系与等价类3-11相容关系3-12序关系函数4.1函数的基本概念4.2复合函数与逆函数,（1）自反性(reflexivity)（2）反自反性(irreflexivity)（3）对称性(symmetry)（4）反对称性(antisymmetry)（5）传递性(transitivity),3-6关系的性质,自反性,反自反性,对称性,反对称性,传递性,需要指出：,从X到Y的关系R是XY的子集，即RXY，而XY（XY）（XY）所以R（XY）（XY）令Z=XY，则RZZ因此，我们今后通常限于讨论同一集合上的关系。,第二部分集合论,需要注意：关系和运算,关系：=、|x,y都是实数且x|PQ是重言式中“”取、时集合论：、：|AB注意：非自反不一定是反自反的。即存在有关系既不是自反的也不是反自反的。,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,对称性symmetry：设RAA,如果对于每个x,yA，每当xRy，就有yRx，则称集合A上的关系R是对称的。R在A上对称(x)(y)(xAyAxRyyRx).R非对称(x)(y)(xAyAxRyyRx)定理：R是对称的MR是对称的GR的任何两个顶点之间若有边,则必有两条方向相反的有向边.,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,对称性(举例)：空关系、恒等关系、全域关系实数：、=：|x,y都是实数且x=y几何图形：三角形的全等：|AB、相似数理逻辑：|PQ是重言式中“”取、时集合论：、不相交：|AB=整数：同余人之间的关系：同学关系、朋友关系、邻居关系,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,反对称性antisymmetry：设RAA,如果对于每个x,yA,每当xRy和yRx，必有x=y，则称集合A上的关系R是反对称的。R是反对称的(x)(y)(xAyAxRyyRxx=y)(x)(y)(xAyAxyxRyyRx).R非反对称(x)(y)(xAyAxRyyRxxy)定理：R是反对称的在MR中,xixj(ijrij=1rji=0)在GR中,xixj(ij),若有有向边,则必没有。,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,反对称性(举例)：空关系实数：、|PQ是重言式集合论：|AB人之间的关系：父与子关系整数：整除关系：|x,y都是整数且x|y注意：非对称不一定反对称；可能有某种关系即是对称的又是反对称的。例如：A=1,2,3,S=,S在A上即是对称的又是反对称的。N=,N在A上即不是对称的又不是反对称的。,第二部分集合论,，恒等关系,、=,、=,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,传递性transitivity：设RAA,如果对于任意的x,y,zA,每当xRy，yRz时就有xRz，称关系R在A上是传递的。R在A上是传递的(x)(y)(z)(xAyAzAxRyyRzxRz)R非传递(x)(y)(z)(xAyAzAxRyyRzxRz)。定理：R是传递的在GR中,xixjxk(ijk),若有有向边和,则必有。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,传递性(举例)：空关系、恒等关系、全域关系实数：、|x,y都是整数且x|y几何图形：三角形的全等：|AB、相似数理逻辑：、：|PQ是重言式集合论：、：|AB人之间的关系：同姓、同性别,自反性与反自反性是相互矛盾的，不能同时成立对称性和反对称性不矛盾、可以同时成立,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,例1：在N=1,2,上：、：|xNyNxy自反,反对称,传递、|xNyNx|xNyNx|y(整除关系)自反,反对称,传递IN=|xNyNx=y(恒等关系)自反,对称,反对称,传递EN=|xNyN=NN(全域关系)自反,对称,传递,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,思考：左边的论述是否完全正确？有没有不严谨的地方？,例2：判断以下关系所具有的性质。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7=,第二部分集合论,反对称,传递,反对称,自反,对称,传递,对称,自反,反对称,传递,反自反，对称，反对称，传递,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,第二部分集合论,xA,有R,xA,有R,若R则R,若R,且xy,则R,若R且R则R,IAR,RIA=,R=Rc,RRcIA,RRR,主对角线元素全是1,主对角线元素全是0,矩阵是对称矩阵,若rij1,且ij,则rji0,M2中1位置,M中相应位置都是1,每个顶点都有环,每个顶点都没有环,两点之间有边,是一对方向相反的边,两点之间有边,是一条有向边,点xi到xj有边,xj到xk有边,则xi到xk也有边,设A=1,2,3，下面分别给出集合A上三个关系的关系图，试判断它们的性质。,（2）非自反，也不是反自反，非对称，反对称，可传递。,（3）是自反的，对称的，可传递的，不是反自反，也不是反对称。,解（1）是自反的，非对称，不是反对称，不可传递,小结:本节介绍了关系的基本性质及其判别方法。,作业：,第二部分集合论,P113(3)(6),P109(2)(5)b)d),21,第二部分集合论,主要内容集合3-1集合的概念和表示法3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分与覆盖,3-10等价关系与等价类3-11相容关系3-12序关系函数4.1函数的基本概念4.2复合函数与逆函数,3-7.1复合关系3-7.2逆关系3-7.3关系的运算性质3-7.4关系矩阵与关系图,3-7复合关系和逆关系,复合关系,逆关系,运算性质,矩阵与图,运算性质,复合(composite)关系:设R为X到Y的关系，S为从Y到Z的关系，则RS称为R和S的复合关系，表示为：RS=|xXzZ(y)(yYRS).定义（屈婉玲版）：二元关系R,S的右复合运算RS=(|y(RS),复合关系,逆关系,矩阵与图,B=离散数学,高等数学,大学物理,大学英语,体育课,C=吃饭,睡觉,打豆豆,变成豆豆,A=周一上午,周二下午,周三下午，周四上午，周五下午,RS=,R=,，,S=,复合关系,逆关系,运算性质,矩阵与图,社交的六度分割原理：地球上任何两个人之间的间隔不超过6个人,第二部分集合论,A=地球上的人；R=|x,yA,且x与y认识,RR2R3R4R5R6=AA,你隔壁老王家孩子的同学的同事的亲戚的朋友认识特朗普,复合关系,逆关系,运算性质,矩阵与图,逆(inverse)关系:设R是X到Y的二元关系，则从Y到X的二元关系Rc(R-1)定义为：Rc=|R.整数集合上的“”关系的逆关系是“”关系。人群中的父与子关系的逆关系是子与父关系。容易看出(Rc)c=R,第二部分集合论,复合关系,逆关系,运算性质,矩阵与图,第二部分集合论,RS=SR=,栗子：R=,S=,Rc=,利用图示（不是关系图）方法求复合关系,复合关系,逆关系,运算性质,矩阵与图,28,关系运算的性质1,设F是任意的关系,则(1)(Fc)c=F(2)domFc=ranF,ranFc=domF,证(1)任取,由逆的定义有(Fc)cFcF.所以有(Fc)c=F.,(2)任取x,xdomFcy(Fc)y(F)xranF所以有domFc=ranF.同理可证ranFc=domF.,29,设F,G,H是任意的关系,则(1)结合律：(FG)H=F(GH)(2)(FG)c=GcFc,(1)证任取,(FG)Ht(FGH)t(s(FG)H)ts(FGH)s(Ft(GH)s(FGH)F(GH)所以(FG)H=F(GH),关系运算的性质2,30,性质2证明,(2)(FG)c=GcFc证任取,(FG)cFGt(FG)t(GcFc)GcFc所以(FG)c=GcFc,31,关系运算的性质3,设R为A上的关系,则RIA=IAR=R,证任取RIAt(RIA)t(Rt=y)RRRyARIARIA同理可证IAR=R,32,关系运算的性质4,分配率：F,G,H为任意关系，则(1)F(GH)=FGFH(2)(GH)F=GFHF(3)F(GH)FGFH(4)(GH)FGFHF,(3)证任取,F(GH)t(FGH)t(FGH)t(FG)(FH)t(FG)t(FH)FGFHFGFH所以有F(GH)FGFH注意：复合运算对并满足分配律，对交满足“弱”分配律,(GH),H),GH),FH,=,33,推广,分配率的结论可以推广到有限多个关系R(R1R2Rn)=RR1RR2RRn(R1R2Rn)R=R1RR2RRnRR(R1R2Rn)RR1RR2RRn(R1R2Rn)RR1RR2RRnR,34,关系运算的性质5,(1)(R1R2)c=R1cR2c(2)(R1R2)c=R1cR2c(3)(AB)c=BA(4)(R)c=Rc,这里RAB-R(5)(R1-R2)c=R1c-R2c,35,关系的幂运算,定义：设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0=|xA=IA(2)Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R,关系矩阵的性质：,(1)MRc=(MR)T.(T表示矩阵转置)(2)MR1R2=MR1MR2(表示布尔乘法,其中加法使用逻辑,乘法使用逻辑),逆关系关系图的性质：,关系Rc的图形是将关系R图形中弧的箭头方向反置。,101100101100011100=_,复合关系,逆关系,运算性质,矩阵与图,例题:设A=a,b,c,R1=,R2=,用MR1,MR2确定MR1c,MR2c,MR1R1,MR1R2,MR2R1,从而求出它们的集合表达式.,复合关系,逆关系,运算性质,矩阵与图,110110MR1=101MR1c=100000010011000MR2=001MR2c=100000110011MR1R2=MR1MR2=011000R1R2=,.,第二部分集合论,复合关系,逆关系,运算性质,矩阵与图,110110111MR1R1=MR1MR1=101101=110000000000R1R1=,.011110101MR2R1=MR2MR1=001101=000000000000R2R1=,.,第二部分集合论,复合关系,逆关系,运算性质,矩阵与图,解:R1c=,R2c=,R1R1=,.R1R2=,.R2R1=,.,第二部分集合论,复合关系,逆关系,运算性质,矩阵与图,第二部分集合论,xA,有R,xA,有R,若R则R,若R,且xy,则R,若R且R则R,IA