离散数学-集合论

2020/5/26,1,离散数学,计算机学院软件与理论教研室（313）,DiscreteMathematics,Email:cslq,Tel:4994019808,2020/5/26,2,第二部分,集合论,Set,RelationandMapping,2020/5/26,3,第三章集合、关系与映射,关系即二元关系,它是集合直乘积的子集映射是特殊的二元关系19世纪末著名德国数学家康托(G.cantor)集合已经发展成为数学及其他各学科不可缺少的描述工具成为数学中最为基本的概念集合论分为两种体系朴素集合论体系(康托集合论体系).康托从抽象原则出发概括出:满足某性质的个体放在一起组成集合隐含矛盾,即罗素(Russell)悖论.公理集合论体系(属于数理逻辑范畴),2020/5/26,4,3.1集合及其运算,1.集合及其表示法用大写英文字母A,B,C,表示集合并用xA表示x是集合A中的元素,读作“x属于A”用xA表示x不是A中的元素,读作“x不属于A”.一般,集合有两种表示法:列举法和描述元素性质法列举法A=a,b,c,d,e;B=书,笔记本,铅笔,课桌,黑板;C=0,1,-3,6;D=北京,天坛,故宫,地球,宇宙.描述元素性质法=x|x是英文字母;Z=x|x是整数;,2020/5/26,5,集合及其表示法,需要注意以下几点：集合中的元素各不相同如1,2,3,4与1,1,2,3,4,4是相同的集合都是含元素1,2,3,4的集合集合中的元素不规定次序如：1,2,3,4=4,2,3,1.有些集合的两种表示法能互相转换,有些则不能如：x|x是英文字母=a,b,c,d,e,f,g,x,y,z;x|x是非负偶数=0,2,4,6,8,10,2n,;x|x是实数不能转换为列举法表示.,2020/5/26,6,集合及其表示法,一些常用集合的表示法:N=x|x是自然数=0,1,2,n,Z=x|x为整数=,-3,-2,-1,0,1,2,3,Z+=x|xZx0=1,2,3,n,Q=x|x是有理数R=x|x为实数还有：P表示素数集合O表示奇数集合E表示偶数集合,2020/5/26,7,集合间的包含与相等,2.定义3.1.1.设A,B为集合，若B中的元素都是A中的元素,则称B是A的子集,记作BA,称A包含B,或B包含于A,并以BA表示B不是A的子集.即BAx(xBxA)BAx(xBxA).定义3.1.2.设A,B为集合,若集合AB且AB,则称A为B的真子集,记作AB.即ABx(xAxB)x(xBxA).例如：若A=1,2,4,B=1,2,3,4,5,则AB,而且AB.对任意集合A有:AA(自反性)对任意集合A,B,C,若AB且BC,则AC(传递性),2020/5/26,8,空集与全集,定义3.1.3.设A,B为集合,若AB且BA,则称A与B相等,记作A=B.定义3.1.4.称不拥有任何元素的集合为空集,记作.空集是任意集合的子集合,是任意非空集合的真子集合和的关系是？空集是任意集合的子集,可以形象地说:是“最小”的集合.但没有最大的集合.在讨论某些具体问题时,往往使用一个在相对的意义下是“最大”的集合”.,2020/5/26,9,空集与全集,定义3.1.5.如果限定所讨论的集合都是某一集合E的子集,则称E为全集全集是一个相对的概念,不同的实际问题可以定义不同的全集.例如当被讨论的集合仅仅是0,2,4,6,6,8时,全集可设为0,2,4,6,8或x|x是10以内的自然数等,2020/5/26,10,集合的幂集,3.定义3.1.6.设A为一个集合,称由A的所有子集组成的集合为A的幂集,记作P(A),即P(A)=X|XA.如：设A=1,2,3则P(A)=,1,2,3,1,2,1,3,2,3,A.若|A|=n,则P(A)的元素个数|P(A)|=2n.元素个数有限的集合称有穷集,对其子集有一种编码方法:设A=a1,a2,a3则A2=A010=a2,A5=A101=a1,a3.,2020/5/26,11,集合的运算,4.定义3.1.7.设A,B为两个集合.称由A与B的公共元素组成的集合为A与B的交集,记作AB即AB=x|xAxB称由A与B的全体元素组成的集合为A与B的并集,记作AB即AB=x|xAxB称属于A,但不属于B的元素组成的集合为A与B的相对补集记为A-B,即A-B=x|xAxB称属于A而不属于B,或属于B而不属于A的元素组成的集合为A与B的对称差集,记为AB即AB=x|(xAxB)(xBxA)设E为全集,AE,称E-A为A的绝对补集,记作A即A=x|xA.,2020/5/26,12,集合的运算,例3.1.1设A=a,b,c,d,eB=a,c,e,gE=a,b,c,d,e,f,g,h则:AB=a,b,c,d,e,gAB=a,c,eA-B=b,dB-A=gAB=b,d,g=(A-B)(B-A)=(AB)-(AB)A=f,g,hB=b,d,f,h.,2020/5/26,13,集合的运算,集合运算的Venn图表示：,2020/5/26,14,基本恒等式,5.集合运算的基本恒等式及其应用定理3.1.1设A,B,C是任意集合,E为全集,则有如下恒等式：幂等律AA=A;AA=A.交换律AB=BA;AB=BA.结合律(AB)C=A(BC);(AB)C=A(BC).分配律A(BC)=(AB)(AC);A(BC)=(AB)(AC).德摩根律绝对形式(AB)=AB;(AB)=AB.相对形式A-(BC)=(A-B)(A-C);A-(BC)=(A-B)(A-C).,2020/5/26,15,基本恒等式,吸收律A(AB)=A;A(AB)=A.零律AE=E;A=.同一律A=A;AE=A.排中律AA=E.矛盾律AA=.余补律=E;E=.双重否定律(A)=A.补交转换律A-B=AB.,2020/5/26,16,基本恒等式,关于对称差运算有以下恒等式:交换律AB=BA结合律A(BC)=(AB)C.对满足分配律A(BC)=(AB)(AC).A=A;AE=A.AA=;AA=E.证明集合等式或包含式主要有以下两种方法:用集合的并、交、补、对称差等定义,通过逻辑等值演算证明新的等式或包含式由已知的集合等式或包含式,通过集合演算证明新的集合等式或包含式,2020/5/26,17,集合恒等式的应用,例3.1.3证明:对任意集合A,B有A(AB)=A.证明:x.xA(AB)xA(xAxB)xA例3.1.4证明:对任意集合A,B有A(AB)=A.证明:A(AB)=(A)(AB)=A(B)=A=A,(前式使用了并、交运算定义,后式运用了逻辑演算的吸收律),A=A=A(B)=(A)(AB)=A(AB).,2020/5/26,18,续,例3.1.5若AB=AC,则B=C.证明:采用方法AB=ACA(AB)=A(AC)(AA)B=(AA)CB=CB=C.,按定义若AB且BA则B=C证明,并不容易,2020/5/26,19,续,例3.1.6证明:A(BC)=(AB)(AC).证明:(AB)(AC)=(AB)(AC)(AC)(AB)=(AB)(AC)(AC)(AB)=(ABC)(ACB)=A(B-C)(C-B)=A(BC),2020/5/26,20,续,对满足分配律,对也满足分配律吗?即是否对任意集合A,B,C有A(BC)=(AB)(AC).,设E=a,b,c,d,e,f,A=a,b,cB=b,c,dC=c,d,eA(BC)=a,b,cb,e=a,b,c,e(AB)(AC)=a,b,c,da,b,c,d,e=e.,对不满足分配律,2020/5/26,21,续,(AB)(AC)=(AB)AC)(AC)AB)=(BAC)(CAB)=A(B-C)(C-B)=A(BC).,(AB)(AC)=A(BC)=(BC)-A,2020/5/26,22,有限集合并集的元素计数,定理3.1.2.设A1,A2,An是n个有穷集合,则它们并集的元素个数可由包含排斥公式计算:证明:设A,B是两个有限集合,则结论显然成立,即有:设对n=k结论成立,即有:当n=k+1时,从由前两式代入整理即得要证结果,2020/5/26,23,续,例3.1.7设A,B,C是三家计算机公司，它们的固定客户分别有12，16和20家。已知A与B，B与C，C与A的公共固定客户分别为6，8和7家，三家的公共固定客户有5家，求三家计算机公司拥有的固定客户家数。解:以A,B,C分别表记A,B,C三家计算机公司的客户集合,知|A|=12,|B|=16,|C|=20,|AB|=6,|AC|=7,|BC|=8,|ABC|=5.求三家计算机公司拥有的固定客户家数,即要计算|ABC|的元素个数.由有限集合并集元素的计数公式包含排斥公式:|ABC|=(|A|+|B|+|C|)-(|AB|+|AC|+|BC|)+|ABC|=(12+16+20)-(6+7+8)+5=32.,2020/5/26,24,罗素悖论,在数理逻辑中,讨论过悖论,罗素悖论在集合论中,其表现形式是:罗素悖论在以所有集合为个体的论域上定义集合S=X|XX,即一切不是自身元素的集合的集合.问题是SS吗?若SS,由定义则SS;若SS,再由定义则SS.矛盾矛盾的本质在于康托的朴素集合论在刻画集合的方法上缺少限制,以为凡是一个性质就能概括一个集合,2020/5/26,25,3.2关系,关系是离散数学中刻画元素之间相互联系的一个重要概念关系数据库模型最基本的关系是二元关系,即发生在两个个体之间的关系.竞赛中的胜负关系,如果每一场比赛都是在两个对手之间进行,不考虑平局,那么比赛x胜y就可以表示成x,y关系a,b,c,b,c,a记录了3场比赛的结果c是第一名,a是第二名,b是最后一名.该例是集合a,b,c上的一个二元关系,2020/5/26,26,3.2.1关系的定义及其表示,有序对与笛卡尔积定义3.2.1.由两个元素,比如x和y,按照一定次序构成的二元组称为一个有序对,记作x,y.其中x是序对的第一元素,y是序对的第二元素.直角坐标系中点的坐标(1,-2),(0,5)有序对中,如果两个元素不相等,是不能交换次序的.(0,1)与(1,0)代表不同的有序对两个有序对x,y与u,v相等x=u且y=v.,2020/5/26,27,续,例3.2.1.设有序对x+y,3=3y-2,x+5根据有序对相等的充要条件,解由第一、第二元素对应相等组成的二元一次方程组得:x=-2,y=0.定义3.2.2.设A,B为集合,以A中元素作为第一元素,B中元素作为第二元素做有序对,所有这样的有序对构成的集合称为A与B的笛卡尔积,记作AB.符号化表示为AB=x,y|xAyB.,2020/5/26,28,续,例3.2.2.设A=0,1,B=a,b则AB=0,a,0,b,1,a,1,bBA=a,0,a,1,b,0,b,1.有穷集A,B的笛卡尔积是有穷集,且|AB|=|A|B|.笛卡尔积不适合交换律,即ABBA除非A=B,或者A,B中至少有一空集.对任意集合S,S=S=.笛卡尔积不适合结合律,即(AB)CA(BC)除非A,B,C中至少有一空集,2020/5/26,29,关系的定义及其表示,笛卡尔积运算对并和交运算适合分配律：n阶笛卡尔积：即n个集合依次连乘的笛卡尔积当这n个集合都为同一集合A时,称作A的n次笛卡尔幂.A1A2An=x1,x2,xn|xiAi,i=1,2,nAn=x1,x2,xn|xiA,i=1,2,n.空间直角坐标系中全体点的集合就是3阶笛卡尔积,亦称A的3次笛卡尔幂，即RRR=R3.,A(BC)=(AB)(AC)A(BC)=(AB)(AC)(AB)C=(AC)(BC)(AB)C=(AC)(BC),2020/5/26,30,续,二元关系(关系)建立在二阶笛卡尔积的集合之上定义3.2.3.如果一个集合中的元素都是有序对或者这个集合是空集,则称这个集合是一个二元关系,记作R.序对x,yR简记为xRy,否则记作.例如R=a,bb,c就可以记为aRb,bRc.显然aRc.例3.2.3.R=x,y|x,yN,x+y1=0,0,0,1,1,0.R=x,y|x,yR,x2+y2=1平面单位圆.,2020/5/26,31,续,例3.2.4.关系数据库中的一个实体模型.表中包括了若干职工的记录每个记录是一个5元组,由5个字段构成,称为属性这些元组的集合构成了一个5元关系R=x1,x2,x3,x4,x5|xi是相应属性.,2020/5/26,32,续,定义3.2.4.设A,B为集合,AB的任何子集所定义的二元关系称为从A到B的二元关系当A=B时则称为A上的二元关系.例3.2.5.A=a,bB=1,2,3则R1=a,1R2=ABR3=R3=,R4=a,a,b,bR5=a,a,a,b,b,a,b,b=A2,都是从A到B的二元关系,都是A上的二元关系.,2020/5/26,33,续,设|A|=m,|B|=n,则|AB|=mnAB的不同的子集有2mn个存在2mn个不同的从A到B的二元关系如果有限集A有|A|=3个元素,|A2|=|AA|=9则A上不同的二元关系有29=512之多,即3元集a,b,c上不同的二元关系有512个,2020/5/26,34,续,定义3.2.5.设A为任意集合,则A=;EA=x,y|xAyA=AA=A2;IA=x,x|xA.分别称为A上的空关系,全域关系与恒等关系.例3.2.6.A=a,bEA=a,a,a,b,b,a,b,b;IA=a,a,b,b.,设A为给定的集合,则LA=x,y|x,yAxyAR,R为实数集;DA=x,y|x,yAx整除yAZ*;R=x,y|x,yAxyA为集合族(S).被分别称为小于等于关系,整除关系和包含关系,2020/5/26,35,二元关系的表示,除了使用集合表达式定义二元关系以外,还可以使用关系矩阵和关系图来表示二元关系.关系矩阵通常用于表示从有穷集合A到有穷集合B的关系或者有穷集合A上的关系关系图只能表示有穷集合A上的关系定义3.2.6.设A=x1,x2,xn,B=y1,y2,ym,R是从A到B的关系,R的关系矩阵是nm级布尔矩阵:MR=(rij)nm,其中rij=1xiRyj(xi,yjR)当R为A上的关系时,R的关系矩阵是n阶方阵,定义3.2.7.设A=x1,x2,xn,R的关系图是GR=A,R其中A为G的结点集,R为边集.xi,xjA,如果xiRxj,在图中就有一条从xi到xj的有向边,2020/5/26,36,二元关系的表示,例3.2.7.设A=a1,a2,a3,a4,a5R=a1,a1,a2,a3,a2,a4,a3,a1,a3,a3,a4,a5,a5,a2,a5,a4,有穷集合定义的关系矩阵和关系图是唯一的,MR=,a2,a5,a4,a3,a1,GR:,2020/5/26,37,3.2.2关系的运算,二元关系作为集合,可以进行并、交、相对补、对称差等运算还可定义其他一些常用的关系运算.定义3.2.8.设R为二元关系R的定义域、值域和域分别记作domR,ranR,fldRdomR=x|y(x,yR)ranR=y|x(x,yR)fldR=domRranR.,例3.2.8.设R=a,b,a,b,a,b,c,c则:domR=a,c,aranR=b,b,cfldR=a,b,c,a,b,c.,2020/5/26,38,续,定义3.2.9.设R为二元关系,R的逆记作R-1，R-1=y,x|x,yR.关系R的逆R-1就是R的每个有序对的两个元素交换以后得到的关系如果R是整数集Z上的小于关系,则R-1就是Z上的大于关系定义3.2.10.设R,S为二元关系,R与S的合成记作RS,RS=x,z|y(x,yRy,zS),2020/5/26,39,续,例3.2.9.设R=a,b,a,b,a,b,c,cS=b,a,b,b,c,b,c,cRS=a,b,a,a,a,b,c,bSR=b,b,b,b关系合成不适合交换律可以把关系看作是一种作用,如果x,yR,y,zS,那么x通过R的作用变到y,y接着通过S的作用又变到z.在R和S的合成作用下将x变到了z,因此x,zRS.这里的y起到一个中介或桥梁的作用.如果对于给定的关系R和S,不存在满足这种条件的中介y,那么RS=.,2020/5/26,40,关系的合成运算,第一种方法是关系图示法.关系图示法只适用于含有有限个有序对的关系给定含有n个有序对的关系R,R的图示由n条有向边构成.将domR中的元素画在左边,ranR的元素画在右边如果对于xdomR,yranR,x,yR,那么从代表x的结点到代表y的结点画一条有向边.所有的n条有向边就构成了R的图示为求R与S的合成,先画出R的图示,在这个图示的后面接上S的图示.如果ranR与domS含有共同的元素,那么这个元素只能是同一个结点,而不能画成两个结点.在这个图中,如果从domR的结点x,经过两步有向边到达ranS的结点z,那么x,zRS.,2020/5/26,41,例3.2.9.设R=a,b,a,b,a,b,c,cS=b,a,b,b,c,b,c,c,a。b。a。a。b。b。c。c。b。c。c。,b。a。b。b。b。b。c。b。c。c。c。a。c。,2020/5/26,42,第二种方法:关系矩阵乘法.继续考虑例3.2.9.中的关系R和S，先将R和S表示成从一个集合到另一个集合上的关系.domR=a,a,c,ranR=b,b,cdomS=b,b,c,c,ranS=a,b,b,cranRdomS=b,b,c,c将R看作从domR到ranRdomS的关系将S看作从ranRdomS到ranS的关系因此R。S就是从domR到ranS的关系.分别写出R和S的关系矩阵MR和MS,然后计算MR和MS的乘积需要注意的是在计算中元素进行相加时,采用逻辑加(即).所得结果即为关系R。S的关系矩阵,例3.2.9.设R=a,b,a,b,a,b,c,cS=b,a,b,b,c,b,c,c,2020/5/26,43,例3.2.9.设R=a,b,a,b,a,b,c,cS=b,a,b,b,c,b,c,c,R。S=a,b,a,a,a,b,c,b,关系的合成运算,2020/5/26,44,定理3.2.1.设R是任意的关系,则(R-1)-1=R.domR-1=ranR,ranR-1=domR.证明:任取x,y,由逆的定义有:x,y(R-1)-1y,xR-1x,yR,所以有(R-1)-1=R.,关系的合成运算,任取x,xdomR-1y(x,yR-1)y(y,xR)xranR.所以有domR-1=ranR另一式同理可证.,关系的逆是相互的;求了逆运算以后,其定义域与值域互换,2020/5/26,45,关系的运算,定理3.2.2.设R,S,H是任意的关系,则关于合成运算成立:(RS)H=R(SH).(RS)-1=S-1R-1.证明:任取x,y,x,y(RS)Ht(x,tRSt,yH)t(s(x,sRs,tS)t,yH)ts(x,sRs,tSt,y)s(x,sRt(s,tSt,y)s(x,sRs,ySH)x,yR(SH)所以(RS)H=R(SH).,任取x,y,x,y(RS)-1y,xRSt(y,tRt,xS)t(x,tS-1t,yR-1)x,yS-1R-1.所以(RS)-1=S-1R-1.,合成运算满足结合律两个关系合成的逆等于它们逆的反次序合成,2020/5/26,46,关系的运算,定理3.2.3.设R是A上的二元关系,IA为恒等关系,则:RIA=IAR=R.证明:任取x,y,x,yRIAt(x,tRt,yIA)t(x,tRt,yIAt=y)x,yR.从而有RIA=R.同理可证另一式.,对于任何A上的关系R,恒等关系对于合成运算是没有贡献的.恒等关系在关系合成中的作用,有似于实数普通乘法中的1.,2020/5/26,47,关系的运算,2.关系的幂运算关系的合成适合结合律可以定义关系的幂运算定义3.2.10.设R为A上的关系,n为自然数,则R的n次幂定义为:R0=x,x|xA=IA.Rn+1=RnR.求解R的n次幂：与R的表示法有关如果关系用集合表达式给出,可以采用关系的图示的方法.为求R的n次幂,将R的图示复制n次,第i个图示从i层的A中的结点到达第i+1层的A中的结点.如果从第1层A中的结点x,经过n步长的有向路径,可以到达最后一层(第n+1层),那么x,yRn.,2020/5/26,48,关系的运算,求解R的n次幂：与R的表示法有关如果R是用关系矩阵MR表示的,只需计算MR的n次方,就得到了Rn的关系矩阵.利用关系图求关系幂的方法比较方便.设R的关系图是GR,先在Rn的关系图中画出与R相同的n个点然后顺序考察原来关系图GR的每个结点x.如果结点x到y有一条长为n的有向通路,那么就在Rn的关系图中加上一条从x到y的有向边.在x=y时,得到的是由x引向x的有向环边.当所有的结点都检查完毕,就得到Rn的关系图.,2020/5/26,49,解:矩阵方法:,例3.2.10.设Aa,b,c,dR=a,b,b,a,b,c,c,d分别用矩阵方法和关系图方法求R的各次幂.,用关系矩阵的方法得到R2=R4=R6=;R3=R5=R7=.,关系图方法:以下给出了R0与R的关系图,以及对R的2次幂,3次幂,的构造结果.,2020/5/26,50,关系的运算,定理3.2.4.设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证明:R为A上的关系,|A|=n,A上的不同关系只有2nn个,列出R的各次幂:R1,R2,Rnn,这些幂中必有两个相等(鸽巢原理:n只以上鸽子飞回n个巢,必存在至少飞进2只鸽子的巢).即存在自然数s和t,使得Rs=Rt.定理3.2.4.说明有穷集上的关系R只有有限个不同的幂,2020/5/26,51,关系的运算,定理3.2.5.设R是A上的关系,m,nN,则关系R关于合成运算成立幂律:RmRn=Rm+n.(Rm)n=Rmn.证明:设定m,对n做归纳.对于任意给定的mN,施归纳于n.若n=0,则有RmR0=RmIA=Rm=Rm+0.假设RmRn=Rm+n,则有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1.所以式成立.对于任意给定的mN,施归纳于n.若n=0,则有(Rm)0=IA=R0=Rm0.假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)nRm=RmnRm=Rmn+m=Rm(n+1).所以式成立,本题的证明方法,也是数学归纳法。与一般的数学归纳法相比命题中有两个自然数。当命题存在多个自然数时,一般只选择其中一个自然数进行归纳,对其他的自然数只要任意给定即可,2020/5/26,52,定理3.2.6.设R是A上的关系,若存在自然数s,t(st)使得Rs=Rt,则:对任何的自然数k,有Rs+k=Rt+k;对任何自然数k,i,有Rs+kp+i=Rs+i,其中p=t-s;令S=R0,R1,Rt-1,则对于任意的自然数q有RqS.证明:Rs+k=RsRk=RtRk=Rt+k.对k做归纳.若k=0,则有Rs+0p+i=Rs+i.假设Rs+kp+i=Rs+i,其中p=t-s,则Rs+(k+1)p+i=Rs+kp+i+P=Rs+kp+iRP=Rs+iRP=Rs+P+i=Rs+t-s+i=Rt+i=Rs+i.由归纳法命题得证,任取qN,若qt,显然有RqS.若qt,则存在自然数k和i,使得q=s+kp+i,其中0ip-1.于是Rq=Rs+kp+i=Rs+i而s+is+p-1=s+(t-s)-1=t-1即Rs+i=Rt-1.即RqS.,2020/5/26,53,关系的运算,定理3.2.6.给出了R的不同幂的一个上界.如果Rs=Rt,那么R的不同的幂至多有t个.如果s和t是使得Rs=Rt成立的最小的自然数,那么R恰好有t个不同的幂.这里的t-s可以看作是幂变化的周期.利用幂的周期性,在某些情况下可以将R的比较高的幂化简成比较低的幂.如例3.2.10.由于R2=R4,且2和4使之成立的最小的自然数,所以R的不同的幂有4个,即R0,R1,R2,R3.利用这个性质,可得R100=R98=R96=R4=R2.,2020/5/26,54,3.2.3关系性质,1.关系性质的定义和判别定义3.2.11.设R是集合A上的关系.如果x(xAx,xR),则称R在A上自反.如果x(xAx,xR),则称R在A上反自反.恒等关系IA,全域关系EA以及小于等于关系LA都是给定集合A上的自反关系空关系,小于关系是A上的反自反关系.非空集合A上的关系R由是否具有自反性和反自反性划为3类:R自反;R反自反;R既不自反也不反自反.,2020/5/26,55,关系的性质,例3.2.11.设A=a,b,cR1=a,a,b,b,b,c,c,cR2=a,bR3=a,a,b,c.对于任意集合A,最大的自反关系是EA,最小的自反关系是IA最大的反自反关系是EA-IA,最小的反自反关系是空关系.R是A上自反关系IARR是A上反自反关系RIA=.从关系矩阵看自反关系的主对角元素都是1反自反关系的主对角元素都是0既不自反也不反自反的关系主对角元素有1也有0,自反关系,反自反关系,既不自反也不反自反,对应于关系图自反关系是每个结点都有环反自反关系是每个结点都无环既不自反也不反自反是有的结点有环,有的结点却无环,2020/5/26,56,续,定义3.2.12.设R是集合A上的关系.如果xy(x,yAx,yRy,xR),则称R在A上对称.如果xy(x,yAx,yRy,xRx=y),则称R在A上反对称.空关系和恒等关系IA,全域关系EA都是A上对称关系空关系和恒等关系IA也是A上反对称关系.小于关系,整除关系,包含关系是相应集合上的反对称关系,反对称性质的理解：任意x,yA，仅当x=y时，才有x,yR并且y,xR.等价定义:若xy(x,yAx,yRxyy,xR),则称R在A上反对称.,2020/5/26,57,续,非空集合A上的关系R根据是否具有对称性和反对称性可以划分为4类:R对称但不是反对称的R反对称但不是对称的R既是对称的也是反对称的R既不是对称的也不是反对称的.例3.2.12.设A=a,b,cR1=a,a,b,b,b,c,c,bR2=a,b,c,aR3=a,a,b,bR4=a,b,b,a,a,c,R1对称但不是反对称,R2反对称但不对称,R3既对称也反对称,R4既不是对称的也不是反对称的,对于任意集合A,最大的对称关系是EA最小的对称关系是空关系最小的反对称关系也是空关系.R是A上对称关系R=R-1R是A上反对称关系RR-1IA.,2020/5/26,58,续,从关系矩阵看对称关系R的关系矩阵MR是对称的,即MR与它的转置矩阵相等反对称关系R的关系矩阵MR中处于对称位置的所有元素(i,j)与(j,i)不能同为1既对称也反对称关系R的关系矩阵,只在主对角元素有1.从关系图看每两个不同的结点之间如有有向边,有向边则是成对反向的每两个不同的结点之间如有有向边,有向边则是单向的既不对称也不反对称关系的关系图中,两个不同的结点之间既有单向边,也有成对反向的边如果关系图中所有不同的结点对之间都无有向边,则这个对应的二元关系就既是对称的,也是反对称的,2020/5/26,59,续,定义3.2.13.设R是集合A上的关系若xyz(x,y,zAx,yRy,zRx,zR)则称R是A上的传递关系.空关系、恒等关系IA、全域关系EA、小于等于关系、整除关系包含关系R等都是相应集合A上的传递关系例3.2.12.设A=a,b,cR1=a,b,b,c,a,cR2=a,b,b,aR3=a,a,b,bR4=a,bR是A上的传递关系RRR.,传递,不具备传递性,传递,传递,2020/5/26,60,有穷集合A上关系R传递性的关系矩阵MR判别法:给出MR计算M=MRMR针对M中元素为1的每个位置,检查MR中相应位置是否也为1.如果在MR中相应的位置都是1,那么R是传递的有穷集合A上关系R传递性的关系图GR判别法:给出集合A=x1,x2,xn上的关系图GR依次考察GR的每一个结点xi,i=1,2,n.若xi经过两步长的有向路径到达xj,则在GR中应该有一条从xi到xj的有向边(若xi=xj则为环边)如果找到某个结点不满足要求,那么R不是传递的,如果不存在这样的结点则R是传递的.,2020/5/26,61,例3.2.13.设A=a,b,c上的关系的关系图如下所示:,（1）反对称，传递但不是对称关系而且也是既不自反也不反自反的关系,（2）反自反但不是对称，不是反对称不是自反也不是传递的关系,（3）自反，传递，反对称但不是对称也不是反自反的关系,（4）不自反，不反自反但是传递而且既是对称也是反对称的关系,（5）自反，反对称但不是传递，不是对称也不是反自反的关系,2020/5/26,62,关系的性质,设R1和R2都是集合A上的关系,则具有下述联系:若R1和R2都自反,则,R1R2,R1R2,R1R2也自反.若R1,R2都反自反,则,R1R2,R1R2,R1-R2也反自反.若R1,R2都对称,则,R1R2,R1R2,R1-R2也对称.若R1,R2都反对称,则,R1R2,R1-R2也反对称.若R1,R2都是传递的,则,R1R2也是传递的.,2020/5/26,63,关系的性质,2.关系的闭包运算求满足指定性质的以给定关系为子集的最小关系的运算称关系的闭包运算闭包运算从已知关系出发,通过增加最少的有序对来生成满足某种指定的关系性质的运算定义3.2.14.设R是集合A上的关系,R的自反(对称;传递)闭包是A上的关系R,使得R满足以下条件:(1)R是自反的(对称的;传递的)(2)RR(3)对A上任何包含R的自反(对称;传递)关系R有RR.,关系R的自反闭包,对称闭包和传递闭包分别记作r(R),s(R)和t(R)如果关系R是自反(对称;传递)的,那么R的自反(对称;传递)闭包r(R)(s(R);t(R)=R.,2020/5/26,64,构造一个关系的闭包有三种方法:(1)集合表达式法定理3.2.7.设R是A上的关系,则有r(R)=RR0;s(R)=RR-1;t(R)=RR2R3.证明:要证RR0满足自反闭包定义:R0=IARR0,即RR0在A上是自反的;RRR0;再证RR0是包含R的最小的自反关系.若R是包含R的自反关系,那么IAR,RR因此RR0=IARR.,证RR-1满足对称闭包定义:由(RR-1)-1=R-1R=RR-1知RR-1是对称的RRR-1再证RR-1是包含R的最小的对称关系.若R是包含R的对称关系,那么(R)-1=R,但RR所以R-1R,因此RR-1R,2020/5/26,65,首先证明RR2R3具有传递性.任取x,y和y,z.x,yRR2R3y,zRR2R3t(x,yRt)s(y,zRs)x,zRtRsx,zRt+sx,zRR2R3.t(R)是具有传递性的包含R的最小关系,RR2R3是具有传递性的包含R的关系t(R)RR2R3;再证明RR2R3t(R)只需证明对任意正整数n,都有Rnt(R).对n做归纳:n=1时显然.假设对n=k时Rkt(R),再证n=k+1时有Rk+1t(R).令x,y任意.则x,yRk+1x,yRkRt(x,tRK)t,yR)t(x,tt(R)t,yt(R)x,yt(R)(t(R)具有传递性).,t(R)=RR2R3.,2020/5/26,66,关系的性质,对于有穷集合A上的关系R有t(R)=RR2R3Rs.式中s|A|.例3.2.14.设A=a,b,c,R=a,a,a,c,b,cr(R)=RR0=IAR=a,a,a,c,b,cIA=a,a,a,c,b,c,b,b,c,cs(R)=RR-1=Ra,a,c,a,c,b=a,a,a,c,b,c,c,a,c,bt(R)=RR2R3=Ra,a,a,c(R2=R3,s3)=a,a,a,c,b,c(R2R).,2020/5/26,67,(2)关系矩阵法(记对应的矩阵为M,Mr,Ms和Mt):Mr=M+E;Ms=M+M;Mt=M+M2+M3+(+为逻辑加)如例3.2.14.,例3.2.14.设A=a,b,c,R=a,a,a,c,b,c,2020/5/26,68,关系的性质,(3)关系图法(设关系R及r(R),s(R),t(R)的关系图分别为G,Gr,Gs,Gt)构造Gr,只需在G中缺少环的每个结点加一个环构造Gs,只需在G中所有存在单向边的不同结点对之间再加一条反向边构造Gt,只需在G中检查每个结点的可达性:结点x若经过至多n(G中结点数|A|)步长的有向路径到达结点y,且G中缺少有向边x,y,那么就给Gt加上一条x到y的有向边.当所有的结点都检查完以后,就得到图Gt.在t(R)的关系图Gt中,x到y有一条边G中x到y存在长至少为1的路径.,2020/5/26,69,(3)关系图法,2020/5/26,70,关系的性质,3.沃舍尔(Warshall)算法关系R的传递闭包,实际上是图的连通关系R*=x,y|在G中存在一条从x到y的有向路径.图的连通性问题通信网络运输路线规划等方面因此传递闭包的计算需要一个高效率的算法.,2020/5/26,71,沃舍尔算法,Warshall在1962年提出了一个有效的算法来求解有限集合上二元关系R的传递闭包设集合A含有n个元素,R是A上的一个二元关系，MR是其关系矩阵,则Warshall算法简述为:“置行查列遍寻真(1),见真行上析当今(i),行推列移下右再,行穷列尽闭包成(Mt)”。,2020/5/26,72,沃舍尔算法,输入:集合A(|A|=n)上关系R的关系矩阵MR=(mij)nn.输出:R的传递闭包t(R)的关系矩阵Mt.1.置MMR;2.取i1;3.对j=1,2,n,如有mji=1,则新取mjk=mjkmik,k=1,2,n;4.ii+1;5.如果in,则转3.,否则输出.例3.2.15.设A=a,b,c,R=a,a,a,c,b,c,c,b则依据沃舍尔算法:,2020/5/26,73,课堂讲习题,由R的关系矩阵判断关系R是否具有传递性.方法:设R是有穷集合A上的关系,则有:给出MR计算M=MRMRM中元素为1的每个位置,检查MR中相应位置是否也为1.如果在MR中相应的位置都是1,则R是传递的示例：设A=a,b,c,R=a,b,a,c,b,c则针对M中元素1的每个位置,经检查MR中相应位置(3,1=1)也是1,所以R是A上的传递关系.,2020/5/26,74,课堂讲习题,证明:R,S都是反对称的RS也是反对称的.R,S都是传递的,但推不出RS是传递的.任取x,y,y,x.x,y,y,xRSx,y,y,xRx=y.即RS也是反对称的.反例:A=1,2,3R=1,1,2,3S=1,2,3,3RS=1,2,2,3不具有传递性质.,证明:,2020/5/26,75,课堂讲习题,计算具有多种性质闭包的运算次序问题:A上关系R,计算自反闭包是r(R),接着算对称闭包记作sr(R),再算传递闭包为tsr(R).,若,，且ij，则,2020/5/26,76,课堂讲习题,计算具有多种性质闭包运算的例与一些重要的事实.设A=a,b,c,R=a,b,a,cr(R)=a,b,a,c,a,a,b,b,c,csr(R)=a,b,a,c,a,a,b,b,c,c,b,a,c,a(一般:sr(R)=rs(R);tr(R)=rt(R)tr(R)=a,b,a,c,a,a,b,b,c,ctsr(R)=a,b,a,c,a,a,b,b,c,c,b,a,c,a,b,c,c,bstr(R)=a,b,a,c,a,a,b,b,c,c,b,a,c,a(一般:st(R)ts(R),只有st(R)ts(R),注意:对称闭包与传递闭包的次序不可颠倒.因为先计算传递闭包,再计算对称闭包在计算对称闭包时可能将传递性丢失.,2020/5/26,77,关系性质与运算的联系表(拥有某性质的二元关系在指定进行集合的一种运算后是否还具有该性质?):,2020/5/26,78,3.2.4等价关系与划分,等价关系是一类重要的二元关系划分是一种对对象集合的分类两者能相互惟一确定.考虑:班上同学的同性别关系.这是一种满足自反,对称和传递性的等价关系把班上同学按男,女分为两个组.这是对班上全体同学的一种划分在同性别关系下形成两个性别类与按男,女分组的划分方法相互惟一确定,2020/5/26,79,等价关系与划分,1.等价关系定义3.2.15.设R是集合A上的关系,如果R是自反、对称和传递的,则称R为A上的等价关系.对于任何元素x,yA,如果xRy,则称x与y等价,记作xy.集合A上的恒等关系IA全域关系EA整数集合Z上的小于等于关系在整数集合Z或者Z的子集上有一种重要的等价关系,即整数模m同余关系:.对于任意整数x和y,xy(modm)的含义是x与y除以m的余数相等(即x与y的差可被m整除),2020/5/26,80,等价关系与划分,例3.2.16.设A=1,2,3,4,5,6,7试构造A上的模3等价关系？R=1,1,1,4,4,1,1,7,7,1,2,2,2,5,5,2,3,3,3,6,6,3,4,4,4,7,7,4,5,5,6,6,7,7.,2020/5/26,81,等价关系与划分,等价类和商集等价关系将集合A的元素划分成若干个子集,彼此等价的元素被分在同一个子集里.上例中的1,4,7除以3的余数都是1,它们在同一个子集里.2和5除以3的余数都是2,它们也在同一个子集里.另外一个子集就是由3与6构成的子集,它们除以3的余数为0.这些子集称作这个等价关系产生的等价类.定义3.2.16.设R是集合A上等价关系,x是A的元素,A中与x等价的全体元素构成的子集称为x的等价类,记作xR.x的等价类xR,简记为x,即x=y|yA,xRy例3.2.16.中的等价类是:1=4=7=1,4,7;2=5=2,5;3=6=3,6.,2020/5/26,82,定理3.2.7.设R是A上的等价关系,则xA,x是A的非空子集.x,yA,如果xRy,则x=