复合关系、逆关系.ppt

《复合关系、逆关系.ppt》由会员分享，可在线阅读，更多相关《复合关系、逆关系.ppt（42页珍藏版）》请在三一办公上搜索。

1、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 序偶和笛卡尔积序偶的概

2、念和表示=,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）传递性(transitivit

3、y),3-6 关系的性质,自反性,反自反性,对称性,反对称性,传递性,需要指出：,从X到Y的关系R是XY 的子集，即RXY，而XY（XY）（XY）所以R（XY）（XY）令Z=XY，则RZZ因此，我们今后通常限于讨论同一集合上的关系。,第二部分 集合论,需要注意：关系和运算,关系：=不相交 朋友 同学 父子运算：,自反性,反自反性,对称性,反对称性,传递性,自反性reflexivity：设R为定义在A上的二元关系，即RAA,如果对于每一个xA，有xRx(R)，则称二元关系R是自反的。R在A上是自反的(x)(xA xRx)R在A上是非自反的(x)(xA R)。定理：R是自反的 IA RMR主对角线

4、上的元素全为1GR的每个顶点处均有自环。,第二部分 集合论,自反性,反自反性,对称性,反对称性,传递性,自反性(举例)：恒等关系、全域关系实数：=：|x,y都是实数且xy几何图形：三角形的全等：|AB、相似 数理逻辑：、：|PQ、|PQ是重言式集合论：|A B,第二部分 集合论,第二部分 集合论,自反性,反自反性,对称性,反对称性,传递性,反自反性irreflexivity：设RAA,如果对于每一个xA，有R，则称二元关系R是反自反的。R在A上是反自反的(x)(xA R)。R在A上是非反自反的(x)(xA xRx)定理：R是反自反的 IAR=MR主对角线上的元素全为0 GR的每个顶点处均无自回

5、路（无环）。,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反自反性(举例)：空关系实数：、|x,y都是实数且x|PQ是重言式 中“”取、时集合论：、：|A B注意：非自反不一定是反自反的。即存在有关系既不是自反的也不是反自反的。,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,对称性symmetry：设RAA,如果对于每个x,yA，每当 xRy，就有 yRx，则称集合A上的关系R是对称的。R在A上对称(x)(y)(xAyAxRyyRx).R非对称(x)(y)(xAyAxRyyRx)定理：R是对称的 MR是对称的 GR的任何两个

6、顶点之间若有边,则必有两条方向相反的有向边.,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,对称性(举例)：空关系、恒等关系、全域关系实数：、=：|x,y都是实数且x=y几何图形：三角形的全等：|AB、相似 数理逻辑：|PQ是重言式 中“”取、时集合论：、不相交：|AB=整数：同余人之间的关系：同学关系、朋友关系、邻居关系,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反对称性antisymmetry：设RAA,如果对于每个x,yA,每当 xRy和yRx，必有x=y，则称集合A上的关系R是反

7、对称的。R是反对称的(x)(y)(xAyA xRy yRx x=y)(x)(y)(xAyA xy xRy yRx).R非反对称(x)(y)(xA yA xRy yRx xy)定理：R是反对称的 在MR中,xixj(ij rij=1rji=0)在GR中,xixj(ij),若有有向边,则必没有。,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反对称性(举例)：空关系实数：、|P Q是重言式 集合论：|A B人之间的关系：父与子关系整数：整除关系：|x,y都是整数且x|y注意：非对称不一定反对称；可能有某种关系即是对称的又是反对称的。例如：A=1,

8、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)(xAyAzAxRy yRzxRz)。定理：R是传递的 在GR中,xi xj xk(ijk),若有有向边和,则必有。,第二部分 集合论,第二部分 集合

9、论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,传递性(举例)：空关系、恒等关系、全域关系实数：、|x,y都是整数且x|y几何图形：三角形的全等：|AB、相似数理逻辑：、：|PQ是重言式 集合论：、：|A B人之间的关系：同姓、同性别,自反性与反自反性是相互矛盾的，不能同时成立对称性和反对称性不矛盾、可以同时成立,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,例1：在 N=1,2,上：、：|xNyNxy自反,反对称,传递、|xNyNx|xNyNx|y(整除关系)自反,反对称,传递IN=|x

10、NyNx=y(恒等关系)自反,对称,反对称,传递EN=|xNyN=NN(全域关系)自反,对称,传递,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,思考：左边的论述是否完全正确？有没有不严谨的地方？,例2：判断以下关系所具有的性质。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7=,第二部分 集合论,反对称,传递,反对称,自反,对称,传递,对称,自反,反对称,传递,反自反，对称，反对称，传递,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传

11、递性,反自反性,第二部分 集合论,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）是自反的，对称的，可传递的，不是

12、反自反，也不是反对称。,解（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

13、 关系矩阵与关系图,3-7 复合关系和逆关系,复合关系,逆关系,运算性质,矩阵与图,运算性质,复合(composite)关系:设R为X到Y的关系，S为从Y到Z的关系，则RS称为R和S的复合关系，表示为：RS=|xXzZ(y)(yYRS).定义（屈婉玲版）：二元关系R,S的右复合运算 RS=(|y(R S),复合关系,逆关系,矩阵与图,B=离散数学,高等数学,大学物理,大学英语,体育课,C=吃饭,睡觉,打豆豆,变成豆豆,A=周一上午,周二下午,周三下午，周四上午，周五下午,RS=,复合关系,逆关系,运算性质,矩阵与图,社交的六度分割原理：地球上任何两个人之间的间隔不超过6个人,第二部分 集合论,

14、A=地球上的人；R=|x,y A,且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是任意

15、的关系,则(1)(Fc)c=F(2)domFc=ranF,ranFc=domF,证(1)任取,由逆的定义有(Fc)c Fc F.所以有(Fc)c=F.,(2)任取x,xdomFc y(Fc)y(F)xranF 所以有 domFc=ranF.同理可证 ranFc=domF.,29,设F,G,H是任意的关系,则(1)结合律：(FG)H=F(GH)(2)(FG)c=GcFc,(1)证 任取,(FG)H t(FGH)t(s(FG)H)t s(FGH)s(Ft(GH)s(FGH)F(GH)所以(FG)H=F(GH),关系运算的性质2,30,性质2证明,(2)(FG)c=GcFc证 任取,(FG)c FG

16、 t(FG)t(GcFc)Gc Fc所以(F G)c=Gc Fc,31,关系运算的性质3,设R为A上的关系,则 RIA=IAR=R,证任取 RIA t(RIA)t(Rt=y)R RR yA R IA RIA同理可证 IAR=R,32,关系运算的性质4,分配率：F,G,H为任意关系，则(1)F(GH)=FGFH(2)(GH)F=GFHF(3)F(GH)FGFH(4)(GH)F GFHF,(3)证 任取,F(GH)t(FGH)t(FGH)t(FG)(FH)t(FG)t(FH)FGFH FGFH所以有 F(GH)FGFH注意：复合运算对并满足分配律，对交满足“弱”分配律,(GH),H),GH),FH

17、,=,33,推广,分配率的结论可以推广到有限多个关系 R(R1R2Rn)=RR1RR2RRn(R1R2Rn)R=R1RR2RRnR R(R1R2 Rn)RR1RR2 RRn(R1R2 Rn)R R1RR2R RnR,34,关系运算的性质5,(1)(R1 R2)c=R1 c R2 c(2)(R1R2)c=R1 c R2 c(3)(AB)c=BA(4)(R)c=Rc,这里R AB-R(5)(R1-R2)c=R1c-R2c,35,关系的幂运算,定义：设 R 为 A 上的关系,n为自然数,则 R 的 n 次幂定义为：(1)R0=|xA=IA(2)Rn+1=RnR注意：对于A上的任何关系 R1 和 R2

18、 都有 R10=R20=IA 对于A上的任何关系 R 都有 R1=R,关系矩阵的性质：,(1)MRc=(MR)T.(T表示矩阵转置)(2)MR1 R2=MR1MR2(表示布尔乘法,其中加法使用逻辑,乘法使用逻辑),逆关系关系图的性质：,关系 Rc 的图形是将关系R图形中弧的箭头方向反置。,复合关系,逆关系,运算性质,矩阵与图,例题:设 A=a,b,c,R1=,R2=,用MR1,MR2确定MR1c,MR2c,MR1R1,MR1R2,MR2R1,从而求出它们的集合表达式.,复合关系,逆关系,运算性质,矩阵与图,1 1 0 1 1 0MR1=1 0 1 MR1c=1 0 0 0 0 0 0 1 0

19、0 1 1 0 0 0MR2=0 0 1 MR2c=1 0 0 0 0 0 1 1 0 0 1 1 MR1R2=MR1 MR2=0 1 1 0 0 0R1R2=,.,第二部分 集合论,复合关系,逆关系,运算性质,矩阵与图,1 1 0 1 1 0 1 1 1 MR1R1=MR1 MR1=1 0 1 1 0 1=1 1 0 0 0 0 0 0 0 0 0 0R1R1=,.0 1 1 1 1 0 1 0 1 MR2R1=MR2 MR1=0 0 1 1 0 1=0 0 0 0 0 0 0 0 0 0 0 0R2R1=,.,第二部分 集合论,复合关系,逆关系,运算性质,矩阵与图,解:R1c=,R2c=,

20、R1R1=,.R1R2=,.R2R1=,.,第二部分 集合论,复合关系,逆关系,运算性质,矩阵与图,第二部分 集合论,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也有边,小结:本节主要介绍了关系的复合运算与逆运算。重点掌握关系的复合运算及其性质、关系的逆运算的性质。,作业：,第二部分 集合论,P113(3)(6),P109(2)(5)b)d),P118(1)(2)(4)(8),