《离散数学——二元关系4.5(22b2学时)》由会员分享，可在线阅读，更多相关《离散数学——二元关系4.5(22b2学时)（49页珍藏版）》请在金锄头文库上搜索。
1、1,二元关系基本概念(重点) 关系的运算 关系的性质(重点) 关系的闭包运算 等价关系与偏序关系(难点),二元关系,在本节中，主要内容是等价关系与偏序关系： 等价关系： 基本概念：等价关系 等价类 商集 集合的划分 理解集合的划分与等价关系之间的关系。 偏序关系： 基本概念：偏序关系 偏序集 哈斯图 能够画出偏序集的哈斯(Hasse)图。 能够找出偏序集中的重要元素。,2,本节要求,3,等价关系,定义1等价关系： A上的二元关系R，如果R是 (1) 自反的 (2) 对称的 (3) 传递的 称R为等价关系。 若R，称x与y等价，记作xy。,定义2 等价类： 把中的等价元素归为一类，称为等价类。
2、更确切的定义， xR = y | yAxRy 称作元素x关于关系R的等价类。,4,等价关系,例1 A52张扑克 R1x与y同花，x，y A R2x与y同点， x，y A 则： R1把分为四类同花类， R2把分为13类同点类。,5,等价关系,注： 等价关系R把的元素分为若干类，各类之间没有公共元素。确定的R产生了对集合的一个划分，即商集。,6,等价关系,定义3 集合的划分(partition)：把集合A分为若干非空子集A1,A2 , ,An ,满足： (1) 当 i j 时，AiAj (2) 则集合 = A1，A2，An 称为的一个划分， Ai(i=1,2, . , n)称为划分块。,7,等价关
3、系,定义4 商集： 等价关系R将A分成若干等价类，每个类选个代表组成新的集合称为A关于R的商集，表示为A/R。 A/R=x|xA,8,等价关系,例1中， A52张扑克 R1x与y同花，x，y A R2x与y同点， x，y A 则： A/R1=红桃扑克，黑桃扑克，梅花扑克，方片扑克 对A的一个划分,9,等价关系,例2 A0，1，2，3，4，5 R，,10,等价关系,11,R是等价关系，但不直观，用关系图表示。,等价关系,12,可以证明二元关系R是自反的，对称的，传递的，且把分成了三个等价类， 0=0， 1=2=3=1，2，3， 4=5=4，5 A/R=0, 1, 4 =0， 1，2，3， 4，5
4、,等价关系,13,例3 Rxy（mod），x，yZ是整数集合Z上模3的同余关系(Congruence Relation) ，可以证明R是等价关系，求各元素等价类及商集。 解：各元素等价类如下(其中kZ)： 0，-6，-3，0，3，6，=x|x=3k 1，-5，-2，1，4，7，= x|x=3k+1 2，-4，-1，2，5，8，= x|x=3k+2 商集：ZR0，1，2 x|x=3k ， x|x=3k+1 ， x|x=3k+2 ,等价关系,14,1. 幂集上定义的“”关系； 2. 整数集上定义的“”关系； 3. 全体中国人所组成的集合上定义的“同性别”关系。 4.全班同学所组成的集合上定义的“同
5、龄”关系及“朋友”关系。,例4 判定下列关系是否是等价关系?若是，求等价类。,等价关系,15,定理1 A在等价关系R下的商集正是A的一种划分，A的任一种划分，也必有A上的一个等价关系R与之对应。即等价关系与集合的划分一一对应。,等价关系,16,定理2设是非空集合A上的一个划分,令 R=|x,y属于的同一个划分块,则R是A上的等价关系，而且R的商集A/R= 。 证明思路: 1) 验证R是自反的，对称的，传递的，因此R是等价关系。 2) 证明集合A/R与相等。,等价关系,17,思考： 已知等价关系，划分的一般计算方法是? 已知划分，等价关系的一般求法是?,商集,已知 = A1，A2，An R=|x
6、,y属于的同一个划分块 = A1 A1 A2 A2 An An =,等价关系,18,例5 设A=1,2,3,4,5. 1) 求A的划分 =1,2,3,4,5对应的等价关系。 略解: R= 2) 已知关系R= 求R对应的划分。 略解： 事实上就是计算A/R.,等价关系,19,1.熟记等价关系的定义； 2.利用等价关系的定义证明一个关系是等价关系； 3.给定A上的等价关系R，会求所有的等价类和商集A/R；并求出对应的集合的划分； 4.给定集合A上的划分，会求对应的等价关系。,总结,1设A=1,2,3,4，在AA上定义二元关系R： ,R x+y = u+v， 求R导出的划分. 2设R是Z上的模 n
7、等价关系, 即 xy x y(modn), 试给出由R确定的Z的划分.,20,作业,21,偏序关系,定义1 偏序关系(Partial Order Relation) ： R是A上的二元关系，如果R满足： (1) 自反的 (2) 反对称的 (3) 传递的 则称R是A上偏序关系，简称偏序，记作 。 若R，则可记作xy (x小于等于y)。,22,例1： ， ， 1 xy，x，y 2 x|y，x，y 3s1s2， s1，s2P() 可证明1，2，3都是集合上的偏序关系，并可写出集合中元素之间的关系。,偏序关系,23,定义2 偏序集(Partial Order Set) ： 集合及上的一个偏序关系组成的
8、二元组，称为偏序集，记为。,注：同一集合上的两个不同的偏序关系，所构成的是两个偏序集， 如： 1和2都定义在，上，但与显然不是一样的偏序集。,偏序关系,关于偏序关系的表示： 可以用简化的关系图Hasse图，来表示偏序关系。,24,简化的关系图： 1)自反性：每个顶点都有自回路，省去。 2)反对称性：两个顶点间只可能有一个箭头，从小到 大安置顶点，可省略箭头。 3)传递性：由于有，R，则R， 故只画，对应的边，省略边。,Hasse图,25,定义3Hasse图： 设是A上的一个偏序关系， (1)如果x y (x与y可比)，则将x画在y下面； (2)如果x y，且不z，使x z，z y (y盖住x)
9、，则x，y间用直线连接； (3)同时符合简化的关系图的绘制。 称这样得到的关系图为Hasse图。,Hasse图,26,画出例1中各关系的Hasse图： ， ， 1 x y，x，y 2 x | y，x，y 3s1s2， s1，s2P(),Hasse图,27,R1,28,29,练习1：设A=2,3,6,12,24,36，“”是A上的整除关系R，画出其一般的关系图和哈斯图。,30,关系图,哈斯图,2,3,6,12,36,24,2,3,6,12,36,24,Hasse图,重要元素： 极大元/极小元，最大元/最小元，上界/下界， 上确界/下确界,31,重要元素,32,定义4 极大元与极小元： 设是偏序集
10、，BA， 若存在yB，在B中找不到一个元素x（xy），使yx ，则称y为B中的极大元。 即极大元是在B中找不到比其更大的元素。 极小元类似定义。,重要元素,33,例2：是偏序集， B， 则 B中极大元：， 极小元：，,重要元素,34,也可通过Hasse图来寻找极大元或极小元。,重要元素,35,注： 1）极大元，极小元必须是子集B中的元素。 2）极大元，极小元并不要求唯一，且同一元素，可以既是极大元，又是极小元，如，。,重要元素,36,定义5 最大元与最小元： 设是偏序集，BA， 若存在yB，对xB，xy ，则称y为B的最大元。 即最大元是B中所有元素都比其小的元素。 最小元类似定义。,重要元素
11、,37,仍借助Hasse图来寻找最大元和最小元。,结论：子集B中是不存在最大元与最小元。,重要元素,38,注： 最大元（最小元）本身应属于子集B，且与B中任一元素都有关系。,重要元素,39,练习2： A，, 3s1 s2，s1，s2P(A)， 是偏序集。 设B， 求其最大元与最小元，极大元与极小元。,重要元素,40,结论： B存在最小元 ，没有最大元。 极小元是，极大元是a , b, a , c, b , c。,重要元素,41,定义6 上界与下界： 设是偏序集，BA， 若存在yA，对 xB，都有x y，称y为 B的上界。 下界类似定义。,重要元素,42,例3： A，, 3s1 s2，s1，s2
12、P(A)， 是偏序集。 设B， 求B的上界与下界。,重要元素,43,结论： (1) B无最大元，但存在B的上界a, b,c。 (2) 为B的最小元，也是B的下界。,44,定义 上确界与下确界： 上确界：最小上界 下确界：最大下界,重要元素,45,例4： 上例中取B=，则 ，与，是B的上界，是B的上确界。,46,结论：(1)，是B的上界。 (2)与无法比大小，不存在上确界。 (3)B的下界不存在，不存在下确界。,例5：A， B，定义偏序集,1.设集合A=a,b,c,d,e,f,g,h，对应的哈斯图见下图令B1=a,b，B2=c,d,e。求出B1，B2的最大元、最小元、极大元、极小元、上界、下界、上确界、下确界。,47,作业,48,2.设集合X=x1,x2,x3,x4,x5上的偏序关系如下图所示，求X的最大元、最小元、极大元、极小元。求子集X1=x2,x3,x4，X2=x3,x4,x5，X3=x1,x3,x5的上界、下界、上确界、下确界、最大元、最小元、极大元和极小元。,作业,3. 课本4.16 提示：1、2题目可列表格表示，如：,49,作业,
