交大数理逻辑课件10-3关系.ppt

第10章关系 10 1二元关系10 2关系矩阵和关系图10 3关系的逆 合成 限制和象10 4关系的性质10 5关系的闭包10 6等价关系和划分10 7相容关系和覆盖10 8偏序关系 关系性质的充要条件 设R为A上的二元关系 则R在A上自反当且仅当IA RR在A上反自反当且仅当R IA R在A上对称当且仅当R R 1R在A上反对称当且仅当R R 1 IAR在A上传递当且仅当R R R 证 必要性 R是传递 R R R R R z x z R z y R R R R R充分性 R R R R是传递 x z R z y R R R R R是传递的 R是传递的 R R R 10 5 2关系闭包的定义 闭包的定义包含R的最小自反关系是R的自反闭包包含R的最小对称关系是R的对称闭包包含R的最小传递关系是R的传递闭包一般地 将R的自反闭包记作r R 对称闭包记作s R 传递闭包记作t R 10 5 3闭包的性质 定理10 5 4对非空集合A上的关系R 有若R是自反的 r R R 若R是对称的 s R R 若R是传递的 t R R 定理10 5 5对非空集合A上的关系R1 R2 若R1 R2则r R1 r R2 s R1 s R2 t R1 t R2 定理10 5 5对非空集合A上的关系R1 R2 则r R1 r R1 r R1 R2 s R1 r R1 s R1 R2 t R1 r R1 t R1 R2 10 5 4闭包的构造方法 设R为A上的关系 则有定理10 5 7 r R R R0 R IA定理10 5 8 s R R R 1定理10 5 9 t R R R2 R3 定理10 5 10 设A为非空集合 A n 则存在一个正整数k n 使得t R R R2 R3 Rk k n t R R R2 R3 Rn以上分别是自反闭包r R 对称闭包s R 和传递闭包t R 的构造方法 证明 t R R R2 R3 先证R R2 R3 t R 当n 1时 R1 R t R 设n k时 Rk t R 下证Rk 1 t R x y Rk 1 x y Rk R z x z R z y Rk z x z t R z y t R x y t R 即Rk 1 t R k 0 故R R2 R3 t R 证明 t R R R2 R3 再证t R R R2 R3 显然R R R2 R3 下证明R R2 R3 是传递的 x z R R2 R3 z y R R2 R3 t x z Rt s z y Rs s t 0的自然数 x y Rt Rs Rt s R R2 R3 x y R R2 R3 根据传递关系的定义 有R R2 R3 是传递的 闭包的构造方法举例 设A a b c 定义A上的二元关系R为 R a b b c c a 试用关系合成运算方法求 r R s R t R 解 r R R IA a b b c c a a a b b c c s R R R 1 a b b c c a b a c b a c t R R R2 R3 R2 R R a c b a c b R3 R2 R a a b b c c IAt R a a a b a c b a b b b c c a c b c c EA 闭包的构造方法 矩阵法 设关系R r R s R t R 的关系矩阵分别为M Mr Ms和Mt 则Mr M IMs M M Mt M M2 M3 说明 I是和M同阶的单位矩阵 M 是M的转置矩阵 注意 在上述等式中矩阵的元素相加时使用逻辑加 闭包的矩阵构造方法举例 设A a b c 定义A上的二元关系R为 R a b b c c a 试求 t R 解 用关系矩阵求t R 的方法如下 闭包的矩阵构造方法举例 其中 表示矩阵的对应元素进行逻辑加运算 闭包同时具有的多种性质 定理10 5 11对非空集合A上的关系R 有若R是自反的 s R t R 是自反的 若R是对称的 r R t R 是对称的 若R是传递的 r R 是传递的 证 R是传递 R R R 而r R R IAr R r R R IA R IA R R IA IA R IA R R R IA IA R IA R R R IA R IA r R 注意 若R是传递的 s R 是不一定是传递的 如 A 1 2 3 R 是传递的r R R IA 是传递的但s R R R 1 不是传递 闭包同时具有的多种性质 定理10 5 12对非空集合A上的关系R 有rs R sr R rt R tr R st R ts R 设A 1 2 R st R s t R s ts R t s R t 10 6等价关系和划分 等价关系是最重要 最常见的二元关系之一 它有良好的性质 在计算机科学和计算机技术 信息科学和信息工程中都有广泛的应用 定义设R为非空集合上的关系 如果R是自反的 对称的和传递的 则称R为A上的等价关系 等价关系的关系矩阵和关系图的特点关系矩阵的主对角线全为1且是对称阵 关系图每一个结点上都有自回路且每两个结点间如果有边 一定有方向相反的两条边 等价关系的实例 设A 1 2 3 4 5 R是A上的等价关系 R 1 1 1 2 2 1 2 2 3 3 3 4 4 3 4 4 5 5 则R的关系矩阵M R 如下 A上的等价矩阵可用正方形的一条对角线和线上的若干正方形表示 M R 的主对角线全为1且是对称阵 所以R是自反的和对称的 还可以用二元关系传递性的定义证明R是传递的 故R是A上的等价关系 等价关系的实例 设A 1 2 3 4 5 6 7 8 A上的关系R如下定义 R x y A x y mod3 其中x y mod3 叫做x与y模3相等 即x除以3的余数与y除以3的余数相等 验证模3相等关系R为A上的等价关系 x A x x 3 0 所以x x mod3 R是自反的 x y A 若x y mod3 x y 3 t t Z y x 3 t t Z y x mod3 R是对称的 x y z A 若x y mod3 y z mod3 x y 3 t1 t1 Z y z 3 t2 t2 Z x z x y y z 3 t1 3 t2 3 t1 t2 t1 t2 Z x z mod3 R是传递的 A上模3等价关系的关系图 设A 1 2 3 4 5 6 7 8 R x y A x y mod3 1 mod3 4 mod3 7 mod3 12 mod3 5 mod3 8 mod3 23 mod3 6 mod3 0 等价类 定义设R为非空集合A上的等价关系 x A 令 x R y y A xRy 称 x R为x关于R的等价类 简记为 x 实例A 1 2 3 4 5 6 7 8 上模3等价关系的等价类 1 R 4 R 7 R 1 4 7 2 R 5 R 8 R 2 5 8 3 R 6 R 3 6 等价类的性质 定理10 6 1设R是非空集合A上的等价关系 对 x y A 下面的结论成立 1 x R 且 x R A 2 若 R 则 x R y R 3 若 R 则 x R y R 4 任何等价类都是A的非空子集 A中任取两个元素 它们的等价类或相等 或是不相交 所有等价类的并集就是A A中任取两个元素 它们的等价类或相等 或是不相交 等价类的性质举例 实例 A 1 2 8 上模3等价关系的等价类 1 4 7 1 4 7 2 5 8 2 5 8 3 6 3 6 1 2 1 3 2 3 1 4 7 2 5 8 3 6 A 商集 定义设R为非空集合A上的等价关系 以R的所有不交的等价类作为元素的集合 称为A在R下的商集 记做A R A R x R x A 实例A 1 2 3 4 5 6 7 8 A关于模3等价关系R的商集为A R 1 4 7 2 5 8 3 6 0 1 2 A关于恒等关系IA商集为 A IA 1 2 8 x x A A关于全域关系EA的商集为 A EA 1 2 8 A 10 6 2集合的划分 定义设A为非空集合 若存在集合 满足下面条件 1 x x x A 即 P A 2 3 A 4 x y x y x y x y 满足条件 1 2 3 称 是A的覆盖 满足全部条件称 为A的一个划分 称 中的元素为A的划分块 如 A关于模3等价关系R的商集是A的一个划分A R 1 4 7 2 5 8 3 6 1 4 7 1 2 5 8 3 5 6 为A的一个覆盖 商集和划分的关系 定理10 6 2对非空集合A上的一个等价关系R A商集A R就是A的一个划分 它称为由等价关系R诱导出来的A的划分 记作 R即由A上的等价关系R可以诱导出A的一个划分 定理10 6 3对非空集合A上的一个划分 令A上的关系R 为R z z x z y z 则R 是A上的等价关系 它称为划分 诱导出来的A上的等价关系 定理10 6 4对非空集合A上的一个划分 和A上的等价关系R 诱导R当且仅当R诱导 所以 集合A上的等价关系与集合A的划分是一一对应的 由划分导出等价关系的方法 定理设S S1 S2 Sm 是A的一个划分 R x y x和y在同一个划分块中 则R是A上的等价关系 划分S导出的等价关系R可以表示为 R S1 S1 S2 S2 Sm Sm 例 设A 1 2 3 4 A的划分S 1 2 3 4 则从S导出的等价关系R为 R 1 1 2 2 2 3 3 2 3 3 4 4 1 1 2 3 2 3 4 4 可以验证R是A上的等价关系 设A 1 2 3 求出A上所有的等价关系 解 先写出集合X上的所有划分 它们是 1 2 3 1 2 1 3 2 3 1 2 3 4 1 2 3 5 1 2 3 设A 1 2 3 求出A上所有的等价关系 对应的等价关系为 R1 2 3 2 3 1 1 2 2 2 3 3 2 3 3 1 1 R2 1 3 1 3 2 2 1 1 1 3 3 1 3 3 2 2 R3 1 2 1 2 3 3 1 1 1 2 2 1 2 2 3 3 R4 1 2 3 1 2 3 A A EAR5 1 1 2 2 3 3 1 1 2 2 3 3 IA 1 2 3 1 2 1 3 2 3 1 2 3 4 1 2 3 5 1 2 3 由等价关系求划分的实例 例设A 1 2 3 4 在A上定义二元关系R R x y u v 求R导出的划分 解 根据的x y 2 3 4 5 6 7 8将A A划分成7个等价类 A A R 10 7相容关系和覆盖 定义对非空集合A上的关系R 如果R是自反的和对称的 则称R为A上的相容关系 相容关系的性质所有等价关系都是相容关系 相容关系的关系矩阵主对角线全为1且是对称阵 相容关系的关系图每一个结点上都有自回路且每两个结点间如果有边 一定有方向相反的两条边 相容关系举例 设A 316 347 204 678 770 A上的二元关系R定义为R x y x A y A x和y有相同数码 x A 有 R R是自反的 R 有 R R是对称的 于是 R是相容关系 令a 316 b 347 c 204 d 678 e 770R a a a b a d b a b b b c b d b e c b c c c e d a d b d d d e e b e c e d e e 相容类 定义对非空集合A上的相容关系 若C A 对 a b C 有 a b R 则称C是由相容关系R产生的相容类 相容类的性质相容类C A x A x 是由相容关系R产生的一个相容类 上例中 a a b b c 都是R产生的相容类 a b d b c e 和 b d e 也是R产生的相容类 最大相容类 定义对非空集合A是上的相容关系R 一个相容类若不是任何相容类的真子集 就称为最大相容类 记为CR 最大相容类CR的性质 x y x CR y CR xRy CR中任意元素x与y都有相容关系R x x A CR y y CR xRy A CR中没有一个元素与CR中的所有元素都有相容的关系R 最大相容类 最大相容类简化关系图的特点 最大完全多边形的顶点构成的集合是最大相容类 孤立点构成的集合是最大相容类 如果一条边不是任何完全多边形的边 则它的两个端点构成的集合是最大相容类例如右图 最大完全3边形的顶点构成的集合 2 3 5 和 2 3 4 孤立点构成的集合 6 不是任何完全多边形的边的两个端点构成的集合 1 5 最大相容类的存在性 定理10 7 1设R是有限集合A上的相容关系 C是R产生的相容类 那么必存在最大相容类CR 使得C CR 证明 设A a1 a2 an 令C0 C 如下构造相容类序列 C0 C1 C2 Ci 1 Ci aj 其中 j是使aj Ci且aj与Ci的每一个元素都有相容关系R的最小下标 因为 A n 所以至多经过n C 步 可结束此过程 序列的最后一个集合就是要求的最大相容类CR 作业12 P190 24P190 27 1 P191 30P191 33