4.5等价关系与偏序关系.doc

授课时间 第九周 第 1 次课 授课章节 4.5 等价关系与偏序关系 任课教师 及职称 唐新华 讲师 教学方法 与手段 板书和电子课件结合 课时安排 2课时 使用教材和 主要参考书 1、教材： 耿素云等，离散数学，清华大学出版社，2008 2.参考书 左孝琳、李为槛、刘永才，离散数学（上海科技文献版）2006 教学与目的要求： 掌握序偶与笛卡尔积的基本概念，并能够计算集合的笛卡尔积；掌握关系、二元关系、空关系、全域关系、相等关系、逆关系、复合关系的的概念，关系的表述方法，掌握关系、二元关系、空关系、全域关系、相等关系、逆关系、复合关系的的性质，能够判定关系的性质（等价关系或偏序关系） 教学重点、难点: 重点：等价关系、等价类、商集、划分的概念，以及等价关系与划分的对应性质 ⑧ 偏序关系、偏序集、哈斯图、偏序集中的特定元素等概念④ 集合A上关系R的自反闭包、对称闭包和传递闭包 ⑤ 关系运算的集合恒等式或者包含式 关系的闭包运算；等价关系、等价类；偏序关系、偏序集、哈斯图4.5 等价关系与偏序关系 一、本节主要内容 等价关系 商集 偏序关系 二、教学内容 等价关系的定义与实例 定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系. 设 R 是一个等价关系, 若x,y∈R, 称 x 等价于y, 记做 x～y.? 实例 设 A={1,2,…,8}, 如下定义A上的关系 R： R = { x,y | x,y∈A∧x≡y(mod 3) }其中 x≡y(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 等价类及其性质 定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系. 设 R 是一个等价关系, 若x,y∈R, 称 x 等价于y, 记做 x～y.? 实例 设 A={1,2,…,8}, 如下定义A上的关系 R： R = { x,y | x,y∈A∧x≡y(mod 3) }其中 x≡y(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. A上模3等价关系的关系图 设 A={1,2,…,8},  R={ x,y| x,y∈A∧x≡y(mod 3) } 定义 设R为非空集合A上的等价关系, x∈A，令[x]R = { y | y∈A∧xRy } 称 [x]R 为 x 关于R 的等价类, 简称为 x 的等价类, 简 记为[x]. 实例 A={ 1, 2, … , 8 }上模 3 等价关系的等价类： [1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6} 定理1 设R是非空集合A上的等价关系, 则 (1) x∈A, [x] 是A的非空子集. (2) x, y∈A, 如果 x R y, 则 [x]=[y]. (3) x, y∈A, 如果 x y, 则 [x]与[y]不交. (4) ∪{ [x] | x∈A}=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,7}è{2,5,8}è{3,6} = {1,2, … ,8} 商集 定义 设R为非空集合A上的等价关系, 以R的所有等价类作为元素的集合称为A关于R的商集, 记做A/R, A/R = { [x]R | x∈A } 实例 A={1,2,…,8}，A关于模3等价关系R的商集为 A/R = { {1,4,7}, {2,5,8}, {3,6} } A关于恒等关系和全域关系的商集为： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} } 划分 定义 设A为非空集合, 若A的子集族π(πíP(A)) 满足下面条件： (1) ??π (2) xy (x,y∈π∧x≠y→x∩y=?) (3) ∪π=A  则称π是A的一个划分, 称π中的元素为A的划分块. 例1 设A＝{a, b, c, d}, 给定π1,π2,π3,π4,π5,