离散数学课件第三章集合与关系-2

3-7复合关系和逆关系二元关系是以序偶为元素的集合，所以可以对它进行集合运算。此外还有一种新的运算：关系的复合定义3-7.1设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则R◦S称为R和S的复合关系，表示为R◦S={x，zx∈A∧z∈C∧y(y∈B∧x，y∈R∧y，z∈S)}复合关系举例例：A={1，2，3，4}，B={3，5，7}，C={1，2，3}R={2,7，3,5，4,3}，S={3,3，7,2}则R◦S={2，2，4，3}如图所示：复合关系的结合律定理：设R1A1A2,R2A2A3,R3A3A4,则(R1◦R2)◦R3=R1◦(R2◦R3)。例：设A={1,2,3,4,5}A上的二元关系R={1,2,3,4,2,2}S={4,2,2,5,3,1,1,3}则R◦S={1,5,3,2,2,5}S◦R={4,2,3,2,1,4}≠R◦S(R◦S)◦R={3,2}R◦(S◦R)={3,2}复合关系的矩阵表示（自学）两个关系的复合可通过相应矩阵相乘获得。复合关系练习练习：R是A上的二元关系，试证R是传递的充要条件是R◦RR证：‘’：x,zR◦R必y使得x,yR，y,zR∵R是传递的∴x,zR∴R◦RR‘’：x,yR,y,zR必有x,zR◦R∵R◦RR∴x,zR∴由x,y,z任意性知xyz(x,yR∧y,zRx,zR)∴R是传递的逆关系定义3-7.2设R是A到B的二元关系，则R的逆是B到A的二元关系，记为Rc，其中Rc={y,x|x,yR}。注：（1）xRyyRcx（2）互换R的关系矩阵的行和列，即得Rc的关系矩阵。即MRc＝MRT（3）颠倒R的关系图中每条弧线的箭头方向，即得Rc的关系图。逆关系举例例1整数集上的‘’关系的逆是‘’关系集合族上的‘’关系的逆是‘’空关系的逆是空关系AB的全域关系的逆是BA的全域关系例2A={0,1,2,3}，R={0,0,0,3,3,2,1,3}则Rc={0,0,3,0,2,3,3,1}定理定理：设R,R2,R1是A到B的关系，则a）(Rc)c=Rb）(R1∪R2)c=R1c∪R2cc）(R1∩R2)c=R1c∩R2d）(~R)c=~(Rc),~R=AB-R即R的补的逆等于逆的补e）(R1-R2)c=R1c-R2cf)(AB)c=BA定理定理3-7.2设R、S分别是A到B、B到C的关系，则(R◦S)c=Sc◦Rc证：设c,a是(R◦S)c的任一元素，则c,a(R◦S)ca,cR◦Sb(a,bRΛb,cS)b(c,bScΛb,aRc)c,aSc◦Rc定理定理3-7.3R是A上的二元关系(a)R是对称的R=Rc(b)R是反对称的R∩RcIA证：(a)‘’：任取a,bR，因为R是对称的，所以a,bRb,aRa,bRc‘’：任取a,bR，则b,aRc∵R=Rc∴b,aR∴R是对称的(b)略3-8关系的闭包运算设R是A上的关系，我们希望R具有某些有用的性质，比如说自反性。如果R不具有自反性，我们通过在R中添加一部分有序对来改造R，得到新的关系R’，使得R’具有自反性。但又不希望R’与R相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的R’就称为R的自反闭包。通过添加有序对来构造的闭包除自反闭包外还有对称闭包和传递闭包。各种闭包的定义定义3-8.1设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R’，使得R’满足以下条件：（1）R’是自反的（对称的或传递的）（2）RR’（3）对A上任何包含R的自反（对称或传递）关系R”，有R’R”。一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。注：R的自反闭包记为r(R),若R是自反的，则R=r(R),反之也成立。R的对称闭包记为s(R),若R是对称的，则R=s(R),反之也成立。R的传递闭包记为t(R),若R是传递的，则R=t(R),反之也成立。构造闭包的方法下面的定理给出了构造闭包的方法：①自反闭包r(R)=R∪IA用关系图解释②对称闭包s(R)=R∪Rc③传递闭包t(R)==R∪R2∪R3∪…ii1R证明r(R)=R∪IA证：设R’=R∪IA∵①xA,x,xR’∴R’具有自反性②RR’③设R”是自反的，且RR”∵R’’是自反的，∴IAR”又∵RR”∴R’=IA∪RR”综上所述，R’满足自反闭包定义的三个条件，∴r(R)=R’=R∪IA证明s(R)=R∪Rc证明：设R’=R∪Rc①R’c=(R∪Rc)c=Rc∪(Rc)c=Rc∪R=R’，所以R’是对称的②R’=R∪RcR③设R”是对称的，且RR”，要证R’R”任取a,b∈R∪Rca,b∈R∨a,b∈Rca,b∈R”∨b,a∈Ra,b∈R”∨b,a∈R”a,b∈R”∨a,b∈R”a,b∈R”∴R’=R∪RcR”综上所述，由定义知道，R’即R∪Rc为R的对称闭包。证t(R)==R∪R2∪R3∪…(R为A上的二元关系）证：(1)证t(R)：①先用归纳法证，对n0,Rnt(R)a)由定义Rt(R)b)设Rnt(R)成立，要证Rn+1t(R)任取a,b∈Rn+1=Rn◦R，∴存在c∈A,使a,c∈Rn,c,b∈R∵由归纳假设和基础步骤知a,c∈t(R)，c,b∈t(R）∵t(R)是传递的，∴a,b∈t(R)即Rn+1t(R)∴对一切n，Rnt(R)ii1Rii1R②根据①的结论，证t(R)：任取a,b∈∴存在一个n，使a,b∈Rnt(R)∴a,b∈t(R)∴t(R)ii1Rii1Rii1R(2)证t(R)①设a,b,b,c是的任意元素必s,t,使得a,b∈Rs,b,c∈Rt∴a,c∈Rt◦Rs=Rt+s∴a,c∈∴是传递的②∵t(R)是包含R的最小传递关系∴t(R)由（1），（2）得t(R)=ii1Rii1Rii1Rii1Rii1Rii1Rii1R闭包运算举例题：设A={a,b,c},R是A上的二元关系，且给定R={a,b,b,c,c,a},求r(R),s(R),t(R)。解：r(R)=R∪IA={a,b,b,c,c,a,a,a,b,b,c,c}s(R)=R∪Rc={a,b,b,a,b,c,c,b,c,a,a,c}t(R)=R∪R2∪R3∪…=R∪R2∪R3（因为R4=R,R5=R2,R6=R3,…)={a,a,b,b,c,c,a,b,b,c,c,a,a,c,b,a,c,b}定理3-8.5设R为X上二元关系，X=n，那么，存在一个正整数k≤n，使得t(Ｒ)=RR2R3...Rk例：P123例题2求R+的算法——Warshall算法A←Mi=1对i列中出现1的各行，分别被‘或’上i行i=i+1i≤n结束Y例：P124例题3P125例题4设有一字母表V={A,B,C,D,e,d,f}并给定下面六条规则：A-Af,B-Dde,C-e,A-B,B-De,D-BfR为定义在V上的二元关系且xiRxj，即是从xi出发用一条规则推出一串字符，使其第一个字符恰为xj。说明每个字母连续应用上述规则可能推出的头字符。闭包运算的性质设R为集合X上的任一二元关系，那么a)rs(R)=sr(R)自反对称闭包等于对称自反闭包b)tr(R)=rt(R)传递自反闭包等于自反传递闭包c)ts(R)st(R)传递对称闭包包含对称传递闭包证明rs(R)=sr(R)证：rs(R)=r(s(R))=r(R∪Rc)=Ix∪R∪Rc=Ix∪R∪Rc∪Ix=(Ix∪R)∪(Rc∪Ixc)=(Ix∪R)∪(R∪Ix)c=s(Ix∪R)=sr(R)证明rt(R)=tr(R)证：rt(R)=r(R∪R2∪…)=IX∪R∪R2∪…tr(R)=t(R∪IX)=IX∪R∪(IX∪R)2∪…∪(IX∪R)n∪…=IX∪R∪R2∪…∪Rn∪…∴rt(R)=tr(R)注：以上证明引用了公式：（证明略）(R∪IX)n=IX∪R∪R2∪…∪Rn∪…证明st(R)ts(R)证：①先证R对称t(R)对称t(R)-1=(RR2R3…)-1=R-1(R2)-1(R3)-1…=R-1(R-1)2(R-1)3…((F◦G)-1=G-1◦F-1，定理3-7.2)=RR2R3…=t(R)t(R)对称.②因为Rs(R),故st(R)st(s(R))而st(s(R))=sts(R)=s(ts(R))=ts(R)st(R)ts(R).注：st(R)ts(R)未必成立。反例：设R={a,b,c,b}则s(R)={a,b,b,a,c,b,b,c}t(s(R))={a,b,b,a,c,b,b,c,a,a,a,c,b,b,c,a,c,c…}s(t(R))=s{a,b,c,b}={a,b,b,a,c,b,b,c}t(s(R))注意：先做传递，再做对称，有可能破坏传递性。3-9集合的划分和覆盖除了把两个集合相互比较外，还常把一个集合分成若干子集讨论。定义3-9.1设A为非空集，S={S1…Sm},SiA，Si(i=1…m)且S1∪S2∪...∪Sm=A，称S是A的覆盖.若再加Si∩Sj=(i,j=1…m,ij)则称S是A的划分,m称为划分的秩。集合的划分和覆盖举例例1设A={1,2,3,4,5}，下面哪些是覆盖，哪些是划分：(1)X={{1,2},{3},{4,5}}(2)Y={{1,2},{2,3},{4,5}}(3)Z={{1,2,3},{4}}(4)U={{1,2,3,4,5}}(5)V={{1},{2},{3},{4},{5}}U称为A的最小划分，V称为A的最大划分。交叉划分定义3-9.2若S1={A1…Am},S2={B1…Bn}是A的二个划分,则S={Ai∩Bj|AiS1∧BjS2}称为A的交叉划分。定理3-9.1设{A1,A2,…,Am}与{B1,B2,…,Bn}为同一集合A的两个划分。则其交叉划分Ai∩Bj亦是原集合的一种划分。交叉划分举例例：设B是所有生物的集合,可划分成{A,P},其中A表示所有动物Animal的集合,P表示所有植物Plant的集合。B也可划分成{F,L},其中F表示史前First生物,L表示史后Last生物。它们的交叉划分为:D={A∩F,A∩L,P∩F,P∩L},其中A∩F是史前动物,A∩L是史后动物,P∩F是史前植物,P∩L是史后植物。加细定义3-9.3设S,S’是集合A的二个划分，若S的每一块均是S’中某块的子集，S是S’的加细。例:A=正整数集S={{1,3,5,7…},{2,4,6…}}S’={{1,5,9…},{3,7，11…},{2,4,6…}}则S’是S的细分定理3-9.2任何两种划分的交叉划分，都是原来各划分的一种加细。练习：3-9（2）证明：1.aA，a与a在同一分块中，故必有aRa。故R是自反的。2.若a与b在同一分块中，b与a也必在同一分块中，即aRbbRa，故R是对称的。3.若a与b在同一分块中，b与c在同一分块中，根据划分的定义，b属于且仅属于一个分块，故a与c必在同一分块中。即aRb∧bRcaRc，故R是传递的。3-10等价关系与等价类等价关系是一类重要的二元关系。