[2018年最新整理]04-关系的性质与闭包.ppt

关系的性质与闭包 离散数学 第4讲 上一讲内容的回顾 集合的笛卡尔乘积 有序对-一种特殊的集合 笛卡尔乘 笛卡尔乘积的性质 二元关系的定 关系的运算 一般集合运算 与定义域或值域有关的运算 逆运算 复合运算(乘法) 二元关系的性质与闭包 关系的几类重要性质 自反 对称 传递 性质满足的充分必要条件 性质与运算之间的关系 闭包的定义与存在性 计算关系R的传递闭包的Warshall算法 自反性 集合A上的关系R: 自反：定义为：对所有的 a?A, (a,a)?R 反自反：定义为：对所有的a?A, (a,a)?R 设 A={1,2,3}, R?A?A {(1,1),(1,3),(2,2),(2,1),(3,3)} 是自反的 {(1,2),(2,3),(3,1)} 是反自反的 {(1,2),(2,2),(2,3),(3,1)} 既不是自反的，也不是反自反的 R 是 A 上的自反关系 iff. IA?R 自反关系的关系图和关系矩阵 对称性 集合A上的关系R： 对称的：定义为：若 (a,b)?R, 则 (b,a)?R 反对称的：定义为：若(a,b)?R 且(b,a)?R ，则a=b 强反对称的：定义为：若 (a,b)?R 则 (b,a)?R (注意：反对称和强反对称都不是对称的否定) 设 A={1,2,3}, R?A?A {(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)} 是对称的 {(1,2),(2,3),(2,2),(3,1)} 是反对称的 {(1,2),(2,3),(3,1)} 既是反对称的，也是强反对称的 {(1,1),(2,2)} 既是对称的，也是反对称的 ? 是对称关系，也是反对称关系，也是强反对称关系！ R 是集合A上的对称关系 iff. R-1=R 对称关系的关系图和关系矩阵 传递性 集合A上的关系R： 传递的：定义为：若 (a,b)?R, (b,c)?R, 则 (a,c) ?R 设 A={1,2,3}, R?A?A {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)} 传递的 {(1,2),(2,3),(3,1)} 是非传递的 Both {(1,3)}和 ? 均为传递关系 集合A上的关系R是传递关系 iff. Rn?R对所有n?1成立 传递关系的关系图和关系矩阵 一些常用关系的性质 正确理解自反关系 一个错误的命题及其“证明”: 如果R是集合A上的对称，传递关系，则R 是A上的自反关系 证明: 对任意的 a,b?A, 若 (a,b)?R, 根据R 的对称性 (b,a)?R; 又根据R的传递性, (a,a)?R. 所以：R 是自反关系 逆关系运算对关系性质的保持 自反性: ?x, (x,x)?R1 ? (x,x)? R1-1 反自反性: ?x, (x,x)? R1 ? (x,x)? R1-1 对称性: ?x,y, if (x,y)? R1-1, then (y,x)? R1, since R1 is symmetric，(x,y)? R1, ∴(y,x)? R1-1 强反对称性: ?x,y, if (x,y)?R1-1, (y,x)?R1-1, then (y,x)?R1, (x,y)?R1, since R1 is antisymmetric，x=y. 传递性: ?x,y,z, if (x,y)?R1-1, (y,z)?R1-1, then (y,x)?R1, (z,y)?R1, since R1 is transitive，(z,x)? R1, ∴(x,z)?R1-1 关系的交运算对运算性质的保持 自反: ?x, ∵(x,x)? R1, (x,x)?R2, ∴(x,x)?R1?R2 反自反: supposing ?x, (x,x)?R1?R2, then (x,x)?R1, (x,x)?R2, contradiction. 对称: ?x,y, (x,y)?R1?R2 ? (x,y)?R1, (x,y)?R2，since R1 and R2 are symmetric，(y,x)?R1, (y,x)?R2, ∴(y,x)?R1?R2. 反对称: ?x,y, supposing (x,y)?R1?R2, (y,x)?R1?R2, then (x,y), (y,x)?R1, and (x,y), (y,x)?R2, since R1 and R2 are both asymmetric，x=y 传递:?x,y,z, if (x,y)?R1?R2, (y,z)?R1?R2, then (x,y), (y,z)?R1,and (x,y),(y,z)?R2, since R1and R2 are both transitive, (x,z)?R