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

1,第二部分 集合论,主要内容集合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 复合函数与逆函数,2,张继科,宁泽涛,上节内容回顾3-1 集合的概念和表示法集合的概念：集合的表示法：列举法、叙述法集合的关系：相等、子集、真子集空集、全集、幂集,张继科,第二部分 集合论,3-2 集合的运算交集、并集、相对补集、绝对补集、对称差,苹果,Mac,3,3-2 集合的运算集合运算等价公式AA=A AA=AAE=E A=A=A AE=AAA=E AA=A=A=E E=AB=BA AB=BAA(AB)=A A(AB)=A(AB)=AB(AB)=ABA-B=AB,第二部分 集合论,(AB)C=A(BC)(AB)C=A(BC)A(BC)=(AB)(AC)A(BC)=(AB)(AC),4,第二部分 集合论,主要内容集合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 复合函数与逆函数,第二部分 集合论,笛卡尔积,3-4序偶与笛卡尔积3-4.1 序偶3-4.2 笛卡尔积,序偶的概念,序偶ordered pair由两个固定次序的客体 a,b组成的序列称为序偶，记作，其中a,b称为序偶的分量。其中,a是第一元素,b是第二元素。序偶相等两个序偶相等：=,当且仅当 xu,y=v。注意:ab,笛卡尔积,序偶的概念,三元组：第一元素也是序偶的序偶=,c.注意 不是三元组！n(2)元组：=,an.N元组相等的条件=ai=bi,i=1,2,n.,笛卡尔积,序偶的概念,笛卡尔积令A和B是任意两个集合，若序偶的第一个元素是A的元素，第二个元素是B的元素，所有这样的序偶集合，称为集合A和B的笛卡尔乘积或直积，记为AB，AB=|xAyB,笛卡尔积,序偶的概念,例1:A=,a,B=1,2,3.AB=,.BA=,.AA=,.BB=,.,笛卡尔积,序偶的概念,当|A|=m，|B|=n时，|AB|是多少？|AB|=mn,笛卡尔积,序偶的概念,笛卡尔积的性质,1.非交换:AB BA(除非 A=B 或者 A=或者 B=)例如:A=1,B=2.AB=,BA=.2.非结合:(AB)C A(BC)(除非 A=或者 B=或者 C=)举例:A=B=C=1.(AB)C=,1,A(BC)=.,笛卡尔积,序偶的概念,3.笛卡尔积分配律：（对或运算满足）（1）A(BC)=(AB)(AC)（2）A(BC)=(AB)(AC)（3）(BC)A=(BA)(CA)（4）(BC)A=(BA)(CA),笛卡尔积的性质,笛卡尔积,序偶的概念,3.笛卡尔积分配律(证明(1)A(BC)=(AB)(AC).证明:,A(BC)x A y(BC)x A(y B y C)(xAyB)(xAyC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC).#,笛卡尔积的性质,笛卡尔积,序偶的概念,4.其他性质：设A,B,C,D是任意集合,(1)若A,则ABAC BA CA BC（即书上的定理3-4.2）(2)AC BD ABCD.（即书上的定理3-4.3）(3)AB=A=B=,笛卡尔积的性质,笛卡尔积,序偶的概念,证明(1)若A,则ABAC BC.证明:()若 B=,则 BC.设 B,由A,设xA,y,yB，AB AC xAyC yC.BC()若B=,则AB=AC.设 B.,AB xAyB xAyC AC ABAC.#,笛卡尔积,序偶的概念,n维笛卡尔积,定义 n维笛卡尔积：A1A2An=|x1A1x2A2xn An AAA=An|Ai|=ni,i=1,2,n|A1A2An|=n1n2nn.n维笛卡尔积性质与2维笛卡尔积类似.,笛卡尔积,序偶的概念,小结：本节介绍了序偶、有序n元组及笛卡尔积的概念。重点理解有序n元组及笛卡尔积的概念。作业：,第三章 集合与关系,P104(1)b)(2)(5),18,第二部分 集合论,主要内容集合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 复合函数与逆函数,现实中的“关系”兄弟关系、长幼关系、同学关系、邻居关系，上下级关系等。数学上的关系：大于关系、小于关系，整除关系。例如：“3小于5”，“x大于y”，“点a在b与c之间”。如何表示关系呢？谓词是一种关系的表达：P(a,b):a是b的长辈,第二部分 集合论,谓词仅仅表示了关系形式，侧重于对客体的描述,本章主要内容：借助序偶和集合来描述关系本身,例如：火车票与座位之间的对号关系。设X表示火车票的集合，Y表示座位的集合，则对于任意的 xX 和 y Y，必定有 x 与y有“对号”关系 x 与y没有“对号”关系。二者之一令R表示“对号”关系，则上述问题可以表示为 xRy 或 xRy。,亦可表示为 R 或 R，因此我们看到对号关系是序偶的集合。,第二部分 集合论,第二部分 集合论,3-5关系及其表示3-5.1 关系的概念3-5.2 几种特殊关系3-5.3 关系的运算3-5.4 关系的表示,关系的概念,特殊关系,关系的运算,关系的表示,3-5.1关系的概念及记号关系二元关系(binary relation)，简称关系，任一序偶的集合即确定了一个二元关系R，R中任一序偶 可记为 R或xRy。不在R中的任一序偶 可记为 R或xRyR1=,R2=|x,y是实数且xy定义域和值域：对任意关系R,可以定义:前域定义域（domain）:dom R=x|y(xRy)值域（range）:ran R=y|x(xRy)域（field）:FLD R=dom R ran R,第二部分 集合论,(1)集合非空,且它的元素都是有序对(2)集合是空集,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,例1:在实数中关系“”可记作“”=|x,y是实数且x y。例2:R1=,R1是二元关系.例3:R2=,a,1 R2不是关系.在集合A上讨论“a爱b”的关系LA=肖峰，庄聚贤，阿紫，阿朱L=,A=段誉，木婉清，钟灵，王语嫣，慕容复L=,A=虚竹，李清露，L=，,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,二元关系的记号：,设R是二元关系，则 R x与y具有R关系 xRy。对比:xRy(中缀(infix)记号)R(后缀(suffix)记号)R(x,y)(前缀(prefix)记号)(这里不同于谓词)例如:2 R 1 R 2。R 5 R 4。,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,X到Y的二元关系R与X YX=x1,x2,Y=y1,y2,R1=,X Y=,X到Y的二元关系令X和Y是任意两个集合，笛卡尔积XY的子集R称为X到Y的二元关系。R是X到Y的二元关系RXY RP(XY)（幂集）若|X|=m,|Y|=n,则|XY|=mn,故|P(XY)|=2mn，即X到Y不同的二元关系共有2mn个,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,X到Y的二元关系(举例),例:设 A=a1,a2,B=b,则A到B的二元关系共有221=4个:R1=,R2=,R3=,R4=,B到A的二元关系也有4个:R5=,R6=,R7=,R8=,。,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,X上的二元关系,X上的二元关系是XX的任意子集。R是X上的二元关系 RXX RP(XX)。若|X|=m,则|XX|=m2,故|P(XX)|=2 m2，即X上不同的二元关系共有2 m2个。,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,X上的二元关系(举例),例1:设 A=a1,a2,AA=,则A上的二元关系共有16个:R1=,R2=,R3=,R4=,R5=,R6=,R7=,R8=,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,R9=,R10=,R11=,R12=,，R13=,，R14=,，R15=,，R16=,。,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,例2:设 A=a,则A上的二元关系共有2个:R1=,R2=.例3:设 A=a,b,c,则A上的二元关系共有29=512个!,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,定义域,值域,域(举例),例:R1=a,b,R2=,R3=,.当a,b不是序偶时,R1不是关系.dom R1=,ran R1=,FLD R1=dom R2=c,e,ran R2=d,f,FLDR2=c,d,e,fdom R3=1,3,5,ran R3=2,3,4,FLD R3=1,2,3,4,5.,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,特殊关系,关系的运算,关系的表示,关系的概念,3-5.2一些特殊关系,设A是任意集合,则可以定义A上的：空关系(empty relation):恒等关系(identity relation):IA=|a A 全域关系(universal relation):UA=AA=|xA yAUA B=AB=|xA yB,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的运算,关系的表示,关系的概念,特殊关系,设AR,则可以定义A上的：小于等于关系：LEA=|xA yA xy 小于关系：LA=|xA yA x|xA yA x|y 例:A=1,2,3,4,5,6,则 DA=,。,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的运算,关系的表示,关系的概念,特殊关系,设A为任意集合,则可以定义P(A)上的:包含关系:A=|xA yA xy 真包含关系：A=|xA yA xy 见P107 例3：H=f,m,s,d长幼关系：,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的运算,关系的表示,关系的概念,特殊关系,3-5.3 关系的运算,定理3-5.1：若Z和S是从集合X到集合Y的两个关系，则Z和S的并、交、补、差仍是X到Y的关系。因为Z、S、Z和S的并、交、补、差都是XY的子集,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,3-5.4二元关系的表示,(1)序偶集合的形式表达(2)关系矩阵：设 A=a1,a2,an,B=b1,b2,bm,RAB,则R的关系矩阵 MR=(rij)nm,其中rij=1,ai R bj 或 R 0,ai R bj 或 R,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,例题：X=x1,x2,x3,x4,Y=y1,y2,y3,R=,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,例如:A=a,b,c,R1=,R2=,则 1 1 0 0 1 1 MR1=1 0 1 MR2=0 0 1 0 0 0 0 0 0,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,A=a1,a2,an，B=b1,b2,bn，RAB,首先在平面上做结点a1,a2,an，b1,b2,bn以“”表示(称为顶点)，若aiRbj，则从结点ai向结点bj画有向边，箭头指向bj，若aiRbj,则ai与bj之间没有线段连接，这样得到的图称为R的关系图 GR。,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,关系图,第二部分 集合论,x1,x2,x3,x4,y1,y2,y3,矩阵表示,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,关系图,定义在集合A上的关系图有所不同例如,A=a,b,c,R1=,R2=,则关系图如下：,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,矩阵表示,关系图,关系矩阵、关系图(讨论):,当A中元素标定次序后,RAA的关系图GR与R的序偶集合表达式可以唯一互相确定。R的序偶集合表达式，关系矩阵，关系图三者均可以唯一互相确定。,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,关系的表示,关系的概念,特殊关系,关系的运算,小结:本节介绍了关系的定义、几种特殊的关系及关系的表示。重点掌握关系的表示方法。,作业：,第二部分 集合论,P109(2)(5)b)d),P104(1)b)(2)(5),45,第二部分 集合论,主要内容集合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）自反性(reflexivity)（2）反自反性(irreflexivity)（3）对称性(symmetry)（4）反对称性(antisymmetry)（5）传递性(transitivity),3-6 关系的性质,自反性,反自反性,对称性,反对称性,传递性,需要指出：,从X到Y的关系R是XY 的子集，即RXY，而XY（XY）（XY）所以R（XY）（XY）令Z=XY，则RZZ因此，我们今后通常限于讨论同一集合上的关系。,第二部分 集合论,需要注意：关系和运算,关系：=不相交 朋友 同学 父子运算：,自反性,反自反性,对称性,反对称性,传递性,自反性reflexivity：设R为定义在A上的二元关系，即RAA,如果对于每一个xA，有xRx(R)，则称二元关系R是自反的。R在A上是自反的(x)(xA xRx)R在A上是非自反的(x)(xA R)。定理：R是自反的 IA RMR主对角线上的元素全为1GR的每个顶点处均有自环。,第二部分 集合论,自反性,反自反性,对称性,反对称性,传递性,自反性(举例)：恒等关系、全域关系实数：=：|x,y都是实数且xy几何图形：三角形的全等：|AB、相似 数理逻辑：、：|PQ、|PQ是重言式集合论：|A B,第二部分 集合论,第二部分 集合论,自反性,反自反性,对称性,反对称性,传递性,反自反性irreflexivity：设RAA,如果对于每一个xA，有R，则称二元关系R是反自反的。R在A上是反自反的(x)(xA R)。R在A上是非反自反的(x)(xA xRx)定理：R是反自反的 IAR=MR主对角线上的元素全为0 GR的每个顶点处均无自回路（无环）。,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反自反性(举例)：空关系实数：、|x,y都是实数且x|PQ是重言式 中“”取、时集合论：、：|A B注意：非自反不一定是反自反的。即存在有关系既不是自反的也不是反自反的。,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,对称性symmetry：设RAA,如果对于每个x,yA，每当 xRy，就有 yRx，则称集合A上的关系R是对称的。R在A上对称(x)(y)(xAyAxRyyRx).R非对称(x)(y)(xAyAxRyyRx)定理：R是对称的 MR是对称的 GR的任何两个顶点之间若有边,则必有两条方向相反的有向边.,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,对称性(举例)：空关系、恒等关系、全域关系实数：、=：|x,y都是实数且x=y几何图形：三角形的全等：|AB、相似 数理逻辑：|PQ是重言式 中“”取、时集合论：、不相交：|AB=整数：同余人之间的关系：同学关系、朋友关系、邻居关系,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反对称性antisymmetry：设RAA,如果对于每个x,yA,每当 xRy和yRx，必有x=y，则称集合A上的关系R是反对称的。R是反对称的(x)(y)(xAyA xRy yRx x=y)(x)(y)(xAyA xy xRy yRx).R非反对称(x)(y)(xA yA xRy yRx xy)定理：R是反对称的 在MR中,xixj(ij rij=1rji=0)在GR中,xixj(ij),若有有向边,则必没有。,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,反对称性(举例)：空关系实数：、|P Q是重言式 集合论：|A B人之间的关系：父与子关系整数：整除关系：|x,y都是整数且x|y注意：非对称不一定反对称；可能有某种关系即是对称的又是反对称的。例如：A=1,2,3,S=,S在A上即是对称的又是反对称的。N=,N在A上即不是对称的又不是反对称的。,第二部分 集合论,，恒等关系,、=,、=,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,传递性transitivity：设RAA,如果对于任意的x,y,zA,每当xRy，yRz时就有xRz，称关系R在A上是传递的。R在A上是传递的(x)(y)(z)(xAyAzAxRyyRzxRz)R非传递(x)(y)(z)(xAyAzAxRy yRzxRz)。定理：R是传递的 在GR中,xi xj xk(ijk),若有有向边和,则必有。,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,传递性(举例)：空关系、恒等关系、全域关系实数：、|x,y都是整数且x|y几何图形：三角形的全等：|AB、相似数理逻辑：、：|PQ是重言式 集合论：、：|A B人之间的关系：同姓、同性别,自反性与反自反性是相互矛盾的，不能同时成立对称性和反对称性不矛盾、可以同时成立,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,例1：在 N=1,2,上：、：|xNyNxy自反,反对称,传递、|xNyNx|xNyNx|y(整除关系)自反,反对称,传递IN=|xNyNx=y(恒等关系)自反,对称,反对称,传递EN=|xNyN=NN(全域关系)自反,对称,传递,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,例2：判断以下关系所具有的性质。A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,R7=,第二部分 集合论,反对称,传递,反对称,自反,对称,传递,对称,自反,反对称,传递,反自反，对称，反对称，传递,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,第二部分 集合论,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也有边,第二部分 集合论,第二部分 集合论,第二部分 集合论,第二部分 集合论,自反性,对称性,反对称性,传递性,反自反性,设 A=1,2,3，下面分别给出集合A上三个关系的关系图，试判断它们的性质。,（2）非自反，也不是反自反，非对称，反对称，可传递。,（3）是自反的，对称的，可传递的，不是反自反，也不是反对称。,解（1）是自反的，非对称，不是反对称，不可传递,62,第二部分 集合论,主要内容集合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 复合函数与逆函数,63,第一部分 数理逻辑,上节内容回顾,3-5 关系及其表示 3-5.1 关系关系：序偶的集合定义域、值域、域 3-5.2 一些特殊关系空关系、恒等关系、全域关系关系的交并补差还是关系 3-5.3 关系的表示序偶集合形式关系矩阵MR关系图GR,3-6 关系的性质 自反性xA,有R反自反性xA,有R对称性若R则R反对称性若R,且xy,则 R传递性若R 且R 则R,第二部分 集合论,xA,有R,xA,有R,若R则R,若R,且xy,则 R,若R 且R 则R,IAR,RIA=,R=Rc,RRcIA,RRR,主对角线元素全是1,主对角线元素全是0,矩阵是对称矩阵,若rij1,且ij,则rji0,M2中1位置,M中相应位置都是1,每个顶点都有环,每个顶点都没有环,两点之间有边,是一对方向相反的边,两点之间有边,是一条有向边,点xi到xj有边,xj 到xk有边,则xi到xk也有边,设 A=1,2,3，下面分别给出集合A上三个关系的关系图，试判断它们的性质。,（2）非自反，也不是反自反，非对称，反对称，可传递。,（3）是自反的，对称的，可传递的，不是反自反，也不是反对称。,解（1）是自反的，非对称，不是反对称，不可传递,小结:本节介绍了关系的基本性质及其判别方法。,作业：P113（3）（6）,第二部分 集合论,小结:本节介绍了关系的基本性质及其判别方法。,作业：P113（3）（6）,第二部分 集合论,