离散数学 关系的性质.ppt

4.3 关系的性质 自反性 反自反性 对称性 反对称性 传递性 自反性与反自反性 实例 例1 A={1,2,3}, R1, R2, R3是A上的关系, 其中R1＝{1,1,2,2}R2＝{1,1,2,2,3,3,1,2}R3＝{1,3} 对称性与反对称性 实例 例2 设A＝{1,2,3}, R1, R2, R3和R4都是A上的关系, 其中 R1＝{1,1,2,2}， R2＝{1,1,1,2,2,1} R3＝{1,2,1,3}， R4＝{1,2,2,1,1,3} 传递性 实例 例3 设A＝{1,2,3}, R1, R2, R3是A上的关系, 其中 R1＝{1,1,2,2} R2＝{1,2,2,3} R3＝{1,3} 关系性质的充要条件 实例 自反性证明 对称性证明 反对称性证明 传递性证明 运算与性质的关系 4.4 关系的闭包 闭包定义 闭包的构造方法 集合表示 矩阵表示 图表示 闭包的性质 闭包定义 定义 设R是非空集合A上的关系, R的自反（对称或传递）闭包是A上的关系R?, 使得R?满足以下条件：（1）R?是自反的（对称的或传递的）（2）R?R?（3）对A上任何包含R的自反（对称或传递）关系 R?? 有 R??R??. 一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递闭包记作 t(R). 闭包的构造方法 （3）t(R)＝R∪R2∪R3∪… 先证R∪R2∪… ? t(R)成立，为此只需证明对任意 的正整数n有 Rn ? t(R)即可。用归纳法。 n＝1时，有 R1＝R ? t(R)。 假设Rn?t(R)成立，那么对任意的x,y有 x,y∈Rn+1＝Rn ? R ? ?t(x,t∈Rn∧t,y∈R) ? ?t(x,t∈t(R)∧t,y∈t(R)) ? x,y∈t(R) （因为t(R)是传递的） 这就证明了Rn+1 ? t(R)。 由归纳法命题得证。 再证t(R)?R∪R2∪…成立，为此只须证明R∪R2∪…是传递的。 任取x,y,y,z，则 y,z∈R∪R2∪… ∧ x,y∈R∪R2∪… ? ?t(y,z∈Rt) ∧ ?s(x,y∈Rs) ? ?t?s(y,z∈Rt ∧ x,y∈Rs) ? ?t?s(x,z∈Rt ? Rs) ? ?t?s(x,z∈Rt+s) ? x,z∈R∪R2∪… 从而证明了R∪R2∪…是传递的。 推论 设R为有穷集A上的关系，则存在正整数r 使得 t(R)=R∪R2∪…∪Rr 闭包的构造方法（续） 闭包的构造方法（续） 实例 R={a,b,b,a,b,c,c,d,d,b}, r(R) = R∪R0 ={a,b,b,a,b,c,c,d,d,b}∪{a,a,b,b,c,c,d,d} ={a,b,b,a,b,c,c,d,d,b,a,a,b,b,c,c,d,d} s(R)= R∪R?1 ={a,b,b,a,b,c,c,d,d,b}∪{b,a,a,b,c,b,d,c, b,d} } ={a,b,b,a,b,c,c,d,d,b ,c,b,d,c,b,d} t(R) = R1∪R2∪R3∪R4 ={a,b,b,a,b,c,c,d,d,b}∪{a,a,a,c,b,b,b,d, c,b,d,a,d,c}∪{a,b,a,d,b,a,b,b,b,c,c,a, c,c,d,b,d,d} ∪{a,a,a,b,a,c,,b,a,b,b,b,c, b,d,c,b,c,d,d,a,d,b,d,c} ={a,a,a,b,a,c,a,d,b,a,b,b,b,c,b,d,c,a, c,b,c,c,c,d,d,a,d,b,d,c,d,d} M r= Ms= Mt= 定理7.11 设R是非空集合A上的关系， 则 （1）R是自反的当且仅当r(R)＝R。 （2）R是对称的当且仅当s(R)＝R。 （3）R是传递的当且仅当t(R)＝R。 * * 若x,y∈R y,z∈R，则x,z∈R), 若x,y∈R且x ? y ,则y,x ?R 若 x,y∈R有y,x∈R), ?x∈A,有x,x?R, ?x∈A,有x,x?R), 定义 如果顶点 xi 连通到xk , 则从 xi到 xk 有边 如果两点之间有边, 是一条有向边(无双向边) 如果两个顶点之间有边, 是一对方向相反的边(无单边) 每个顶点都没有环 每个顶点都有 环 关系图 对M2中1所在位置, M中相应位置都是1 若rij＝1, 且 i≠j, 则rji＝0 矩阵是对称矩阵 主对角线元素全是0 主对角线元素 全是1 关系 矩阵 R?R?R R∩R?1? IA R=R?1 R∩