离散数学-耿素云(第5版)-4.3-4PPT优秀课件

1、1 4.3 关系的性质关系的性质 n自反性自反性 n反自反性反自反性 n对称性对称性 n反对称性反对称性 n传递性传递性 2 自反性与反自反性自反性与反自反性 定义定义 设设R为为A上的关系上的关系, (1) 若若 x(xA R), 则称则称R在在A上是上是自反自反的的. (2) 若若 x(xA R), 则称则称R在在A上是上是反自反反自反的的. 实例：实例： 反关系：反关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA 小于等于关系小于等于关系LA, 整除关系整除关系DA 反自反关系：实数集上的小于关系反自反关系：实数集上的小于关系 幂集上的真包含关系幂集上的真包含关系 3 实例实

2、例 例例1 A=1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3 R2自反自反, R3反自反反自反, R1既不是自反也不是反自反的既不是自反也不是反自反的 4 对称性与反对称性对称性与反对称性 定义定义 设设R为为A上的关系上的关系, (1) 若若 x y(x,yARR), 则称则称R 为为A上上对称对称的关系的关系. (2) 若若x y(x,yARRx=y), 则称则称R为为A上的上的反对称反对称关系关系. 实例：实例： 对称关系：对称关系：A上的全域关系上的全域关系EA, 恒等关系恒等关系IA和空和空 关系关系 反对称关系：恒等关系反对称关系：恒等

3、关系IA，空关系是空关系是A上的反对上的反对 称关系称关系. 5 实例实例 例例2 设设A1,2,3, R1, R2, R3和和R4都是都是A上的关系上的关系, 其中其中 R1,， R2, R3,， R4, R1 对称、反对称对称、反对称. R2 对称，不反对称对称，不反对称. R3 反对称，不对称反对称，不对称. R4 不对称、也不反对称不对称、也不反对称. 6 传递性传递性 定义定义 设设R为为A上的关系上的关系, 若若 x y z(x,y,zARRR), 则称则称R是是A上的上的传递传递关系关系. 实例：实例： A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系 小于等

4、于关系小于等于关系, 小于关系，整除关系，包含关系，小于关系，整除关系，包含关系， 真包含关系真包含关系 7 实例实例 例例3 设设A1,2,3, R1, R2, R3是是A上的关系上的关系, 其中其中 R1, R2, R3 R1 和和 R3 是是A上的传递关系上的传递关系 R2不是不是A上的传递关系上的传递关系 8 关系性质的充要条件关系性质的充要条件 设设R为为A上的关系上的关系, 则则 (1) R在在A上上自反自反当且仅当当且仅当 IA R (2) R在在A上上反自反反自反当且仅当当且仅当 RIA= (3) R在在A上上对称对称当且仅当当且仅当 R=R 1 (4) R在 在A上上反对称反

5、对称当且仅当当且仅当 RR 1 IA (5) R在在A上上传递传递当且仅当当且仅当 R R R 9 关系性质判别关系性质判别 自反自反反自反反自反对称对称反对称反对称传递传递 表达式表达式 IA RRIA=R=R 1 RR 1 IA R R R 关系关系 矩阵矩阵 主对主对 角线角线 元素元素 全是全是1 主对角主对角 线元素线元素 全是全是0 矩阵是对称矩阵是对称 矩阵矩阵 若若rij1, 且且 ij, 则则rji 0 对对M2中中1 所在位置所在位置, M中相应中相应 位置都是位置都是1 关系图关系图 每个每个 顶点顶点 都有都有 环环 每个顶每个顶 点都没点都没 有环有环 如果两个顶如果

6、两个顶 点之间有边点之间有边, 是一对方向是一对方向 相反的边相反的边 (无单边无单边) 如果两点如果两点 之间有边之间有边, 是一条有是一条有 向边向边(无双无双 向边向边) 如果顶点如果顶点 xi 连通到连通到 xk , 则从则从 xi 到到 xk 有边有边 10 实例实例 例例8 判断下图中关系的性质判断下图中关系的性质, 并说明理由并说明理由. (b)反自反，不是自反的；反对称，不是对称的；反自反，不是自反的；反对称，不是对称的； 是传递的是传递的. (a)不自反也不反自反；对称不自反也不反自反；对称, 不反对称；不传递不反对称；不传递. (c)自反，不反自反；反对称，不是对称；不传递

7、自反，不反自反；反对称，不是对称；不传递. 11 自反性证明自反性证明 证明模式证明模式 证明证明R在在A上自反上自反 任取任取x, x A . R 前提前提 推理过程推理过程 结论结论 例例4 证明若证明若 IA R ，则则 R在在A上自反上自反. 证证 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的上是自反的. 12 对称性证明对称性证明 证明模式证明模式 证明证明R在在A上对称上对称 任取任取 R . R 前提前提 推理过程推理过程 结论结论 例例5 证明若证明若 R=R 1 , 则则R在在A上对称上对称. 证证 任取任取 R R 1 R 因此因此 R 在在 A 上是

8、对称的上是对称的. 13 反对称性证明反对称性证明 证明模式证明模式 证明证明R在在A上反对称上反对称 任取任取 R R . x=y 前提前提 推理过程推理过程 结论结论 例例6 证明若证明若 RR 1 IA , 则则R在在A上反对称上反对称. 证证 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反对称的上是反对称的. 14 传递性证明传递性证明 证明模式证明模式 证明证明R在在A上传递上传递 任取任取， R R . R 前提前提 推理过程推理过程 结论结论 例例7 证明若证明若 R R R , 则则R在在A上传递上传递. 证证 任取任取， R R R R

9、R 因此因此 R 在在 A 上是传递的上是传递的. 15 运算与性质的关系运算与性质的关系 自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性 R1 1 R1R2 R1R2 R1 R2 R1 R2 16 4.4 关系的闭包关系的闭包 n闭包定义闭包定义 n闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示 n闭包的性质闭包的性质 17 闭包定义闭包定义 定义定义 设设R是非空集合是非空集合A上的关系上的关系, R的的自反（对自反（对 称称或或传递）闭包传递）闭包是是A上的关系上的关系R , 使得使得R 满足以满足以 下条件：下条件： （1）R 是自

10、反的（对称的或传递的）是自反的（对称的或传递的） （2）R R （3）对）对A上任何包含上任何包含R的自反（对称或传递）的自反（对称或传递） 关系关系 R 有有 RR . 一般将一般将 R 的自反闭包记作的自反闭包记作 r(R), 对称闭包记作对称闭包记作 s(R), 传递闭包记作传递闭包记作 t(R). 18 闭包的构造方法闭包的构造方法 定理定理1 设设R为为A上的关系上的关系, 则有则有 (1) r(R) = RR0 (2) s(R) = RR 1 (3) t(R) = RR2R3 说明：说明： 对于有穷集合对于有穷集合A (|A|=n) 上的关系上的关系, (3)中的并最多中的并最多

11、不超过不超过 Rn. 若若 R是自反的，则是自反的，则 r(R)=R; 若若R是对称的，则是对称的，则 s(R)=R; 若若R是传递的，则是传递的，则 t(R)=R. 19 设关系设关系R, r(R), s(R), t(R)的关系矩阵分别为的关系矩阵分别为M, Mr, Ms 和和 Mt , 则则 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和是和 M 同阶的单位矩阵同阶的单位矩阵, M是是 M 的转置矩阵的转置矩阵. 注意在上述等式中矩阵的元素相加时使用逻辑加注意在上述等式中矩阵的元素相加时使用逻辑加. 闭包的构造方法（续）闭包的构造方法（续） 20

12、 闭包的构造方法（续）闭包的构造方法（续） 设关系设关系R, r(R), s(R), t(R)的关系图分别记为的关系图分别记为G, Gr, Gs, Gt , 则则Gr, Gs, Gt 的顶点集与的顶点集与G 的顶点集相等的顶点集相等. 除了除了G 的边以外的边以外, 以下述方法添加新边：以下述方法添加新边： 考察考察G的每个顶点的每个顶点, 如果没有环就加上一个环，最如果没有环就加上一个环，最 终得到终得到Gr . 考察考察G的每条边的每条边, 如果有一条如果有一条 xi 到到 xj 的单的单 向边向边, ij, 则在则在G中加一条中加一条 xj 到到 xi 的反方向边，最终的反方向边，最终 得到得到Gs. 考察考察G的每个顶点的每个顶点 xi, 找从找从 xi 出发