等价关系与偏序关系

《等价关系与偏序关系》由会员分享，可在线阅读，更多相关《等价关系与偏序关系（7页珍藏版）》请在金锄头文库上搜索。

1、山东政法学院教案模版授课时间 第九周 第 1 次课授课章节4.5 等价关系与偏序关系任课教师及职称唐新华讲师教学方法与手段板书和电子课件结合课时安排2 课时使用教材和主要参考书1、教材： 耿素云等，离散数学，清华大学出版社，2008 2.参考书左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006教学与目的要求：掌握序偶与笛卡尔积的基本概念，并能够计算集合的笛卡尔积；掌握关系、二元关系、空关系、全域关系、相等关系、逆关系、复合关系的的概念，关系的表述方法，掌握关系、二元关系、空关系、全域关系、相等关系、逆关系、复合关系的的性质，能够判定关系的性质（等价关系或偏序关系）教学重点、难点:重点：

2、等价关系、等价类、商集、划分的概念，以及等价关系与划分的对应性质 偏序关系、偏序集、哈斯图、偏序集中的特定元素等概念 集合 A 上关系 R 的自反闭包、对称闭包和传递闭包 关系运算的集合恒等式或者包含式 难点：关系的闭包运算；等价关系、等价类；偏序关系、偏序集、哈斯图教学内容:4.5 等价关系与偏序关系等价关系与偏序关系 一、本节主要内容一、本节主要内容 等价关系 商集 偏序关系 二、教学内容二、教学内容 等价关系的定义与实例 定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上 的等价关系. 设 R 是一个等价关系, 若R, 称 x 等价于 y, 记

3、做 xy. 实例 设 A=1,2,8, 如下定义 A 上的关系 R： R = | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 与 y 模 3 相等, 即 x 除以 3 的余数与 y 除以 3 的余数相等. 等价类及其性质 定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上 的等价关系. 山东政法学院教案模版设 R 是一个等价关系, 若R, 称 x 等价于 y, 记做 xy. 实例 设 A=1,2,8, 如下定义 A 上的关系 R： R = | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 与 y 模 3 相等,

4、即 x 除以 3 的余数与 y 除以 3 的余数相等. A 上模 3 等价关系的关系图 设 A=1,2,8, R= | x,yAxy(mod 3) 定义 设 R 为非空集合 A 上的等价关系, xA，令xR = y | yAxRy 称 xR 为 x 关于 R 的等价类, 简称为 x 的等价类, 简 记为x. 实例 A= 1, 2, , 8 上模 3 等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,6 定理 1 设 R 是非空集合 A 上的等价关系, 则(1) xA, x 是 A 的非空子集.(2) x, yA, 如果 x R y, 则 x=y.(3) x, yA, 如

5、果 x y, 则 x与y不交.(4) x | xA=A，即所有等价类的并集就是 A. 实例 A= 1, 2, , 8 上模 3 等价关系的等价类：1=4=7=1,4,7，2=5=8=2,5,8，3=6=3,6以上 3 类两两不交， 1,4,72,5,83,6 = 1,2, ,8 商集 定义 设 R 为非空集合 A 上的等价关系, 以 R 的所有等价类作为元素的集合称为 A 关于 R 的商集, 记做 A/R, A/R = xR | xA 实例 A=1,2,8，A 关于模 3 等价关系 R 的商集为A/R = 1,4,7, 2,5,8, 3,6 A 关于恒等关系和全域关系的商集为：A/IA = 1

6、,2, ,8山东政法学院教案模版A/EA = 1, 2, ,8 划分 定义 设 A 为非空集合, 若 A 的子集族(P(A) 满足下面条件：(1) (2) xy (x,yxyxy=)(3) =A 则称是 A 的一个划分, 称中的元素为 A 的划分块. 例 1 设 Aa, 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 则1和2 是 A 的划分, 其他都不是 A 的划分. 为什么？ 等价关系与划分的一一对应

7、 商集 A/R 就是 A 的一个划分 不同的商集对应于不同的划分 任给 A 的一个划分, 如下定义 A 上的关系 R：R = | x,yAx 与 y 在的同一划分块中 则 R 为 A 上的等价关系, 且该等价关系确定的商集就是. 例 2 给出 A1,2,3上所有的等价关系 求解思路：先做出 A 的所有划分, 然后根据划分写 出对应的等价关系. 等价关系与划分之间的对应山东政法学院教案模版4 对应于全域关系 EA，5 对应于恒等关系 IA1,2和3分别对应等价关系 R1, R2 和 R3. R1=,IA，R2=,IAR3=,IA例 3 设 A=1, 2, 3, 4，在 AA 上定义二元关系 R：

8、 ,R x+y = u+v， 求 R 导出的划分. 解 AA=, , , , , , , , , , , , , 根据 的 x + y = 2,3,4,5,6,7,8 将 AA 划分成 7 个 等价类：(AA)/R= , , , , , , , , , , , , , 偏序关系 定义 非空集合 A 上的自反、反对称和传递的关系，称为 A 上的偏序关系，记作. 设 为偏序关系, 如果, 则记作 xy, 读作 x“小于等于”y. 实例集合 A 上的恒等关系 IA 是 A 上的偏序关系. 小于等于关系, 整除关系和包含关系也是相应集合上的偏序关系. 相关概念 x 与 y 可比：设 R 为非空集合 A

9、 上的偏序关系, x,yA, x 与 y 可比 xy yx. 结论：任取两个元素 x 和 y, 可能有下述情况： xy (或 yx), xy, x 与 y 不是可比的. 全序关系： R 为非空集合 A 上的偏序, x,yA, x 与 y 都是可比的，则称 R 为全序关系 实例：数集上的小于等于关系是全序关系整除关系不是正整数集合上的全序关系 盖住：设 R 为非空集合 A 上的偏序关系, x, yA, 如果 x y 且不存在 zA 使得 x z y, 则称 y 盖住 x.实例： 1, 2, 4, 6 集合上的整除关系, 2 盖住 1, 4 和 6 盖住 2. 4 不盖住 1.山东政法学院教案模版

10、偏序集与哈斯图 定义 集合 A 和 A 上的偏序关系一起叫做偏序集, 记作 . 实例：整数集和小于等于关系构成偏序集，幂集 P(A)和包含关系构成偏序集. 哈斯图：利用偏序自反、反对称、传递性简化的关系图 特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低 的元素的顺序在前，具有盖住关系的两个结点之间连边例 4 哈斯图实例 例 5 已知偏序集 的哈斯图如右图所示, 试求出集合 A 和关系 R 的表达式. A=a, b, c, d, e, f, g, h R=,IA 偏序集的特定元素 定义 设为偏序集, BA, yB. (1) 若x(xByx) 成立, 则称 y 为

11、B 的最小元. (2) 若x(xBxy) 成立, 则称 y 为 B 的最大元. (3) 若x (xBx y) 成立, 则称 y 为 B 的极小元. (4) 若x (xBy x) 成立, 则称 y 为 B 的极大元. 特殊元素的性质山东政法学院教案模版对于有穷集，极小元和极大元必存在，可能存在 多个. 最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元. 孤立结点既是极小元，也是极大元. 偏序集的特定元素(续) 定义 设为偏序集, BA, yA.(1) 若x(xBxy) 成立, 则称 y 为 B 的上界. (2) 若x(xByx) 成立, 则称 y 为 B 的下界

12、. (3) 令 Cy | y 为 B 的上界, 则称 C 的最小元为 B 的最小上界 或 上确界. (4) 令 Dy | y 为 B 的下界, 则称 D 的最大元为 B 的最大下界 或 下确界.特殊元素的性质下界、上界、最大下界、最小上界不一定存在 下界、上界存在不一定惟一 最大下界、最小上界如果存在，则惟一 集合的最小元就是它的最大下界，最大元就是它的最小上界；反之不对. 实例 例 6 设偏序集如下图所示，求 A 的极小元、最小 元、极大元、最大元. 设 Bb,c,d, 求 B 的下界、上 界、最大下界、最小上界. 极小元：a, b, c, g； 极大元：a, f, h； 没有最小元与最大元. B 的下界和最大下界都 不存在, 上界有 d 和 f, 最小上界为 d. 复习思考题、作业题：习题 4、 15 16 17山东政法学院教案模版下次课预习要点：函数的定义和性质复合函数和反函数实施情况及教学效果分析:院系部审核意见:院系部负责人签字年 月 日