离散数学-二元关系与运算PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,二元关系和运算,第四章,1,1,.,二元有序组,：,由两个元素,x,和,y,按一定顺序排成二元组，记作：,。,4.1,二元关系的概念,如：平面直角坐标系中点的坐标,一、二元关系的概念,2,二元有序组的性质,(1),当,x,y,时，,(2)=,，,当且仅当,x,=,u,，,y,=,v,(1),、,(2,)说明有序组区别于集合,n,元有序组,：,由,n,个元素,x,1,，,x,2,，,，,x,n,，,按一定顺序排成的,n,元组，记作：(,x,1,，,x,2,，,，,x,n,),。,3,2.,一种新的集合运算,积运算：,设,A,、,B,为两集合，用,A,中元素为第一元素，,B,中元素作为第二元素构成的二元有序组的全体叫做,A,和,B,的笛卡儿积。,记作：,A,B,符号化：,A,B,=|,x,A,y,B,4,例,4.1,设,A,=,a,b,，,B,=0,1,2,，,求,A,B,，,B,A,解：,根据笛卡儿积的定义知,A,B,=,B,A,=,一般地：如果|,A,|=,m,，,|,B,|=,n,，,则|,A,B,|=|,B,A,|=,m,n,5,积运算的性质,(1),若,A,，,B,中有一个空集，则笛卡儿积是空集，即：,B,=,A,=,(2),当,A,B,，,且,A,，,B,都不是空集时，有,A,B,B,A,(3),当,A,，,B,，,C,都不是空集时，有(,A,B,),C,A,(,B,C,),因为,(,A,B,),C,中的元素,z,，,而,A,(,B,C,),中的元素为,x,。,6,(4),A,(,B,C,)=(,A,B,),(,A,C,)(,对,的分配律),(,B,C,),A,=(,B,A,),(,C,A,),A,(,B,C,)=(,A,B,),(,A,C,),(,B,C,),A,=(,B,A,),(,C,A,),我们证明：,A,(,B,C,)=(,A,B,),(,A,C,),(?,),(?,),(?,),7,证明思想,要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；,二是利用已有的集合运算的性质,(,算律和已证明过的公式,),，仿照代数恒等式的证明方法，一步步从左,(,右,),边推出右,(,左,),边，或从左、右边分别推出同一个集合式子。,一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。,8,证明：,用第一种方法,对于任意的,A,(,B,C,),x,A,y,(,B,C,),x,A,(,y,B,y,C,),(,x,A,y,B,),(,x,A,y,C,),A,B,A,C,(,A,B,),(,A,C,),A,(,B,C,)=(,A,B,),(,A,C,),9,例,4.2,设,A,=1,2,，求,P,(,A,),A,解：,P,(,A,),A,=,，,1,，,2,，,1,2,=,，,，,n,阶笛卡儿积：,=(,x,1,x,2,x,n,)|,x,1,A,1,x,2,A,2,x,n,A,n,A,1,A,2,A,n,1,2,，,，,，,，,，,10,二元关系：,如果一个集合的元素都是二元有序组，则这个集合称为一个二元关系，记作：,R,。,如果,R,，,记作,x,R y,如果,R,，,记作,x R y,3,、二元关系的数学定义,11,从,A,到,B,的二元关系：,设,A,，,B,为集合，,A,B,的任何子集所定义的二元关系叫做从,A,到,B,的二元关系。,若,A=B,，,叫做,A,上的二元关系；,若,|,A,|,n,，,则|,A,A,|,n,2,。,就是说，,A,上有 个不同的二元关系，其中包括空关系、全域关系,U,A,和恒等关系,I,A,。,A,A,的所有子集有 个。,12,例,4.3,设,A,=,a,b,，,写出,P,(,A,),上的包含关系,R,：,解：,P,(,A,)=,a,b,a,b,R,=,13,A,上关系的表示法,1.,关系矩阵：,设,A,=,x,1,x,2,x,n,),，,R,是,A,上的关系，,r,ij,=,1,若,x,i,R,x,j,0,若,x,i,R x,j,(,i,j,=1,2,n,),则 (,r,ij,),nxn,=,是,R,的关系矩阵,令：,二、二元关系的表示方法,14,2.,关系图：,以,E,=|,x,i,A,x,j,A,x,i,Rx,j,为有向边集组成的有向图,G,=,以,V,=,A,=,x,1,x,2,x,n,为顶点集，,15,例,4.4,设,A,=1,2,3,4,，,R,=,是,A,上的关系，试写出,R,的关系矩阵并画出关系图：,解：,关系矩阵：,0 0 1 1,0 0 0 0,0 1 0 0,1 1 0 0,关系图：,1,3,4,2,16,4.2,关系的运算,关系,R,的定义域：,dom,R,=,x,|(,y,),R,(,即,R,中有序组的第一个元素构成的集合,),关系,R,的值域：,ran,R,=,y,|(,x,),R,(,即,R,中有序组的第二个元素构成的集合,),一、关系的定义域与值域,17,例,4.5,下列关系都是整数集,Z,上的关系，分别求出它们的定义域和值域：,(1),R,1,=|,x,y,Z,x,y,(2),R,2,=|,x,y,Z,x,2,+,y,2,=1,(3),R,3,=|,x,y,Z,y,=2,x,(4),R,4,=|,x,y,Z,|,x,|=|,y,|=3,18,解：,dom,R,1,=ran,R,1,=,Z,解：,R,2,=,dom,R,2,=(?),ran,R,2,=(?),(1),R,1,=|,x,y,Z,x,y,(2),R,2,=|,x,y,Z,x,2,+,y,2,=1,19,解：,dom,R,3,=,Z,，,ran,R,3,=,偶数,解：,dom,R,4,=,ran,R,4,=(?),(3),R,3,=|,x,y,Z,y,=2,x,(4),R,4,=|,x,y,Z,|,x,|=|,y,|=3,20,二、关系的常用运算,F,是任意关系，,F,的逆,F,1,=|,yFx,F,、,G,是任意两个关系，,F,与,G,的合成记作：,F,G,=|(,z,)(,xGz,zFy,),关系,F,在集,A,上的限制，记作：,F,|,A,=|,xFy,x,A,集,A,在关系,F,下的象,F,A,=ran(,F,|,A,),(1),逆：,(2),合成：,(3),限制：,(4),象：,21,例,4.6,设,F,，,G,是,N,上的关系，其定义为：,F,=|,x,y,N,y,=,x,2,G,=|,x,y,N,y,=,x,+1,求,G,1,，,F,G,，,G,F,，,F,|,1,2,，,F,1,2,解：,由定义知：,G,1,=|,y,x,N,y,=,x,+1,列出,G,1,中的元素就是,G,1,=,22,为了求,F,G,，,可以先直观表示如下：,对任何,x,N,x,x,+1=,G,即,y,=(,x,+1),2,因此,F,G,=|,x,y,N,y,=(,x,+1),2,同理可求,G,F,=|,(?)(,自己做！),发现,F,G,G,F,F,|,1,2=,F,1,2=ran(,F,|,1,2)=1,4,F,Z,Z,2,=,y,23,关系运算的性质：,设,F,、,G,、,H,、,为任意关系，则有：,(1)(,F,1,),1,=,F,(2)dom,F,1,=ran,F,，,ran,F,1,=dom,F,(3)(,F,G,),H,=,F,(,G,H,),(4)(,F,G,),1,=,G,1,F,1,(5),F,(,G,H,),=,F,G,F,H,(,对,的分配律,),(6),F,(,G,H,),F,G,F,H,(,对,的半分配律,),(7)(,G,H,),F,=,G,F,H,F,(8)(,G,H,),F,G,F,H,F,(?),(?),24,任取,(,F,G,),1,F,G,(,z,)(,G,F,),(,z,)(,G,1,F,1,),G,1,F,1,(4)(,F,G,),1,=,G,1,F,1,的证明：,25,任取,F,(,G,H,),(,z,)(,G,H,),F,),(,z,)(,G,H,),F,)(,注意对括号的顺序,),(,z,)(,G,F,(,H,F,),F,G,F,H,F,(,G,H,)=,F,G,F,H,(5),F,(,G,H,),=,F,G,F,H,的证明：,26,4.3,关系的性质,R,的关系矩阵：主对角线元素全是1,R,的关系图：每个顶点都有环,自反性：,x,A,有,R,(,R,是,A,上的关系,),关系矩阵：主对角线元素全是0,关系图：每个顶点都没有环,反自反性：,x,A,R,27,对称性：,若,R,，,则,R,关系矩阵：对称阵,关 系 图：如果两个顶点之间有边，一定是一对,方向相反的边,。,28,反对称性：,若,R,且,x,y,，,则,R,关系矩阵：如果,r,ij,=1,，,且,i j,，,则,r,ji,=0,关系图：如果两个顶点之间有边，一定是只有一条有向边。,29,传递性：,若,R,且,R,，,则,R,关系图：如果顶点,x,i,到,x,j,有边，,x,j,到,x,k,有边，则从,x,i,到,x,k,有边,30,例,4.7,设,A,=1,2,10,，,对于,A,上的关系,R,=|(,x,y,)/3,I,I,为整数集，问,R,有哪些性质？,31,解：,逐条性质加以验证,R,=|(,x,y,)/3,I,任取,A,中元素,x,，,由于(,x,x,)/3=0,，,所以,R,是,自反的,；,又设,A,中任意两个元素,x,y,，,如果,xRy,，,即,x,y,可被3整除，则,yx,也一定可被3整除，即,yRx,，,从而,R,是,对称的,；,如果,A,中三 个元素,x,，,y,，,z,满足,xRy,，,yRz,，,则,x,y,，,yz,被3整除，由于,x,z,=(,x,y,)+(,yz,),，,所以,x,z,被3整除，从而,xRz,即,R,具有,传递性,。,32,4.4,关系的闭包运算,闭包：,设,R,A,A,，,自反闭包,记作,r,(,R,),对称闭包,记作,s,(,R,),传递闭包,记作,t,(,R,),由,A,求,r,(,R,),，,s,(,R,),，,t,(,R,),的过程叫,闭包运算,。,那么，包含,R,而使之具有自反性质的最小关系，称之为,R,的,自反闭包,；,包含,R,而使之具有对称性质(传递性质)的最小关系，称之为,R,的对称,(传递)闭包,。,一、定义,33,幂运算：,设,R,A,A,，,k,N,，,约定,(1),R,0,=,I,A,=|,x,A,(2),R,1,=,R,(3),R,k+1,=,R,k,R,显然,R,m,R,n,=,R,m+n,(,R,m,),n,=,R,mn,二、计算方法,为了有效地计算关系,R,的各种闭包，先引进关系的幂运算概念。,34,闭包运算的方法：,设,R,是,A,上的任一关系，则,(1),r,(,R,),=,R,I,A,(2),s,(,R,),=,R,R,(3),t,(,R,),=,R,R,2,R,3,R,n,35,矩阵形式,：,(,M,为,R,的关系矩阵,),(1),Mr,=,M,+,E,(2),Ms,=,M,+,M,(,M,是,M,的转置,),(3),Mt,=,M,+,M,2,+,M,3,其中“,+”,均表示“逻辑加”,36,例,4.8,设,A,=,a,b,c,d,，,A,上的关系,求,r,(,R,),，,s,(,R,),和,t,(,R,),解：,r,(,R,)=,R,I,A,=,R,=,=,R,三、实例,37,s,(,R,)=,R,R,=,t,(,R,)=,R,R,2,R,3,=,R,38,而,R,2,=,R,R,R,3,=,R,2,R,R,4,=,R,3,R,=,=,=,实际上，看到当,k,4,时，已有,R,4,R,R,2,R,3,故,t,(,R,)=,R,R,2,R,3,=,39,四、闭包运算的性质,设,A,是有限集且|,A,|=,n,，,R,A,A,，,则：,40,4.6,等价关系和偏序关系,等价关系：,集,A,上的关系,R,是自反的,对称的和传递的。,等价类：,R,是集,A,上的等价关系，对于任一,a,A,，,a,R,=,x,|,aRx,x,A,被称为,a,的等价类。,即,A,中所有和,a,有,R,关系的元素的集合。,一、等价关系及用途,41,等价类的性质：,R,是非空集合，对任意的,x,，,y,A,，,下面的结论成立：,(1),x,且,x,A,(,等价类为,A,的子集,),(2),若,xRy,，,则,x,=,y,(3),若,x,Ry,，,则,x,y,=,42,集,A,在等价关系,R,下的商集：,设,R,为非空集,A,上的等价关系，以,R,的不交的等价类为元素的集合叫做,A,在,R,下的商集，记作,A,/,R,.,即：,A,/,R,=,x,R,|,x,A,43,集,A,的划分：,设,A,是非空集合，,(1),(2),中任意两个元素不交,(3),中所有元素的并集为,A,则,为,A,的划分。,如果存在一个,A,的子集族,，,P,(,A,),满足以下条件：,44,由等价类的性质和商集的定义可知，商集,A,/,R,是,A,的划分，称之为由,R,诱导的划分。,反过来，给定,A,的任一划分,，则,A,被分割成若干个划分块。,若定义,A,上的二元关系,R,：,x,，,y,A,且,x,y,属,的同一块，则,xRy,，,那么,R,是,A,上的等价关系，称之为由,诱导的等价关系。,集,A,上的等价关系与划分是一一对应的。,45,例,4.9,设,A,=1,2,3,，,求出,A,上所有的等价关系：,解：,先求,A,的各种划分：只有1个划分块的划分,1,，具有两个划分块的划分,2,，,3,，和,4,，具有,3,个划分块,5,。,1,=,A,2,=1,2,3,，,4,=3,1,2,，,3,=2,1,3,，,5,=1,2,3,46,设对应于划分,i,的等价关系,R,i,，,i,=1,2,5,，,则有,R,5,=,，,，,R,1,=,，,，,，,R,2,=,，,R,3,=,，,R,4,=,，,，,，,，,，,，,，,，,，,，,，,，,，,，,，,47,偏序关系：,集,A,上的关系,R,是自反的，反对称的和传递的，记作“,”，且称,A,),为偏序集。,二、偏序关系及用途,48,例,4.10,设,A,=2,4,6,8,，,A,上关系,R,是通常意义下的小于或等于关系，试写出,R,并验证它是偏序关系。,解：,R,=,(1),自反性：,(2),反对称性：,(3),传递性：,均属于,R,对任意的,R,，,必有,x,y,，,当,x,y,时，,y,x,，,从而,R,对任意的,R,，,R,由于,x,y,y,z,，,所以,x,z,，,从而,R,。,49,例,4.11,设,C,=,a,b,a,b,，,C,上关系,T,是集合的“包含于”，试写出,T,，,并验证它是偏序关系。,解：,同例,4.10,类似，自己做！,50,偏序集的哈斯图,(1),用小圆圈表示偏序集的元素,(,称为结点,),；,(2),按每个元素在偏序中的次序从底向上列结点位置；,(3),对于偏序集中任意两个元素,x,和,y,，,如果,x,y,且不存在另一个元素,a,，,使,x,a,a,y,，,则在,x,与,y,两结点之间划上一杠，即“|”(,x,在下，,y,在上),51,全序关系：,设,是偏序集，,(,x,)(,y,)(,x,A,y,A,(,x,y,y,x,),成立，则称,A,),为全序集，这时的偏序关系叫全序关系。,全序集,A,),中全部元素可以排序，它的哈斯图为一条直线。,如果,52,偏序集中的一些特殊元素,设,是偏序集，,B,A,(1),如果,y,B,，,使得,(,x,)(,x,B,y,x,),为真，则,y,是,B,的最小元,(“,小于”,B,中所有元,),(2),如果,y,B,，,使得,(,x,)(,x,B,x,y,),为真，则,y,是,B,的最大元,(“,大于”,B,中所有元,),53,(4),若,y,B,，,使得,(,x,)(,x,B,x,y,),，,则称,y,是,B,的极大元,(,B,中没有比,y,大的其他元,),(5),若,y,A,，,使得,(,x,)(,x,B,x,y,),为真，则称,y,是,B,的上界,(3),若,y,B,，,使得,(,x,)(,x,B,x,y,),，,则称,y,是,B,的极小元,(,B,中找不到,x,小于,y,),54,(6),若,y,A,，,使得,(,x,)(,x,B,y,x,),为真，则称,y,是,B,的下界,(7),令,C,=,y,|,y,为,B,的上界，则称,C,的最小元为,B,的上确界或最小上界,(8),令,D,=,y,|,y,为,B,的下界，则,D,的最大元为,B,的下确界或最大下界,55,12,8,4,6,10,例,4.12,画出,和,的哈斯图，并指出其中的特殊元。,解：,(1),的哈斯图如下：,9,2,5,1,3,7,11,由图可知,1,为最小元，没有最大元；,7,8,9,10,11,12,均为极大元，极小元为,1,；,1,为,1,2,12,的下界，也是下确界；,1,2,12,中没有上确界或上界。,56,(2),的哈斯图如下：,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,也分别为它们的极小元和极大元、下确界和上确界。,57,a,b,c,d,e,例,4.13,已知偏序集,的哈斯图如下：,h,g,f,试写出对应的,A,和,A,上的偏序关系,R,，,并指出,A,中的特殊元。,58,解：,A,=,a,b,c,d,e,f,g,h,直接由哈斯图可知：,A,中没有最小元和最大元；,e,g,和,h,均为,A,的极大元，,a,b,f,和,h,均为,A,的极小元；没有上确界和下确界。,R,=,a,b,c,d,e,h,g,f,59,小结与学习要求：,了解二元关系的定义和表示方法；熟练掌握关系的性质和运算；特别是复合和三种闭包运算,;,理解等价关系和偏序关系，明确它们在描述研究对象的结构和特点时重要作用,(,即分类和覆盖,),。它们在计算机科学中有重要应用。,60,