元关系4.5等价关系.ppt

1 离散数学DiscreteMathematics 主讲 陈哲云青岛理工大学计算机工程学院2013 09 第4章二元关系 二元关系 4 1二元关系基本概念 重点 4 2关系的运算4 3关系的性质 重点 4 4关系的闭包4 5等价关系和偏序关系 重点及难点 4 6函数的基本概念 等价关系 本节内容主要说明等价关系和集合的划分 分类 之间的关系 1 等价关系 等价类 商集 集合的划分 2 集合的划分 等价关系 等价关系 定义等价关系 设A上的二元关系R 如果R是自反的 对称的 传递的 则称R为等价关系 若 R 称x与y等价 记作x y 等价关系 例1数学中一些常见的等价关系 1 数理逻辑中的公式等值关系 2 无向图中 点的连通 关系 3 方程组的 同解 关系 4 代数系统中的 同构 关系 等价关系 例2设集合A 1 2 3 4 5 6 7 8 R是A上的模3同余关系 请画出关系图 1 4 72 5 83 6 等价类 定义等价类 把具有相同性质的元素归为一类设R是A上的等价关系 则称 x R y y A x y 为x关于R的等价类 等价类 例3设学生集合A a b c d e f R1和R2分别是A上的 同性别 关系和 同宿舍 关系 求所有元素关于R1和R2的等价类 其中元素属性如下表 解 关于R1的等价类 关于R2的等价类 等价类 练习试写出A 1 2 3 4 5 6 7 8 上关于模3同余关系的等价类 解 1 4 7 1 4 7 2 5 8 2 5 8 3 6 3 6 等价类 上述两例可以看出 1 等价关系实际上 同类关系 是对集合按照某种性质进行的 分类 2 这种分类的特点是 各个不同类之间无共同元素 同类元素具有相同的特性 所有类的并集是原集合 等价类 定理设R是非空集合A上的等价关系 则 1 x A x 2 x y A 如果xRy 则 x y 3 x y A 如果xy 则 x y 4 等价类或者完全相同 或者完全不同 其并集恰好是A 商集 定义商集 等价类的集合A R x x A 性质商集是集合的一个划分 集合的划分 定义集合的划分把集合A分为若干非空子集A1 A2 An 满足 1 当i j时 Ai Aj 2 则子集族 A1 A2 An 称为A的一个划分 Ai i 1 2 n 称为划分块 集合的划分 例4分别给出学生集合A a b c d e f 根据 性别 和 宿舍 进行的划分 1和 2 解 1 a d f b c d A1 A2 其中A1 a d f A2 b d c 2 a d f b c d A1 A2 A3 其中A1 a d A2 f A3 b d c 集合的划分 例5试给出集合A 1 2 3 的所有划分 集合的划分与等价关系 性质1 等价关系对应集合的一个划分 等价关系 等价类 商集 集合的划分2 集合的一个划分对应着一个等价关系 这个等价关系的商集恰好是这个划分 集合的划分与等价关系 例6试给出学生集合A a b c d e f 关于 性别 的划分所对应的等价关系R 解 a d f b c d A1 A2 R x y同性别 x y A1 x y A2 x y A1 x y A2 A1 A1 A2 A2 集合的划分与等价关系 性质设 A1 A2 An 为A的一个划分 则 所对应的等价关系R可由如下方法得到 R x y属于 的同一划分块 具有相同的性质 A1 A1 A2 A2 An An 小结 等价关系是 分类关系 集合的划分与等价关系本质上相同 可以相互导出 1 等价关系导出划分 等价关系 商集 2 集合的划分导出等价关系 R x y属于 的同一划分块 具有相同的性质 集合的划分与等价关系 例7试写出集合A 1 2 3 上的所有等价关系 解 1 写出所有划分 2 写出每个划分对应的每个等价关系 略 作业 1 给定集合A 1 2 3 4 且A中的关系R R 求包含R的最小的等价关系R 前已求 并写出商集A R 2 给定集合S 1 2 3