离散数学等价关系与偏序关系.ppt

1 4 5等价关系与偏序关系 等价关系的定义等价类及其性质商集与集合的划分等价关系与划分的一一对应相容关系偏序关系偏序集与哈斯图偏序集中的特定元素 2 4 5等价关系和划分 定义设R是A上的二元关系 如果 1 R是自反的 2 R是对称的 3 R是可传递的 则称R是A上的等价关系 若 R 称x等价于y 记做x y 等价关系是经常使用的重要的二元关系 1 等价关系的定义 一 等价关系 3 例如 我们用a b c d e f分别表示6位大学生 其中a b c都姓张 d e f都姓李 若令集合A a b c d e f 张李 R是A上的同姓氏关系 同姓的大学生认为是相关的 容易验证同姓氏关系R是A上的等价关系 1 因为每一个大学生都和自已是同姓的 所以满足自反性 2 当 a b R时有 b a R 所以满足对称性 3 当 a b R和 b c R时有 a c R 所以R是可传递的 由此可得同姓氏关系R是等价关系 4 又如设集合A的情况同上所述 若令集合A a b c d e f 2022 其中a b c d都是20岁 e f都是22岁 如果年龄相同的大学生认为是相关的 那么 同年龄 关系R是等价关系 1 因为每一个大学生都和自已是同年龄的 所以满足自反性 2 当 a b R时有 b a R 所以满足对称性 3 当 a b R和 b c R时有 a c R 所以R是可传递的 由此可得同年龄关系R是等价关系 5 再如设集合A的情况同上所述 若令集合A a b d c e f 同房间同房间 其中a b d同住一个房间 c e f同住另一个房间 如果同住一个房间的大学生认为是相关的 那么 同房间 关系R也是等价关系 1 因为每一个大学生都和自已是同房间的 所以满足自反性 2 当 a b R时有 b a R 所以满足对称性 3 当 a b R和 b c R时有 a c R 所以R是可传递的 由此可得同房间关系R是等价关系 6 由上述3个例子可知那种同姓氏 同房间 同年龄的关系都是等价关系 如果抽象地讨论 对集合A中的元素按照某种特性分成几个组 每个元素只属于一个组 如按年龄分组 即同年龄人在同一组内 或按姓氏分组 即同姓人在同一组内 并且定义在同一组内的元素是相关的 而不在同一组内的元素是不相关的 那么由此产生的二元关系必然是等价关系 由此可知等价关系所具有的重要特性 由此可见 等价关系实际上是同组关系 7 下面将利用表格和关系矩阵来进一步了解等价关系的特征 2 等价关系的表格表示和关系矩阵 为了方便将上述3个例子综合如下 1 a b c都姓 张 d e f都姓 李 2 a b c d都是20岁 e f都是22岁 3 a b d同住一个房间 c e f同住另一个房间 下面分别画出 1 2 3 所表示的等价关系的表格和关系矩阵 8 abcdef 1 a b c都姓 张 d e f都姓 李 abcdef 易见在描述等价关系的表格中 带有 的格子将形成若干个正方形 而在关系矩阵中则有一些小方阵 其元素都是1 而其它元素都是0 9 对于 2 所示的等价关系的表格表示和关系矩阵也有上述特征 abcdef abcdef 2 a b c d都是20岁 e f都是22岁 10 对于 3 所示的等价关系 如果将集合A a b c d e f 中的顺序改为A a b d c e f 也就是把相关的元素排在一起那么所画出的表格也显示上述特征 3 a b d同住一个房间 c e f同住另一个房间 abdcef abdcef 11 例1设集合A 1 2 3 4 5 6 7 R是A上的模3同余关系 试说明此关系是等价关系 并画出表格和关系矩阵 解 1 相同数被3除后余数一定相同 所以R上自反的 显然R也是对称的 又由于A中任意元素a 可写为 a 3k r 所以当 a b R时 有a b 3k 因此当 a b R和 b c R时 即有 a b 3k1 b c 3k2 于是a c a b b c 3 k1 k2 3k 由此可得 a c R 所以R是可传递的 说明此关系是等价关系 12 在集合A中 以相关元素顺序排列 即 A 1 4 7 2 5 3 6 也就是把相关的元素排在一起那么所画出的表格表示和关系矩阵如下 由此可见模3同余关系也是一种分组关系 它是把A中的元素被3除后 余数为1的分为一组 1 4 7 余数为2的分为一组 2 5 余数为3的分为一组 3 6 1472536 1472536 13 以上的例子不仅说明集合A上的等价关系实际上是一种 同组 关系 即当集合A确定一种 分组 形式后 也就确定了A上的一种等价关系 只要将同一组的元素认作是相关的 反之当确定一个A上的等价关系后 也就确定了A上的一种 分组 形式 只要将相关元素合成一组 为了详细地讨论这一问题 下面介绍等价类和划分这两个概念 14 二 等价类 定义 设R是A上的等价关系 a A 由A中所有与a相关的元素组成的集合称为a关于R的等价类 记作 a R 例如集合A 1 2 3 4 5 6 7 R是A上的模3同余关系 显然R是A上等价关系 A中各元素关于R的等价类分别是 2 R 2 5 5 R 2 5 显然相关元素的等价类是相同的 所以不同的等价类仅有3个 它们是 1 R 2 R 3 R 15 又如设集合A a b c d e f g 其中a b c d e f g分别表示7位大学生 且a b都是20岁 c d都是22岁 e f都是24岁 g是25岁 R是A的同年龄关系 写出A中各元素关于R的等价类 显然 a R a b b R a b c R c d d R c d e R e f f R e f g R g 定义 R是A上的等价关系 由R的所有不同的等价类作为元素构成的集合 称为A关于R的商集 记作A R 16 商 和除法有关 比如把一块蛋糕平均分成四份 从两种不同的角度看这件事 从算术角度看 1用4除 每份1 4 这就是 商 于是 1 1 4 1 4 1 4 1 4从集合角度看 集合A用模3同余关系R划分 得到三个等价类 所以A 1 4 7 2 5 3 6 1 R 2 R 3 R 商集 17 思考 1 集合A 1 3 5 7 9 R是A上的模4同余关系 求R的商集A R 3 R 7 R 3 7 1 R 5 R 9 R 1 5 9 所以A关于R的商集A R 1 5 9 3 7 答案 18 答案 有4个是不相同的等价类 它们是 a b c d e f g h 2 A a b c d e f g h A上的等价关系R如图所示 所以A关于R的商集为A R a b c d e f g h abcdefgh 写出A关于R的商集 19 三 集合的划分 定义 设A是集合 A1 A2 An 是A的子集 如果A1 A2 An A 且Ai Aj i j i 1 2 n j 1 2 n 由以A1 A2 An作为元素构成的集合S A1 A2 An 称为A的一个划分 每一个子集Ai称为块 例如A a b c d e f A2 a d e b c f A1 a b c d e f A3 a f b d e c 则A1 A2 A3都是A的划分 在A1中 a b c d e f 是块 20 思考 设A a b c d 给定 1 2 3 4 5 6如下 1 a b c d 2 a b c d 3 a a b c d 4 a b c 5 a b c d 6 a a b c d 问哪些是A的划分 哪些不是A的划分 答案 1和 2是A的划分 其他都不是A的划分 21 由此可知 如果R是A上的等价关系 则商集A R就是A上的一个划分 等价类就是块 定理 集合A上的一个划分能确定一个A上的等价关系 反之确定了A上的一个等价关系也能确定A上的一个划分 例如A a b c d e A a b c d e 那么它所确定的等价关系的表格表示如图所示 abcde 22 又如A a b c d e R为A上的等价关系 其表格表示如图所示 则由R确定的划分为A a b c d e abcde 由此可知 集合A上的等价关系与划分可以建立1 1对应关系 23 例1 设A是具有5个元素的集合 问满足下列条件的等价关系有多少种 1 等价类中至少含有2个元素 2 至少有一个等价类含有2个元素 解答 1 由于集合A上的等价关系与划分是1 1对应关系 所以等价类中至少有2个元素的等价关系与块中至少有2个元素的划分的个数相同 而块中至少有2个元素的划分共有两类 一类是划分中仅有1块 块中含有5个元素 这样的划分仅有1种 另一类是划分中有2块 其中1块含有2个元素 另一块含有3个元素 这样的划分有种 所以当时等价类中至少含有2个元素的等价关系共有11种 24 2 同理至少有1个等价类含有2个元素的等价关系的个数与至少有1个块含有2个元素的划分的个数相同 而至少有1个块含有2个元素的划分可分为三类 所以当时至少有一个等价类含有2个元素的等价关系共有10 10 15 35种 第一类是划分中含有2块 各块中含有的元素数分别为2 3 第三类是划分中有4块 各块中含有的元素数分别为2 1 1 1 第二类是划分中有3块 各块中含有的元素数分别为2 2 1 这样的划分共有种 这样的划分有种 这样的划分有种 25 例2 设R是A上的自反关系 且当 a b R和 a c R时 必有 b c R 证明R是等价关系 证明 因为当 a b R和 a c R时 必有 b c R 由于R是自反关系 即 a a R 于是有 当 a b R和 a a R时 必有 b a R 因此R是对称关系 由于R是对称关系 所以当 a b R b c R时 必有 b a R b c R 由题设可得 a c R 所以R是传递关系 因此R是等价关系 26 思考 1 设I是整数集合 当a b 0时 a b R 说明R不是等价关系 2 设R是A上的自反关系 且当 a b R和 b c R时 必有 c a R 证明R是等价关系 3 设A是具有4个元素的集合 问在A上可以有多少种不同的等价关系 27 1 设I是整数集合 当a b 0时 a b R 说明R不是等价关系 解 因为 1 0 R 0 1 R 但 1 1 R 说明R不是传递关系 所以R不是等价关系 解 28 2 设R是A上的自反关系 且当 a b R和 b c R时 必有 c a R 证明R是等价关系 证明 因为当 a b R和 b c R时 必有 c a R 由于R是自反关系 即 b b R 于是有 当 a b R和 b b R时 必有 b a R 因此R是对称关系 由于当 a b R和 b c R时 必有 c a R 又由于R是对称关系 由此可得 a c R 所以R是传递关系 因此R是等价关系 29 3 设A是具有4个元素的集合 问在A上可以有多少种不同的等价关系 解 由于A上的等价关系与A上的划分1 1对应 所以A上有多少种不同的划分就有多少种不同的等价关系 设A a b c d 分以下几种情况讨论 1 当划分中仅含有1个块时 这样的划分仅有1种 a b c d 2 当划分中含有2个块时 它们为 a b c d b a c d c a b d d a b c a b c d a c b d b c a d 这样的划分应有 7种 30 3 当划分中含有3个块时 它们为 a b c d a c b d a d c b b c a d b d a c c d a b 4 当划分中含有4个块时 这样的划分仅有1种 a b c d 综上所述 当A是具有4个元素的集合时 在A上共有1 7 6 1 15 种 不同的等价关系 31 四 相容关系 定义 设R是A上的二元关系 如果满足 1 R是自反的 2 R是对称的 则称R是A上的相容关系 易知 等价关系是一种特殊的相容关系 即具有传递的相容关系 在人际关系中朋友关系是相容关系 但它不是等价关系 因为它满足自反性 对称性 但它不满足可传递性 32 设A boy root cat beer and R是A上的二元关系 其定义为 当两个单词至少有一个字母相同时 则认为是相关的 显然R是自反的 对称的 所以R是A上的相容关系 但它不是等价关系 因为它不是可传递的 如 boy root R root cat R 而 boy cat R 33 定义 设R是A上的相容关系 B是A的子集 而且在B中任意两个元素都是相关的 则称B为由相容关系R产生的相容类 34 例如设A 134 345 275 347 348 129 R是A上的二元关系 其定义为 a b A 且a和b至少有一个数码相同 则 a b R 显然R是相容关系 A的子集 134 347 348 275 345 134 129 等都是相容类 对于前两个相容类 都能添加新的元素组成新的相容类 如在相容类 134 347 348 中添加新的元素345 可组成新的相容类 134 347 348 345 在相容类 275 345 中添加新的元素347 可组成新的相容类 275 345 347 而对于第三个相容类 134 129 添加任意一个新元素就不再组成相容类 称这样的相容类为最大相容类 35 对于最大相容类还可以这样认定 R是A上的相容关系 B是相容类 在差集A B中没有元素能和B中所有元素都是相关的 则称B为最大相容类 利用相容关系的图形表示可以很方便地确定相容类和最大相容类 36 如图所示中 完全多边形的顶点集合就是相容类 所谓完全多边形是指每个顶点都与其它顶点有边联结的多边形 例如三角形是完全多边形 一个四边形加上两条对角线也是完全多边形 由于顶点134 348 347构成了一个三角形 所以 134 348 347 是相容类 同理 275 345 347 是相容类 134 347 348 345 也是相容类 如 37 由此可见 图中最大的完全多边形的顶点集合就最大相容类 这里的 最大 是这样的含义 如果一个完全多边形 在添加任何新的顶点就不再成为完全多边形 则称此完全多边形是最大的完全多边形 如由顶点134 347 348 345构成的完全多边形是最大完全多边形 由顶点345 275 347构成的完全多边形也是大完全多边形 易见 在该图中 有四个最大相容类 它们是 192 134 129 275 345 275 347 134 345 347 348 38 定义 A是集合 A1 A2 An都是它的非空子集 令S A1 A2 An 如果A1 A2 An A 则称S为A的覆盖 例如A 1 2 3 4 5 S 1 2 2 3 4 1 3 5 则S是A的覆盖 39 定义 S A1 A2 An 是集合A的覆盖 且对于S中任意元素Ai 不存在S中的其它元素Aj 使得Ai是Aj的子集 则称S为A的完全覆盖 例如A a b c d e S1 a b b c d d e S2 a b a b c a d e 其中S1是A的覆盖又是完全覆盖 而S2是A的覆盖但不是完全覆盖 因为 a b 是 a b c 的子集 40 相容关系和覆盖之间的关系 如果R是A上的相容关系 对于A中的任意元素a 集合 a 是一个相容类 并且可以对此集合不断地添加新的元素 直到使它成为最大相容类 因此 A中的每一个元素都将是某一个最大相容类的元素 由此可见 相容关系R产生的所有最大相容类构成的集合是A的一个覆盖 又由最大相容类的定义可知 一个最大相容类决不是另一个最大相容类的子集 所以由最大相容类构成的集合是A的一个完全覆盖 由此可得下面的结论 R是A上的相容关系 R能确定一个A上的完全覆盖 反之 当给定A的一个完全覆盖时 则能确定A上的相容关系R 使R产生的最大相容类构成的集合就是这个完全覆盖 41 例 A 1 2 3 4 5 6 R为A上的相容关系 其图形表示如图所示 求R所确定的完全覆盖 解 由图可知 R产生的最大相容类为 1 2 6 1 4 5 3 6 所以R确定的完全覆盖S 1 2 6 1 4 5 3 6 42 例 A a b c d e f g A的完全覆盖S a b b c f g c d e 写出S所确定的相容关系R 解由S容易得到R的图形表示 如图 所以S所确定的相容关系 R a a b b a b b a c c f f g g b c c b b f f b b g g b c f f c c g g c f g g f d d e e c d d c c e e c d e e d 43 思考 1 集合A a1 a2 a3 a4 a5 a6 R是A上的相容关系 其关系矩阵为 求R的所有最大相容类 2 集合A 111 122 341 456 795 893 R是A上的二元关系 当a b A 且a和b至少有一个数码相同 则 a b R 试画出R的关系图 并写出R的所有最大相容类 44 3 集合A a b c d e f g 完全覆盖S a b c d c d e d e f f g 写出S所确定的相容关系R