复合关系、逆关系.ppt

《复合关系、逆关系.ppt》由会员分享，可在线阅读，更多相关《复合关系、逆关系.ppt（42页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二部分第二部分 集合论集合论p主要内容主要内容p集合集合p3-1集合的概念和表示法p3-2集合的运算p3-4序偶与笛卡尔积p3-5关系及其表示p3-6关系的性质p3-7复合关系和逆关系p3-8关系的闭包运算p3-9集合的划分与覆盖p3-10等价关系与等价类p3-11相容关系p3-12序关系p函数函数p4.1函数的基本概念p4.2复合函数与逆函数1第一部分第一部分 数理逻辑数理逻辑p上节内容回顾上节内容回顾pp3-53-5关系及其表示关系及其表示关系及其表示关系及其表示p3-5.1关系关系关系：序偶的集合定义域、值域、域p 3-5.2一些特殊关系一些特殊关系空关系、恒等关系、全域关系关系的交并

2、补差还是关系p3-5.3关系的表示关系的表示序偶集合形式关系矩阵MR关系图GRpp3-43-4序偶和笛卡尔积序偶和笛卡尔积序偶的概念和表示=,z,zx,笛卡尔积AB=|xAyB不满足交换律、结合律与、满足分配率2第二部分第二部分 集合论集合论p主要内容主要内容p集合集合p3-1集合的概念和表示法p3-2集合的运算p3-4序偶与笛卡尔积p3-5关系及其表示p3-6关系的性质p3-7复合关系和逆关系p3-8关系的闭包运算p3-9集合的划分与覆盖p3-10等价关系与等价类p3-11相容关系p3-12序关系p函数函数p4.1函数的基本概念p4.2复合函数与逆函数3（1）自反性自反性(reflexivi

3、ty)（2）反自反性反自反性(irreflexivity)（3）对称性对称性(symmetry)（4）反对称性反对称性(antisymmetry)（5）传递性传递性(transitivity)3-6 关系的性质关系的性质自反性自反性自反性自反性反自反性反自反性反自反性反自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性需要指出：需要指出：从从X到到Y的关系的关系R是是X Y 的子集，即的子集，即R X Y，而而X Y （X Y）（X Y）所以所以R （X Y）（X Y）令令Z=X Y，则，则R Z Z因此，我们今后通常限于讨论同一集合上的关系。因此，我们今后

4、通常限于讨论同一集合上的关系。第二部分第二部分 集合论集合论需要注意：关系和运算需要注意：关系和运算关系：关系：=不相交不相交 朋友朋友 同学同学 父子父子运算：运算：自反性自反性自反性自反性反自反性反自反性反自反性反自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性自自反反性性reflexivity：设设R为为定定义义在在A上上的的二二元元关关系系，即即 R A A,如如 果果 对对 于于每每一一个个x A，有有xRx(R)，则称，则称二元关系二元关系R是自反的是自反的。R在在A上是自反的上是自反的 (x)(x A xRx)R在在A上是非自反的上是非自反的

5、 (x)(x A R)。定理：定理：定理：定理：R是自反的是自反的 IA RMR主对角线上的元素全为主对角线上的元素全为1GR的每个顶点处均有自环。的每个顶点处均有自环。第二部分第二部分 集合论集合论自反性自反性反自反性反自反性反自反性反自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性自反性自反性(举例举例)：恒等关系、全域关系恒等关系、全域关系实数：实数：=：|x,y都是实数且都是实数且xy几何图形几何图形：三角形的全等：三角形的全等：|A B、相似、相似 数理逻辑：数理逻辑：、：|PQ、|PQ是重言式是重言式集合论：集合论：|A B第二部分第二部分 集

6、合论集合论第二部分第二部分 集合论集合论自反性自反性反自反性反自反性反自反性反自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性irreflexivity：设设R A A,如果对于如果对于每一个每一个x A，有有 R，则称，则称二元关系二元关系R是是反自反的反自反的。R在在A上是反自反的上是反自反的 (x)(x A R)。R在在A上是非反自反的上是非反自反的 (x)(x A xRx)定理：定理：定理：定理：R是反自反的是反自反的 IA R=MR主对角线上的元素全为主对角线上的元素全为0 GR的每个顶点处均无自回路（无环）。的每个顶点处均无自回

7、路（无环）。第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性反自反性反自反性(举例举例)：空关系空关系实数：实数：、：|x,y都是实数且都是实数且xy数理逻辑：数理逻辑：|PQ是重言式是重言式中中“”取取、时时集合论：集合论：、：|A B注意：注意：非自反非自反不一定是不一定是反自反反自反的。的。即存在有关系即存在有关系既既不是不是自反的自反的也也不是不是反自反的反自反的。第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对

8、称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性对称性对称性symmetry：设设R A A,如果对于如果对于每个每个x,y A，每当，每当 xRy，就有就有 yRx，则称，则称集合集合A上的上的关系关系R是对称的是对称的。R在在A上对称上对称 (x)(y)(x A y A xRyyRx).R非对称非对称 (x)(y)(x A y A xRy yRx)定理：定理：定理：定理：R是对称的是对称的 MR是对称的是对称的 GR的的任任何何两两个个顶顶点点之之间间若若有有边边,则则必必有有两两条条方方向向相相反反的的有向边有向边.第二部分第二部分 集合论集合论第

9、二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性反自反性反自反性对称性对称性(举例举例)：空关系、恒等关系、全域关系空关系、恒等关系、全域关系实数：实数：、=：|x,y都是实数且都是实数且x=y几何图形几何图形：三角形的全等：三角形的全等：|A B、相似、相似 数理逻辑数理逻辑：|PQ是重言式是重言式中中“”取取、时时集合论：、不相交集合论：、不相交：|AB=整数：同余整数：同余人之间的关系：同学关系、朋友关系、邻居关系人之间的关系：同学关系、朋友关系、邻居关系第二部分第二部分

10、 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性反自反性反自反性反对称性反对称性antisymmetry：设设R A A,如果如果对于对于每个每个x,y A,每当每当 xRy和和yRx，必有必有x=y，则称集，则称集合合A上的关系上的关系R是反对称的是反对称的。R是反对称的是反对称的 (x)(y)(x A y A xRy yRx x=y)(x)(y)(x A y A xy xRy yRx).R非反对称非反对称 (x)(y)(x A y A xRy yRx x y

11、)定理：定理：定理：定理：R是反对称的是反对称的 在在MR中中,xi xj(i j rij=1rji=0)在在GR中中,xi xj(i j),若若有有有有向向边边,则则必必没没有有。第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对称性对称性对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性反自反性反自反性反对称性反对称性(举例举例)：空关系：空关系实数：实数：、数理逻辑：数理逻辑：|PQ是重言式是重言式集合论：集合论：|A B人之间的关系：人之间的关系：父与子父与子关系关系整数整数：整除：整除关系关系：|x,

12、y都是整数且都是整数且x|y注注意意：非非对对称称不不一一定定反反对对称称；可可能能有有某某种种关关系系即即是是对对称称的的又又是是反反对称的对称的。例如例如：A=1,2,3,S=,S在在A上即是对称的又是反对称的。上即是对称的又是反对称的。N=,N在在A上即不是对称的又不是反对称的。上即不是对称的又不是反对称的。第二部分第二部分 集合论集合论，恒等关系，恒等关系、=、=第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对称性对称性对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性反自反性反自反性传递性传递性tr

13、ansitivity：设设R A A,如果对于如果对于任意的任意的x,y,z A,每当每当xRy，yRz时就有时就有xRz，称，称关系关系R在在A上是传递的上是传递的。R在在A上是传递的上是传递的(x)(y)(z)(x A y A z A xRy yRzxRz)R非传递非传递(x)(y)(z)(x A y A z A xRy yRz xRz)。定理：定理：定理：定理：R是传递的是传递的 在在GR中中,xi xj xk(i j k),若若有有有有向向边边和和,则必有则必有。第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反

14、性自反性自反性自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性反自反性反自反性反自反性反自反性传递性传递性(举例举例)：空关系、恒等关系、全域关系：空关系、恒等关系、全域关系实数：实数：、=、整数整数：同余、整除：同余、整除关系关系：|x,y都是整数且都是整数且x|y几何图形几何图形：三角形：三角形的全等：的全等：|A B、相似、相似数理逻辑：数理逻辑：、：|PQ是重言式是重言式集合论：集合论：、：|A B人之间的关系：同姓、同性别人之间的关系：同姓、同性别自反性与反自反性是相互矛盾的，不能同时成立自反性与反自反性是相互矛盾的，不能同时成立自反性与反自反性是相互矛盾的

15、，不能同时成立自反性与反自反性是相互矛盾的，不能同时成立对称性和反对称性不矛盾、可以同时成立对称性和反对称性不矛盾、可以同时成立对称性和反对称性不矛盾、可以同时成立对称性和反对称性不矛盾、可以同时成立第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性反自反性反自反性反自反性反自反性例例1：在：在 N=1,2,上：上：、：|x N y N x y自反自反,反对称反对称,传递传递、：|x N y N xy反自反反自反,反对称反对称,传递传

16、递D=|x N y N x|y (整除关系整除关系)自反自反,反对称反对称,传递传递IN=|x N y N x=y (恒等关系恒等关系)自反自反,对称对称,反对称反对称,传递传递EN=|x N y N=N N (全域关系全域关系)自反自反,对称对称,传递传递第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性反自反性反自反性思考：思考：思考：思考：左边的论述是否完全正确？左边的论

17、述是否完全正确？左边的论述是否完全正确？左边的论述是否完全正确？有没有不严谨的地方？有没有不严谨的地方？有没有不严谨的地方？有没有不严谨的地方？例例2：判断以下关系所具有的性质。：判断以下关系所具有的性质。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7=第二部分第二部分 集合论集合论反对称反对称,传递传递反对称反对称自反自反,对称对称,传递传递对称对称自反自反,反对称反对称,传递传递 反自反，对称，反对称反自反，对称，反对称，传递，传递第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论第二部分第二部分 集合论集合论自反性自反性自反性自

18、反性对称性对称性对称性对称性反对称性反对称性反对称性反对称性传递性传递性传递性传递性反自反性反自反性反自反性反自反性第二部分第二部分 集合论集合论自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性定义定义集合集合关系关系矩阵矩阵关系关系图图 x A,有有 R x A,有有 R若若 R则则 R若若 R,且且x y,则则 R若若 R且且 R则则 RIA RRIA=R=RcRRc IAR R R主对角线主对角线元素全是元素全是1主对角线元主对角线元素全是素全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1,且且ij,则则rji0M2中中1位置位置,M中相应位置中相应位置都是都是1每个顶

19、点都每个顶点都有环有环每个顶点都每个顶点都没有环没有环两点之间有两点之间有边边,是一对方是一对方向相反的边向相反的边两点之间有两点之间有边边,是一条有是一条有向边向边点点xi到到xj有边有边,xj 到到xk有边有边,则则xi到到xk也有边也有边设设 A=1,2,3A=1,2,3，下面分别给出集合，下面分别给出集合A上三个关系的关系图，上三个关系的关系图，试判断它们的性质。试判断它们的性质。（2 2）非自反，也不是反自反，非对称，非自反，也不是反自反，非对称，反对称，反对称，可传递。可传递。（3 3）是自反的，对称的，可传递的，）是自反的，对称的，可传递的，不是反自反，不是反自反，也不是反对称也

20、不是反对称。解解 （1 1）是自反的，）是自反的，非对称，不是反对称，不可传递非对称，不是反对称，不可传递 小结小结:本节介绍了关系的本节介绍了关系的基本性质基本性质及其及其判别判别方法。方法。作业：作业：第二部分第二部分 集合论集合论P113(3)(6)P109(2)(5)b)d)第二部分第二部分 集合论集合论p主要内容主要内容p集合集合p3-1集合的概念和表示法p3-2集合的运算p3-4序偶与笛卡尔积p3-5关系及其表示p3-6关系的性质p3-7复合关系和逆关系p3-8关系的闭包运算p3-9集合的划分与覆盖p3-10等价关系与等价类p3-11相容关系p3-12序关系p函数函数p4.1函数的

21、基本概念p4.2复合函数与逆函数213-7.1 复合关系复合关系3-7.2 逆关系逆关系3-7.3 关系的运算性质关系的运算性质3-7.4 关系矩阵与关系图关系矩阵与关系图3-7 复合关系和逆关系复合关系和逆关系复合关系复合关系复合关系复合关系逆关系逆关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图矩阵与图矩阵与图矩阵与图运算性质运算性质运算性质运算性质复合复合(composite)关系关系:设设R为为X到到Y的关系的关系，S为从为从Y到到Z的关系的关系，则，则RS称为称为R和和S的复合关系，表示为：的复合关系，表示为：RS=|x X z Z(y)(y Y R S).定义（屈婉玲版）：

22、二元关系定义（屈婉玲版）：二元关系定义（屈婉玲版）：二元关系定义（屈婉玲版）：二元关系R,SR,S的的的的右右右右复合复合复合复合运算运算运算运算 R R S S=(=(|y y(R R S S)复合关系复合关系逆关系逆关系逆关系逆关系矩阵与图矩阵与图矩阵与图矩阵与图B=离散数学,高等数学,大学物理,大学英语,体育课C=吃饭,睡觉,打豆豆,变成豆豆A=周一上午,周二下午,周三下午，周四上午，周五下午RS=,R=,，S=,复合关系复合关系逆关系逆关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图矩阵与图矩阵与图矩阵与图社交的六度分割原理：社交的六度分割原理：社交的六度分割原理：社交的六度分

23、割原理：地球上任何两个人之间的间隔不超过地球上任何两个人之间的间隔不超过地球上任何两个人之间的间隔不超过地球上任何两个人之间的间隔不超过6 6个人个人个人个人第二部分第二部分 集合论集合论A=地球上的人地球上的人；R=|x,yA,且且x与与y认识认识RR2R3R4R5R6=AA你你隔壁老王家孩子的同学的同事的亲戚的朋友认识隔壁老王家孩子的同学的同事的亲戚的朋友认识特朗普特朗普复合关系复合关系逆关系逆关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图矩阵与图矩阵与图矩阵与图逆逆(inverse)关系关系:设设R是是X到到Y的二元关系，则从的二元关系，则从Y到到X的二元关系的二元关系Rc(R

24、-1)定义定义为：为：Rc=|R.整数集合上的整数集合上的“”关系的逆关系是关系的逆关系是“”关系。关系。人群中的父与子关系的逆关系是子与父关系。人群中的父与子关系的逆关系是子与父关系。容易看出容易看出(Rc)c=R第二部分第二部分 集合论集合论复合关系复合关系复合关系复合关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图矩阵与图矩阵与图矩阵与图第二部分第二部分 集合论集合论R S=S R=,栗子：栗子：R=,S=,Rc=利用图示（利用图示（不是关系图不是关系图）方法求复合关系）方法求复合关系复合关系复合关系复合关系复合关系逆关系逆关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图

25、矩阵与图矩阵与图矩阵与图关系运算的性质关系运算的性质1 1 设设F是任意的关系是任意的关系,则则(1)(Fc)c=F(2)domFc=ranF,ranFc=domF证证(1)任取任取,由逆的定义有由逆的定义有(Fc)cFcF.所以有所以有(Fc)c=F.(2)任取任取x,xdomFc y(Fc)y(F)xranF所以有所以有domFc=ranF.同理可证同理可证ranFc=domF.28设设F,G,H是任意的关系是任意的关系,则则(1)结合律：结合律：(F G)H=F(G H)(2)(F G)c=Gc Fc(1)证证任取任取,(F G)H t(F GH)t(s(FG)H)t s(FGH)s(F

26、 t(GH)s(FG H)F(G H)所以所以(F G)H=F(G H)关系运算的性质关系运算的性质2 229性质性质2 2证明证明(2)(F G)c=Gc Fc证证 任取任取,(F G)c F G t(F G)t(Gc Fc)Gc Fc所以所以(F G)c=Gc Fc 30关系运算的性质关系运算的性质3 3设设R为为A上的关系上的关系,则则 R IA=IA R=R证证任取任取R IA t(RIA)t(Rt=y)RRRyARIAR IA同理可证同理可证IA R=R31关系运算的性质关系运算的性质4 4分配率：分配率：分配率：分配率：F,G,H为任意关系，则为任意关系，则(1)F(G H)=F

27、G F H (2)(G H)F=G F H F(3)F(GH)F GF H (4)(GH)F G FH F(3)证证任取任取,F(GH)t(FGH)t(FGH)t(FG)(FH)t(FG)t(FH)F GF HF GF H所以有所以有F(GH)F GF H注意：复合运算对并满足分配律，对交满足注意：复合运算对并满足分配律，对交满足注意：复合运算对并满足分配律，对交满足注意：复合运算对并满足分配律，对交满足“弱弱弱弱”分配律分配律分配律分配律(G(G H)H)H)GG H)H)F H=32推广推广分配率的结论可以推广到有限多个关系分配率的结论可以推广到有限多个关系 R(R1 R2 Rn)=R R

28、1 R R2 R Rn (R1 R2 Rn)R=R1 R R2 R Rn R R(R1R2 Rn)R R1R R2 R Rn (R1R2 Rn)R R1 RR2 R Rn R 33关系运算的性质关系运算的性质5 5(1)(R(1)(R1 1 R R2 2)c c=R=R1 1 c c R R2 2 c c(2)(R(2)(R1 1 R R2 2)c c=R=R1 1 c c R R2 2 c c(3)(AB)(3)(AB)c c=BA=BA(4)(R)(4)(R)c c=R=Rc c,这里这里这里这里R R AB-RAB-R(5)(R(5)(R1 1-R-R2 2)c c=R=R1 1c c-

29、R-R2 2c c34关系的幂运算关系的幂运算定义：定义：设设 R 为为 A 上的关系上的关系,n为自然数为自然数,则则 R 的的 n 次幂次幂定义为：定义为：(1)R0=|x A =IA(2)Rn+1=Rn R注意：注意：l对于对于A上的任何关系上的任何关系 R1 和和 R2 都有都有 R10=R20=IA l对于对于A上的任何关系上的任何关系 R 都有都有 R1=R35关系矩阵的性质：关系矩阵的性质：(1)MRc=(MR)T.(T表示矩阵转置表示矩阵转置)(2)MR1 R2=MR1 MR2 (表示布尔乘法表示布尔乘法,其中加法使用逻辑其中加法使用逻辑,乘法使用逻辑乘法使用逻辑 )逆关系关系

30、图的性质：逆关系关系图的性质：关系关系 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

31、 0 1 1 0 0 0MR2=0 0 1 MR2c=1 0 0 0 0 0 1 1 0 0 1 1 MR1 R2=MR1 MR2=0 1 1 0 0 0R1R2=,.第二部分第二部分 集合论集合论复合关系复合关系复合关系复合关系逆关系逆关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图矩阵与图 1 1 0 1 1 0 1 1 1 MR1 R1=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 MR2 R1=MR2 MR1=0 0 1 1 0 1 =0 0 0 0 0 0 0 0 0 0 0 0R2R1

32、=,.第二部分第二部分 集合论集合论复合关系复合关系复合关系复合关系逆关系逆关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图矩阵与图解解:R1c=,R2c=,R1R1=,.R1R2=,.R2R1=,.第二部分第二部分 集合论集合论复合关系复合关系复合关系复合关系逆关系逆关系逆关系逆关系运算性质运算性质运算性质运算性质矩阵与图矩阵与图第二部分第二部分 集合论集合论自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性定义定义集合集合关系关系矩阵矩阵关系关系图图 x A,有有 R x A,有有 R若若 R则则 R若若 R,且且x y,则则 R若若 R且且 R则则 RIA RR

33、IA=R=RcRRc IAR R R主对角线主对角线元素全是元素全是1主对角线元主对角线元素全是素全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1,且且ij,则则rji0M2中中1位置位置,M中相应位置中相应位置都是都是1每个顶点都每个顶点都有环有环每个顶点都每个顶点都没有环没有环两点之间有两点之间有边边,是一对方是一对方向相反的边向相反的边两点之间有两点之间有边边,是一条有是一条有向边向边点点xi到到xj有边有边,xj 到到xk有边有边,则则xi到到xk也有边也有边小结小结:本节主要介绍了关系的本节主要介绍了关系的复合运算复合运算与与逆逆运算运算。重点掌握关系的。重点掌握关系的复合运算及其性质复合运算及其性质、关系的逆运算的性质关系的逆运算的性质。作业：作业：第二部分第二部分 集合论集合论P113(3)(6)P109(2)(5)b)d)P118(1)(2)(4)(8)