4.离散数学_二元关系

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,庄伯金 bjzhuang,*,庄伯金 bjzhuang,1,第四章,二元关系,庄伯金 bjzhuang,2,主要内容,二元关系的基本概念,关系的运算,关系的性质,关系的闭包,等价关系与偏序关系,庄伯金 bjzhuang,3,有序对与笛卡儿积的概念,定义(有序对,)：,由两个元素,x,和,y，,按一定顺序排列成的二元组。称为,有序对,或,序偶,，记作。,x,为第一元素，,y,为第二元素；,有顺序的要求：当,xy,时，；,=,x=u,y=v。,定义(笛卡儿积,)：,设,A,B,为集合，用,A,中的元素为第一元素，,B,中的元素为第二元素构成有序对的集合，称为,A,和,B,的,笛卡儿积,，记作,AB。,AB=|xA,yB,庄伯金 bjzhuang,4,笛卡儿积的性质(1),任意集合与空集的笛卡儿积为空集,A,=,A=,笛卡儿积不满足交换律,ABBA,笛卡儿积不满足结合律,(AB)CA(BC),庄伯金 bjzhuang,5,笛卡儿积的性质(2),笛卡儿积对交并满足分配律,A(BC)=(AB)(AC),(BC)A=(BA)(CA),A(BC)=(AB)(AC),(BC)A=(BA)(CA),子集的笛卡儿积仍为子集,ACBDABCD,笛卡儿积,例：,A=1,2，,求,P(A)A。,庄伯金 bjzhuang,6,庄伯金 bjzhuang,7,二元关系的概念,定义(二元关系)：如果一个集合满足以下条件之一：,(1),集合非空，且它的元素都是有序对；(2)集合是空集，则称该集合为一个,二元关系,(简称,关系,)，记作,R。,二元关系是集合,二元关系是有序对的集合,若R，,可记为,xRy。,定义：设,A,和,B,为集合，,AB,的任何子集所定义的二元关系叫做从,A,到,B,的二元关系；若,AB，,则叫做,A,上的二元关系。,庄伯金 bjzhuang,8,二元关系的域,定义域,：,R,中所有有序对的第一元素构成的集合称为,R,的定义域，记作,domR。,值域,：,R,中所有有序对的第二元素构成的集合称为,R,的值域，记作,ranR。,域,：,R,的定义域和值域的并集称为,R,的域，记作,fldR。,例：,R=,庄伯金 bjzhuang,9,二元关系的概念,有限集合上的关系总数也是有限的,|A|=m，|B|=n，,则|,AB|=mn，,所以，,A,到,B,上的关系共有,2,mn,种。,A,上的特殊关系,空关系：,AA,的空集,全域关系：,E,A,=|x,A,y,A=AA；,恒等关系：,I,A,=| x,A。,庄伯金 bjzhuang,10,常见关系,小于等于关系：,L,A,=|x,y,A,xy，,其中,A,R,整除关系：,D,B,=|x,yB,x,整除,y，,其中,B,Z,*,包含关系：,R,=|x,y,A,xy，,其中,A,为集合族,例：,B=a,b，,A,=P(B)，,求,R,。,庄伯金 bjzhuang,11,关系的表示方法,集合表达式,关系矩阵,关系图,庄伯金 bjzhuang,12,关系矩阵,设,A=x,1,x,2,.,x,n,，R,是,A,上的关系，令,r,ij,=1，,若R,r,ij,=0，,若R,则有,是,R,的关系矩阵,，记作,M,R,。,庄伯金 bjzhuang,13,关系图,设,A=x,1,x,2,.,x,n,，R,是,A,上的关系。令图,G=V,E，,其中顶点集,V=A，,有向边集合,E,满足,x,i,x,j,V，E,x,i,Rx,j,。,则称图,G,为,R,的关系图，记作,G,R,。,关系的表示,例：,A=1,2,3,4, R=, , , , ，,求,M,R,和,G,R,。,庄伯金 bjzhuang,14,庄伯金 bjzhuang,15,关系的运算,逆关系,：设,R,为二元关系，,R,的逆关系,(简称,R,的逆) 记作,R,-1,，,其中,R,-1,=|R。,右复合,：设,F,和,G,为二元关系，,G,对,F,的右复合记作,FG,，,其中,FG=|t(FG)。,左复合,：设,F,和,G,为二元关系，,G,对,F,的左复合,记作,FG，,其中,FG=|t(GF)。,庄伯金 bjzhuang,16,关系的运算,限制,：设,R,为二元关系，,A,为集合，,R,在,A,上的限制,记作,RA,，,其中,RA=|RxA。 RA,的值域称为,A,在,R,下的像,，记作,RA,，,其中,RA=ran(RA)。,幂,：设,R,为,A,上的关系，,n,为自然数，则,R,的,n,次幂,定义为：,R,0,=|xA=I,A,R,n+1,=R,n,R,基本的集合运算,庄伯金 bjzhuang,17,关系的运算规律,定理1：设,F,是任意关系，则,(F,-1,),-1,=F,domF,-1,=ranF, ranF,-1,=domF,定理2：设,F、G,和,H,是任意的关系，则,(FG)H=F(GH),(FG),-1,=G,-1,F,-1,定理3：设,R,为,A,上的关系，则,RI,A,=I,A,R =R,庄伯金 bjzhuang,18,关系的运算规律,定理4：设,F、G,和,H,为任意关系，则,F,(GH)=F,GF,H,(GH),F=G,FH,F,F,(GH),F,GF,H,(GH),F,G,FH,F,定理5：设,F,为关系，,A、B,为集合，则,F,(AB)=F,AF,B,FAB=FAFB,F,(AB)=F,AF,B,FAB,FAFB,庄伯金 bjzhuang,19,关系的运算规律,定理6：设,A,为,n,元集，,R,是,A,上的关系，则存在自然数,s,和,t，,使得,R,s,=R,t,。,定理7：设,R,为,A,上的关系，,m、n,为自然数，则有,R,m,R,n,=R,m+n,；,(R,m,),n,=R,mn,。,定理8：设,R,为,A,上的关系，若存在自然数,s,和,t(st)，,满足,R,s,=R,t,，,则,对任意自然数,k，,有,R,s+k,=R,t+k,；,对任意自然数,k,和,i，,有,R,s+kp+i,=R,s+i,，,其中,p=t-s；,令,S=R,0,R,1,.,R,t-1,，,则对于任意的自然数,q，R,q,S。,庄伯金 bjzhuang,20,关系的性质,自反性,反自反性,对称性,反对称性,传递性,庄伯金 bjzhuang,21,自反性与反自反性,定义1：设,R,为集合,A,上的二元关系，,若,x(xA,R)，,则称,R,在,A,上具有,自反性,；,若,x(xAR)，,则称,R,在,A,上具有,反自反性,。,例：设,A=1,2,3,R,1,R,2,R,3,是,A,上的关系，判断他们是否具有自反性或反自反性,R,1,=,R,2,=,R,3,=,庄伯金 bjzhuang,22,对称性与反对称性,定义2：设,R,为,A,上的二元关系,若,x,y(x,yARR)，,则称,R,是,A,上的,对称关系,；,若,x,y(x,yARR x=y)，,则称,R,是,A,上的,反对称关系,。,例：设,A=1,2,3,R,1,R,2,R,3,R,4,为,A,上的关系，判断他们的对称性与反对称性：,R,1,=,R,2,=,R,3,=,R,4,=,庄伯金 bjzhuang,23,传递性,定义3：设,R,为,A,上的二元关系，若,x,y,z(x,y,zARRR)，,则称,R,是,A,上的,传递关系,。,例：设,A=1,2,3，,R,1,R,2,R,3,是,A,上的关系，判断他们是否具有传递性,R,1,=,R,2,=,R,3,=,庄伯金 bjzhuang,24,五种性质成立的充要条件,定理：设,R,为,A,上的二元关系，则,R,在,A,上自反当且仅当,I,A,R；,R,在,A,上反自反当且仅当,RI,A,=,；,R,在,A,上对称当且仅当,R=R,-1,；,R,在,A,上反对称当且仅当,R,R,-1,I,A,；,R,在,A,上传递当且仅当,R,R,R,庄伯金 bjzhuang,25,关系性质的保持,自反性,反自反性,对称性,反对称性,传递性,R,-1,Y,Y,Y,Y,Y,R,1,R,2,Y,Y,Y,Y,Y,R,1,R,2,Y,Y,Y,N,N,R,1,R,2,N,Y,Y,Y,N,R,1,R,2,Y,N,N,N,N,庄伯金 bjzhuang,26,关系的闭包,定义：设,R,是,A,上的关系，,R,的自反（对称或传递）闭包是,A,上的关系,R,，,并满足,R,是自反的（对称的或传递的）；,RR,；,对,A,上任何一个包含,R,的自反（对称或传递）关系,R,，R,R,；,R,的,自反闭包,记作,r(R),，,对称闭包,记作,s(R),，,传递闭包,记作,t(R),。,庄伯金 bjzhuang,27,闭包的构造,定理：设,R,为,A,上的关系，则有,r(R)=RI,A,；,s(R)=RR,-1,t(R)=RR,2,R,3,.,例,设,A=a,b,c,d，A,上的关系,R=, , , ，,求,R,的自反闭包、对称闭包和传递闭包。,庄伯金 bjzhuang,28,庄伯金 bjzhuang,29,等价关系与等价类,定义：设,R,为非空集合,A,上的关系，如果,R,满足自反性、对称性和传递性，则称,R,为,A,上的一个,等价关系,。若R，,则称,x,等价于,y。,例：集合,A=N，,定义,A,上的关系,R,为：,R=|x,yAxy(mod 3),设,R,为非空集合,A,上的等价关系，,xA，,令,x,R,=y|yAR，,称,x,R,为,x,关于,R,的等价类,，简称为,x,的等价类,，简记为,x,。,庄伯金 bjzhuang,30,等价类的性质,定理：设,R,为,A,上的等价关系，则,xA，x,非空；,x,yA，,若R，,则,xy=,；,x,yA，,若R，,则,x=y；,x=A。,庄伯金 bjzhuang,31,商集与集合的划分,定义：设,R,为非空集合,A,上的等价关系，以,R,的所有等价类为元素的集合称为,A,关于,R,的,商集,，记作,A/R,，,即,A/R=x|xA。,定义：设,A,为非空集合，若,A,的子集族,满足：,；,x,y(x,y ,xyxy=,)；,=,A。,则称为,A,的一个,划分,，称中的元素为,A,的划分块。,商集,A/R,是,A,的一个划分。,商集与集合的划分,定理：对于集合,A,的任何一个划分，存在,A,上的一个等价关系,R,，使得该划分为,A,关于,R,的商集,A/R,。反之亦然。,庄伯金 bjzhuang,32,庄伯金 bjzhuang,33,练习,设集合,A=1,2,3,4,5，,找出,A,上的等价关系,R，,使得,R,能产生划分1,2,3,4,5，并画出关系图。,设,R,是一个二元关系，,S=|c(RR)。,证明：若,R,是等价关系，则,S,也是等价关系。,庄伯金 bjzhuang,34,偏序关系,定义：设,R,为非空集合,A,上的一个关系，若,R,具有自反性、反对称性和传递性，则称,R,为,A,上的,偏序关系,，记作,。如果,，则称,x,小于或等于,y,。,定义：设,R,为非空集合,A,上的偏序关系，定义,x,yA，,xy,xyxy；,x,yA，,x,与,y,可比,xyy,x。,定义：集合,A,和,A,上的偏序关系一起叫做,偏序集,，记作(,A,)。,定义：设,R,为非空集合,A,上的偏序关系，如果,x,yA，x,与,y,都是可比的，则称,R,为,A,上的,全序关系,（或,线序关系,）。,庄伯金 bjzhuang,35,偏序图的表示,哈斯图,排序：若,xy，,将,x,放在,y,的下方；,连线：,x,yA，,如果,xy，,且不存在,z，,使得,xzy，,则将,x,和,y,连线。,例：偏序集(1,2,3,4,5,6,7,8,9,整除),庄伯金 bjzhuang,36,偏序集中的特殊元素,定义：设(,A,),为偏序集，,BA，,yB,，,若,x(xB,y,x)，,则称,y,为,B,的,最小元,；,若,x(xB,x,y)，,则称,y,为,B,的,最大元,；,若,x(xB,x,y,x=y,)，,则称,y,为,B,的,极小元,；,若,x(xB,y,x,x=y,)，,则称,y,为,B,的,极大元,。,定义：设(,A,),为偏序集，,BA，,yA,，,若,x(xB,x,y)，,则称,y,为,B,的,上界,；,若,x(xB,y,x)，,则称,y,为,B,的,下界,；,令,C=y|y,为,B,的上界，则,C,的最小元为,B,的,上确界,；,令,D=y|y,为,B,的下界，则,D,的最大元为,B,的,下确界,。,偏序集中的特殊元素,例：设,A=1,2,3,4,5,6,7,8,9,10,11,12,24,，集合,A,上的偏序关系为整除关系，,B=2,3,4,6,9,庄伯金 bjzhuang,37,庄伯金 bjzhuang,38,函数的概念,定义：设任意两非空集合,A,和,B，F,为,A,到,B,上的关系，若,xA，,都存在,唯一的,yB,，,使得F，,则称,F,为,A,到,B,的,函数,或,映射,，记作,F：A,B,。,若F，,可记作,y=F(x)，,称,x,为自变量，,y,为,F,在,x,上的函数值。,函数是关系，所以函数是集合。,函数,F=G,F,G,GF,所有从,A,到,B,的函数记作,B,A,=F|F: A,B，,读作,B,上,A,。,庄伯金 bjzhuang,39,函数的概念,定义：设函数,F: A,B,若,x,1,x,2,A，,且,x,1,x,2,，,都有,F(x,1,)F(x,2,)，,则称,F,为,A,到,B,的,单射,；,若,ranF=B，,则称,F,为,A,到,B,的,满射,；,若,F,既是单射又是满射，则称,F,为,A,到,B,的,双射,，或,一一对应函数,。,庄伯金 bjzhuang,40,常用函数,常值函数：函数,F: A,B，,对,xA，,存在一固定元素,cB，,满足,F(x)=c；,恒等函数：,I,A,=|xA；,单调函数：函数,F: A,B，,x,1,x,2,A，,若,x,1,x,2,时,F(x,1,)F(x,2,)，,则称,F,为单调递增函数；,F(x,1,)F(x,2,)，,则称,F,为单调递减函数；,特征函数：任意集合,A,A，,函数,X,A,:A,0,1，,若,xA,，,则,F(x)=1，,否则，,F(x)=0；,自然映射：设,R,为,A,上的等价关系，函数,G:A,A/R，G(x)=x。,庄伯金 bjzhuang,41,函数的运算,复合函数：设函数,F,与,G，,满足：,dom(GF)=x|xdomFF(x)domG；,xdom(GF)，GF(x)=G(F(x)。,则称,GF,为,G,对,F,的复合函数。,反函数：若函数,F,的逆关系也是函数，则称为,F,的反函数，记为,F,-1,。,定理：设函数,F: A,B,为双射，则其逆关系,F,-1,仍为函数，且是从,B,到,A,的双射。,庄伯金 bjzhuang,42,作业(1),P113 4.2,P113 4.3,P115 4.11,庄伯金 bjzhuang,43,作业(,2,),P115 4.12,P115 4.13,P116 4.14,P115 4.9,P116 4.16(1),P116 4.21,P116 4.22,P116 4.24,