离散数学--4.3关系的性质.ppt

4.3 关系的性质 4.3.1关系性质的定义和判别 自反性与反自反性 对称性与反对称性 传递性 4.3.2 关系的闭包 闭包定义 闭包计算 Warshall算法 自反性与反自反性 对称性与反对称性 传递性 关系性质的充要条件 自反性证明 对称性证明 反对称性证明 传递性证明 关系性质判别 实例 运算与性质的关系 闭包定义 定义4.17 设R是非空集合A上的关系, R 的自反 (对称或传 递) 闭包 是A上的关系R?, 使得 R?满足以下条件： (1) R?是自反的（对称的或传递的） (2) R ?R? (3) 对A上任何包含R 的自反（对称或传递）关系R?? 有 R??R??. 一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递 闭包记作 t(R). 闭包的构造方法 定理4.7的证明 只证 (1) 和 (3) 证 r(R)=R∪R0 只需证明R∪R0 满足闭包定义. R∪R0包含了R 由IA?R∪R0可知 R∪R0 在 A上是自反的. 下面证明R∪R0是包含R 的最小的自反关系. 假设R?是包含R 的自反关系，那么IA?R?, R?R?， 因此有 R∪R0=IA?R ?R? 定理4.7的证明（续） 任取x,y和y,z x,y?R∪R2∪R3∪…. ? y,z?R∪R2∪R3∪…. ? x,z?R∪R2∪R3∪…. 于是，由R∪R2∪R3∪….的传递性得 t(R) ?R∪R2∪R3∪… 对n 进行归纳证明 Rn ?t(R). n=1时显然为真. 假设n=k时为真，那么对于任意x,y x,y?Rk+1? x,y?Rk°R ??t (x,t?Rk ?t,y?R) ??t (x,t?t(R)?t,y?t(R)) ?x,y?t(R) （t(R)传递） 于是， R∪R2∪R3∪… ? t(R) 闭包的构造方法（续） 闭包的构造方法（续） 实例 传递闭包的计算——Warshall算法 算法思路： 考虑 n+1个矩阵的序列M0, M1, …, Mn, 将矩阵 Mk 的 i 行 j 列的元素记作Mk[i,j]. 对于k=0,1,…,n, Mk[i,j]=1当且仅当在 R 的关系图中存在一条从 xi 到 xj 的路径，并且这条路径 除端点外中间只经过{x1, x2, …, xk}中的顶点. 不难证明M0 就是R 的关系矩阵，而 Mn 就对应了R 的传递闭包. Warshall算法： 从M0开始，顺序计算 M1, M2, …, 直到 Mn 为止. Warshall算法的依据 Warshall算法及其效率 算法4.1 Warshall算法 输入：M （R 的关系矩阵） 输出：Mt （t(R)的关系矩阵） 1. Mt?M 2. for k?1 to n do 3. for i?1 to n do 4. for j?1 to n do 5. Mt[i, j] ?Mt[i, j] + Mt[i, k]?Mt[k, j] * 定义4.14 设R为A上的关系,? (1) 若?x(x∈A→x,x?R), 则称R在A上是自反的. (2) 若?x(x∈A→x,x?R), 则称R在A上是反自反的. 自反：A上的全域关系EA, 恒等关系IA, 小于等于关系LA, 整除关系DA 反自反：实数集上的小于关系、幂集上的真包含关系. R2自反, R3 反自反, R1既不自反也不反自反. 例1 A = {a, b, c}, R1, R2, R3 是 A上的关系, 其中 R1 = {a,a,b,b} R2 = {a,a,b,b,c,c,a,b} R3 = {a,c} 例2 设A＝{a,b,c}, R1, R2, R3和R4都是A上的关系, 其中  R1＝{a,a,b,b}， R2＝{a,a,a,b,b,a} R3＝{a,b,a,c}， R4＝{a,b,b,a,a,c} 定义4.15 设R为A上的关系,?(1) 若?x?y(x,y∈A∧x,y∈R→y,x∈R), 则称R为A上 对称的关系.(2) 若?x?y(x,y∈A∧x,y∈R∧y,x∈R→x=y), 则称R 为A上的反对称关系.实例 对称：A上的全域关系EA, 恒等关系IA和空关系? 反对称：恒等关系IA，空关系是A上的反对称关系 R1 对称、反对称. R2 对称，不反对称. R3 反对称，不对称. R4 不对称、也不反对称 例3 设A