离散数学——二元关系4.5(22B2学时).pptVIP

*;在本节中，主要内容是等价关系与偏序关系： 等价关系： 基本概念：等价关系 等价类 商集 集合的划分 理解集合的划分与等价关系之间的关系。 偏序关系： 基本概念：偏序关系 偏序集 哈斯图 能够画出偏序集的哈斯(Hasse)图。 能够找出偏序集中的重要元素。;*;[定义2] 等价类： 把Ａ中的等价元素归为一类，称为等价类。 更确切的定义， [x]R = { y | y∈A∧xRy } 称作元素x关于关系R的等价类。 ;例1 A＝｛52张扑克｝ R1＝｛x，y｜x与y同花，x，y ∈A｝ R2＝｛x，y｜x与y同点， x，y ∈A ｝ 则： R1把Ａ分为四类同花类， R2把Ａ分为13类同点类。 ;注： 等价关系R把Ａ的元素分为若干类，各类之间没有公共元素。确定的R产生了对集合Ａ的一个划分，即商集。 ;[定义3] 集合的划分(partition)：把集合A分为若干非空子集A1,A2 ,… ,An ,满足： (1) 当 i ≠ j 时，Ai∩Aj＝? (2) 则集合? = {A1，A2，…，An} 称为Ａ的一个划分， Ai(i=1,2, ... , n)称为划分块。 ;[定义4] 商集： 等价关系R将A分成若干等价类，每个类选个代表组成新的集合称为A关于R的商集，表示为A/R。 A/R={[x]|x∈A} ;例1中， A＝｛52张扑克｝ R1＝｛x，y｜x与y同花，x，y ∈A｝ R2＝｛x，y｜x与y同点， x，y ∈A ｝ 则： A/R1={{红桃扑克}，{黑桃扑克}，{梅花扑克}，{方片扑克}} ————对A的一个划分 ;例2 A＝｛0，1，2，3，4，5｝ R＝｛0，0，1，1，2，2，3，3，1，2，1，3，2，1，2，3，3，1，3，2，4，4，4，5，5，4，5，5｝ ;*;*;*;*;*;*;*;*;*;1．设A={1,2,3,4}，在A?A上定义二元关系R： x,y,u,v?R ? x+y = u+v， 求R导出的划分. 2．设R是Z上的模 n 等价关系, 即 x?y ? x ? y(modn), 试给出由R确定的Z的划分?. ;*;*;*;关于偏序关系的表示： 可以用简化的关系图——Hasse图，来表示偏序关系。;*;*;*;*;*;练习1：设A={2,3,6,12,24,36}，“≤”是A上的整除关系R，画出其一般的关系图和哈斯图。 ;重要元素： 极大元/极小元，最大元/最小元，上界/下界， 上确界/下确界;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;1.设集合A={a,b,c,d,e,f,g,h}，对应的哈斯图见下图令B1={a,b}，B2={c,d,e}。求出B1，B2的最大元、最小元、极大元、极小元、上界、下界、上确界、下确界。 ;*;3. 课本4.16 提示：1、2题目可列表格表示，如：