离散数学-关系-3.pdf

定义3 9 1设A是非空集合 S1 S2 Sm Si i 1 m 且满足 Si Si A S1 S2 Sm A 则称 是A的一个覆盖 定义3 9 2设A是非空集合 S1 S2 Sm Si i 1 m 是A的一个覆盖 满足Si Sj i j 则称 是A的一个划分 称Si i 1 m 是A的划分块 定义中的 Si Sj i j 是指 中的元素两两互不相 交 3 9 集合的覆盖与划分 例设 A a b c 以下是A的子集构成的集合 S a b b c Q a a b a c D a b c G a b c E a b c F a a c 试确定哪些集合是A的覆盖 哪些集合是A的划分 哪些集 合既不是覆盖 也不是划分 解 S和Q是A的覆盖 但不是划分 D G和E是A的覆盖 也是 划分 F不是A的覆盖 也不是划分 集合G a b c 是单元素集 它有一个元素 a b c 对单 元素集 a b c 认为它的元素的并集就是 a b c 同时 也认为它的元素是两两互不相交的 所以集合G a b c 是A的划分 3 9 集合的覆盖与划分 在A的所有划分中基数最大的划分叫做A的最大划分 基数最小的划分 叫做A的最小划分 在上例中 E是A的最大划分 G是A的最小划分 例 设A 1 2 3 试确定A的所有划分 解 有一个划分块的划分是 1 2 3 有两个划分块的划分是 1 2 3 2 1 3 3 1 2 有三个划分块的划分是 1 2 3 下图是A的所有划分的示意图 a 表示有一个划分块的划分 1 2 3 b c 和 d 表示有两个划分块的划分 1 2 3 2 1 3 和 3 1 2 e 表示有三个划分块的划分 1 2 3 3 9 集合的覆盖与划分 定理3 9 1 设A A1 A2 Ar 与B B1 B2 Bs 是C的两种 划分 则集合 X Ai Bj i 1 r j 1 s Ai Bj 也是C的划分 证明 先证 Ai Bj C 由A B是C的划分知 Ai C Bj C 所以Ai Bj C 3 9 集合的覆盖与划分 再证 A1 B1 A1 B2 A1 Bs A2 B1 A2 B2 A2 Bs Ar B1 Ar B2 Ar Bs A1 B1 B2 Bs Ar B1 B2 Bs A1 A2 Ar B1 B2 Bs C C C CBA r i s j ji 11 3 9 集合的覆盖与划分 最后证X中的元素是两两互不相交的 在X中取任意两个不同元素 Ai Bh与Aj Bk 分三 种情况讨论 设 i j h k Ai Bh Aj Bk Ai Aj Bh Bk Bh Bk 设 i j h k Ai Bh Aj Bk Ai Aj Bh Bk 设 i j h k Ai Bh Aj Bk Ai Aj Bh Bk Ai Aj 3 9 集合的覆盖与划分 定义3 9 3 定理3 9 1中定义的集合X叫做原来两种 划分A和B的交叉划分 定义3 9 4 设A A1 A2 Ar 与B B B2 Bs 是 C的两种划分 如果 Ai A Bk B 使得 Ai Bk 则称A是B的加细 也称A是B的细分 3 9 集合的覆盖与划分 3 9 集合的覆盖与划分 定理3 9 2 任何两种划分的交叉划分都是原来两 种划分的一种加细 证明 设A A1 A2 Ar 与B B1 B2 Bs 是C的 两种划分 X Ai Bj i 1 r j 1 s Ai Bj 是A和B的交叉划分 因为Ai Bj Ai Ai Bj Bj 所以X是A的一种加 细 也是B的一种加细 等价关系是最重要 最常见的二元关系之一 它有良好 的性质 在计算机科学和计算机技术 信息科学和信息 工程中都有广泛的应用 目前对等价关系的研究是深入 而完备的 本节介绍等价关系的主要结论 定义3 10 1 设R X X 如果R是自反的 对称的和传递 的 则称R是X上的等价关系 设R是等价关系 若 R 称x等价于y 因为等价关系是自反的和对称的 所以等价关系的关系 矩阵主对角线全为1且是对称阵 其关系图每一个结点 上都有自回路且每两个结点间如果有边 一定有方向相 反的两条边 3 10 等价关系与等价类 例 设A 1 2 3 4 5 R是A上的二元关系 R 证明R是A上的等价关系 证明 写出R的关系矩阵MR如下 10000 01100 01100 00011 00011 R M MR的主对角线全为1且是 对称阵 所以R是自反的和对 称的 还可以用二元关系传 递性的定义证明R是传递的 故R是A上的等价关系 3 10 等价关系与等价类 从图中不难看出 等价关系R 的关系图被分为三个互不连通的 部分 每部分中的结点两两都有 关系 不同部分中的任意两个结 点则没有关系 3 10 等价关系与等价类 也可以用关系图说明R是等价关系 图是R的关系图 在R 的关系图中每一个结点上都有自回路 每两个结点间如果有 边 一定有方向相反的两条边 所以R是自反的和对称的 与前面一样 也可以用二元关系传递性的定义证明R是传递 的 故R是A上的等价关系 设x和y是两个整数 k是一个正整数 若x y用k除的余 数相等 就称x和y模k同余 也称x和y模k的的等价 记 为 x y mod k 设x y 用k除的商为t1 t2 余数为a1 a2 数学上将x y 表示成为 x k t1 a1 t1 I a1 I且0 a1 k y k t2 a2 t2 I a2 I且0 a2 k 若x y用k除的余数相等 x y k t1 t2 t1 t2 I 即x y可以被k整除 所以 x和y模k同余还可以描述 为 x y可以被k整除 3 10 等价关系与等价类 例设R x I y I x y mod k 是整数集合I上的二元关 系 证明R是等价关系 证明 设a b c是任意的整数 因为 a a k 0 所以 a a mod k R 故R是自反的 若 R a b mod k a b k t t I b a a b k t t I b a mod k R 故R是对称的 若 R且 R a b k t1 t1 I b c k t2 t2 I a c a b b c k t1 k t2 k t1 t2 t1 t2 I R 故R是传递的 所以R是整数集合I上的等价关系 3 10 等价关系与等价类 定义3 10 2 设R是X上的等价关系 x X 集合 y y X xRy 叫做x形成的R等价类 记为 x R 在上例中 等价关系R等价类为 1 R 2 R 1 2 3 R 4 R 3 4 5 R 5 在R的关系图中 三个互不连通的部分 每一部分中的所有结 点构成一个等价类 模3等价关系的等价类叫模3等价类 模3等价类有以下三个 0 R 6 3 0 3 6 1 R 5 2 1 4 7 2 R 4 1 2 5 8 3 10 等价关系与等价类 3 10 等价关系与等价类 定理3 10 1 设 R是X上的等价关系 x X 则有 x R X x x R 定理证明留作练习 从定理4 5 1可以看出 等价关系的任何等价类是该等 价关系前域 或陪域 的子集 例如 模3等价类是整数 集合的子集 0 R I 1 R I 2 R I 从定理3 10 1还可以看出 任何等价类是非空集合 x 形成的R等价类 x R至少有一个元素x 例如 在模3等 价类中 0 0 R 1 1 R 2 2 R 定理3 10 2 设R是X上的等价关系 对于X的任意元素a和b aRb 的充分必要条件是 a R b R 证明 设aRb 下证 a R b R c a R aRc 由R的对称性有cRa 由条件aRb和R的传递性 得cRb 再根据R的对称性有bRc c b R 故 a R b R 类似地可以证明 b R a R 这就证明了 a R b R 设 a R b R 下证aRb 由定理4 5 1知a a R 因为 a R b R 所以a b R bRa 由R的对称性有aRb 3 10 等价关系与等价类 3 10 等价关系与等价类 定义3 10 3 设R是X上的等价关系 R的所有等价类组成的 集合 x R x X 叫做X关于R的商集 记为X R 在例4 19中 等价关系R 有三个等价类 1 R 2 R 1 2 3 R 4 R 3 4 5 R 5 A关于 R的商集 A R 1 R 2 R 5 R 1 2 3 4 5 模3等价关系R的等价类有以下三个 0 R 1 R和 2 R 由它确定的整数集合I关于R的商集I R 0 R 1 R 2 R 定理3 10 3 设 R是X上的等价关系 X关于R的商集X R是X 的一个划分 证明 由定理4 5 1知 x R X且 x R 证明 X 因为 x R X 所以 X 另一方面 x X 由定理4 5 1知 x x R x 所以 X 故 X Xx R x Xx R x Xx R x Xx R x Xx R x Xx R x 3 10 等价关系与等价类 证明商集X R中的元素是两两互不相交的 设 a R b R 证明 a R b R 假定 a R b R c a R b R c a R c b R aRc bRc aRc cRb 因为R是对称的 aRb 因为R是传递的 a R b R 定理4 5 2 与假定矛盾 所以 a R b R 3 10 等价关系与等价类 定理3 10 4 设S S1 S2 Sm 是X的一个划分 R x和y在同一个划分块中 则R是X上的等价关系 证明 设x X S1 S2 Sm 因为S是X的一个划分 所 以存在惟一的划分块Sj S 使x Sj 于是有 R 即 R是自反的 设 R x和y在某个划分块Sj中 则y和x也在划分 块Sj中 所以 R 即R是对称的 设 R R x和y在Si中且y和z在Sj中 y Si Sj 因为S是X的一个划分 其中元素两两互不相 交 故必有Si Sj x和z在Sj中 R 即R是传递的 3 10 等价关系与等价类 将定理3 10 4中的等价关系R叫做划分S导出的等价关 系 划分S导出的等价关系R也可以表示为 R S1 S1 S2 S2 Sm Sm 例 设X 1 2 3 4 X的划分S 1 2 3 4 试写 出S导出的等价关系R 解 R 1 1 2 3 2 3 4 4 可以验证R是X上的等价关系 3 10 等价关系与等价类 定理3 10 5 设R S集合X上的等价关系 则R S 当且仅当 X R X S 证明 设R S 证明X R X S 先证 x X x R x S a x R xRa xSa a x S 所以 x R x S 类似地可以证明 x S x R 这就证明了 x R x S 再证 X R X S x R X R x R x S X S 即 x R X S 所以X R X S 类似地可以证明X S X R 于是X R X S 设X R X S 证明R S 因为X R X S a R X R 必存在 c S X S 使 a R c S R aRb b a R b a R a a R b c S a c S cSb cSa bSc cSa bSa aSb S 所以R S 类似地可以证明S R 于是R S 3 10 等价关系与等价类 例 设X 1 2 3 写出集合X上的所有等价关系 解 先写出集合X上的所有划分 它们是 S1 1 2 3 S2 1 2 3 S3 1 3 2 S4 2 3 1 S5 1 2 3 对应的等价关系为 R1 1 2 3 1 2 3 X X R2 1 2 1 2 3 3 R3 1 3 1 3 2 2 R4 2 3 2 3 1 1 R5 1 1 2 2 3 3 IX 3 10 等价关系与等价类 定义3 11 1 设R X X 如果R是自反的和对称的 则称R 是X上的相容关系 根据定义3 11 1 相容关系有以下三个性质 所有等价关系都是相容关系 相容关系的关系矩阵主对角线全为1且是对称阵 相容关系的关系图每一个结点上都有自回路且每两 个结点间如果有边 一定有方向相反的两条边 3 11 相容关系 例1设A 316 347 204 678 770 A上的二元关系R定义为 R x A y A x和y有相同数码 证明R是A上的相容关系 写出关系矩阵和关系图 用关系矩阵和 关系图验证R是A上的相容关系 证明 1 集合A中的每个数自己和自己有相同数码 故R是自反的 对于集合A中任意x和y 如果x和y有相同数码 则y和x也有相同数 码 故R是对称的 于是 R是相容关系 令a 316 b 347 c 204 d 678 e 770 用列举法将R表示为 R IA 3 11 相容关系 11110 11011 10110 11111 01011 R M 2 R的关系矩阵MR主对角线全为1且是对称阵 说明R是相容关系 3 R的关系图如右图所示 在关系图中 每一个结点上都有自回路 且每两个结点间如果有边 一定有方向相反的两条边 表明了R是相 容关系 3 11 相容关系 因为相容关系的关系图每 一个结点上都有自回路且每两 个结点间如果有边 一定有方 向相反的两条边 所以可省去 每一个结点上的自回路 将两 个结点间方向相反的两条有向 边改为一条无向边 得到一个 简化图 此图叫做R的简化关 系图 例1中的相容关系R的简 化关系图如图所示 3 11 相容关系 定义3 11 2设R是X上相容的关系 C X 如果 a b C 有 R 则称C是由相容关系R产生的相容类 如果R是X上的相容关系 C是由相容关系R产生的相容类 从定义可 以看出 相容类C一定是X的子集 x X 因为相容关系R是自反的 R 所以 x 是由相 容关系R产生的一个相容类 即X中的任何元素组成的单元素集是由 相容关系R产生的一个相容类 在例1中 a a b b c b d e 都是R产生的相容类 a b d a b d 和 b c e b c e 也是R产生的相容类 但是 b d e 与任何非空集合的并集都不再是R产生的相容类 这种 相容类叫做最大相容类 3 11 相容关系 定义3 11 3 设R是X上的相容关系 C是R产生的相容类 如果它不是其 它任何相容类的真子集 则称C为最大相容类 记为CR 根据定义3 11 3 最大相容类CR具有如下的性质 CR中任意元素x与CR中的所有元素都有相容关系R X CR中没有一个元素与CR中的所有元素都有相容的关系R 性质 的意思是 CR是R产生的相容类 即最大相容类首先是相容 类 性质 的意思是 CR是最大相容类 利用相容关系的简化关系图可以求最大相容类 方法如下 最大完全多边形的顶点构成的集合是最大相容类 孤立点构成的集合是最大相容类 如果一条边不是任何完全多边形的边 则它的两个端点构成 的集合是最大相容类 3 11 相容关系 例2 设X 1 2 3 4 5 6 R是X上的相容关系 它的简化关系图 如图所示 试找出所有最大相容类 解 最大完全3边形的顶点构成的集合 2 3 5 和 2 3 4 孤立点构成的集合 6 不是任何完全多边形的边的两个端点 构成的集合 1 5 所以 最大相容类为 2 3 5 2 3 4 1 5 和 6 3 11 相容关系 定理3 11 1 设R是有限集合X上的相容关系 C是R产生的 相容类 那么必存在最大相容类CR 使得 C CR 证明 设X x1 x2 xn 令C0 C 如下构造相容类序列 C0 C1 C2 Ci 1 Ci xj 其中 j是使 xj Ci且xj与Ci的每一个元素都有相容 关系R的x的最小下标 因为 X n 所以至多经过n C 步 可结束此过程 序列的最后一个集合就是要求的最大相容类CR 3 11 相容关系 定理3 11 2 设X是有限集合 R是X上的相容关系 由R产生的所有最大 相容类构成的集合是X的覆盖 证明 设R产生的所有最大相容类构成的集合为 C1 C2 Cn 由相容类的定义知 任何最大相容类Ci都是X的子集 证明X C1 C2 Cn 因为Cj X 所以 C1 C2 Cn X x X x 是相容类 根据定理3 11 1 必存在最大相容类Ci 使得 x Ci 而Ci C1 C2 Cn 所以x C1 C2 Cn 这就证明X C1 C2 Cn 故X C1 C2 Cn 3 11 相容关系 定义4 6 4 设R是X上的相容关系 S CR CR是由R产生的最大 相容类 叫做集合X的完全覆盖 记为CR X 例3 在例2中最大相容类构成的集合为 2 3 5 2 3 4 1 5 6 它是集合X 1 2 3 4 5 6 的一个完全覆盖 根据相容关系和相容类的定义 X中的任何元素组成的单 元素集是由相容关系R产生的一个相容类 所以 1 2 3 4 5 6 都是相容类 集合 1 2 3 4 5 6 是X的覆盖 即某些相容类构成集合也是X的覆盖 所以由相容关系R产生的相容类构成的X的覆盖并不惟 一 但是一个相容关系只对应惟一的一个完全覆盖 3 11 相容关系 定理3 11 3 设S S1 S2 Sm 是X的一个覆盖 则 R S1 S1 S2 S2 Sm Sm 是X上的相容关系 证明 x X 因为S是X的一个覆盖 存在Si S 使x Si 于是有 Si Si S1 S1 S2 S2 Sm Sm R 即 R 所以R是自反的 设 R S1 S1 S2 S2 Sm Sm Si Si Si Si 而 Si Si S1 S1 S2 S2 Sm Sm R 即 R 所以R是对称的 将定理3 11 3中的R叫做覆盖S导出的相容关系 3 11 相容关系 例 设X 1 2 3 4 S1 1 2 3 3 4 S2 1 2 2 3 1 3 3 4 是X的两个覆盖 试写出S1和S2导出的相容关系R1和R2 解 R1 1 2 3 1 2 3 3 4 3 4 R2 1 2 1 2 2 3 2 3 1 3 1 3 3 4 3 4 在例中 S1 S2 但是R1 R2 这说明不同的覆盖可以导出相同的相容 关系 定理3 11 4 集合X上的相容关系R与集合X的完全覆盖CR X 是一一对应 的 证明留作作业 3 11 相容关系 定义3 12 1设R X X 如果R是自反的 反对称的 和传递的 则称R是X上的偏序关系 记为 二重组称为偏序集 如果 记 为x y 读作x小于等于y 例1 在集合N 0 上的小于等于关系和整除关系 都是偏序关系 3 12 序关系 3 12 序关系 例2 设A是集合 P A 是A的幂集 P A 上的包含关系 为 x P A y P A x y 试证明 是P A 上偏序关系 证 x P A x x 即 是自反的 设 由 定义有 x y y x 根据集合相等的定义 x y 即 是反对称的 设 由 的定义有 x y y z 根据集合包含的传递性 x z 再由关系 定义有 即 是传递的 因此 是P A 上偏序关系 另外 任意集合A上的恒等关系IA是自反的 反对称的和 传递的 IA是A上偏序关系 实数集合上的小于等于关系 也是自反的 反对称的和传递的 它是实数集合上的偏 序关系 定义3 12 2 设为偏序集 对X中的元素x和y 如果 x y x y且没有X中的其它元素z使x z和z y 则称y盖 住了x 3 12 序关系 例3 设A 2 5 6 10 15 30 A上的整除关系R定义如下 R x A y A x整除y 验证R是A上的偏序关系 分析哪些元素盖住了另一些元 素 哪些元素没有盖住了另一些元素 解 因为A的任何元素都能整除它自己 所以R是自反的 当x 整除y且y整除x时 一定有x y 所以R是反对称的 当x 整除y且y整除z x一定整除z 所以R是传递的 即R是A 上的偏序关系 3 12 序关系 3 12 序关系 用列举法将R表示为 R 6和10盖住了2 但30没有盖住了2 因为 R和 R 10和15盖住了5 但30没有盖住了5 因为 R和 R 30盖住了6 10和15 定义3 12 3设为偏序集 集合 x X y X y盖住了x 叫做X上的盖住关系 记为COV X 设 COV X 是X上的盖住关系 如果 COV X 根据 定义3 12 3 y盖住了x 由定义3 12 2知 x y 即 故COV X 所以任何盖住关系COV X都是相 应偏序关系 的子集 例4 在例3中 偏序集的盖住关系 COV A 3 12 序关系 设是偏序集 它的盖住关系COV X是惟一的 所以可 以利用盖住关系做一图 表示该偏序集 这个图叫做 哈斯图 偏序集的哈斯图的画法如下 用 表示X中的每一个元素 如果 x y 则将x画在y的下方 若 COV X 则在x和y间画一条直线 例3的哈斯图如下 3 12 序关系 例5设A a b B P A a b a b 是A的幂集合 幂集合P A 上的包含关系 R x P A y P A x y 试写出盖住关系COVP A 画出它的哈斯图 解 用列举法将R 表示为 R IB 在例2中 已证R 是P A 上的偏序关系 P A 上的盖住关系为 COV P A 哈斯图如图所示 3 12 序关系 定义3 12 4 设是偏序集 B X b B 如果B 中没有任何元素x满足x b且b x x b 则称b 是B的极大元 极小元 当B X时 B的极大元 极小元 称为偏序集 的极大元 极小元 3 12 序关系 3 12 序关系 例6 设A a b c d e f g h A上的二元关系 R IA 验证R是A上的偏序关系 写出盖住关系COV A 画出哈斯 图 找出集合A的极大元和极小元 解 容易验证R是自反的 反对称的和传递的 R是A上的偏序关系 COV A 哈斯图如图所示 集合A的极大元是 a f h 集合A的极小元是 a b c g 由定义3 12 4和例6可以得出以下结论 孤立点既是极大元又是极小元 极大元和极小元不惟一 有限集合B的极大 元和极小元一定存在 在哈斯图中 如果集合B的某个元素不存在B 的其它元素从上 下 方与其相通 则该元素就 是B的极大元 极小元 3 12 序关系 3 12 序关系 定义3 12 5 设是偏序集 B X b B 如果 对任意x B 都有 x b b x 则称b是B的最大 元 最小元 当B X时 B的最大元 最小元 称为偏序集 的最大元 最小元 在例6中 集合A没有最大元和最小元 在例5中 令B a B的最大元是 a B 的最小元是 令B a b B没有最大元 和最小元 定理3 12 1 设是偏序集 B X 如果B有 最大元 最小元 则必惟一 证明 设a b都是B的最大元 由a是B的最大元得 b a 由b是B的最大元得a b 因为 是反对称 的 所以a b 即B的最大元惟一 类似地可证明最小元惟一 3 12 序关系 3 12 序关系 从以上例题和定理3 12 1可以得出以下结论 最大元和最小元不一定存在 如果存在 一定 惟一 在哈斯图中 如果集合B的某个元素向下 上 通向B的所有元素 则该元素就是B的最大元 最小 元 定义3 12 6 设是偏序集 B X b X 对任意 x B 都有x b b x 则称b是B的上界 下界 例7 设A 2 3 6 12 24 36 其上的整除关系 R a A b A a能整除b 是A上的偏序关系 试求盖住关系COV A 画出哈斯图 确定下列集合的上界和下界 B1 2 3 6 B2 12 24 36 解 用列举法将R表示为 R IA 盖住关系 COV A 3 12 序关系 3 12 序关系 哈斯图如图所示 B1 2 3 6 B2 12 24 36 B1的上界是6 12 24 36 没有下界 B2的下界是2 3 6 12 没有上界 从本例可以看出 上界和下界并不惟一 在哈斯图中 如果集合X的某 个元素向下 上 通向B的所有元素 则该元素就是B的上界 下界 定义3 12 7设是偏序集 B X 如果存在B的 一个上界 下界 b 对B的任意一个上界 下 界 y 都有b y y b 则称b是B的最小上界 最 大下界 也叫上确界 下确界 记为LUB B GL