十一月8号离散数学.pptVIP

第4章 二元关系与函数 4.4 关系的闭包 4.5 等价关系和偏序关系 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). 闭包的构造方法1.集合并运算 定理1 设R为A上的关系, 则有 (1) r(R) = R∪R0(2) s(R) = R∪R1(3) t(R) = R∪R2∪R3∪…说明： 对于有穷集合A (|A|=n) 上的关系, (3)中的并最多 不超过 Rn. 性质 设关系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 的转置矩阵. 注意在上述等式中矩阵的元素相加时使用逻辑加. 闭包的构造方法（续）2.利用关系矩阵 闭包的构造方法（续） 设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt , 则Gr, Gs, Gt 的顶点集与G 的顶点集相等. 除了G 的边以外, 以下述方法添加新边：  考察G的每个顶点, 如果没有环就加上一个环，最终得到Gr . 考察G的每条边, 如果有一条 xi 到 xj 的单向边, i≠j, 则在G中加一条 xj 到 xi 的反方向边，最终得到Gs. 考察G的每个顶点 xi, 找从 xi 出发的每一条路径，如果从 xi 到路径中任何结点 xj 没有边，就加上这条边. 当检查完所有的顶点后就得到图Gt . 闭包的构造方法（续）3.利用关系图 [解法三] 利用关系矩阵(略)。 4.5 等价关系与偏序关系 等价关系的定义与实例 等价类及其性质 商集与集合的划分 等价关系与划分的一一对应 偏序关系 偏序集与哈斯图 偏序集中的特定元素 等价关系的定义 定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系. 设 R 是一个等价关系, 若x,y∈R, 称 x 等价于y, 记做 x～y.  等价关系的验证 验证模 3 相等关系 R 为 A上的等价关系, 因为自反性 x∈A, 有x ≡ x(mod 3)对称性 x, y∈A, 若 x ≡ y(mod 3), 则有 y ≡ x(mod 3)传递性 x, y, z∈A, 若x ≡ y(mod 3), y ≡ z(mod 3), 则有 x≡z(mod 3) 实例 设 A={1,2,…,8}, 如下定义A上的关系 R： R = { x,y | x,y∈A∧x≡y(mod 3) }其中 x≡y(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. A上模3等价关系的关系图 设 A={1,2,…,8},  R={ x,y| x,y∈A∧x≡y(mod 3) } 已知 只要证 是等价关系， 是自反的，要证 是对称的和传递的即可。 等价类 定义 设R为非空集合A上的等价关系, x∈A，令[x]R = { y | y∈A∧xRy } 称 [x]R 为 x 关于R 的等价类, 简称为 x 的等价类, 简 记为[x]. 实例 A={ 1, 2, … , 8 }上模 3 等价关系的等价类： [1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6} 等价类的性质 实例 A={ 1, 2, … , 8 }上模 3 等价关系的等价类： [1]=[4]=[7]={1,4,7}， [2]=[5]=[8]={2,5,8}， [3]=[6]={3,6} 以上3 类两两不交， {1,4,7}{2,5,8}{3,6} = {1,2, … ,8} 商集 定义 设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = { [x]R | x∈A } 实例 A={1,2,…,8},A关于模