离散数学等价偏序函数.

第六节等价关系与划分主要内容等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应一、等价关系的定义与实例定义7.15设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若x,y∈R,称x等价于y,记做x～y.在我们日常生活和学习中，就有一些等价关系的例子，如：（1）在一群人的集合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。（2）命题公式间的逻辑等值关系是等价关系。（3）集合上的恒等关系是等价关系。（4）在同一平面上直线之间的平行关系，三角形之间的相似关系都是等价关系。实例设A={1,2,…,8},如下定义A上的关系R：R={x,y|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.不难验证R为A上的等价关系,因为x∈A,有x≡x(mod3)x,y∈A,若x≡y(mod3),则有y≡x(mod3)x,y,z∈A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)图6模3等价关系的关系图图6x二、等价类及其性质1．等价类定义7.16设R为非空集合A上的等价关系,x∈A，令[x]R={y|y∈A∧xRy}称[x]R为x关于R的等价类,简称为x的等价类,简记为[x]或.A={1,2,…,8}上模3等价关系的等价类：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[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,如果xy,则[x]与[y]不交.（4）∪{[x]|xA}=A三、商集与集合的划分1.定义7.17设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R={[x]R|x∈A}实例设A={1,2,…,8}，A关于模3等价关系R的商集为A/R={{1,4,7},{2,5,8},{3,6}}A关于恒等关系和全域关系的商集为：A/IA={{1},{2},…,{8}}A/EA={{1,2,…,8}}2．集合的划分定义7.18设A为非空集合,若A的子集族π(πP(A))满足下面条件：（1）π（2）xy(x,yπ∧x≠y→x∩y=)（3）∪π=A则称π是A的一个划分,称π中的元素为A的划分块例设A＝{a,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,y|x,yA∧x与y在π的同一划分块中}则R为A上的等价关系,且该等价关系所确定的商集就是π.A上的等价关系与A的划分是一一对应的.例给出A＝{1,2,3}上所有的等价关系如下图,先做出A的所有划分,从左到右分别记作π1,π2,π3,π4,π5.12312345图7这些划分与A上的等价关系之间的一一对应是：π4对应于全域关系EA,π5对应于恒等关系IA,π1,π2和π3分别对应于等价关系R1,R2和R3.其中R1={2,3,3,2}∪IAR2={1,3,3,1}∪IAR3={1,2,2,1}∪IA附录：等价关系在计算机科学中的应用关系概念对计算机科学的理论和应用都非常重要，复合的数据结构、如陈列表、树等，用来表示数据的集合，这些数据是由元素间的关系联系的。关系是数学模型的一部分，它常常在数据结构内隐含地体现出来，数值应用、信息检索、网络问题等就是关系的应用领域，因而关系的运算和处理是重要的。关系在包括程序结构和算法分析的理论方面也有重要的作用。例：在信息检索系统中，所有生物的集合X可分割成{P，A}，P表示所有植物集合，A表示所有动物集合；也可构成{E，F}，E表示史前生物，F表示史后生物，其交叉划分Q={P∩E,P∩F,A∩E,A∩F}主要内容：偏序关系偏序关系的定义偏序关系的实例偏序集与哈斯图偏序集中的特殊元素及其性质极大元、极小元、最大元、最小元上界、下界、最小上界、最大下界第七节偏序关系一、偏序关系1．定义7.19偏序关系：非空集合A上的自反、反对称和传递的关系，记作≼.设≼为偏序关系,如果x,y∈≼,则记作x≼y,读作x“小于或等于”y.2.实例集合A上的恒等关系IA是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.3．相关概念定义7.20设R为非空集合A上的偏序关系,x,y∈A,x与y可比x≼y∨y≼x.任取两个元素x和y,可能有下述几种情况发生：x≺y(或y≺x),x＝y,x与y不是可比的.定义7.21R为非空集合A上的偏序关系,x,y∈A,x与y都是可比的，则称R为全序（或线序）实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系定义7.22x,y∈A,如果x≺y且不存在z∈A使得x≺z≺y,则称y覆盖x.例如{1,2,4,6}集合上的整除关系2覆盖1,4和6覆盖2.但4不覆盖1.二、偏序集与哈斯图1．偏序集定义7.23集合A和A上的偏序关系≼一起叫做偏序集,记作A,≼.实例：整数集合Z和数的小于或等于关系≤构成偏序集Z,≤集合A的幂集P(A)和包含关系R构成偏序集P(A),R.2．哈斯图利用偏序关系的自反、反对称、传递性进行简化的关系图特点：每个结点没有环两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前具有覆盖关系的两个结点之间连边三、偏序集中的特殊元素.1.最小元、最大元、极小元、极大元定义7.24设A,≼为偏序集,BA,y∈B.（1）若x(x∈B→y≼x)成立,则称y为B的最小元.（2）若x(x∈B→x≼y)成立,则称y为B的最大元.（3）若x(x∈B∧x≼y→x=y)成立,则称y为B的极小元.（4）若x(x∈B∧y≼x→x=y)成立,则称y为B的极大元.性质：对于有穷集，极小元和极大元一定存在，还可能存在多个.最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元.2．下界、上界、下确界（最大下界）、上确界（最小上界）定义7.25设A,≼为偏序集,BA,y∈A.（1）若x(x∈B→x≼y)成立,则称y为B的上界.（2）若x(x∈B→y≼x)成立,则称y为B的下界.（3）令C＝{y|y为B的上界},则称C的最小元为B的最小上界或上确界.（4）令D＝{y|y为B的下界},则称D的最大元为B的最大下界或下确界.性质：下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下确界、上确界如果存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确界；反之不对.1284610例画出{1,2,…,12},R整除和P({a,b,c}),R的哈斯图，并指出其中的特殊元。解：(1){1,2,…,12},R整除的哈斯图如下：92513711由图可知1为最小元，没有最大元；7,8,9,10,11,12均为极大元，极小元为1；1为{1,2,…,12}的下界，也是下确界；{1,2,…,12}中没有上确界或上界。(2)P({a,b,c}),R的哈斯图如下：P({a,b,c})={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}{a,b,c}{a,c}{a,b}{b,c}{c}{a}{b}由图可知：为P({a,b,c})的最小元，{a,b,c}为它的最大元；同时，{a,b,c}也分别为它们的极小元和极大元、下确界和上确界。abcde例已知偏序集A，≼的哈斯图如下：hgf试写出对应的A和A上的偏序关系R，a,a,b,b,c,c,d,d,e,e,f,f,g,g,h,h}解：A={a,b,c,d,e,f,g,h}R={a,c,a,d,a,e,abcdehgfb,c,b,d,b,e,c,e,d,e,f,g,例设偏序集A,≼如下图所示，求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、下确界、上确界.图10解极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在,上界有d和f,最小上界为d.例：画出集合S={1,2,3,4,5,6}在偏序关系“整除”下的哈斯图，并讨论：a)写出{1,2,3,4,5,6}的极大（小）元，最大（小）元，b)分别写出{2,3,6}及{2,3,5}的上界，下界，上确界，下确界。解：设≤为整除关系：“≤”={1,2,1,3,1,4,1,5,1,6,2,4,2,6,3,61,1,2,2,3,3,4,4,5,5,6,6}在偏序集S,≤中，COV（S）={1,2,1,3,1,5,2,4,2,6,3,6}COV（S）={1,2,1,3,1,5,2,4,2,6,3,6}1○○○○○○23546极大元：4，5，6极小元：1最大元：没有最小元：1{2,3,6}的上（确）界：6下（确）界：1{2,3,5}的上（确)界:无下（确）界：1序关系在项目管理中的应用（实例：调度问题）假设一个项目由20个任务构成，某些任务只能在其他任务结束之后完成，怎么找到关于这些项目的顺序？如果只有一台机器，而且每项任务的截止时间没有限制，则对这个问题可用拓扑排序来解决。所谓拓扑排序：将原来的偏序集A,R扩张成一个对应的全序集A,R’。所以为了构造该问题的求解模型，我们首先建立任务集合上的部分序集，使得a≤b当且仅当a和b是任务且直到a结束后b才能开始。例：P129图7.97.10第八节习题课1．主要内容有序对与笛卡儿积的定义与性质二元关系、从A到B的关系、A上的关系关系的表示法：关系表达式、关系矩阵、关系图关系的运算：定义域、值域、域、逆、合成、限制、像、幂关系运算的性质A上关系的自反、反自反、对称、反对称、传递的性质A上关系的自反、对称、传递闭包A上的等价关系、等价类、商集与A的划分A上的偏序关系与偏序集2．要求：基本概念要清楚熟练掌握关系的三种表示法能够判定关系的性质（等价关系或偏序关系）掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念以下基本运算要熟练AB,domR,ranR,fldR,R1,RS,Rn,r(R),s(R),t(R)求等价类和商集A/R给定A的划分，求出所对应的等价关系求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界掌握基本的证明方法证明涉及关系运算的集合等式证明关系的性质、证明关系是等价关系或偏序关系2．设A={1,2,3,4}，在AA上定义二元关系R：x,y,u,vRx+y=u+v，求R导出的划分.解AA={1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4}根据有序对x,y中的x+y=2,3,4,5,6,7,8将A划分成等价类：A/R={{1,1},{1,2,2,1},{1,3,2,2,3,1},{1,4,2,3,3,2,4,1},{2,4,3