离散数学等价偏序函数

第六节 等价关系与划分,主要内容等价关系的定义与实例等价类及其性质商集与集合的划分 等价关系与划分的一一对应,一、等价关系的定义与实例定义7.15 设R为非空集合上的关系. 如果R是自反的、对称的和传递的, 则称R为A上的等价关系. 设R是一个等价关系, 若R, 称x等价于y, 记做xy.在我们日常生活和学习中，就有一些等价关系的例子，如： （1）在一群人的集合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。 （2）命题公式间的逻辑等值关系是等价关系。 （3）集合上的恒等关系是等价关系。 （4）在同一平面上直线之间的平行关系，三角形之间的相似关系都是等价关系。,实例 设A=1,2,8, 如下定义A上的关系R： R=| x,yAx y(mod 3)其中x y(mod 3)叫做x与y模3相等, 即x除以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等价关系的关系图,图6,2等价类的性质 定理7.14 设R是非空集合A上的等价关系, 则（1）xA, x是A的非空子集.（2）x,yA, 如果xRy, 则 x = y.（3）x,yA, 如果x y, 则 x与y不交.（4）x | xA=A,三、商集与集合的划分 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, , 8 A/EA = 1,2,8,2集合的划分 定义7.18 设A为非空集合, 若A的子集族( P(A)满足下面条件：（1） （2）xy(x,yxyxy=)（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的一个划分, 如下定义A上的关系R： R=| x,yAx与y在的同一划分块中 则R为A上的等价关系, 且该等价关系所确定的商集就是. A上的等价关系与A的划分是一一对应的.,例 给出A1,2,3上所有的等价关系解 如下图, 先做出A的所有划分, 从左到右分别记作1,2,3,4,5.,1,2,3,图7,这些划分与A上的等价关系之间的一一对应是：4对应于全域关系EA, 5对应于恒等关系IA, 1,2和3分别对应于等价关系R1, R2和R3.  其中 R1=,IAR2=,IAR3=,IA,附录：等价关系在计算机科学中的应用,关系概念对计算机科学的理论和应用都非常重要，复合的数据结构、如陈列表、树等，用来表示数据的集合，这些数据是由元素间的关系联系的。关系是数学模型的一部分，它常常在数据结构内隐含地体现出来，数值应用、信息检索、网络问题等就是关系的应用领域，因而关系的运算和处理是重要的。关系在包括程序结构和算法分析的理论方面也有重要的作用。例：在信息检索系统中，所有生物的集合X可分割成P，A，P表示所有植物集合，A表示所有动物集合；也可构成E，F，E表示史前生物，F表示史后生物，其交叉划分Q=P E,P F,A E,A F,第七节 偏序关系,一、偏序关系 1定义7.19 偏序关系：非空集合A上的自反、反对称和传递的关系，记作.设为偏序关系, 如果, 则记作xy, 读作x“小于或等于”y. 2. 实例集合A上的恒等关系IA是A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系.,3相关概念定义7.20 设R为非空集合A上的偏序关系, x,yA, x与y可比 xyyx. 任取两个元素x和y, 可能有下述几种情况发生： xy(或yx), xy, x与y不是可比的.定义7.21 R为非空集合A上的偏序关系, x,yA, x与y都是可比的，则称R为全序（或线序）,实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系,定义7.22 x,yA, 如果xy且不存在zA使得xzy, 则称y覆盖x.例如1,2,4,6集合上的整除关系,2覆盖1, 4和6覆盖2. 但4不覆盖1.,二、偏序集与哈斯图1偏序集定义7.23 集合A和A上的偏序关系一起叫做偏序集, 记作.,实例：整数集合Z和数的小于或等于关系构成偏序集集合A的幂集P(A)和包含关系R构成偏序集.,2哈斯图利用偏序关系的自反、反对称、传递性进行简化的关系图特点：每个结点没有环两个连通的结点之间的序关系通过结点位置的高 低表示，位置低的元素的顺序在前具有覆盖关系的两个结点之间连边,三、偏序集中的特殊元素. 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的极大元.,性质：对于有穷集，极小元和极大元一定存在，还可能存在多个. 最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元. 孤立结点既是极小元，也是极大元.,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的最大下界或下确界.,性质：下界、上界、下确界、上确界不一定存在 下界、上界存在不一定惟一 下确界、上确界如果存在，则惟一 集合的最小元就是它的下确界，最大元就是它的 上确界；反之不对.,例 画出和的哈斯图，并指出其中的特殊元。,解： (1) 的哈斯图如下：,由图可知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,c,由图可知： 为P(a,b,c)的最小元，a,b,c为它的最大元；,同时，a,b,c也分别为它们的极小元和极大元、下确界和上确界。,a,b,c,d,e,例 已知偏序集的哈斯图如下：,h,g,f,试写出对应的A和A上的偏序关系R，, , , , ,解： A = a,b,c,d,e,f, g,h,R = ,a,b,c,d,e,h,g,f, ,例 设偏序集如下图所示，求A的极小元、最小元、极大元、最大元. 设Bb,c,d, 求B的下界、上界、下确界、上确界.,图10,解 极小元：a, b, c, g； 极大元：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的上界，下界，上确界，下确界。,解：设为整除关系：“”=,在偏序集中，COV（S）=,COV（S）=,1,极大元：4，5，6极小元：1最大元：没有 最小元：1,2,3,6的上（确）界：6 下（确）界：1,2,3,5的上（确)界:无 下（确）界：1,序关系在项目管理中的应用（实例：调度问题）假设一个项目由20个任务构成，某些任务只能在其他任务结束之后完成，怎么找到关于这些项目的顺序？如果只有一台机器，而且每项任务的截止时间没有限制，则对这个问题可用拓扑排序来解决。所谓拓扑排序：将原来的偏序集扩张成一个对应的全序集。所以为了构造该问题的求解模型，我们首先建立任务集合上的部分序集，使得ab当且仅当a和b是任务且直到a结束后b才能开始。,例：P129 图7.9 7.10,第八节 习题课,1  主要内容有序对与笛卡儿积的定义与性质二元关系、从A到B的关系、A上的关系关系的表示法：关系表达式、关系矩阵、关系图关系的运算：定义域、值域、域、逆、合成、限制、像、幂关系运算的性质A上关系的自反、反自反、对称、反对称、传递的性质A上关系的自反、对称、传递闭包A上的等价关系、等价类、商集与A的划分A上的偏序关系与偏序集,2要求：基本概念要清楚熟练掌握关系的三种表示法 能够判定关系的性质（等价关系或偏序关系）掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念,以下基本运算要熟练AB, dom R, ranR, fldR, R1, RS , Rn , r( R), s( R), t( R)求等价类和商集A/R给定A的划分，求出所对应的等价关系求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界 掌握基本的证明方法 证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系,2设A=1,2,3,4，在AA上定义二元关系R：,>R x+y = u+v，求R导出的划分.,解 AA=, , , , , , , , , , , , , , , 根据有序对中的x+y=2,3,4,5,6,7,8将A划分成等价类： A/R=, , , , , , , , , , , , , , ,4设偏序集 的哈斯图如图所示. （1）写出A和R的集合表达式 （2）求该偏序集中的极大元、极小元、最大元最小元,主要内容函数的定义函数的性质函数的逆函数的合成与后面各章的关系是代数系统的基础,第八章 函数,注：因时间关系只讲函数定义和性质。,一、函数的定义与相关概念1函数定义 定义8.1 设F为二元关系, 若xdomF都存在唯一的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是双射的,例 判断下面函数是否为单射, 满射, 双射的, 为什么?（1）f：RR, f(x)= x2+2x1（2）f：RZ, f(x)=x（3）f：RR, f(x)=2x+1（4）f：R+R+, f(x)=(x2+1)/x, 其中R+为正实数集.,解（1）f：RR, f(x)=x2+2x1在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. 该函数既不是单射的也不是满射的.,三、练习 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.,解,（1）能构成f：AB,f：AB既不是单射也不是满射, 因为f(3)=f(5)=9, 且7ranf.（2）不能构成f：AB, 因为f不是函数. f且f, 与函数定义矛盾.（3）不能构成f：AB, 因为domf = 1,2,3,4 A.（4）能构成f：AB, 且f：AB是双射的.,