高等数学-离散数学及其应用-课件-第七章二元关系ppt.ppt

变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1主要内容主要内容l 有序对与笛卡儿积有序对与笛卡儿积l 二元关系的定义与表示法二元关系的定义与表示法l 关系的运算关系的运算l 关系的性质关系的性质l 关系的闭包关系的闭包l 等价关系与划分等价关系与划分l 偏序关系偏序关系第七章第七章 二元关系二元关系变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分27.1 有序对与笛卡儿积有序对与笛卡儿积定义定义7.1 由两个元素由两个元素 x 和和 y，按照一定的顺序组成的二元组，按照一定的顺序组成的二元组称为称为有序对有序对，记作，记作.有序对性质有序对性质: (1) 有序性有序性 （当（当x y时）时） (2) 与与相等的充分必要条件是相等的充分必要条件是 = x=u y=v. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分3笛卡儿积笛卡儿积定义定义7.2 设设A,B为集合，为集合，A与与B的的笛卡儿积笛卡儿积记作记作A B，且，且 A B = | x A y B.例例1 A=1,2,3, B=a,b,c A B =, B A =, A=, B= P(A) A = , P(A) B = 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分4笛卡儿积的性质笛卡儿积的性质(1) 不适合交换律不适合交换律 A B B A (A B, A, B)(2) 不适合结合律不适合结合律 (A B) C A (B C) (A, B, C)(3) 对于并或交运算满足分配律对于并或交运算满足分配律 A (B C) = (A B) (A C) (B C) A = (B A) (C A) A (B C) = (A B) (A C) (B C) A = (B A) (C A) (4) 若若 A 或或 B 中有一个为空集，则中有一个为空集，则 A B 就是空集就是空集. A = B = (5) A C B DA B C D.(6) 若若 |A| = m, |B| = n, 则则 |A B| = mn 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分5性质证明性质证明证明证明 A (B C) = (A B) (A C)证证 任取任取 A(BC) xAyBC xA(yByC) (xAyB)(xAyC) ABAC (AB)(AC)所以有所以有A(BC) = (AB)(AC).变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分6实例实例例例2 (1) 证明证明A=B,C=D A C=B D (2) A C = B D是否推出是否推出 A=B,C=D? 为什么？为什么？解解 (1) 任取任取 A C x A y C x B y D B D(2) 不一定不一定.反例如下：反例如下： A=1，B=2, C = D = , 则则A C = B D但是但是A B.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分77.2 二元关系二元关系定义定义7.3 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：(1) 集合非空集合非空, 且它的元素都是有序对且它的元素都是有序对(2) 集合是空集集合是空集则称该集合为一个则称该集合为一个二元关系二元关系, 简称为关系，记作简称为关系，记作R.如果如果R, 可记作可记作xRy；如果；如果 R, 则记作则记作x y实例：实例：R=, S=,a,b. R是二元关系是二元关系, 当当a, b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写1R2, aRb, a c等等. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分8A到到B的关系与的关系与A上的关系上的关系定义定义7.4设设A,B为集合为集合, AB的任何子集所定义的二元关系叫做的任何子集所定义的二元关系叫做从从A到到B的二元关系的二元关系, 当当A=B时则叫做时则叫做A上的二元关系上的二元关系.22n例例3 A=0,1, B=1,2,3, 那么那么 R1=, R2=AB, R3=, R4=R1, R2, R3, R4是从是从 A 到到 B 的二元关系的二元关系, R3 和和 R4 也是也是A上的二元关系上的二元关系. 计数计数: |A|=n, |AA|=n2, AA的子集有个的子集有个. 所以所以 A上有上有个不同的二元关系个不同的二元关系. 例如例如 |A| = 3, 则则 A上有上有=512个不同的二元关系个不同的二元关系. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分9A上重要关系的实例上重要关系的实例定义定义7.5 设设 A 为集合为集合, (1) 是是A上的关系，称为上的关系，称为空关系空关系(2) 全域关系全域关系 EA = | xAyA = AA 恒等关系恒等关系 IA = | xA 小于等于关系小于等于关系 LA = | x,yAxy, A为实数子集为实数子集 整除关系整除关系 DB = | x,yBx整除整除y, A为非为非0整数子集整数子集 包含关系包含关系 R = | x,yAx y, A是集合族是集合族.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分10实例实例例如例如, A=1, 2, 则则 EA = , IA = , 例如例如 A = 1, 2, 3, B=a, b, 则则 LA = , DA = ,例如例如 A = P(B) = ,a,b,a,b, 则则 A上的包含关系是上的包含关系是 R = , ,类似的还可以定义：类似的还可以定义： 大于等于关系大于等于关系, 小于关系小于关系, 大于关系大于关系, 真包含关系等真包含关系等.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分11关系的表示关系的表示1. 关系矩阵关系矩阵 若若A=x1, x2, , xn，R是是A上的关系，上的关系，R的关系矩阵是布尔的关系矩阵是布尔矩阵矩阵MR = (rij )n n, 其中其中 rij = 1 R 2. 关系图关系图 若若A= x1, x2, , xm，R是从是从A上的关系，上的关系，R的关系图是的关系图是GR=, 其中其中A为结点集，为结点集，R为边集为边集. 如果如果属于属于 关系关系R，在图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边. 注意：注意：l 关系矩阵适合表示有穷集关系矩阵适合表示有穷集A上的关系（可推广为从上的关系（可推广为从A到到B的的关系）关系）l 关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分12实例实例例例4 A=1,2,3,4, R=, R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下： 0010000011000011RM变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分137.3 关系的运算关系的运算关系的基本运算关系的基本运算定义定义7.6 关系的关系的定义域定义域、值域值域与与域域分别定义为分别定义为 domR = x | y ( R) ranR = y | x ( R) fldR = domR ranR 例例5 R=, 则则 domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分14关系运算关系运算(逆与合成逆与合成)定义定义7.7 关系的关系的逆运逆运算算 R 1 = | R 定义定义7.8 关系的关系的合成合成运算运算 F G = | t ( F G) 例例6 R = , , , S = , , , , R 1 = , , , R S = , , S R = , , , 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分15合成的图示法合成的图示法利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R S =, , S R =, , , 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分16关系运算关系运算(限制与像限制与像)定义定义7.9 设设R为二元关系为二元关系, A是集合是集合 (1) R在在A上的上的限制限制记作记作 R A, 其中其中 R A = | xRyxA (2) A在在R下的下的像像记作记作RA, 其中其中 RA=ran(R A) 说明：说明：l R在在A上的限制上的限制 R A是是 R 的子关系，即的子关系，即 R A Rl A在在R下的像下的像 RA 是是 ranR 的子集，即的子集，即 RA ranR 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分17实例实例例例7 设设R=, 则则 R 1 = , R = R 2,3 = , R1 = 2,3 R = R3 = 2 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分18关系运算的性质关系运算的性质定理定理7.1 设设F是任意的关系是任意的关系, 则则 (1) (F 1) 1=F (2) domF 1= ranF, ranF 1= domF证证 (1) 任取任取, 由逆的定义有由逆的定义有 (F 1) 1 F 1 F.所以有所以有(F 1) 1=F.(2) 任取任取x, xdomF 1 y(F 1) y(F) xranF 所以有所以有 domF 1=ranF. 同理可证同理可证 ranF 1=domF.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分19定理定理7.2 设设F, G, H是任意的关系是任意的关系, 则则(1) (F G) H = F (G H)(2) (F G) 1 = G 1 F 1关系运算的性质关系运算的性质证证 (1) 任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H) F (G H) 所以所以 (F G) H = F (G H)变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分20证明证明(2) 任取任取, (F G) 1 F G t (FG) t (G 1F 1) G 1 F 1所以所以 (F G) 1 = G 1 F 1 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分21关系运算的性质关系运算的性质定理定理7.3 设设R为为A上的关系上的关系, 则则 R IA= IA R=R证证任取任取 R IA t (RIA) t (Rt=yyA) R变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分22关系运算的性质关系运算的性质定理定理7.4 (1) F (G H) = F GF H (2) (GH) F = G FH 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 H F GF H所以有所以有 F (GH)=F GF H变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分23推广推广定理定理7.4 的结论可以推广到有限多个关系的结论可以推广到有限多个关系 R (R1R2Rn) = R R1R R2R Rn (R1R2Rn) R = R1 RR2 RRn R R (R1R2 Rn) R R1R R2 R Rn (R1R2 Rn) R R1 RR2 R Rn R 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分24关系运算的性质关系运算的性质定理定理7.5 设设F 为关系为关系, A, B为集合为集合, 则则(1) F (AB) = F AF B(2) F AB = F AF B(3) F (AB) = F AF B(4) F AB F AF B 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分25证明证明证证 只证只证 (1) 和和 (4). (1) 任取任取 F (AB) FxAB F(xAxB) (FxA)(FxB) F AF B F AF B 所以有所以有F (AB) = F AF B. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分26证明证明(4) 任取任取y, yF AB x (FxAB) x (FxAxB) x (FxA)(FxB) x (FxA) x (FxB) yF AyF B yF AF B所以有所以有F AB=F AF B. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分27关系的幂运算关系的幂运算定义定义7.10设设 R 为为 A 上的关系上的关系, n为自然数为自然数, 则则 R 的的 n 次幂次幂定义为：定义为：(1) R0 = | xA = IA(2) Rn+1 = Rn R注意：注意：l对于对于A上的任何关系上的任何关系 R1 和和 R2 都有都有 R10 = R20 = IA l对于对于A上的任何关系上的任何关系 R 都有都有 R1 = R变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分28例例 8 设设A = a,b,c,d, R = , 求求R的各次幂的各次幂, 分别用矩阵和关系图表示分别用矩阵和关系图表示. 0000100001010010M解解 R 与与 R2的关系矩阵分别是：的关系矩阵分别是： 0000000010100101000010000101001000001000010100102M幂的求法幂的求法变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分29R3和和R4的矩阵是：的矩阵是：因此因此M4=M2, 即即R4=R2. 因此可以得到因此可以得到 R2=R4=R6=， R3=R5=R7=R0的关系矩阵是的关系矩阵是 0000000010100101,000000000101101043MM 10000100001000010M幂的求法幂的求法变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分30关系图关系图R0, R1, R2, R3,的关系图如下图所示的关系图如下图所示. R0R1R2=R4=R3=R5=变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分31幂运算的性质幂运算的性质定理定理7.6 设设 A 为为 n 元集元集, R 是是A上的关系上的关系, 则存在自然数则存在自然数 s 和和 t, 使得使得 Rs = Rt.证证 R 为为A上的关系上的关系, 由于由于|A|=n, A上的不同关系只有上的不同关系只有 个个. 列出列出 R 的各次幂的各次幂 R0, R1, R2, , , , 必存在自然数必存在自然数 s 和和 t 使得使得 Rs = Rt 22nR22n变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分32定理定理7.7 设设 R 是是 A上的关系上的关系, m, nN, 则则 (1) Rm Rn = Rm+n(2) (Rm)n = Rmn 幂运算的性质幂运算的性质证证 用归纳法用归纳法(1) 对于任意给定的对于任意给定的mN, 施归纳于施归纳于n.若若n=0, 则有则有 Rm R0 = Rm IA = Rm = Rm+0 假设假设 Rm Rn = Rm+n, 则有则有 Rm Rn+1 = Rm (Rn R) = (Rm Rn) R = Rm+n+1 , 所以对一切所以对一切m,nN 有有 Rm Rn = Rm+n. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分33证明证明(2) 对于任意给定的对于任意给定的mN, 施归纳于施归纳于n.若若n=0, 则有则有 (Rm)0 = IA = R0 = Rm0 假设假设 (Rm)n = Rmn, 则有则有 (Rm)n+1 = (Rm)n Rm = (Rmn) Rn = Rmn+m = Rm(n+1)所以对一切所以对一切m,nN 有有 (Rm)n = Rmn. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分34定理定理7.8 设设R 是是A上的关系上的关系, 若存在自然数若存在自然数 s, t (st) 使得使得 Rs=Rt, 则则 (1) 对任何对任何 kN有有 Rs+k = Rt+k (2) 对任何对任何 k, iN有有 Rs+kp+i = Rs+i, 其中其中 p = t s (3) 令令S = R0,R1,Rt 1, 则对于任意的则对于任意的 qN 有有RqS幂运算的性质幂运算的性质证证 (1) Rs+k = Rs Rk = Rt Rk = Rt+k (2) 对对k归纳归纳. 若若k=0, 则有则有Rs+0p+i = Rs+i假设假设 Rs+kp+i = Rs+i, 其中其中p = t s, 则则 Rs+(k+1)p+i = Rs+kp+i+p = Rs+kp+i Rp = Rs+i Rp = Rs+p+i = Rs+t s+i = Rt+i = Rs+i 由归纳法命题得证由归纳法命题得证.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分35证明证明(3) 任取任取 qN, 若若 q t, 显然有显然有 RqS, 若若q t, 则存在自然数则存在自然数 k 和和 i 使得使得 q = s+kp+i, 其中其中0ip 1.于是于是 Rq = Rs+kp+i = Rs+i 而而 s+i s+p 1 = s+t s 1 = t 1从而从而证明了证明了 RqS.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分367.4 关系的性质关系的性质定义定义7.11 设设 R 为为A上的关系上的关系, (1) 若若 x(xA R), 则称则称 R 在在 A 上是上是自反自反的的.(2) 若若 x(xA R), 则称则称 R 在在 A 上是上是反自反反自反的的. 实例：实例：自反：全域关系自反：全域关系EA, 恒等关系恒等关系IA, 小于等于关系小于等于关系LA, 整除关系整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系. A=1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R2 自反自反 ，R3 反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分37对称性与反对称性对称性与反对称性定义定义7.12 设设 R 为为 A上的关系上的关系, (1) 若若 x y( x,yARR), 则称则称 R 为为 A上上对对称称的关系的关系.(2) 若若 x y( x,yARRx=y), 则称则称 R 为为A上的上的反对称反对称关系关系.实例：对称关系：实例：对称关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA和空关系和空关系反对称关系：恒等关系反对称关系：恒等关系IA和空关系也是和空关系也是A上的反对称关系上的反对称关系. 设设A1,2,3, R1, R2, R3和和R4都是都是A上的关系上的关系, 其中其中 R1,，R2, R3,，R4, R1：对称和反对称；：对称和反对称； R2：只有对称；：只有对称；R3：只有反对称；：只有反对称； R4：不对称、不反对称：不对称、不反对称变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分38传递性传递性定义定义7.13 设设R为为A上的关系上的关系, 若若 x y z(x,y,zARRR),则称则称 R 是是A上的上的传递传递关系关系.实例：实例： A上的全域关系上的全域关系 EA,恒等关系恒等关系 IA和空关系和空关系 ，小于等小于等于和小于关系，整除关系，包含与真包含关系于和小于关系，整除关系，包含与真包含关系设设 A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3R1和和R3是是A上的传递关系上的传递关系, R2不是不是A上的传递关系上的传递关系. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分39关系性质成立的充要条件关系性质成立的充要条件定理定理7.9 设设R为为A上的关系上的关系, 则则(1) R 在在A上自反当且仅当上自反当且仅当 IA R(2) R 在在A上反自反当且仅当上反自反当且仅当 RIA = (3) R 在在A上对称当且仅当上对称当且仅当 R=R 1(4) R 在在A上反对称当且仅当上反对称当且仅当 RR 1 IA(5) R 在在A上传递当且仅当上传递当且仅当 R R R 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分40证明证明证明证明 只证只证(1)、(3)、(4)、(5)(1) 必要性必要性任取任取, 由于由于R 在在A上自反必有上自反必有 IA x,yAx=y R从而证明了从而证明了IA R充分性充分性.任取任取x, 有有 xA IA R因此因此 R 在在A上是自反的上是自反的. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分41证明证明(3) 必要性必要性. 任取任取, R R R 1所以所以 R = R 1充分性充分性.任取任取, 由由R = R 1得得R R 1 R所以所以R在在A上是对称的上是对称的变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分42证明证明(4) 必要性必要性. 任取任取, 有有 RR 1 RR 1 RR x=y x,y A IA这就证明了这就证明了RR 1 IA充分性充分性. 任取任取, RR RR 1 RR 1 IA x=y从而证明了从而证明了R在在A上是反对称的上是反对称的.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分43证明证明(5) 必要性必要性. 任取任取有有 R R t (RR) R所以所以 R R R充分性充分性. 任取任取,R, 则则 RR R R R 所以所以 R 在在 A上是传递的上是传递的变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分44自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合集合IA RRIA=R=R 1RR 1 IAR R R关系关系矩阵矩阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元素全是0矩阵是矩阵是对称矩阵对称矩阵若若rij1, 且且ij, 则则rji0M2中中1位置位置, M中相应位中相应位置都是置都是1关系关系图图每个顶每个顶点都有点都有环环每个顶点每个顶点都没有环都没有环两点之间两点之间有边有边, 是是一对方向一对方向相反的边相反的边两点之间有两点之间有边边,是一条有是一条有向边向边点点xi到到xj有有边边, xj 到到xk有边有边, 则则xi到到xk也有边也有边 关系性质的三种等价条件关系性质的三种等价条件变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分45关系性质的判别关系性质的判别例例9 判断下列各图的性质判断下列各图的性质 (a) (b) (c) 解：解：(a) 对称对称(b) 反自反、反对称、传递反自反、反对称、传递(c) 自反、反对称自反、反对称变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分46自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 关系的性质和运算之间的联系关系的性质和运算之间的联系变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分477.5 关系的闭包关系的闭包 主要内容主要内容l 闭包定义闭包定义l 闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示l 闭包的性质闭包的性质 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分48闭包定义闭包定义定义定义7.14 设设R是非空集合是非空集合A上的关系上的关系, R的的自反自反(对称对称或或传递传递)闭闭包包是是A上的关系上的关系R , 使得使得R 满足以下条件：满足以下条件：(1) R 是自反的是自反的(对称的或传递的对称的或传递的) (2) R R (3) 对对A上任何包含上任何包含R的自反的自反(对称或传递对称或传递)关系关系R 有有RR R的自反闭包记作的自反闭包记作r(R), 对称闭包记作对称闭包记作s(R), 传递闭包记作传递闭包记作t(R). 定理定理7.10 设设R为为A上的关系上的关系, 则有则有(1) r(R)=RR0(2) s(R)=RR 1(3) t(R)=RR2R3说明：对有穷集说明：对有穷集A(|A|=n)上的关系上的关系, (3)中的并最多不超过中的并最多不超过Rn变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分49证明证明证证 只证只证(1)和和(3). (1) 由由IA=R0 RR0 知知 RR0是自反的是自反的, 且满足且满足R RR0设设R 是是A上包含上包含R的自反关系的自反关系, 则有则有R R 和和IA R . 从而有从而有RR0 R . RR0满足闭包定义满足闭包定义, 所以所以r(R)=RR0.(1) 先证先证 RR2 t(R)成立成立. 用归纳法证明对任意正整数用归纳法证明对任意正整数n 有有Rn t(R). n=1时有时有R1=R t(R). 假设假设Rn t(R)成立成立, 那么对任意的那么对任意的 Rn+1=Rn R t ( RnR) t (t(R)t(R) t(R) 这就证明了这就证明了Rn+1 t(R). 由归纳法命题得证由归纳法命题得证. 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分50证明证明再证再证 t(R) RR2成立成立, 为此只须证明为此只须证明RR2传递传递. 任取任取, 则则 RR2RR2 t (Rt) s(Rs) t s (Rt Rs ) t s (Rt+s ) RR2从而证明了从而证明了RR2是传递的是传递的.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分51闭包的矩阵表示和图表示闭包的矩阵表示和图表示设关系设关系R, r(R), s(R), t(R)的关系矩阵分别为的关系矩阵分别为M, Mr , Ms 和和 Mt 则则 Mr=M+E Ms=M+M Mt=M+M2+M3+E 是单位矩阵是单位矩阵, M 是是 转置矩阵，相加时使用转置矩阵，相加时使用逻辑加逻辑加.设关系设关系R, r(R), s(R), t(R)的关系图分别记为的关系图分别记为G, Gr, Gs, Gt, 则则Gr , Gs , Gt 的顶点集与的顶点集与G 的顶点集相等的顶点集相等. 除了除了G 的边以外的边以外, 以下述以下述方法添加新的边：方法添加新的边： (1) 考察考察G 的每个顶点的每个顶点, 若没环就加一个环，得到若没环就加一个环，得到Gr (2) 考察考察G 的每条边的每条边, 若有一条若有一条 xi 到到 xj 的单向边的单向边, ij, 则在则在G 中加一条中加一条 xj 到到 xi 的反向边的反向边, 得到得到Gs(3) 考察考察G 的每个顶点的每个顶点 xi, 找找 xi 可达的所有顶点可达的所有顶点 xj (允许允许i=j )， 如果没有从如果没有从 xi 到到 xj 的边的边, 就加上这条边就加上这条边, 得到图得到图Gt变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分52实例实例例例9 设设A=a,b,c,d, R=, R和和r(R), s(R), t(R)的关系图如下图所示的关系图如下图所示. Rr(R)s(R)t(R)变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分53求传递闭包的算法求传递闭包的算法算法算法 Warshall输人：输人：M（R的关系矩阵）的关系矩阵）输出：输出：MT（t(R)的关系矩阵）的关系矩阵）1MTM2for k1 to n do3 for i1 to n do 4 for j1 to n do5 MTi,jMTi,j+MTi,k MTk,j 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分54实例实例 1111111111111111,11111000111111110111100001110111,0010100001110010,001010000101001043210MMMMM设设A=a,b,c,d, R=, R的传递闭包的矩阵如下：的传递闭包的矩阵如下： 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分55闭包的性质闭包的性质定理定理7.11 设设R是非空集合是非空集合A上的关系上的关系, 则则(1) R是自反的当且仅当是自反的当且仅当 r(R)=R. (2) R是对称的当且仅当是对称的当且仅当 s(R)=R. (3) R是传递的当且仅当是传递的当且仅当 t(R)=R.定理定理7.12 设设R1和和R2是非空集合是非空集合A上的关系上的关系, 且且 R1 R2, 则则(1) r(R1) r(R2) (2) s(R1) s(R2) (3) t(R1) t(R2)证明证明 略略变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分56定理定理7.13 设设R是非空集合是非空集合A上的关系上的关系,(1) 若若R是自反的是自反的, 则则 s(R) 与与 t(R) 也是自反的也是自反的(2) 若若R是对称的是对称的, 则则 r(R) 与与 t(R) 也是对称的也是对称的(3) 若若R是传递的是传递的, 则则 r(R) 是传递的是传递的. 说明：如果需要进行多个闭包运算，比如求说明：如果需要进行多个闭包运算，比如求R的自反、对的自反、对称、传递的闭包称、传递的闭包 tsr(R)，运算顺序如下：，运算顺序如下： tsr(R) = rts(R) = trs(R)闭包的性质闭包的性质证明证明 略略变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分577.6 等价关系与划分等价关系与划分 主要内容主要内容l 等价关系的定义与实例等价关系的定义与实例l 等价类及其性质等价类及其性质l 商集与集合的划分商集与集合的划分l 等价关系与划分的一一对应等价关系与划分的一一对应 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分587.6 等价关系与划分等价关系与划分定义定义7.15 设设R为非空集合上的关系为非空集合上的关系. 如果如果R是自反的、对称的和是自反的、对称的和传递的传递的, 则称则称R为为A上的上的等价关系等价关系. 设设 R 是一个等价关系是一个等价关系, 若若R, 称称 x等价于等价于y, 记做记做xy. 实例实例 设设 A=1,2,8, 如下定义如下定义A上的关系上的关系R： R=| x,yAx y(mod 3)其中其中x y(mod 3)叫做叫做 x与与 y 模模3相等相等, 即即x除以除