离散数学等价偏序函数省公共课一等奖全国赛课获奖课件.pptx

第六节第六节 等价关系与划分等价关系与划分主要内容等价关系定义与实例等价类及其性质商集与集合划分 等价关系与划分一一对应 第1页一、等价关系定义与实例一、等价关系定义与实例定义定义7.15设设R为非空集合上关系为非空集合上关系.假如假如R是自反、对是自反、对称和传递称和传递,则称则称R为为A上等价关系上等价关系.设设R是一个等价是一个等价关系关系,若若R,称称x等价于等价于y,记做记做xy.在我们日常生活和学习中，就有一些等价关系例子，在我们日常生活和学习中，就有一些等价关系例子，如：如：（1）在一群人集合上年纪相等关系是等价关系，）在一群人集合上年纪相等关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递。而朋友关系不一定是等价关系，因为它可能不是传递。（2）命题公式间逻辑等值关系是等价关系。）命题公式间逻辑等值关系是等价关系。（3）集合上恒等关系是等价关系。）集合上恒等关系是等价关系。（4）在同一平面上直线之间平行关系，三角形之间）在同一平面上直线之间平行关系，三角形之间相同关系都是等价关系。相同关系都是等价关系。第2页实例实例设设A=1,2,8,以下定义以下定义A上关系上关系R：R=|x,yAx y(mod3)其中其中x y(mod3)叫做叫做x与与y模模3相等相等,即即x除以除以3余数与余数与y除以除以3余数相等余数相等.不难验证不难验证R为为A上等价关系上等价关系,因为因为 xA,有有x x(mod3)x,yA,若若x y(mod3),则有则有y x(mod3)x,y,zA,若若x y(mod3),y z(mod3),则有则有x z(mod3)第3页图6模3等价关系关系图图6第4页二、等价类及其性质二、等价类及其性质1等价类等价类 定义定义7.16 设设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即即A中全部和中全部和x有有R关系元素集合。关系元素集合。第5页2等价类性质等价类性质 定理定理7.14 设设R是非空集合是非空集合A上上等价关系等价关系,则则（1）x A,x是是A非空子集非空子集.（2）x,y A,假如假如xRy,则则 x=y.（3）x,y A,假如假如x y,则则 x与与y不交不交.（4）x|x A=A第6页三、商集与集合划分三、商集与集合划分 1.定义定义7.17设设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,6A关于恒等关系和全域关系商集为：关于恒等关系和全域关系商集为：A/IA=1,2,8A/EA=1,2,8第7页2集合划分集合划分定义定义7.18设设A为非空集合为非空集合,若若A子集族子集族(P(A)满足下面条件：满足下面条件：（1）（2）x y(x,y xyxy=)（3）=A则称则称是是A一个划分一个划分,称称中元素为中元素为A划分块划分块第8页例例设设Aa,b,c,d,给定给定1,2,3,4,5,6以下：以下：1=a,b,c,d2=a,b,c,d3=a,a,b,c,d4=a,b,c5=,a,b,c,d6=a,a,b,c,d则则1和和2是是A划分划分,其它都不是其它都不是A划分划分.第9页四、商集与划分对应关系四、商集与划分对应关系商集商集A/R就是就是A一个划分一个划分,不一样商集对应于不一样不一样商集对应于不一样划分划分.任给任给A一个划分一个划分,以下定义以下定义A上关系上关系R：R=|x,y Ax与与y在在同一划分块中同一划分块中则则R为为A上等价关系上等价关系,且该等价关系所确定商集就且该等价关系所确定商集就是是.A上等价关系与上等价关系与A划分是一一对应划分是一一对应.第10页例例给出给出A1,2,3上全部等价关系上全部等价关系解解以下列图以下列图,先做出先做出A全部全部划分划分,从左到右分别记作从左到右分别记作1,2,3,4,5.123图7第11页这些划分与这些划分与A上上等价关系等价关系之间一一对应是：之间一一对应是：4对应于对应于全域关系全域关系EA,5对应于对应于恒等关系恒等关系IA,1,2和和3分别对应于等价关系分别对应于等价关系R1,R2和和R3.其中其中R1=,IAR2=,IAR3=,IA第12页附录：等价关系在计算机科学中应用附录：等价关系在计算机科学中应用关系概念对计算机科学理论和应用都非常主要，复关系概念对计算机科学理论和应用都非常主要，复合数据结构、如陈列表、树等，用来表示数据集合，这合数据结构、如陈列表、树等，用来表示数据集合，这些数据是由元素间关系联络。关系是数学模型一部分，些数据是由元素间关系联络。关系是数学模型一部分，它经常在数据结构内隐含地表达出来，数值应用、信息它经常在数据结构内隐含地表达出来，数值应用、信息检索、网络问题等就是关系应用领域，因而关系运算和检索、网络问题等就是关系应用领域，因而关系运算和处理是主要。关系在包含程序结构和算法分析理论方面处理是主要。关系在包含程序结构和算法分析理论方面也有主要作用。也有主要作用。例：在信息检索系统中，全部生物集合例：在信息检索系统中，全部生物集合X可分割成可分割成P，A，P表示全部植物集合，表示全部植物集合，A表示全部动物集合；表示全部动物集合；也可组成也可组成E，F，E表示史前生物，表示史前生物，F表示史后生物，其表示史后生物，其交叉划分交叉划分Q=PE,P F,A E,A FE,P F,A E,A F第13页第七节 偏序关系第14页一、偏序关系一、偏序关系1定义定义7.19 偏序关系偏序关系：非空集合：非空集合A上上自反自反、反对称反对称和和传递传递关关系，记作系，记作.设设 为偏序关系为偏序关系,假如假如,则记作则记作x y,读作读作x“小于或等于小于或等于”y.2.实例实例集合集合A上恒等关系上恒等关系IA是是A上偏序关系上偏序关系.小于或等于关系小于或等于关系,整除关系和包含关系也是对应集整除关系和包含关系也是对应集合上偏序关系合上偏序关系.第15页3相关概念相关概念定义定义7.20设设R为非空集合为非空集合A上偏序关系上偏序关系,x,yA,x与与y可比可比x yy x.任取两个元素任取两个元素x和和y,可能有下述几个情况发生：可能有下述几个情况发生：x y(或或y x),xy,x与与y不是可比不是可比.定义定义7.21R为非空集合为非空集合A上偏序关系上偏序关系,x,yA,x与与y都是可比，则称都是可比，则称R为为全序（或线序）全序（或线序）第16页实例：数集上小于或等于关系是全序关系实例：数集上小于或等于关系是全序关系整除关系不是正整数集合上全序关系整除关系不是正整数集合上全序关系 定义定义7.22x,yA,假如假如x y且不存在且不存在zA使得使得x z y,则则称称y覆盖覆盖x.比如比如1,2,4,6集合上整除关系集合上整除关系2覆盖覆盖1,4和和6覆盖覆盖2.但但4不覆盖不覆盖1.第17页二、偏序集与哈斯图二、偏序集与哈斯图1偏序集偏序集定义定义7.23集合集合A和和A上偏序关系上偏序关系 一起叫做偏序集一起叫做偏序集,记作记作.实例：实例：整数集合整数集合Z和数小于或等于关系和数小于或等于关系组成偏序集组成偏序集集合集合A幂集幂集P(A)和包含关系和包含关系R 组成偏序集组成偏序集.第18页2哈斯图哈斯图利用偏序关系自反、反对称、传递性进行简化关系图利用偏序关系自反、反对称、传递性进行简化关系图特点：特点：每个结点没有环每个结点没有环两个连通结点之间序关系经过结点位置高两个连通结点之间序关系经过结点位置高 低表示，位置低元素次序在前低表示，位置低元素次序在前含有覆盖关系两个结点之间连边含有覆盖关系两个结点之间连边第19页三、偏序集中特殊元素.1.最小元、最大元、极小元、极大元最小元、最大元、极小元、极大元定义7.24设为偏序集,BA,yB.（1）若x(xByx)成立,则称y为B最小元.（2）若x(xBxy)成立,则称y为B最大元.（3）若x(xBxyx=y)成立,则称y为B极小元.（4）若x(xByxx=y)成立,则称y为B极大元.性质：对于有穷集，极小元和极大元一定存在，还可能存在多个.最小元和最大元不一定存在，假如存在一定惟一.最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元.第20页2下界、上界、下确界（最大下界）、上确界（最下界、上界、下确界（最大下界）、上确界（最小上界）小上界）定义定义7.25设为偏序集,BA,yA.（1）若x(xBxy)成立,则称y为B上界.（2）若x(xByx)成立,则称y为B下界.（3）令Cy|y为B上界,则称C最小元为B最小上界或上确界.（4）令Dy|y为B下界,则称D最大元为B最大下界或下确界.性质：性质：下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下确界、上确界假如存在，则惟一 集合最小元就是它下确界，最大元就是它 上确界；反之不对.第21页12 84610例例画出画出和和哈斯哈斯图，并指出其中特殊元。图，并指出其中特殊元。解：解：(1)哈斯图以下：哈斯图以下：92513711由图可知由图可知1为最小元，没有最大元；为最小元，没有最大元；7,8,9,10,11,12均为极大元，极小元为均为极大元，极小元为1；1为为1,2,12下界，也是下确界；下界，也是下确界；1,2,12中没有上确界或上界。中没有上确界或上界。第22页(2)哈斯图以下：哈斯图以下：P(a,b,c)=,a,b,c,a,b,a,c,b,c,a,b,ca,b,ca,ca,bb,cca b由图可知：由图可知：为为P(a,b,c)最小元，最小元，a,b,c为它最为它最大元；大元；同时同时，a,b,c也分别为它也分别为它们极小元和极大元、下确界和上确界。们极小元和极大元、下确界和上确界。第23页abcde例例已知偏序集已知偏序集哈斯图以下：哈斯图以下：hgf试写出对应试写出对应A和和A上偏序关系上偏序关系R，第24页,解：解：A=a,b,c,d,e,f,g,hR=,abcdehgf,第25页例 设偏序集以下列图所示，求A极小元、最小元、极大元、最大元.设Bb,c,d,求B下界、上界、下确界、上确界.图10 解极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B下界和最大下界都不存在,上界有d和f,最小上界为d.第26页例：画出集合例：画出集合S=1,2,3,4,5,6在偏序关系在偏序关系“整除整除”下下哈斯图，并讨论：哈斯图，并讨论：a)写出写出1,2,3,4,5,6极大（小）元，最大（小）元，极大（小）元，最大（小）元，b)分别写出分别写出2,3,6及及2,3,5上界，下界，上确界，上界，下界，上确界，c)下确界。下确界。解：设解：设为整除关系：为整除关系：“”=,在偏序集在偏序集中，中，COV（S）=,第27页COV（S）=,123546极大元：极大元：4，5，6极小元：极小元：1最大元：没有最大元：没有最小元：最小元：12,3,6上（确）界：上（确）界：6下（确）界：下（确）界：12,3,5上（确上（确)界界:无无下（确）界：下（确）界：1第28页序关系在项目管理中应用（实例：调度问题）序关系在项目管理中应用（实例：调度问题）假设一个项目由假设一个项目由20个任务组成，一些任务只能在其它个任务组成，一些任务只能在其它任务结束之后完成，怎么找到关于这些项目标次序？任务结束之后完成，怎么找到关于这些项目标次序？假如只有一台机器，而且每项任务截止时间没有限假如只有一台机器，而且每项任务截止时间没有限制，则对这个问题可用拓扑排序来处理。制，则对这个问题可用拓扑排序来处理。所谓拓扑排序：将原来偏序集所谓拓扑排序：将原来偏序集扩张成一个对扩张成一个对应全序集应全序集。所认为了结构该问题求解模型，我们首先建立任务所认为了结构该问题求解模型，我们首先建立任务集合上部分序集，使得集合上部分序集，使得ab当且仅当当且仅当a和和b是任务且是任务且直到直到a结束后结束后b才能开始。才能开始。例：例：P129图图7.97.10第29页第八节第八节 习题课习题课 1主要内容主要内容有序对与笛卡儿积定义与性质有序对与笛卡儿积定义与性质二元关系、从二元关系、从A到到B关系、关系、A上关系上关系关系表示法：关系表示式、关系矩阵、关系图关系表示法：关系表示式、关系矩阵、关系图关系运算：定义域、值域、域、逆、合成、限制、关系运算：定义域、值域、域、逆、合成、限制、像、幂关系运算性质像、幂关系运算性质A上关系自反、反自反、对称、反对称、传递性质上关系自反、反自反、对称、反对称、传递性质A上关系自反、对称、传递闭包上关系自反、对称、传递闭包A上等价关系、等价类、商集与上等价关系、等价类、商集与A划分划分A上偏序关系与偏序集上偏序关系与偏序集第30页2要求：要求：基本概念要清楚基本概念要清楚熟练掌握关系三种表示法熟练掌握关系三种表示法能够判定关系性质（等价关系或偏序关系）能够判定关系性质（等价关系或偏序关系）掌握含相关系运算集合等式掌握含相关系运算集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念集等概念第31页 以下基本运算要熟练以下基本运算要熟练A B,domR,ranR,fldR,R 1,R S,Rn,r(R),s(R),t(R)求等价类和商集求等价类和商集A/R给定给定A划分划分，求出，求出 所对应等价关系所对应等价关系求偏序集中极大元、极小元、最大元、最小元、上界、求偏序集中极大元、极小元、最大元、最小元、上界、下界、上确界、下确界下界、上确界、下确界掌握基本证实方法掌握基本证实方法证实包括关系运算集合等式证实包括关系运算集合等式证实关系性质、证实关系是等价关系或偏序关系证实关系性质、证实关系是等价关系或偏序关系第32页2设设A=1,2,3,4，在，在A A上定义二元关系上定义二元关系R：,R x+y=u+v，求求R导出划分导出划分.解解A A=,依据有序对依据有序对中中x+y=2,3,4,5,6,7,8将将A划分成等价划分成等价类：类：A/R=,第33页4设偏序集设偏序集哈斯图如图所表示哈斯图如图所表示.（1）写出）写出A和和R集合表示式集合表示式（2）求该偏序集中极大元、极小元、最大元）求该偏序集中极大元、极小元、最大元最小元最小元第34页主要内容主要内容函数定义函数定义函数性质函数性质函数逆函数逆函数合成函数合成与后面各章关系与后面各章关系是代数系统基础是代数系统基础第八章第八章 函数函数注：因时间关系只讲函数定义和性质。注：因时间关系只讲函数定义和性质。第35页一、函数定义与相关概念一、函数定义与相关概念1函数定义函数定义定义定义8.1设设F为为二元关系二元关系,若若 xdomF都存在都存在唯一唯一yranF使使xFy成立成立,则称则称F为函数为函数对于函数对于函数F,假如有假如有xFy,则记作则记作y=F(x),并称并称y为为F在在x值值.例例F1=,F2=,F1是函数是函数,F2不是函数不是函数第36页二函数性质二函数性质定义定义8.6设设f：AB,（1）若）若ranf=B,则称则称f：AB是满射是满射.（2）若）若 yranf都存在唯一都存在唯一xA使得使得f(x)=y,则称则称f：AB是单射是单射.（3）若）若f：AB既是满射又是单射既是满射又是单射,则称则称 f：AB是双射是双射第37页例例判断下面函数是否为单射判断下面函数是否为单射,满射满射,双射双射,为何为何?（1）f：RR,f(x)=x2+2x 1（2）f：RZ,f(x)=x（3）f：RR,f(x)=2x+1（4）f：R+R+,f(x)=(x2+1)/x,其中其中R+为为正实数集正实数集.第38页解（解（1）f：RR,f(x)=x2+2x 1在在x=1取得极大值取得极大值0.既不是单射也不是满射既不是单射也不是满射.（2）f：RZ,f(x)=x 是满射是满射,但不是单射但不是单射,比如比如f(1.5)=f(1.2)=1.（3）f：RR,f(x)=2x+1是满射、单射、双射是满射、单射、双射,因为它是单调函数而且因为它是单调函数而且ranf=R.（4）f：R+R+,f(x)=(x2+1)/x有极小值有极小值f(1)=2.该函数既不是单射也不是满射该函数既不是单射也不是满射.第39页三、练习三、练习1对对给给定定A,B和和f,判判断断是是否否组组成成函函数数f：AB.假假如如是是,说说 明明 f：AB是是 否否 为为 单单 射射、满满 射射、双双 射射.（1）A=1,2,3,4,5,B=6,7,8,9,10,f=,.（2）A,B同同(1),f=,.（3）A,B同同(1),f=,.（4）A=B=R,f(x)=x3.第40页解（1）能组成）能组成f：AB,f：AB既不是单射也不是满射既不是单射也不是满射,因为因为f(3)=f(5)=9,且且7 ranf.（2）不能组成）不能组成f：AB,因为因为f不是函数不是函数.f且且 f,与函数定义矛盾与函数定义矛盾.（3）不能组成）不能组成f：AB,因为因为domf=1,2,3,4 A.（4）能组成）能组成f：AB,且且f：AB是双射是双射.第41页