离散数学--关系的合成 ppt课件.ppt

离散数学第二部分集合论关系论3关系的合成*PPT课件关系的合成关系的逆本节主要内容:关系的合成x是y的父亲y是z的母亲x是z的什么关系?x是y的父亲y是x的什么关系?*PPT课件设R是从集合X到集合Y的关系,合成关系关系的合成定义S是从集合Y到集合Z的关系。于是,可把从X到Z的关系RºS定义成:RºS={<x,z>|(xX)Λ(zZ)Λ(y)((yY)Λ(<x,y>R)Λ(<y,z>S))}通常称RºS是关系R和S的合成关系。从R和S求得Rº S的运算,称为关系的合成。*PPT课件合成关系关系的合成例1:R={<x,3x>|x,yI}(1)RºS=I是整数集合,R,S是I上的关系S={<x,5x>|x,yI}{<x,15x>|xI}(2)SºR={<x,15x>|xI}(3)RºR={<x,9x>|xI}(4)SºS={<x,25x>|xI}*PPT课件合成关系关系的合成例1:I是整数集合,R,S是I上的关系RºS的关系图*PPT课件合成关系关系的合成例2:R={<x,y>|x,yPx是y的父亲}(1)RºR表示的关系是:P是所有人的集合,R和S是P上的关系S={<x,y>|x,yPx是y的母亲}xRºRy表示x是y的祖父(2)RºS表示的关系是:xRºSy表示x是y的外祖父(3){<x,y>|x,yPx是y的祖母}的集合表示为:SºR*PPT课件合成关系关系的合成注①若R1的值域与R2的定义域的交集为空,则R1ºR2为空关系②设IA、IB分别为A和B上的相等关系,R是A到B的二元关系则IAºR=RºIB=R但RºIA,RºIB无意义③在关系图上,R1ºR2是由<a,c>这样的序偶组成,从aA到cC有一长度为2的路径,其中第一条弧属于R1第二条弧属于R2.*PPT课件给定集合X,Y,Z和W。设R1是从X到Y的关系;R2和R3都是从Y到Z的关系,R4是从Z到W的关系,于是应有:合成关系合成关系的分配率定理(1)R1º(R2∪R3)=(R1ºR2)∪(R1ºR3)(3)R1º(R2∩R3)(R1ºR2)∩(R1ºR3)(4)(R2∩R3)ºR4(R2ºR4)∩(R3ºR4)(2)(R2∪R3)ºR4=(R2ºR4)∪(R3ºR4)*PPT课件合成关系证明:(1)R1º(R2∪R3)=(R1ºR2)∪(R1ºR3)即证明两个序偶集合相等<x,z>R1º(R2∪R3)(y)((<x,y>R1)∧(<y,z>R2∪R3))(y)((<x,y>R1)∧(<y,z>R2∨<y,z>R3))(y)((<x,y>R1∧<y,z>R2)∨(<x,y>R1∧<y,z>R3))(y)((<x,y>R1∧<y,z>R2))∨(y)(<x,y>R1∧<y,z>R3))<x,z>R1ºR2<x,z>R1ºR2∪R1ºR3合成关系的分配率∨<x,z>R1ºR3*PPT课件合成关系合成关系的结合率给定集合X,Y,Z和W。定理(R1ºR2)ºR3=R1º(R2ºR3)设R1是从X到Y的关系R2是从Y到Z的关系,R3是从Z到W的关系,于是有:*PPT课件