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

3-7 复合关系和逆关系 二元关系是以序偶为元素的集合，所以可以对它 进行集合运算。 此外还有一种新的运算：关系的复合 定义3-7.1 设R是从集合A到集合B上的二元关系，S 是从集合B到集合C上的二元关系，则RS称为R和S 的复合关系，表示为 RS= xAzC y(yBRS) 复合关系举例 例：A=1，2，3，4，B=3，5，7，C=1，2，3 R=，S=， 则 RS=， 如图所示： 复合关系的结合律 定理：设R1 A1 A2, R2 A2 A3, R3 A3 A4, 则 (R1R2)R3 = R1(R2R3)。 例：设A=1,2,3,4,5 A上的二元关系R=, S=, 则 RS=, SR=, RS (RS)R= R(SR)= 复合关系的矩阵表示（自学） 两个关系的复合可通过相应矩阵相乘获得。 复合关系练习 练习：R是A上的二元关系，试证R是传递的充要条 件是RRR 证： ：RR 必y使得 R，R R是传递的 R RRR ：R, R 必有R R R RR R 由x,y,z任意性知 xyz(RRR) R是传递的 逆关系 定义3-7.2 设R是A到B的二元关系，则R的逆是B到A 的二元关系，记为Rc，其中Rc =|R 。 注 ：（1）xRyyRcx （2）互换R的关系矩阵的行和列，即得Rc的 关系矩阵。 即 M M R R c c M M R R T T （3）颠倒R的关系图中每条弧线的箭头方向 ，即得Rc的关系图。 逆关系举例 例1 整数集上的 关系 集合族上的 关系的逆是 空关系的逆是空关系 AB的全域关系的逆是BA的全域关系 例2 A=0,1,2,3，R=, 则 Rc = , 定理 定理：定理：设R,R2,R1是A到B的关系，则 a） (Rc)c=R b） (R1R2)c = R1cR2c c） (R1R2)c = R1cR2 d） (R)c = (Rc), R=AB-R 即R的补的 逆等于逆的补 e） (R1-R2)c =R1c -R2c f) (AB)c = BA 定理 定理3-7.2 设R、S分别是A到B、B到C的关系， 则(RS)c=Sc Rc 证：设 是(RS)c 的任一元素， 则 (RS)c RS b(RS) b(c,bScRc) Sc Rc 定理 定理3-7.3 R是A上的二元关系 (a) R是对称的 R=Rc (b) R是反对称的 RRcIA 证：(a)：任取R，因为R是对称的， 所以RRR c ：任取R ， 则Rc R=Rc 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)=RIA 对称闭包 s(R)=RRc 传递闭包 t(R)= = RR2R3 证明 r(R)=RIA 证：设R = RIA xA,R R具有自反性 RR 设R”是自反的，且RR” R是自反的，IAR” 又RR” R=IARR” 综上所述，R满足自反闭包定义的三个条件 ， r(R)= R= RIA 证明 s(R)=RRc 证明：设 R= RRc Rc=(RRc)c=Rc(Rc)c= RcR=R ， 所以R是对称的 R=RRcR 设R”是对称的，且RR” ，要证 RR” 任取RRcRRc R”R R”R” R”R” R” R=RRcR” 综上所述，由定义知道，R即RRc为R的对称闭包 。 证 t(R)= = RR2R3(R为A上的二元关系 ） 证：(1)证 t(R)： 先用归纳法证，对n0, Rn t(R) a)由定义 R t(R) b)设Rn t(R)成立，要证Rn+1 t(R) 任取Rn+1=RnR， 存在cA,使Rn,R 由归纳假设和基础步骤知 t(R) ，t(R） t(R)是传递的， t(R) 即 Rn+1 t(R) 对一切n， Rn t(R) 根据的结论，证 t(R)： 任取 存在一个n，使Rn t(R) t(R) t(R) (2) 证 t(R) 设,是 的任意元素 必s,t,使得Rs,Rt RtRs = Rt+s 是传递的 t(R)是包含R的最小传递关系 t(R) 由（1），（2）得 t(R) = 闭包运算举例 题：设A=a,b,c, R是A上的二元关系，且给定 R=, 求r(R),s(R),t(R)。 解：r(R)= R IA = , s(R)= R Rc = , t(R)=RR2R3 = RR2R3 （因为R4=R,R5=R2,R6=R3,) = , , 定理3-8.5 设R为X上二元关系，X=n，那么，存 在一个正整数kn，使得 t()= R R2 R3 . Rk 例：P123例题2 求R+的算法Warshall算法 AM i=1 对i列中出现1的各行，分别被或上i行 i=i+1 in 结束 Y 例：P124例题3 P125例题4 设有一字母表V=A,B,C,D,e,d,f并给定下面 六条规则： A-Af, B-Dde, C-e, A-B, B-De, D-Bf R为定义在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(RRc) = IxRRc = IxRRcIx = (IxR)(RcIxc) = (IxR)(RIx)c = s(IxR) = sr(R) 证明 rt(R)=tr(R) 证：rt(R) = r(RR2) = IXRR2 tr(R) = t( RIX) = IXR(IXR)2(IXR)n = IXRR2Rn rt(R)=tr(R) 注：以上证明引用了公式：（证明略） ( RIX)n = IXRR2Rn 证明 st(R) ts(R) 证： 先证 R对称t( R )对称 t( R )-1 = (RR2R3)-1 = R-1(R2)-1(R3)-1 = R-1(R-1)2(R-1)3 (FG)-1=G-1F-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= , 则s(R)= , t(s(R)= , , s(t(R)= s , = , t(s(R) 注意：先做传递，再做对称，有可能破坏传递性。 3-9 集合的划分和覆盖 除了把两个集合相互比较外，还常把一个集合 分成若干子集讨论。 定义3-9.1 设A为非空集，S=S1Sm,SiA，Si (i=1m)且S1S2.Sm=A，称S是A的覆盖. 若再加SiSj= (i,j=1m,ij)则称S是A的划分 ,m称为划分的秩。 集合的划分和覆盖举例 例例1 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=A1Am,S2=B1Bn是A的二个划 分,则 S=AiBj|AiS1BjS2 称为A的交叉划分。 定理3-9.1 设 A1,A2,Am与B1,B2,Bn为同 一集合A的两个划分。则其交叉划分AiBj亦是原集 合的一种划分。 交叉划分举例 例：例：设B是所有生物的集合, 可划分成A, P, 其 中A表示所有动物Animal的集合, P表示所有植物 Plant的集合。 B也可划分成 F, L,其中F表示史前First生 物,L表示史后Last生物。 它们的交叉划分为 : D = AF, AL, PF, PL, 其中AF是史前动物, AL是史后动物, PF是史前植物, PL是史后植物。 加细 定义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. aA，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 等价关系与等价类 等价关系是一类重要的二元关系。 定义3-10.1 若集合A上的二元关系R是自反的，对 称的和传递的，称R是等价关系。若R是等价关系， aRb，可读为“a等价于b”。 例如， 数中的相等关系，是等价关系 集合中的相等关系，是等价关系 命题演算中关系，是等价关系 全域关系是等价关系，空集上任何关系是 等价关系。 等价关系举例 例： 设A=1,2,8，如下定义A上的关系R： R=|x，yAxy(mod 3) 其中xy(mod 3)叫做模3同余，即x除以3的余数与 y除以3的余数相等。不难验证R为A上的等价关系， 因为 xA，有xx(mod 3)， x，yA，若xy(mod 3)，则有yx(mod 3)， x，y，zA，若xy(mod 3)，yz(mod 3)， 则有xz(mod 3)。 该关系的关系图如下： 等价关系举例（续） 不难看出，上述关系图被分为三个互不相连通 的部分。每部分中的数两两都有关系，不同部分中 的数则没有关系。每一部分中的所有的顶点构成一 个等价类。 等价类 定义3-10.2 设R是A上的等价关系，对aA，集合 aR=x|xRa称为a关于R的等价类，简记为a， a 称为等价类aR的表示元素。 从以上定义可以知道，a的等价类是A中所有与a 等价的元素构成的集合。上例中的等价类是： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6 例：设I是整数集，R是模3同余关系， 即R=|xIyIxy(mod3) 不难验证R是等价关系，其等价类为 0R = -6,-3,0,3,6 1R = -2,1,4 2R = -4,-1,2,5 等价类的每一元素均可作本等价类的表示元素。 定理3-10.1 设给定集合A上的等价关系R， 对于a,b A 有 aRb iff aR=bR 证： aaR=bR 根据等价类定义 aRb aRb xaR xRa xRb xbR 由x的任意性知，aR=bR 商集 定义3-10.3 集合A上的等价关系R，其等价类集合 aR|a A，称为A关于R的商集，记为A/R。 例1： A=1,2,8， R= |x，yAxy(mod 3) 则A/R= 1,4,7,2,5,8,3,6 例2： A为正整数集合，R是模3同余关系， 则A/R= 0R,1R,2R ， 其中 0R = -6,-3,0,3,6 1R = -2,1,4 2R = -4,-1,2,5 显然： 商集是集合的集合。 商集的每个元素是等价关系的一个等价类。 等价类中的每个元素都是集合A上的元素。 同一等价类中的任意两个元素都具有关系R。 商集举例 例：设集合S = a, b, c, d, e, f, g，S上的等 价关系R如下表所示，求商集S/R。 abcdefg a b c d e f g S/R = a, b, c, d, e, f, g 思考：R=? 根据等价类对集合进行划分 定理3-10.2 集合A上的等价关系R决定了A的一个划 分，即为商集A/R。 证明 A/R= aR|aA （1）根据等价类定义，aA，aR A aR A aA，aRa aaR A aR aR=A A/R是一个覆盖 根据等价类对集合进行划分 （2）证：需证 a,bA， 若aRbR ， 则 aRbR= 。 反证法：若aRbR 则caRbR cRa 且 cRb R是对称、传递的 aRb 则 aR=bR ，这与前提矛盾。 由（1），（2） 得A/R是一个划分。 定理3-10.3 集合A的任一划分S确定了A的一个等价 关系R。 证明 设S=S1，S2，Sm（构造性证明） 定义关系R: aRb当且仅当a,b在S的同一块中， 现证R是等价关系。 (1) aA， a与a在同一块中 aRa，自反性成立。 (2) a,bA ，若aRb，则a与b在同一块中，则b 与a也在同一块 bRa，即 aRbbRa 对称性成立 (3) a,b,cA，若aRb， bRc，则a与b在同一块， b与c在同一块 SiSj= (ij) a与c在同一块，即aRbbRcaRc 传递性成立 综上所述，R是A的一个等价关系，且A/R=S 定理3-10.3举例 例： A=a,b,c,d,e，S= a,b,c,d,e ， 求由S确定的等价关系。 解：设 R1=a,ba,b= , R2=cc= R3=d,ed,e= , 则 R=R1R2R3是由S确定的等价关系。 若S=a,b,c,d,e，则由S确定的等价关 系是什么？ 定理3-10.4 设R1，R2是非空集合A上的等价关系 ，则R1=R2 A/R1=A/R2。 证明 ：若R1=R2 A/R1=aR1|aA，A/R2=aR2|aA 则 xaR1 R1 R2 xaR2 ， aR1 aR2 同理可证， aR2 aR1 aR1 = aR2 A/R1 = A/R2 ：aA， aR1 A/R1 A/R1= A/R2 必 cR2A/R2，使 aR1 =cR2 a,bA R1 aaR1baR1 acR2bcR2 R2 R1 R2 同理可证：R2R1 R1 = R2 综上所述，R1=R2 A/R1=A/R2 例：设和是非空集A的划分,R、R是分别由 、确定的等价关系，试证 细分 R R 证：R 则a、b在的同一块 中， 细分 a、b在的同一块 R R R ：设 Si aSi， 则 Si=aR=x|xRa xSi xRaxRaxaR aRaR 由 Si的任意性，知 细分 细分 R R 加细（细分）图解 3-11 相容关系 定义3-11.1 设R是集合A上的二元关系，若R是自反 的和对称的，称R是相容关系。 例：所有等价关系是相容关系； 在一群人的集合中, 朋友关系也是相容关系。 相容关系的表示方法 因为相容关系是自反和对称的, 其关系矩阵是对 称的且主对角线元素全为1, 因此我们可仅用下三 角矩阵T来表示和存储就够了, 即关系矩阵可以简 化为“阶梯形”。 相容关系的关系图可简记为： 用无向边代替 二有向边 自回路省略 相容关系的表示方法(P135例题) 111000 111110 111100 011110 010110 000001 x1 x6 x4 x3 x2 x5 相容关系r的矩阵及图形表示 定义3-11.2 设R是集合A上的相容关系, 若CA, 若任意a,bC, 有aRb, 则称C是由R产生的相容类 。 例：上例相容关系r产生的相容类。 最大相容类 定义3-11.3 设R为定义在集合A上的相容关系，如 果不能真包含在任何其他相容类中的相容类，称作 最大相容类，记为CR。 例：P137例题1 a3 a4 a2 a5 a7 a6 a1 相容关系的确定 利用相容关系的关系图来确定相容类和最大相 容类是方便的。 极大完全子图的顶点集合就是最大相容类。 所谓极大完全子图是指每对顶点都有边相连的多 边形,而最大相容类外的任何顶点不可能与类内的 所有顶点相连。 另外孤立顶点, 以及不在极大完全子图两个顶点 及其连线, 也是最大相容类。 例 设给定的相容关系图表示成下图, 写出所有的 最大相容类。 解 最大相容类：h, a, b, d, e, f, b, c, d, f, g。 完全覆盖 定义3-11.4 设R为定义在集合A上的相容关系，其最 大相容类的集合称作集合A的完全覆盖，记为CR(A)。 例1： 1 2 3 4 5 6 A的完全覆盖是： 1，2，3，4，5，6，5，2，6，3 3-12 序关系 定义3-12.1 若集合A上的二元关系R是自反的、反 对称的和传递的，则称R是A的偏序关系，记作 。 设 为偏序关系，如果 ，则记作x y， 读作“小于或等于”。序偶称为偏序集合。 注意这里的“小于或等于”不是指数的大小， 而是在偏序关系中的顺序性。x“小于或等于”y的 含义是：依照这个序，x排在y的前边或者x就是y。 根据不同偏序的定义，对序有着不同的解释。例如 整除关系是偏序关系，3 6的含义是3整除6。大于 或等于关系也是偏序关系，针对这个关系写5 4是 说大于或等于4,关系中5排在4的前边，也就是5比4 大。 盖住 定义3-12.2 在偏序集中，如果x,yA ， x y， x y，且没有其他元素z满足x z、 z y，则称元素y盖住元素x。并且把所有具备盖住 性质的续偶集合记作COV A， COV A=|y盖住x 例：A为正整数m12的因子的集合，并设 为整除 关系，求COV A。(P140) 哈斯图（偏序集合图） 对于给定的偏序集 ，它的盖住关系是 唯一的，所以可以用哈斯图表示偏序集合图。 哈斯图作图规则： 用小圆圈代表元素。 如果 x y，且x y，则将代表y的小圆圈画在 代表x的小圆圈之上。 如果 COV A,则在x与y之间用直线连接 。 哈斯图举例 例：画出偏序集 的哈斯图。 哈斯图举例（续） 例：A=a,b,c， 画出 的哈斯图。 a b c a,b a,c b,c a,b,c 哈斯图举例（续） 例：已知偏序集的哈斯图如图所示，试求出 集合A和关系R的表达式。 解： A=a,b,c,d,e,f,g,h R=, ,IA abc de f h g 偏序集中的特殊元素 定义3-12.5,3-12.6 设为偏序集，B是A的子 集，yB。 若 x(xBy x)成立，则称y为B的最小元。 若 x(xBx y)成立，则称y为B的最大元。 若bB,且B中不存在任何元素x,使bx且b x 称b是B的极大元。 若bB,且B中不存在任何元素x,使bx且x b 称b是B的极小元。 例：设偏序集如图所示，求A的极小元，最 小元，极大元，最大元。 abc de f h g 解:极小元：a,b,c,g。 极大元：a,f,h。 没有最小元与最大元。 由这个例子可以知道， 哈斯图中的孤立顶点既是极 小元也是极大元。 ba ed c 解：A不存在最大、最小元；极大元素为d,e,极 小元素为a,b； B的最大元素为c，没有最小元素；极大元素 为c, 极小元素为a,b。 例：设A=a,b,c,d,e、 B=a,b,c，则各自的最大 最小元素、极大极小元素是 哪些？ 最小元是B中最小的元素，它与B中其它元素都 可比；而极小元不一定与B中元素可比，只要没有 比它小的元素，它就是极小元。对于有穷集B，极 小元一定存在，但最小元不一定存在。最小元如果 存在，一定是唯一的，但极小元可能有多个。如果 B中只有一个极小元，则它一定是B的最小元。如果 B中存在最小元，则它一定是B的唯一极小元。类似 的，极大元与最大元也有这种区别。 定理定理3-12.13-12.1 设是一偏序集合，且BA，若B 有最大（最小）元，则是唯一的。 证： 设a,b都是B的最大元素， 那么a b,b a，从偏序关系的反对称性 ，得a=b。 最小元证明情况与此类似。 上界、下界 定义定义3-12.73-12.7，3-12.8 3-12.8 设为偏序集，BA， yA。 （1） 若 x(xBx y)成立，则称y为B的 上界。 （2） 若 x(xBy x)成立，则称y为B的 下界。 （3） 令Cy|y为B的上界，则称C的最小元 为B的最小上界或上确界。 （4） 令Dy|y为B的下界，则称D的最大元 为B的最大下界或下确界。 设为有序集，BA。 的哈斯图如下所示 。 A= a，b，c，d，e，f，g，h，i，j，k , B=a，b，c，d，e，f，g B=h，i，j，k jk hi fg edcb a jk hi fg edcb a B B的上界 B的下下界 B 由定义可知，B的最小元一定是B的下界，同时 也是B的最大下界。同样的，B的最大元一定是B的 上界，同时也是B的最小上界。但反过来不一定正 确，B的下界不一定是B的最小元，因为它可能不是 B中的元素。同样的，B的上界也不一定是B的最大 元。 序关系（注意） （1）B的最大（小）元素和极大（小）元素必须 是子集B的元素，而B的上界（下界）和最