离散数学第四章：二元关系和函数.ppt

二元关系和函数,第四章,2,第4章 二元关系与函数,4.1 集合的笛卡儿积与二元关系4.2 关系的运算4.3 关系的性质4.4 关系的闭包4.5 等价关系和偏序关系4.6 函数的定义和性质4.7 函数的复合和反函数,3,4.1 集合的笛卡儿积和二元关系,有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示,4,有序对的性质：1）有序性（当x y时）2）与 相等的充分必要条件是=x=u y=v,例4.1=，求 x,y.解 3y 4=2,x+5=y y=2,x=3,4.1 二元关系的概念,1.有序对/序偶：由两个元素x和y按一定顺序排成二元组，记作：。其中x称作第一个元素；y称作第二个元素。,5,实例：1.空间直角坐标系中的坐标 是有序三元组2.图书馆记录是一个有序六元组.,2.有序n元组：一个有序 n(n3)元组 是一个有序对，其中第一个元素是一个有序 n-1元组，即,xn=。,我们将来的研究重点为有序二元组，即有序对/序偶,6,例4.2 A=1,2,3,B=a,b,c,C=AB=,BA=,AA=,AC=CA=,3.笛卡儿积：设A,B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对.所有这样的有序对组成的集合叫做 A与B 的笛卡儿积 记作AB,即 AB=|xA yB。,7,笛卡儿积的性质：1.不适合交换律 ABBA(AB,A,B)2.若A或B中有一个为空集，则AB就是空集.A=B=3.若|A|=m,|B|=n,则|AB|=mn 4.不适合结合律(AB)CA(BC)(A,B,C)例：A=1,B=2,C=3AB=,(AB)C=,3=BC=,A(BC)=,8,二元关系：集合中两个元素之间的某种关系例3 甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：，其中表示x胜y，它表示了集合甲,乙,丙中元素之间的一种胜负关系.例4 有A、B、C3个人和四项工作G1、G2、G3、G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2.那么，人和工作之间的对应关系可以记作 R,C,G2 它表示了工人集合A,B,C到工作集合G1,G2,G3,G4之间的关系,如R,可记作 xRy；如果R,则记作xR y实例：R1=,R2=,R3=,3,4，R4=|xNy ZR1,R2,R4是二元关系；R3不是二元关系。,4.二元关系：如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对(以有序对为 元素的集合)（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.,10,5.从A到B的关系与A上的关系设A,B为集合,AB的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做 A上的二元关系.,例5 A=0,1,B=1,2,3,R1=,R2=AB,R3=,R4=.那么 R1,R2,R3,R4是从 A 到 B 的二元关系,R3和R4同时也是 A上的二元关系.计数：|A|=n,|B|=m,|AB|=nm,AB的子集有 个.所以 A到B上有 个不同的二元关系.|A|=n,|AA|=,AA的子集有 个.所以 A上有 个不同的二元关系.例如|A|=3,则 A上有512个不同的二元关系.,11,A上重要关系的实例,设 A 为任意集合，是 A 上的关系，称为空关系EA,IA 分别称为全域关系与恒等关系，定义如下：EA=|xAyA=AA IA=|xA例如,A=1,2,则 EA=,IA=,注：IA;IA,12,A上重要关系的实例（续）,小于等于关系 LA,整除关系DA,包含关系R定义：LA=|x,yAxy,DA=|x,yAx整除y,R=|x,yP(A)xy,A是某集合.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.,13,实例,例如 A=1,2,3,B=a,b,则 LA=,DA=,P(B)=,a,b,a,b,则 B上的包含关系是 R=,14,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=x1,x2,xm，B=y1,y2,yn，R是从A到B的关系，以A元素为行，B元素为列，MR=rij mn,其中 rij=1 R，否则rij=0。关系图：若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,以A中元素为结点，如果 R，则从 xi 到 xj 有一条有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图仅适于表示A上的关系,15,实例,A=1,2,3,4,R=,R的关系矩阵MR和关系图GR如下：习题：4.1,练习,1.令A=1,2,3;B=a,b,求R1=,的关系矩阵。2.令A=1,2,3;求R2=,的关系图。3.令F=,，G=,求FG,GF,FF。（方法自选）,17,基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质,4.2 关系的运算,4.2 关系的运算,关系R的定义域：domR=x|(y)R(即R中有序组的第一个元素构成的集合),关系R的值域：ranR=y|(x)R(即R中有序组的第二个元素构成的集合),一、关系的定义域与值域,关系R的域：fldR=domR ranR,19,关系的基本运算定义,例1 R=,则 domR=1,2,4 ranR=2,3,4 fldR=1,2,3,4,20,关系的基本运算定义（续）,R1=|R RS=|z(S R)例2 R=,S=,R1=,RS=,SR=,二.逆与合成,21,合成运算的图示方法,利用图示（不是关系图）方法求合成 R=,S=,RS=,SR=,R,S,S,R,S RR S,22,实例 R=,R1=,R1=2,4 R1,2=,R=R1,2=2,4,三 限制和像：已知二元关系F 和集合A F 在A上的限制 FA=|xFy xA A 在F下的像 FA=ran(FA),注意：,FAF,FA ranF,23,四.关系运算的基本性质,(1),(2),(3)不满足交换律：F GG F,(4)满足结合律：F G H=F(G H),(5),25,五.A上关系的幂运算,设R为A上的关系,n为自然数,则 R 的 n次幂定义为：(1)R0=|xA=IA(2)Rn+1=Rn R 注意：对于A上的任何关系R1和R2都有 R10=R20=IA 对于A上的任何关系 R 都有 R1=R,26,(1)定义法：对于集合表示的关系R，计算 Rn 就是n个R左复合.(2)矩阵乘法：矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.（线性代数，逻辑乘法）(3)关系图法：若点a经k(k=1,2,n)条线可到达点b，则在 的关系图上，a到b有线相连。例3 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为,六.幂的求法：,27,同理，R0=IA,R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=,R3=R5=R7=,28,R0,R1,R2,R3,的关系图如下图所示,关系图法,结论：仅当A有回路时，上述结论成立。,当图中没有回路时：,30,七.幂的性质：,当关系图有回路时：,(2),(3),31,证明（2）：用数学归纳法 若n=0,则有 RmR0=RmIA=Rm=Rm+0 假设RmRn=Rm+n,则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1。,幂运算的性质（续）,证明（3）：若n=0,则有 假设 则有,课后习题：4.2，4.3，4.13,4.3 关系的性质,R的关系矩阵：主对角线元素全是1,R的关系图：每个顶点都有环,自反性：x A 有R(R是A上的关系),关系矩阵：主对角线元素全是0,关系图：每个顶点都没有环,反自反性：x A R,例1：A=1,2,3,R1=,R2=,R3=,R4=,R5=,既不是自反的也不是非自反的,自反的,自反的,既不是自反的也不是非自反的,反自反的,例1：,是自反的一定不是反自反的；是反自反的一定不是自反的,！在自反性方面R有3种可能：自反的；反自反的；既非自反又非反自反的,对称性：若 R，则 R,关系矩阵：对称阵(aij=aji),关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。,反对称性：若 R且xy，则 R,关系矩阵：如果rij=1，且 i j，则rji=0,关系图：如果两个顶点之间有边，一定是只有一条有向边。,！R=|xR既是对称关系又是反对称关系,例2：,A=1,2,3,R1=,R2=,R3=,R4=,R5=,反对称的,既对称又反对称的,对称的,反对称的,既非对称又非反对称的,！在对称性方面R有4种可能：对称的；反对称的；既对称又反对称的；既非对称又非反对称的,传递性：若 R且 R，则 R,关系图：如果顶点xi到xj有边，xj到xk有边，则从xi到xk有边,！若a可经过两条或两条以上的线到达b，则 R,例3：,A=1,2,3,4,R1=,R2=,R3=,R4=,R5=,传递的,传递的,非传递的,传递的,非传递的,！在传递性方面，R有两种可能：传递的；非传递的。,练习：,自反的,对称的,反对称的,传递的,自反的,对称的,传递的,反自反的,反对称的,反对称的,传递的,课后习题：4.4，4.12,根据关系图判断关系的综合性质：,4.4 关系的闭包运算,闭包：设RAA，,自反闭包 记作 r(R),对称闭包 记作 s(R),传递闭包 记作 t(R),那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包；,包含R而使之具有传递性质的最小关系，称之为R的传递闭包。,一、定义,包含R而使之具有对称性质的最小关系，称之为R的对称闭包。,幂运算：设RAA，kN，约定,(1)R0=IA=|xA,(2)R1=R,(3)Rk+1=Rk R,二、计算方法,为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。,逻辑运算方法：设R是A上的任一关系，则,(1)r(R)=RIA,(2)s(R)=RR,(3)t(R)=RR2R3 Rn-1,矩阵形式：(M为R的关系矩阵),(1)Mr=M+E（单位矩阵）,(2)Ms=M+M(M 是M的转置),(3)Mt=M+M2+.+Mn-1,其中“+”均表示“逻辑加”,关系图法：,(1)自反闭包图：对没有加环的点加环,(2)对称闭包图：单边的加方向相反的边,(3)传递闭包图：若Ai经过两条或两条以 上的边可到达Aj，且无 边则加边,例4.10 设A=a,b,c,d，A上的关系,求 r(R)，s(R)和 t(R),解：1.逻辑求法：r(R)=RIA,=,R=,=R,三、实例,=,=R,s(R)=RR,t(R)=RR2R3 Rn-1,=R,=,R=,2.矩阵运算：,R=,3.关系图方法：,课后习题：4.14,R,r(R),t(R),s(R),4.5 等价关系和偏序关系,等价关系：集A上的关系R是自反的,对称的和传递的。,一、等价关系及用途,例：A=1,2,3,8，R=|x y(mod 3)则 147，258，36,设 R 是一个等价关系,若R,称 x 等价于y,记做 xy.,相容关系：R是集A上的关系，且R是自反的，对称的,(1)在一群人的集合上年龄，姓名相同的关系是等价关系,而朋友关系是相容关系，因为它可能不是传递的.(2)动物是按种属分类的；“具有相同种属性”的关系是动物集合上的等价关系.(3)集合上的恒等关系和全域关系都是等价关系.(4)在同一平面上三角形之间的相似关系是等价关系,但直线间的平行关系不是等价关系也不是相容关系,因为它不是自反的.,例子：,！等价关系一定是相容关系；相容关系不一定是等价关系,等价类：R是集A上的等价关系，对于任一aA，,aR=x|aRx,xA,被称为a的等价类。,即：xR=y|xy,在例中：1R=4R=7R=1,4,7;2R=5R=8R=2,5,8;3R=6R=9R=3,6,9;,等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：,(1)xR 且xR A(等价类为A的子集),(2)若xy则xR=yR，反之成立。,(3)若xRy，则xR yR=,集A在等价关系R下的商集：设R为非空集A上的等价关系，A在R下的商集记作A/R，A/R=xR|xA.(集合的集合）,例的商集为：A/R=1,4,7,2,5,8,3,6,9,注意：A/EA=A A/IA=x|xA,集A的划分：令=A/R，满足以下性质：,(1),(2)中任意两个元素不交,(3)中所有元素的并集为A,则 为A的划分。,集合A上的划分是不唯一的,对于集合A，若给定一个等价关系，则我们可唯一确定一个商集,集合A上的等价关系与划分是一一对应的。,集合A上的一个商集可唯一确定A上的一个划分,例 设A=1,2,3，求出A上所有的等价关系：,解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2，3，和4，具有3个划分块5。,设对应于划分i 的等价关系 Ri，i=1,2,5，则有,R5=，,R1=，,R2=，,R3=，,R4=，,，,，,，,，,，,，,，,，,偏序关系：集合A上的关系R是自反的，反对称的和传递的，记作“”。,二、偏序关系及用途,设R为偏序关系,如果R,则记作x y,读作“x小于等于y”.注意:这里的“小于等于”不是指数的大小,而是在偏序关系中的顺序性.,例 设A=1,2,3，求出A上的大于等于关系：,解：=,其中：1 1,2 1,2 2,3 1,3 2,33,偏序关系例子：,（1）任何集合A上的恒等关系,（2）集合A的幂集P(A)上的包含关系,（4）正整数集上的整除关系都是偏序关系.,（3）实数集上的小于等于，大于等于关系,相关概念：,偏序集：集合A和偏序关系R 构成一个偏序集，记作。如：,等,可比：对于任意两个元素x和y，若xy或y x，则x与y是可比的,全序关系与全序集：若A中任意两个元素都是可比的，则R为全序关系；为全序集。,盖住：如果xy，且不存在z使x z y(不是间接的),则称y能盖住x。,例：,锅，笼屉，锅盖,火车卧铺的下铺，中铺，上铺,例 设A=1,2,3,4，求出A上的整除关系：,解:R整除=,则：2,3能盖住1；4能盖住2；4不能盖住1,偏序集的哈斯图,(1)去掉箭头；（盖住）,(2)去掉间接关系；（传递）,(3)去掉环。（自反的）,哈斯图实例,例：画出 和,全序关系的哈斯图：,全序集中全部元素可以排序，它的哈斯图为一条直线。也称为线序集。,集合A上的偏序关系与哈斯图是一一对应的。,课后习题：4.16,(2)若yA，使得(x)(xAyx)，则称y是A的极大元(没有比我大的),(1)若yA，使得(x)(xAxy)，则称y是A的极小元(没有比我小的),偏序集中的一些特殊元素,设是偏序集,极小元与极大元一定存在，不一定唯一,(3)如果yA，使得(x)(xAyx)为真，则y是A的最小元(比谁都小),(4)如果yB，使得(x)(xB xy)为真，则y是B的最大元(比谁都大),最小元与最大元或唯一或不存在,例子：,左图：极小元为1;极大元为5,9,6,8,7 最小元为1;没有最大元。,右图：极小元为;极大元为a,b,c 最小元为;最大元为a,b,c。,上图：极小元为a,b,c,g;极大元为a,f,h 没有最小元也没有最大元。,结论(1):最小元一定是极小元；最大元一定是极大元.(2):孤立点既是极小元又是极大元,(6)若yA，使得(x)(xB yx)为真，则称y是B的下界（比B中每一个都小）,(7)令C=y|y为B的上界，则称C的最小元为B的上确界或最小上界（上界的最小元）,(8)令D=y|y为B的下界，则D的最大元为B的下确界或最大下界（下界的最大元）,(5)若yA，使得(x)(xB xy)为真，则称y是B的上界（比B中每一个都大）,设是偏序集,B A,对以下哈斯图，令B=2，3，6,则B的上界为6,12;B的下界为1;B的上确界为6;下确界为1.,例子：,令C=2,4,则C的上界为4,8,12;C的下界为1,2;C的上确界为4;下确界为2.,考虑下图中的偏序集.令B=b,c,d,则B的下界和最大下界都不存在,上界有d和f,最小上界为d.,结论(1):上界和下界不一定存在，不一定唯一。(2):上确界和下确界或者不存在或者唯一。(3):集合的最小元就是它的最大下界，最大元 就是它的最小上界；反之不对.,课后习题：4.6,小结与学习要求：,了解二元关系的定义和表示方法；熟练掌握关系的性质和运算；特别是幂，合成和三种闭包运算;理解等价关系和偏序关系，明确它们在描述研究对象的结构和特点时重要作用(即分类和覆盖)。它们在计算机科学中有重要应用。重点：关系的表示方法；关系的合成，幂运算；关系性质判断；闭包求法；哈斯图画法；哈斯图的八个特殊元素的求法。,作业二,课后习题：4.1，4.2，4.3，4.4，4.6，4.12，4.13，4.14，4.16,