关系的概念、表示及性质ppt课件

第二部分集合论,主要内容集合3-1集合的概念和表示法3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分与覆盖,3-10等价关系与等价类3-11相容关系3-12序关系函数4.1函数的基本概念4.2复合函数与逆函数,1,张继科,宁泽涛,上节内容回顾3-1集合的概念和表示法集合的概念：集合的表示法：列举法、叙述法集合的关系：相等、子集、真子集空集、全集、幂集,张继科,第二部分集合论,3-2集合的运算交集、并集、相对补集、绝对补集、对称差,苹果,Mac,2,3-2集合的运算集合运算等价公式AA=AAA=AAE=EA=A=AAE=AAA=EAA=A=A=EE=AB=BAAB=BAA(AB)=AA(AB)=A(AB)=AB(AB)=ABA-B=AB,第二部分集合论,(AB)C=A(BC)(AB)C=A(BC)A(BC)=(AB)(AC)A(BC)=(AB)(AC),3,第二部分集合论,主要内容集合3-1集合的概念和表示法3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分与覆盖,3-10等价关系与等价类3-11相容关系3-12序关系函数4.1函数的基本概念4.2复合函数与逆函数,4,第二部分集合论,笛卡尔积,3-4序偶与笛卡尔积3-4.1序偶3-4.2笛卡尔积,序偶的概念,5,序偶orderedpair由两个固定次序的客体a,b组成的序列称为序偶，记作，其中a,b称为序偶的分量。其中,a是第一元素,b是第二元素。序偶相等两个序偶相等：=,当且仅当xu,y=v。注意:ab,笛卡尔积,序偶的概念,6,三元组：第一元素也是序偶的序偶=,c.注意不是三元组！n(2)元组：=,an.N元组相等的条件=ai=bi,i=1,2,n.,笛卡尔积,序偶的概念,7,笛卡尔积令A和B是任意两个集合，若序偶的第一个元素是A的元素，第二个元素是B的元素，所有这样的序偶集合，称为集合A和B的笛卡尔乘积或直积，记为AB，AB=|xAyB,笛卡尔积,序偶的概念,8,例1:A=,a,B=1,2,3.AB=,.BA=,.AA=,.BB=,.,笛卡尔积,序偶的概念,9,当|A|=m，|B|=n时，|AB|是多少？|AB|=mn,笛卡尔积,序偶的概念,10,笛卡尔积的性质,1.非交换:ABBA(除非A=B或者A=或者B=)例如:A=1,B=2.AB=,BA=.2.非结合:(AB)CA(BC)(除非A=或者B=或者C=)举例:A=B=C=1.(AB)C=,1,A(BC)=.,笛卡尔积,序偶的概念,11,3.笛卡尔积分配律：（对或运算满足）（1）A(BC)=(AB)(AC)（2）A(BC)=(AB)(AC)（3）(BC)A=(BA)(CA)（4）(BC)A=(BA)(CA),笛卡尔积的性质,笛卡尔积,序偶的概念,12,3.笛卡尔积分配律(证明(1)A(BC)=(AB)(AC).证明:,A(BC)xAy(BC)xA(yByC)(xAyB)(xAyC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC).#,笛卡尔积的性质,笛卡尔积,序偶的概念,13,4.其他性质：设A,B,C,D是任意集合,(1)若A,则ABACBACABC（即书上的定理3-4.2）(2)ACBDABCD.（即书上的定理3-4.3）(3)AB=A=B=,笛卡尔积的性质,笛卡尔积,序偶的概念,14,证明(1)若A,则ABACBC.证明:()若B=,则BC.设B,由A,设xA,y,yB，ABACxAyCyC.BC()若B=,则AB=AC.设B.,ABxAyBxAyCACABAC.#,笛卡尔积,序偶的概念,15,n维笛卡尔积,定义n维笛卡尔积：A1A2An=|x1A1x2A2xnAnAAA=An|Ai|=ni,i=1,2,n|A1A2An|=n1n2nn.n维笛卡尔积性质与2维笛卡尔积类似.,笛卡尔积,序偶的概念,16,小结：本节介绍了序偶、有序n元组及笛卡尔积的概念。重点理解有序n元组及笛卡尔积的概念。作业：,第三章集合与关系,P104(1)b)(2)(5),17,第二部分集合论,主要内容集合3-1集合的概念和表示法3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分与覆盖,3-10等价关系与等价类3-11相容关系3-12序关系函数4.1函数的基本概念4.2复合函数与逆函数,18,现实中的“关系”兄弟关系、长幼关系、同学关系、邻居关系，上下级关系等。数学上的关系：大于关系、小于关系，整除关系。例如：“3小于5”，“x大于y”，“点a在b与c之间”。如何表示关系呢？谓词是一种关系的表达：P(a,b):a是b的长辈,第二部分集合论,谓词仅仅表示了关系形式，侧重于对客体的描述,本章主要内容：借助序偶和集合来描述关系本身,19,例如：火车票与座位之间的对号关系。设X表示火车票的集合，Y表示座位的集合，则对于任意的xX和yY，必定有x与y有“对号”关系x与y没有“对号”关系。二者之一令R表示“对号”关系，则上述问题可以表示为xRy或xRy。,亦可表示为R或R，因此我们看到对号关系是序偶的集合。,第二部分集合论,20,第二部分集合论,3-5关系及其表示3-5.1关系的概念3-5.2几种特殊关系3-5.3关系的运算3-5.4关系的表示,关系的概念,特殊关系,关系的运算,关系的表示,21,3-5.1关系的概念及记号关系二元关系(binaryrelation)，简称关系，任一序偶的集合即确定了一个二元关系R，R中任一序偶可记为R或xRy。不在R中的任一序偶可记为R或xRyR1=,R2=|x,y是实数且xy定义域和值域：对任意关系R,可以定义:前域定义域（domain）:domR=x|y(xRy)值域（range）:ranR=y|x(xRy)域（field）:FLDR=domRranR,第二部分集合论,(1)集合非空,且它的元素都是有序对(2)集合是空集,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,22,例1:在实数中关系“”可记作“”=|x,y是实数且xy。例2:R1=,R1是二元关系.例3:R2=,a,1R2不是关系.在集合A上讨论“a爱b”的关系LA=肖峰，庄聚贤，阿紫，阿朱L=,A=段誉，木婉清，钟灵，王语嫣，慕容复L=,A=虚竹，李清露，L=，,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,23,二元关系的记号：,设R是二元关系，则Rx与y具有R关系xRy。对比:xRy(中缀(infix)记号)R(后缀(suffix)记号)R(x,y)(前缀(prefix)记号)(这里不同于谓词)例如:2R1R2。R5R4。,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,24,X到Y的二元关系R与XYX=x1,x2,Y=y1,y2,R1=,XY=,X到Y的二元关系令X和Y是任意两个集合，笛卡尔积XY的子集R称为X到Y的二元关系。R是X到Y的二元关系RXYRP(XY)（幂集）若|X|=m,|Y|=n,则|XY|=mn,故|P(XY)|=2mn，即X到Y不同的二元关系共有2mn个,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,25,X到Y的二元关系(举例),例:设A=a1,a2,B=b,则A到B的二元关系共有221=4个:R1=,R2=,R3=,R4=,B到A的二元关系也有4个:R5=,R6=,R7=,R8=,。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,26,X上的二元关系,X上的二元关系是XX的任意子集。R是X上的二元关系RXXRP(XX)。若|X|=m,则|XX|=m2,故|P(XX)|=2m2，即X上不同的二元关系共有2m2个。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,27,X上的二元关系(举例),例1:设A=a1,a2,AA=,则A上的二元关系共有16个:R1=,R2=,R3=,R4=,R5=,R6=,R7=,R8=,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,28,R9=,R10=,R11=,R12=,，R13=,，R14=,，R15=,，R16=,。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,29,例2:设A=a,则A上的二元关系共有2个:R1=,R2=.例3:设A=a,b,c,则A上的二元关系共有29=512个!,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,30,定义域,值域,域(举例),例:R1=a,b,R2=,R3=,.当a,b不是序偶时,R1不是关系.domR1=,ranR1=,FLDR1=domR2=c,e,ranR2=d,f,FLDR2=c,d,e,fdomR3=1,3,5,ranR3=2,3,4,FLDR3=1,2,3,4,5.,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,特殊关系,关系的运算,关系的表示,关系的概念,31,3-5.2一些特殊关系,设A是任意集合,则可以定义A上的：空关系(emptyrelation):恒等关系(identityrelation):IA=|aA全域关系(universalrelation):UA=AA=|xAyAUAB=AB=|xAyB,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的运算,关系的表示,关系的概念,特殊关系,32,设AR,则可以定义A上的：小于等于关系：LEA=|xAyAxy小于关系：LA=|xAyAx|xAyAx|y例:A=1,2,3,4,5,6,则DA=,。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的运算,关系的表示,关系的概念,特殊关系,33,设A为任意集合,则可以定义P(A)上的:包含关系:A=|xAyAxy真包含关系：A=|xAyAxy见P107例3：H=f,m,s,d长幼关系：,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的运算,关系的表示,关系的概念,特殊关系,34,3-5.3关系的运算,定理3-5.1：若Z和S是从集合X到集合Y的两个关系，则Z和S的并、交、补、差仍是X到Y的关系。因为Z、S、Z和S的并、交、补、差都是XY的子集,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,35,3-5.4二元关系的表示,(1)序偶集合的形式表达(2)关系矩阵：设A=a1,a2,an,B=b1,b2,bm,RAB,则R的关系矩阵MR=(rij)nm,其中rij=1,aiRbj或R0,aiRbj或R,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,36,例题：X=x1,x2,x3,x4,Y=y1,y2,y3,R=,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,37,例题：X=x1,x2,x3,x4,Y=y1,y2,y3,R=,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,38,例如:A=a,b,c,R1=,R2=,则110011MR1=101MR2=001000000,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,39,A=a1,a2,an，B=b1,b2,bn，RAB,首先在平面上做结点a1,a2,an，b1,b2,bn以“”表示(称为顶点)，若aiRbj，则从结点ai向结点bj画有向边，箭头指向bj，若aiRbj,则ai与bj之间没有线段连接，这样得到的图称为R的关系图GR。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,关系图,40,第二部分集合论,例题：X=x1,x2,x3,x4,Y=y1,y2,y3,R=,x1,x2,x3,x4,y1,y2,y3,矩阵表示,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,关系图,41,定义在集合A上的关系图有所不同例如,A=a,b,c,R1=,R2=,则关系图如下：,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,关系图,42,关系矩阵、关系图(讨论):,当A中元素标定次序后,RAA的关系图GR与R的序偶集合表达式可以唯一互相确定。R的序偶集合表达式，关系矩阵，关系图三者均可以唯一互相确定。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,关系的表示,关系的概念,特殊关系,关系的运算,43,小结:本节介绍了关系的定义、几种特殊的关系及关系的表示。重点掌握关系的表示方法。,作业：,第二部分集合论,P109(2)(5)b)d),P104(1)b)(2)(5),44,第二部分集合论,主要内容集合3-1集合的概念和表示法3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分与覆盖,3-10等价关系与等价类3-11相容关系3-12序关系函数4.1函数的基本概念4.2复合函数与逆函数,45,（1）自反性(reflexivity)（2）反自反性(irreflexivity)（3）对称性(symmetry)（4）反对称性(antisymmetry)（5）传递性(transitivity),3-6关系的性质,自反性,反自反性,对称性,反对称性,传递性,46,需要指出：,从X到Y的关系R是XY的子集，即RXY，而XY（XY）（XY）所以R（XY）（XY）令Z=XY，则RZZ因此，我们今后通常限于讨论同一集合上的关系。,第二部分集合论,需要注意：关系和运算,关系：=、|x,y都是实数且x|PQ是重言式中“”取、时集合论：、：|AB注意：非自反不一定是反自反的。即存在有关系既不是自反的也不是反自反的。,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,51,对称性symmetry：设RAA,如果对于每个x,yA，每当xRy，就有yRx，则称集合A上的关系R是对称的。R在A上对称(x)(y)(xAyAxRyyRx).R非对称(x)(y)(xAyAxRyyRx)定理：R是对称的MR是对称的GR的任何两个顶点之间若有边,则必有两条方向相反的有向边.,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,52,对称性(举例)：空关系、恒等关系、全域关系实数：、=：|x,y都是实数且x=y几何图形：三角形的全等：|AB、相似数理逻辑：|PQ是重言式中“”取、时集合论：、不相交：|AB=整数：同余人之间的关系：同学关系、朋友关系、邻居关系,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,53,反对称性antisymmetry：设RAA,如果对于每个x,yA,每当xRy和yRx，必有x=y，则称集合A上的关系R是反对称的。R是反对称的(x)(y)(xAyAxRyyRxx=y)(x)(y)(xAyAxyxRyyRx).R非反对称(x)(y)(xAyAxRyyRxxy)定理：R是反对称的在MR中,xixj(ijrij=1rji=0)在GR中,xixj(ij),若有有向边,则必没有。,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,54,反对称性(举例)：空关系实数：、|PQ是重言式集合论：|AB人之间的关系：父与子关系整数：整除关系：|x,y都是整数且x|y注意：非对称不一定反对称；可能有某种关系即是对称的又是反对称的。例如：A=1,2,3,S=,S在A上即是对称的又是反对称的。N=,N在A上即不是对称的又不是反对称的。,第二部分集合论,，恒等关系,、=,、=,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,55,传递性transitivity：设RAA,如果对于任意的x,y,zA,每当xRy，yRz时就有xRz，称关系R在A上是传递的。R在A上是传递的(x)(y)(z)(xAyAzAxRyyRzxRz)R非传递(x)(y)(z)(xAyAzAxRyyRzxRz)。定理：R是传递的在GR中,xixjxk(ijk),若有有向边和,则必有。,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,56,传递性(举例)：空关系、恒等关系、全域关系实数：、|x,y都是整数且x|y几何图形：三角形的全等：|AB、相似数理逻辑：、：|PQ是重言式集合论：、：|AB人之间的关系：同姓、同性别,自反性与反自反性是相互矛盾的，不能同时成立对称性和反对称性不矛盾、可以同时成立,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,57,例1：在N=1,2,上：、：|xNyNxy自反,反对称,传递、|xNyNx|xNyNx|y(整除关系)自反,反对称,传递IN=|xNyNx=y(恒等关系)自反,对称,反对称,传递EN=|xNyN=NN(全域关系)自反,对称,传递,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,58,例2：判断以下关系所具有的性质。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7=,第二部分集合论,反对称,传递,反对称,自反,对称,传递,对称,自反,反对称,传递,反自反，对称，反对称，传递,第二部分集合论,第二部分集合论,第二部分集合论,第二部分集合论,自反性,对称性,反对称性,传递性,反自反性,59,第二部分集合论,xA,有R,xA,有R,若R则R,若R,且xy,则R,若R且R则R,IAR,RIA=,R=R1,RR1IA,RRR,主对角线元素全是1,主对角线元素全是0,矩阵是对称矩阵,若rij1,且ij,则rji0,M2中1位置,M中相应位置都是1,每个顶点都有环,每个顶点都没有环,两点之间有边,是一对方向相反的边,两点之间有边,是一条有向边,点xi到xj有边,xj到xk有边,则xi到xk也有边,第二部分集合论,第二部分