离散数学等价偏序函数

1、第六节第六节 等价关系与划分等价关系与划分主要内容等价关系的定义与实例等价类及其性质商集与集合的划分 等价关系与划分的一一对应 一、等价关系的定义与实例一、等价关系的定义与实例定义定义7.15 设设R为非空集合上的关系为非空集合上的关系. 如果如果R是自反的、对是自反的、对称的和传递的称的和传递的, 则称则称R为为A上的等价关系上的等价关系. 设设R是一个等价是一个等价关系关系, 若若R, 称称x等价于等价于y, 记做记做xy.在我们日常生活和学习中，就有一些等价关系的例子，在我们日常生活和学习中，就有一些等价关系的例子，如：如： （1）在一群人的集合上年龄相等的关系是等价关系，）在一群人的集

2、合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。而朋友关系不一定是等价关系，因为它可能不是传递的。 （2）命题公式间的逻辑等值关系是等价关系。）命题公式间的逻辑等值关系是等价关系。 （3）集合上的恒等关系是等价关系。）集合上的恒等关系是等价关系。 （4）在同一平面上直线之间的平行关系，三角形之间的）在同一平面上直线之间的平行关系，三角形之间的相似关系都是等价关系。相似关系都是等价关系。实例实例 设设A=1,2,8, 如下定义如下定义A上的关系上的关系R： R=| x,yAx y(mod 3)其中其中x y(mod 3)叫做叫做x与与y模模3相等相等, 即即x除以

3、除以3的余数与的余数与y除以除以3的余数相等的余数相等. 不难验证不难验证R为为A上的等价关系上的等价关系, 因为因为 xA, 有有x x(mod 3) x,yA, 若若x y(mod 3), 则有则有y x(mod 3) x,y,zA, 若若x y(mod 3), y z(mod 3), 则有则有x z(mod 3)图6模3等价关系的关系图图6x二、等价类及其性质二、等价类及其性质 1 等价类等价类 定义定义7.16 设设R为非空集合为非空集合A上的等价关系上的等价关系, xA，令，令 xR = y | yAxRy称称xR为为x关于关于R的等价类的等价类, 简称为简称为x的等价类的等价类,

4、简记为简记为x或或.A=1, 2, , 8上模上模3等价关系的等价类：等价关系的等价类：1 = 4 = 7 = 1, 4, 72 = 5 = 8 = 2, 5, 83 = 6 = 3, 6即即A中所有和中所有和x有有R关系的元素的集合。关系的元素的集合。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三、商集与集合的划分三、商集与集合的划分 1.

5、 定义定义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, , 8 A/EA = 1,2,82集合的划分集合的划分 定义定义7.18 设设A为非空集合为非空集合, 若若A的子集族的子集族( P(A)满足下面条件：满足下面条

6、件：（1） （2） x y(x,y xyxy=)（3） = A则称则称是是A的一个划分的一个划分, 称称中的元素为中的元素为A的划分块的划分块 例例 设设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的划分的划分. 四、商集与划分的对应关系四、商集与划分的对应关系商集商集A/R就是就是A的一个划分的一个划分, 不同的商集对应于不同不同的商集对应于不同的划分的划分. 任给任给A的一个划分的一

7、个划分, 如下定义如下定义A上的关系上的关系R： R=| x,y Ax与与y在在的同一划分块中的同一划分块中 则则R为为A上的等价关系上的等价关系, 且该等价关系所确定的商集就且该等价关系所确定的商集就是是. A上的等价关系与上的等价关系与A的划分是一一对应的的划分是一一对应的. 例例 给出给出A1,2,3上所有的等价关系上所有的等价关系解解 如下图如下图, 先做出先做出A的所有的所有划分划分, 从左到右分别记作从左到右分别记作1,2,3,4,5.123图7这些划分与这些划分与A上的上的等价关系等价关系之间的一一对应是：之间的一一对应是：4对应于对应于全域关系全域关系EA, 5对应于对应于恒等

8、关系恒等关系IA, 1,2和和3分别对应于等价关系分别对应于等价关系R1, R2和和R3. 其中其中 R1=,IAR2=,IAR3=,IA附录：等价关系在计算机科学中的应用附录：等价关系在计算机科学中的应用 关系概念对计算机科学的理论和应用都非常重要，关系概念对计算机科学的理论和应用都非常重要，复合的数据结构、如陈列表、树等，用来表示数据的集复合的数据结构、如陈列表、树等，用来表示数据的集合，这些数据是由元素间的关系联系的。关系是数学模合，这些数据是由元素间的关系联系的。关系是数学模型的一部分，它常常在数据结构内隐含地体现出来，数型的一部分，它常常在数据结构内隐含地体现出来，数值应用、信息检索

9、、网络问题等就是关系的应用领域，值应用、信息检索、网络问题等就是关系的应用领域，因而关系的运算和处理是重要的。关系在包括程序结构因而关系的运算和处理是重要的。关系在包括程序结构和算法分析的理论方面也有重要的作用。和算法分析的理论方面也有重要的作用。例：在信息检索系统中，所有生物的集合例：在信息检索系统中，所有生物的集合X可分割成可分割成P，A，P表示所有植物集合，表示所有植物集合，A表示所有动物集合；表示所有动物集合；也可构成也可构成E，F，E表示史前生物，表示史前生物，F表示史后生物，表示史后生物，其交叉划分其交叉划分Q=P E,P F,A E,A FE,P F,A E,A F第七节 偏序关

10、系一、偏序关系一、偏序关系 1定义定义7.19 偏序关系偏序关系：非空集合：非空集合A上的上的自反自反、反对称反对称和和传递传递的关系，记作的关系，记作 .设设 为偏序关系为偏序关系, 如果如果 , 则记作则记作x y, 读作读作x“小于或等于小于或等于”y. 2. 实例实例集合集合A上的恒等关系上的恒等关系IA是是A上的偏序关系上的偏序关系. 小于或等于关系小于或等于关系, 整除关系和包含关系也是相应集整除关系和包含关系也是相应集合上的偏序关系合上的偏序关系. 3相关概念相关概念定义定义7.20 设设R为非空集合为非空集合A上的偏序关系上的偏序关系, x,yA, x与与y可比可比 x yy

11、x. 任取两个元素任取两个元素x和和y, 可能有下述几种情况发生：可能有下述几种情况发生： x y(或或y x), xy, x与与y不是可比的不是可比的.定义定义7.21 R为非空集合为非空集合A上的偏序关系上的偏序关系, x,yA, x与与y都是可比的，则称都是可比的，则称R为为全序（或线序）全序（或线序）实例：数集上的小于或等于关系是全序关系实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系整除关系不是正整数集合上的全序关系 定义定义7.22 x,yA, 如果如果x y且不存在且不存在zA使得使得x z y, 则称则称y覆盖覆盖x.例如例如1,2,4,6集合上的整除关

12、系集合上的整除关系2覆盖覆盖1, 4和和6覆盖覆盖2. 但但4不覆盖不覆盖1. 二、偏序集与哈斯图二、偏序集与哈斯图1偏序集偏序集定义定义7.23 集合集合A和和A上的偏序关系上的偏序关系 一起叫做偏序集一起叫做偏序集, 记记作作.实例：实例：整数集合整数集合Z和数的小于或等于关系和数的小于或等于关系构成偏序集构成偏序集集合集合A的幂集的幂集P(A)和包含关系和包含关系R 构成偏序集构成偏序集. 2哈斯图哈斯图利用偏序关系的自反、反对称、传递性进行简化的关利用偏序关系的自反、反对称、传递性进行简化的关系图系图特点：特点：每个结点没有环每个结点没有环两个连通的结点之间的序关系通过结点位置的高两个

13、连通的结点之间的序关系通过结点位置的高 低表示，位置低的元素的顺序在前低表示，位置低的元素的顺序在前具有覆盖关系的两个结点之间连边具有覆盖关系的两个结点之间连边三、偏序集中的特殊元素.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的极大元. 性质：对于有穷集，极小元和极大元一定存在，还可能存在多个. 最小元和最大元不一定存在，如果

14、存在一定惟一.最小元一定是极小元；最大元一定是极大元. 孤立结点既是极小元，也是极大元.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的最大下界或下确界.性质：性质：下界、上界、下确界、上确界不一定存在 下界、上界存在不一定惟一 下确界、上确界如果存在，则惟一 集合的最小元就

15、是它的下确界，最大元就是它的 上确界；反之不对.12 84610例例 画出画出和和的哈的哈斯图，并指出其中的特殊元。斯图，并指出其中的特殊元。解：解： (1) 的哈斯图如下：的哈斯图如下：92513711由图可知由图可知1为最小元，没有最大元；为最小元，没有最大元；7,8,9,10,11, 12均为极大元，极小元为均为极大元，极小元为1；1为为1,2,12的下界，也是下确界；的下界，也是下确界；1,2,12中没有上确界或上界。中没有上确界或上界。(2) 的哈斯图如下：的哈斯图如下：P(a,b,c)= ,a,b,c,a,b,a,c,b,c,a,b,ca,b,ca,ca,bb,cca b由图可知：

16、由图可知： 为为P(a,b,c)的最小元，的最小元，a,b,c为它的为它的最大元；最大元；同时同时 ，a,b,c也分别为它们也分别为它们的极小元和极大元、下确界和上确界。的极小元和极大元、下确界和上确界。abcde例例 已知偏序集已知偏序集的哈斯图如下：的哈斯图如下：hgf 试写出对应的试写出对应的A和和A上的偏序关系上的偏序关系R ，, , , , ,解：解： A = a,b,c,d,e,f, g,hR = ,abcdehgf, ,例 设偏序集如下图所示，求A的极小元、最小元、极大元、最大元. 设Bb,c,d, 求B的下界、上界、下确界、上确界. 图10 解 极小元：a, b, c, g；

17、极大元：a, f, h；没有最小元与最大元. B的下界和最大下界都不存在, 上界有d和f, 最小上界为d. 例：画出集合例：画出集合S=1,2,3,4,5,6在偏序关系在偏序关系“整除整除”下下的哈斯图，并讨论：的哈斯图，并讨论：写出写出1,2,3,4,5,6的极大（小）元，最大（小）元，的极大（小）元，最大（小）元，分别写出分别写出2,3,6及及2,3,5的上界，下界，上确界，的上界，下界，上确界，a) 下确界。下确界。解：设解：设为整除关系：为整除关系：“”=,在偏序集在偏序集中，中，COV（S）=,COV（S）=,123546极大元：极大元：4，5，6极小元：极小元：1最大元：没有最大元

18、：没有 最小元：最小元：12,3,6的上（确）界：的上（确）界：6 下（确）界：下（确）界：12,3,5的上（确的上（确)界界:无无 下（确）界：下（确）界：1序关系在项目管理中的应用（实例：调度问题）序关系在项目管理中的应用（实例：调度问题）假设一个项目由假设一个项目由20个任务构成，某些任务只能在其他个任务构成，某些任务只能在其他任务结束之后完成，怎么找到关于这些项目的顺序？任务结束之后完成，怎么找到关于这些项目的顺序？如果只有一台机器，而且每项任务的截止时间没有限如果只有一台机器，而且每项任务的截止时间没有限制，则对这个问题可用拓扑排序来解决。制，则对这个问题可用拓扑排序来解决。所谓拓扑

19、排序：将原来的偏序集所谓拓扑排序：将原来的偏序集扩张成一个对扩张成一个对应的全序集应的全序集。所以为了构造该问题的求解模型，我们首先建立任务所以为了构造该问题的求解模型，我们首先建立任务集合上的部分序集，使得集合上的部分序集，使得ab当且仅当当且仅当a和和b是任务且是任务且直到直到a结束后结束后b才能开始。才能开始。例：例：P129 图图7.9 7.10第八节第八节 习题课习题课 1 主要内容主要内容有序对与笛卡儿积的定义与性质有序对与笛卡儿积的定义与性质二元关系、从二元关系、从A到到B的关系、的关系、A上的关系上的关系关系的表示法：关系表达式、关系矩阵、关系图关系的表示法：关系表达式、关系矩

20、阵、关系图关系的运算：定义域、值域、域、逆、合成、限制、关系的运算：定义域、值域、域、逆、合成、限制、像、幂关系运算的性质像、幂关系运算的性质A上关系的自反、反自反、对称、反对称、传递的性质上关系的自反、反自反、对称、反对称、传递的性质A上关系的自反、对称、传递闭包上关系的自反、对称、传递闭包A上的等价关系、等价类、商集与上的等价关系、等价类、商集与A的划分的划分A上的偏序关系与偏序集上的偏序关系与偏序集2要求：要求：基本概念要清楚基本概念要清楚熟练掌握关系的三种表示法熟练掌握关系的三种表示法 能够判定关系的性质（等价关系或偏序关系）能够判定关系的性质（等价关系或偏序关系）掌握含有关系运算的集

21、合等式掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念集等概念 以下基本运算要熟练以下基本运算要熟练A B, dom R, ranR, fldR, R 1, R S , Rn , r( R), s( R), t( R)求等价类和商集求等价类和商集A/R给定给定A的划分的划分 ，求出，求出 所对应的等价关系所对应的等价关系求偏序集中的极大元、极小元、最大元、最小元、上求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界界、下界、上确界、下确界 掌握基本的证明方法掌握基本的证明方法 证明涉及关系运算的集

22、合等式证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关证明关系的性质、证明关系是等价关系或偏序关系系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=, , , , , , , , , , , , , , 4设偏序集设偏序集 的哈斯图如图所示的哈斯图如图所示. （1）写出）写出A和和R的集合表达式的集合表达式 （2）求

23、该偏序集中的极大元、极小元、最大元）求该偏序集中的极大元、极小元、最大元最小元最小元 （1）A = a, b, c, d, e R = , , , , , , IA （2）极大元和最大元是a, 极小元是d, e；没有最小元. 主要内容主要内容函数的定义函数的定义函数的性质函数的性质函数的逆函数的逆函数的合成函数的合成与后面各章的关系与后面各章的关系是代数系统的基础是代数系统的基础 第八章第八章 函数函数注：因时间关系只讲函数定义和性质。注：因时间关系只讲函数定义和性质。一、函数的定义与相关概念一、函数的定义与相关概念1函数定义函数定义 定义定义8.1 设设F为为二元关系二元关系, 若若 xdo

24、mF都存在都存在唯一唯一的的yranF使使xFy成立成立, 则称则称F为函数为函数 对于函数对于函数F, 如果有如果有xFy, 则记作则记作y=F(x), 并称并称y为为F在在x的值的值. 例例 F1=, F2=, F1是函数是函数, F2不是函数不是函数二函数的性质二函数的性质 定义定义8.6 设设f：AB,（1）若）若ranf=B, 则称则称f：AB是满射的是满射的.（2）若）若 yranf都存在唯一的都存在唯一的xA使得使得f(x)=y, 则称则称f：AB是单射的是单射的.（3）若）若f：AB既是满射又是单射的既是满射又是单射的, 则称则称 f：AB是双射的是双射的例例 判断下面函数是否为单射判断