离散数学讲义第3章

1,天津财经大学信息科学与技术系王宁ninglw,DiscreteMathematics,离散数学讲义（电子版）,2,第二篇集合论,3,集合论的发展历史,集合论是现代数学的基础,它已深入到各种科学和技术领域中，被广泛应用到数学和计算机科学的各分支中去。在开关理论、形式语言、数据库等领域得到了卓有成效的应用。,4,集合论的发展历史（续）,集合论的创始人康托尔（GeorgCantor18451918）德国著名数学家。,5,集合论的发展历史（续）,在1874年，发表了题为“关于所有实代数数所成集合的一个性质”的论文，开创了现代集合论的研究，为现代数学奠定了基础。,1903年，Russell悖论集合理论中出现了悖论。,为了解决集合论的悖论,上世纪初开始了集合论公理学方向的研究,它是数理逻辑的中心问题之一。,悖论举例:(1)理发师只给不给自己理发的人理发。(2)我正在说谎。,6,第三章集合与关系,7,第三章集合与关系,本章包括以下内容：,3-1集合的概念和表示3-2集合的运算3-4序偶与笛卡尔积3-5关系及其表示3-6关系的性质,8,3-7复合关系和逆关系3-8关系的闭包运算3-9集合的划分和覆盖3-10等价关系与等价类3-11相容关系3-12序关系,第三章集合与关系,本章包括以下内容：,9,集合是一个不能精确定义的基本概念。,3-1集合的概念和表示法,有限（无限）集：集合中元素个数为有限（无限）个。,aA表示a是集合A的元素，读作“a属于集合A”。aA表示a不是A中的元素，读作“a不属于集合A”。,集合：由一些确定对象所组成的整体。（Asacollectionofsomeobjects.）把具有同一性质的一些东西汇集成一个整体，就形成一个集合。,集合的元素：汇集成集合的各个对象。,10,集合的表示方法：,3-1集合的概念和表示法（续）,（1）枚举法A=a,b,c,nB=桌子，灯泡，自然数，老虎,（2）描述法（谓词公式法）A=x|xP(x)（若p(b)为真，则bA，否则，bA）,例如：S1=x|x是正奇数S2=x|x是中国的省S3=y|y=a或y=b,11,示例：（1）A=a,b,c（2）B=2,4,6,2n（3）C=x|x0（4）D=(x,y)|x2+y2=1（5）E=x|x是天津财经大学2006级学生,3-1集合的概念和表示法（续）,12,两个集合相等的定义（外延性原理）：,3-1集合的概念和表示法（续）,注意：集合元素还可以允许是集合。,例如：S=a，1，2，p，q。此时，qq，但qS。,当且仅当两个集合A和B有相同的成员时，称这两个集合是相等的，记做A=B。否则称它们是不相等的，记做AB。,又如：1，2，4=1，2，2，4=1，4，21，2，41，2，4,13,子集的两个性质：,定理：集合A和集合B相等的充分必要条件是这两个集合互为子集，也即AB且BA。,3-1集合的概念和表示法（续）,定义：设A和B是任意两个集合，如果A的每一个元素也是B的元素，则称A是B的子集，或称A包含在B内，或B包含A。记做AB，或BA。,注意元素属于集合同集合之间包含关系的区别。,集合相等的判定条件：,（1）自反性：AA（2）传递性：(AB)(BC)(AC),例：设A=1，1，则1A，1A，1A,14,真子集：设A和B是任意两个集合，如果A的每一个元素都是B的元素，而B中至少有一个元素不属于A，则称A是B的真子集，记作AB。,3-1集合的概念和表示法（续）,空集：不包含任何元素的集合，记作。=x|P(x)P(x)，P(x)为任意谓词。,定理：空集是任何集合的子集，即A,AB(x)(xAxB)(x)(xBxA)(AB)(AB),例如：整数集是有理数集的真子集。,注意：，但,15,平凡子集：A和是A的平凡子集。,3-1集合的概念和表示法（续）,全集：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作E。,(x)(xE)为永真。故E=x|P(x)P(x)，P(x)为任意谓词。,全集的概念相当于数论中的论域。,幂集：给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集，记作P(A)。,例如：A=a，b，c，P(A)=,a,b,c,a,b,a,c,b,c,a,b,c,注：幂集是一个集合的集合，“集合A的幂集的元素”与“集合A的子集”说法一致。,16,定理：如果有限集A的元素个数为n，则其幂集的元素个数为2n。,3-1集合的概念和表示法（续）,证明：A的所有由k个元素组成的子集数为：,又因为A，因此P(A)的总数N为：,而,令x=y=1，有故P(A)的元素个数为2n。,17,P(S)=Si|iJ，J=i|i是二进制数且00.0i11.1nn,3-1集合的概念和表示法（续）,引进一种编码用来唯一表示有限集幂集的元素：,以S=a，b，c为例：,P(S)=Si|iJ，J=i|i是二进制数且000i111,例如：S3=S011=b，c，S6=S110=a，b等。,18,（1）集合的交,集合不相交AB=,3-2集合的运算,若集合A,B没有共同元素，则可写为AB=，称作A与B不相交。,19,3-2集合的运算（续）,例1：设AB，求证ACBC,集合交运算的性质：（可以对照合取运算的性质来记）,另外：ABA，ABB,证明：若xA，则xB。对任意xAC，xA且xC，即xB且xC，即xBC，得证。,a）AA=A,b）A=,c）AE=A,d）AB=BA,e）(AB)C=A(BC),20,AB,A,B,（2）集合的并,3-2集合的运算（续）,21,3-2集合的运算（续）,例2：设AB，CD，求证ACBD,集合并运算的性质：,另外：AAB，BAB,证明：对任意的xAC，即xA或xC，根据已知条件，若xA，由AB，则xB，故xBC；若xC，由CD，则xD，故xBD。因此ACBD。,同理可证：ABACBC。,a）AA=A,b）AE=E,c）A=A,d）AB=BA,e）(AB)C=A(BC),22,￥,23,n个集合的交运算,n个集合的并运算,3-2集合的运算（续）,24,3-2集合的运算（续）,定理：设A，B，C为三个集合，则下列分配律成立：a）A(BC)=(AB)(AC)b）A(BC)=(AB)(AC),证明：设S=A(BC)，T=(AB)(AC)，若xS，则xA且xBC，即xA，xB或xA，xC，即xAB或xAC，即xT。因此ST。,反之，若xT，则xAB或xAC，即xA，xB或xA，xC，即xA且xBC，因此xS，得到TS。因此S=T。,b）的证明与a）类似。,25,3-2集合的运算（续）,定理：设A，B为两个集合，则下列吸收律成立：a）A(AB)=Ab）A(AB)=A,证明：a）A(AB)=(AE)(AB)=A(EB)=Ab）A(AB)=(AA)(AB)=A(AB)=A,定理：设AB，当且仅当AB=B或AB=A,证明：若AB，则对任意xA有xB，对xAB，则xA或xB，即xB，故ABB，又BAB，得到AB=B。反之，若AB=B，因为AAB，故而AB。同理可证AB，当且仅当AB=A。,26,相对补集（差集）,（3）集合的补,3-2集合的运算（续）,27,绝对补集,A,集合的补,3-2集合的运算（续）,28,3-2集合的运算（续）,例3：设A=2，5，6，B=1，2，4，7，9，则A-B=5，6,集合绝对补运算的性质：,例4：设A为素数集合，B为奇数集合，则A-B=2,a）(A)=A,b）E=,c）=E,d）AA=E,e）AA=,29,3-2集合的运算（续）,定理：设A，B为任意两个集合，则下列关系成立：a）(AB)=ABb）(AB)=AB,证明：,a）(AB)=x|x(AB),=x|x(AB),=x|(xA)(xB),=x|(xA)(xB),=AB,b）类似可证。,30,3-2集合的运算（续）,定理：设A，B为任意两个集合，则下列关系成立：a）A-B=ABb）A-B=A-(AB),证明：,a）证略。,b）设xA-B，即xA且xB。因为xB，有x(AB)，故xA-(AB)，即A-BA-(AB),又设xA-(AB)，则xA且x(AB)（即x(AB)）即xA且xA或者xA且xB。而xA且xA不可能，故而xA且xB，即xA-B得到A-(AB)A-B,因此A-B=A-(AB),31,3-2集合的运算（续）,定理：设A，B，C为任意三个集合，则：A(B-C)=(AB)-(AC),证明：,A(B-C)=A(BC)=ABC,(AB)-(AC)=(AB)(AC),=(AB)(AC),=(ABA)(ABC),=(ABC),=ABC,因此A(B-C)=(AB)-(AC)。,32,3-2集合的运算（续）,定理：设A，B为两个集合，若AB，a）BAb）(B-A)A=B,证明：,a）若xA，则xB，因此若xB则xA，故xB必有xA，即BA。,b）(B-A)A=(BA)A=(BA)(AA)=(BA)E=(BA)。,因为若AB则有BA=B，因此，(B-A)A=B。,33,（4）集合的对称差,3-2集合的运算（续）,34,3-2集合的运算（续）,集合对称差运算的性质：,另外：AB=(AB)(AB)(AB),a）AB=BA,b）A=A,c）AA=,d）AB=(AB)(AB),e）(AB)C=A(BC),=(AB)(AB),35,3-4序偶与笛卡尔积,两个具有固定次序的客体组成一个序偶（有序对），它常常表达两个客体之间的关系。记作x,y。,序偶,定义：两个序偶相等x,y=u,v当且仅当x=u和y=v同时成立。,例如：上，下，中国，亚洲a，b等。,注：序偶可看作具有两个元素的集合，但它的元素具有确定次序。,36,3-4序偶与笛卡尔积（续）,推广：三元组，四元组，n元组,三元组：x,y,z，并约定记作x,y,zx,y,z=u,v,wiffx=u，y=v，z=w,注意：x,y,z不是三元组。,四元组：x,y,z,w，记作x,y,z,wx,y,z,w=p,q,r,s(x=p)(y=q)(z=r)(w=s),n元组：x1,x2,xn-1,xn，且x1,x2,xn-1,xn=x1,x2,xn-1,xn(x1=y1)(x2=y2)(xn-1=yn-1)(xn=yn),37,3-4序偶与笛卡尔积（续）,定义：令A和B是任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样的序偶集合，称为集合A和B的笛卡尔乘积或直积，记作AB。,约定：若A=或B=，则AB=,注意：ABBA,(AB)CA(BC),38,3-4序偶与笛卡尔积（续）,例1：A=a,b，B=1，2，3，则,AB=a,1,a,2,a,3,b,1,b,2,b,3,BA=1,a,2,a,3,a,1,b,2,b,3,b,AA=a,a,a,b,b,a,b,b,BB=1,1,1,2,1,3,2,1,2,2,2,33,1,3,2,3,3,可见，ABBA=。,又(AB)C=a,b,c|(aA),(bB),(cC),而A(BC)=a,b,c|(aA),b，cBC,由于a,b,c不是三元组，因此,(AB)CA(BC),39,3-4序偶与笛卡尔积（续）,定理：设A，B，C为任意三个集合，则有：A(BC)=(AB)(AC)A(BC)=(AB)(AC)(AB)C=(AC)(BC)(AB)C=(AC)(BC),证明:(c),x,y(AB)C(xAB)(yC),(xAxB)(yC),(xAyC)(xByC),(x,yAC)(x,yBC),(x,yACBC),40,定理：若C，则AB(AC)(BC)(CA)(CB),3-4序偶与笛卡尔积（续）,证明：若yC，设AB，有,x,yAC(xA)(yC),(xB)(yC)x,yBC，,因此，(AC)(BC)。,反之，若C，(AC)(BC)，取yC，则有xA(xA)(yC)x,yAC,x,yBC(xB)(yC)xB。,因此，AB。,同理可证第二部分。,41,3-4序偶与笛卡尔积（续）,定理：设A,B,C,D为四个非空集合，则(AB)(CD)的充要条件为AC，BD,证明：若(AB)(CD)，对任意的xA，yB，有(xA)(yB)x,yABx,yCD,(xC)(yD)。,即AC，BD。,反之，若AC，BD，设任意的xA，yB，有,x,yAB(xA)(yB)(xC)(yD)x,yCD,因此(AB)(CD)。,42,3-5关系及其表示,定义1：任意序偶的集合确定了一个二元关系R，R中的任意a,b序偶可记作a,bR或aRb,不在R中的任意序偶记作a,bR。,例如：实数中关系可记作=x,y|x,y是实数且xy,定义2：令X和Y是任意两个集合，直积XY的子集R称作X到Y的关系。,定义：令R为二元关系，由x,yR的所有x组成的集合domR称为R的前域。domR=x|(y)(x,yR),使x,yR的所有y组成的集合ranR称为R的值域。ranR=y|(x)(x,yR),R的前域和值域一起称为R的域，记作FLDRFLDR=domRranR,43,3-5关系及其表示（续）,观察下图：,可见：domRX，ranRY，FLDR=domRranRXY,特殊关系：XY的两个平凡子集，空关系：R=；全域关系：R=XY,注：当X=Y时，关系R称为在X上的二元关系。,44,例1：设A=1，2，3，5，B=1，2，4，H=1，2，1，4，2，4，3，4,3-5关系及其表示（续）,例2：设X=1，2，3，4，求X上的关系，以及dom，ran,则domH=1，2，3，ranH=2，4，FLDH=1，2，3，4,解：=2,1,3,1,4,1,3,2,4,2,4,3dom=2,3,4，ran=1,2,3,45,3-5关系及其表示（续）,例3：H=f,m,s,d表示一个家庭中的父母子女集合，则：,全域关系：同一家庭成员：H1=f,m,f,s,f,d,m,f,m,s,m,d,s,f,s,m,s,d,d,f,d,m,d,s,f,f,m,m,d,d,s,s,空关系：互不相识。,设长幼关系为：H3，H3=f,s,f,d,m,s,m,ddomH3=f,m，ranH3=s，d,46,3-5关系及其表示（续）,定义：设Ix为X上的二元关系，满足Ix=x,x|xX，则称Ix是X上的恒等关系。,例4：设X=1,2,3,4，关系H=x,y|(x-y)/2是整数，S=x,y|(x-y)/3是正整数，求HS，HS，H，S-H。,例如：A=1，2，3，IA=1,1,2,2,3,3,解：H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2，S=4,1,HS=,HS=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2，4,1,H=1,2,2,1,2,3,3,2,3,4,4,3,1,4,4,1,S-H=4,1,47,3-5关系及其表示（续）,定理：设Z和S是从集合X到集合Y的两个关系，则Z和S的并，交，补，差仍是X到Y的关系。,注：若X=x1,x2,xm和Y=y1,y2,yn为有限集，则X到Y的关系R也可以用矩阵或图形表示，即为关系矩阵和关系图。,关系矩阵：MR=rijmn，其中i=1,2,m；j=1,2,n,关系图：在平面上作出结点x1,x2,xm和y1,y2,yn。如果xiRyj到，则自结点xi至yj作一条有向弧，箭头指向yj，否则，xi与yj间没有线连接。即得到关系图。,48,3-5关系及其表示（续）,例5：设X=x1,x2,x3,x4和Y=y1,y2,y3,R=x1,y1,x1,y3,x2,y2,x2,y3,x3,y1,x4,y1,x4,y2,则R的关系矩阵为关系图为：,49,3-5关系及其表示（续）,例6：设A=1,2,3,4，写出集合A上的大于关系的关系矩阵。,解：=2,1,3,1,3,2,4,1,4,2,4,3关系矩阵为,关系矩阵为,50,3-5关系及其表示（续）,例7：设A=1,2,3,4,5，在集合A上的二元关系R为：R=1,5,1,4,2,3,3,1,3,4,4,4则R的关系图为：,注：(1)关系图中对结点的位置和线段或弧线的长短无要求。(2)今后通常讨论同一个集合上的关系。,51,3-6关系的性质,自反关系：如果对所有xX，都有x,xR。R在X上自反(x)(xXxRx),例如：实数集合上的关系及平面上三角形的全等关系。,对称关系：如果对所有x，yX，每当x,yR时，都有y,xR。R在X上对称(x)(y)(xXyXxRyyRx),例如：平面上三角形的相似关系等。,传递关系：对所有x，y，zX，若x,yR，y,zR，则有x,zR。R在X上传递(x)(y)(z)(xXyXzXxRyyRzxRz),例如：实数集合上的关系，0，使得xiRpxj成立。即存在序列e1,e2,ep-1，有xiRe1,e1Re2,ep-1Rxj。设满足上述条件的最小的p大于n，则在上述序列中必有0tn不成立。,78,3-8关系的闭包运算（续）,例2：设A=a,b,c,d，A上的二元关系R=a,b,b,a,b,c,c,d求t(R)。解：,因此，n个元素的有限集上关系R的传递闭包可以写作,79,3-8关系的闭包运算（续）,即t(R)=a,a,a,b,a,c,a,d,b,a,b,b,b,c,b,d,c,d,因此,80,3-8关系的闭包运算（续）,传递闭包的Warshall算法,(1)A:=M,(2)i:=1,(3)对所有j，如果Aj,i=1，则对k=1,2,n，Aj,k:=Aj,k+Ai,k,(4)i:=i+1,(5)若in，则转到步骤(3)，否则，停止。,81,3-8关系的闭包运算（续）,例3：已知关系矩阵M，求t(R)。,82,3-8关系的闭包运算（续）,解：,83,3-8关系的闭包运算（续）,i=1时，第一列只有A1,1=1，将第一行于第一行个对应元素进行逻辑加，仍记于第一行：,84,3-8关系的闭包运算（续）,i=2时，第二列中A1,2=1，A4,2=1，分别将第一行，第四行个元素和第二行对应元素逻辑相加，仍记于第一行和第四行：,85,3-8关系的闭包运算（续）,i=4时，第四列中A1,4=A2,4=A4,4=1，分别将第一、二、四行个元素和第四行对应元素逻辑相加，仍记于第一、二、四行：,i=3时，第三列中没有非零元，A的赋值不动。,86,3-8关系的闭包运算（续）,i=5时，第五列中A3,5=1，将第三行各元素和第五行对应元素逻辑相加，仍记于第三行。由于第五行的元素都等于零，因此A的赋值不变。,i=6，7时，第六、七列中没有非零元，A的赋值不动。,87,3-8关系的闭包运算（续）,例4：设字母表V=A,B,C,D,e,d,f，并且AAf,BDde,Ce,AB,BDe,DBfR为定义在V上的二元关系且xiRxj，即使从xi出发用一条规则推出一串字符，使其第一个字符恰为xj。说明每个字母连续应用上述规则可能推出的头字符。解：R的关系矩阵：,88,3-8关系的闭包运算（续）,则xiR+xj，表示从xi出发，经过多次连续推导而得到的字符串，其第一个字符恰为xj的关系。此关系即是上例中计算的。因此，R+=A,A,A,B,A,D,B,B,B,D,C,eD,BD,D,89,3-8关系的闭包运算（续）,定理：设R为集合X上的二元关系，则：a)rs(R)=sr(R)b)rt(R)=tr(R)c)ts(R)st(R),证明：令Ix表示X上的恒等关系。,a)sr(R)=s(IxR)=(IxR)(IxR)c=(IxR)(IxcRc)=IxRRc=Ixs(R)=rs(R),b)tr(R)=t(IxR)=i=1(IxR)i=i=1(Ix(j=1iRj)=Ix(i=1j=1iRj)=Ixi=1Ri=Ixt(R)=rt(R),90,3-9集合的划分和覆盖,定义：,等价定义：,1.若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，则这些分块的全体构成的集合叫做A的一个覆盖。,2.如果A中每个元素属于且仅属于一个分块，则这些分块的全体构成的集合叫做A的一个划分（分化）。,1.令A为给定的非空集合，S=S1,S2,Sm，其中SiA，Si(i=1,2,m)且j=1mSi=A，集合S称作集合A的覆盖。,2.如果除以上条件外，另有SiSj=(i=j)，则称S是A的划分（分化）。,91,3-9集合的划分和覆盖（续）,例：A=a,b,c，考虑下列集合：S=a,b,b,cQ=a,a,b,a,cD=a,b,cG=a,b,cE=a,b,cF=a,a,c则：S，Q是A的覆盖，D,G,E是A的划分。且G是A的最小划分，E是A的最大划分。F既不是划分也不是覆盖。,注：,显然，划分覆盖，反之不成立。,任意集合的最小划分就是由这个集合的全部元素组成的一个分块的集合。,任意集合的最大划分就是由每个元素构成一个单元素分块的集合。,给定一个集合A，其划分并不唯一，但已知一个集合却很容易构造出一种划分。,92,3-9集合的划分和覆盖,定义：若A1,A2,Ar与B1,B2,Bs是同一集合A的两种划分，则其中所有AiBj组成的集合称为原来两种划分的交叉划分。,定理：设A1,A2,Ar与B1,B2,Bs是同一集合X的两种划分，则其交叉划分也是原集合的一种划分。,证明：交叉划分为A1B1,A1B2,A1Bs,A2B1,A2B2,A2Bs,ArB1,ArB2,ArBs。从中任取两个元素AiBh,AjBk，考察(AiBh)(AjBk)，,1）若ij且h=k，因为AiAj=，因此(AiBh)(AjBk)=BhBk=,2）若ij且hk，因为AiAj=，BhBk=，因此(AiBh)(AjBk)=,93,3-9集合的划分和覆盖（续）,3）若i=j且hk，同1）类似。因为AiAj=，BhBk=，故(AiBh)(AjBk)=。另外，(A1B1)(A1B2)(A1Bs)(A2B1)(A2B2)(A2Bs)(ArB1)(ArB2)(ArBs)=(A1(B1B2Bs)(A2(B1B2Bs)(Ar(B1B2Bs)=(A1A2Ar)(B1B2Bs)=XX=X得证。,94,3-9集合的划分和覆盖（续）,定义：若A1,A2,Ar与B1,B2,Bs是同一集合X的两种划分，若对于每一个Ai都有Bk满足AiBk，则A1,A2,Ar称为是B1,B2,Bs的加细。,定理：任何两种划分的交叉划分，都是原来各划分的一种加细。,证明：设A1,A2,Ar与B1,B2,Bs的交叉划分为T，对T中的任意元素AiBj，必有AiBjAi，AiBjBj,95,3-10等价关系与等价类,定义：设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则R称为等价关系。,例如：平面上三角形集合中，三角形的相似关系是等价关系,例1：设集合T=1,2,3,4，R=1,1,1,4,4,1,4,4,2,2,2,3,3,2,3,3，则R是T上的等价关系。,1,3,2,4,解：R的关系矩阵与关系图如下，由关系图和关系矩阵可以看出R是自反和对称的，再逐个检查序偶，得到R是传递的。,96,例2：设I为整数集，R=x,y|xy(modk)，证明R是等价关系。,3-10等价关系与等价类（续）,证明：任意给定a,b,cI，,1）a-a=k0，即a,aR,2）若ab(modk)，即a-b=kt（t为整数），b-a=-kt，因此，ba(modk),3）若ab(modk)，bc(modk)，即a-b=kt，b-c=ks（s，t为整数），a-c=a-b+b-c=k(t+s)，因此，ac(modk),97,定义：设R为集合A上的等价关系，对任何aA，集合aR=x|xA,aRx称为元素a形成的R等价类。,3-10等价关系与等价类（续）,注：由定义知等价类是非空集合，因此任给集合A及其上的等价关系R，必可写出A上各元素的等价类。,例3：设I为整数集，R是同余模3的关系，即R=x,y|xy(mod3)，则由I的元素所产生的等价类为,0R=,-6,-3,0,3,6,1R=,-5,-2,1,4,7,2R=,-4,-1,2,5,8,并有0R=3R=-3R=1R=4R=-2R=2R=5R=-1R=,98,3-10等价关系与等价类（续）,定理：给定集合A上的等价关系R，对于a,bA，有aRb当且仅当aR=bR,证明：若aR=bR，因为aaR，故abR，故aRb。反之，若aRb，设caR，则aRccRacRbcbR，即aRbR，同理可证bRaR，得证aR=bR。,定义：设R为集合A上的等价关系，其等价类集合aR|aA称为A关于R的商集，记作A/R。,例如：例1中的商集T/R=1R，2R，例3中的商集I/R=0R，1R，2R。,99,3-10等价关系与等价类（续）,定理：集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。,证明：把与A的固定元a有等价关系的元素放在一起组成一个子集aR，则所有这样的子集组成商集A/R。,1）在A/R=aR|aA中，aAaR=A；,2）任给aA，由于R是自反的，故必有aRa，即aaR，因此a的每个元素确属于一个分块；,3）（利用反证法证明A的每个元素只能属于一个分块）若abR且acR，并有bRcR，则bRa，cRa，由对称性，有aRc，再由传递性有bRc，因此必有bR=cR，与假设矛盾，得证。因此A/R是A上的一个划分。,100,3-10等价关系与等价类（续）,定理：集合A上的一个划分确定了A的元素间的一个等价关系。,证明：设集合A的一个划分S=S1,S2,Sm定义关系R：aRb当且仅当a，b在同一分块中。下面证明关系R就是一个等价关系。,1）a与a必在同一分块中，即aRa，R是自反的；,2）若a与b在同一分块中，b与a也在同一分块中，即aRbbRa，R是对称的；,3）若a与b在同一分块中，b与c也在同一分块中，由SiSj=(ij)，即b属于且仅属于一个分块，因此a与c也在同一分块中，即(aRb)(bRc)(aRc)，R是传递的。,所以R是等价关系，且S=A/R。,101,3-10等价关系与等价类（续）,例4：设A=a,b,c,d,e，划分S=a,b,c,d,e，由划分S确定A上的一个等价类。,解：设,R1=a,ba,b=a,a,a,b,b,a,b,b,R2=cc=c,c,R3=d,ed,e=d,d,d,e,e,d,e,e,令R=R1R2R3，易证R为等价关系。,102,3-10等价关系与等价类（续）,定理：设R1，R2为非空集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2。,证明：A/R1=aR1|aA，A/R2=aR2|aA，若R1=R2，对任意的aA，则aR1=x|xA,aR1x=x|xA,aR2x=aR2，故aR1|aA=aR2|aA，即A/R1=A/R2。反之，若aR1|aA=aR2|aA，对任意的aR1A/R1，必存在cR2A/R2，使得aR1=cR2，故a,bR1aaR1baR1acR2bcR2a,bR2所以R1R2，同理可证R2R1，得到R1=R2。,103,3-11相容关系,定义：设集合A上的关系r，若r是自反的，对称的，则R称为相容关系。,例如：A为英文单词集合cat,teacher,cold,desk,knife,by关系r=x,y|x,yA且x和y有相同的字母，则r是相容关系。将这六个英文单词分别记为x1,x2,x6，r的关系图与关系矩阵如下。,104,3-11相容关系（续）,注：相容关系是自反和对称的，因此,x1,x6,x5,x4,x3,x2,（1）关系矩阵的对角线上的元素都是1，且矩阵是对称的，可以将矩阵用阶梯形表示如下,（2）在关系图上，每个结点都有自回路且每两个相关结点间的弧线都是成对出现的，为了简化，可以不画自回路并用单线代替双向弧线,105,3-11相容关系（续）,定义：设r是集合A上的相容关系，若CA，如果对于C中的任意两个元素a1，a2，有a1ra2，称C是相容关系r产生的相容类。,例如：上例的相容关系r可产生相容类x1，x2，x1，x3，x2，x3，x6，x2，x4，x5,定义：设r是集合A上的相容关系，不能真包含在任何其他相容类中的相容类称作最大相容类，记作Cr,在相容关系图中，最大完全多边形（其每个顶点都与其它顶点连接的多边形）的顶点集合；或者一个孤立顶点；或者不是完全多边形的边的两个结点的连线，都是最大相容类。,注：对于一个相容类，如果加入任何一个新元素都不再组成相容类，就称它为最大相容类。,106,3-11相容关系（续）,例1：设给定相容关系图，则最大相容类为a1，a2，a4，a6，a3，a4，a6，a4，a5，a7,定理：设r为有限集A上的相容关系，C是一个相容类，则必存在一个最大相容类Cr，使得CCr。,证明：设A=a1,a2,an，构造相容类序列C=C0C1C2，且Ci+1=Ciaj，其中j是满足ajCi，而aj与Ci中各元素都有相容关系的最小足标。由于A的元素个数|A|=n，所以至多经过n-|C|步可使这个过程中止，而此序列的最后一个相容类，就是所要找的最大相容类。,107,3-11相容关系（续）,定义：在集合A上给定相容关系r，其最大相容类的集合称作集合A的完全覆盖，记作Cr(A)。,定理：设集合A的覆盖A1,A2An，由它确定的关系R=A1A1A2A2AnAn是相容关系。,证明：因为A=i=1nAi，对于任意xA，必存在某个j0，使得xAj，所以x,xAjAj，即x,xR因此R是自反的。其次，若有任意x,yA且x,yR，则必存在某个h0使得x,yAhAh，则y,xAhAh，即y,xR，因此R是对称的。,注：集合A的最大相容类集合必覆盖A。,注：给定集合A相容关系r，只能对应唯一一个完全覆盖。,108,注：给定集合A上的任意覆盖，必可在A上构造对应于此覆盖的一个相容关系，但不同的覆盖却能构造相同的相容关系。,定理：集合A上的相容关系与完全覆盖Cr(A)存在着一一对应。,3-11相容关系（续）,例如：A=1,2,3,4，两个覆盖1,2,3,3,4和1,2,2,3,1,3,3,4可以产生相同的相容关系。,r=1,1,1,2,2,1,2,2,2,3,3,2,1,3,3,1,3,3,4,4,3,4,4,3,109,3-12序关系,定义：设集合A上的一个关系R满足自反性，反对称性和传递性，则称R为A上的一个偏序关系，A与偏序关系组成的序偶称为偏序集，记作A,例1：在实数集R上证明小于等于关系“”是偏序关系。,例2：集合A=2,3,6,8，令=x,y|x整除y，则是偏序关系。,证明：,（1）自反性：任意给定aR，有aa成立,（2）反对称性：任给a，bR，如果ab且ba，则a=b,（3）传递性：任给a，b，cR，如果ab且bc，则ac,证明：=2,23,36,68,82,62,83,6，可见其满足自反、反对称和传递性，因此是偏序关系。,110,3-12序关系（续）,定义：在偏序集合A,中，如果x，yA，xy，xy且没有其它元素z满足xz，zy，则称元素y盖住元素x。并且记作COVA=x,y|x,yA；y盖住x,例3：设A是正整数m=12的因子的集合，并设为整除关系，求COVA。,解：m=12的因子集合A=1，2，3，4，6，12=1,21,31,41,61,122,42,62,123,64,126,121,12,23,34,46,612,12COVA=1,21,32,42,63,64,126,12,111,3-12序关系（续）,对于给定偏序集A,，其盖住关系是唯一，所以可用盖住的性质画出偏序集合图，或称哈斯图，其作图规则为：（1）用小圆圈代表元素。（2）如果xy且xy，则将代表y的小圆圈画在代表x的小圆圈之上。（3）若x,yCOVA，则在x与y之间用直线连接。=x,y|x,yA；y盖住x,例如：上例中偏序集的哈斯图如下。,112,3-12序关系（续）,定义：设偏序集合A,，在A的一个子集中，如果每两个元素都是有（偏序）关系的，则称这个子集为链。在A的一个子集中，如果每两个元素都无关，则称这个子集为一个反链。,例4：设集合A=a,b,c,d,e上的二元关系为R=a,aa,ba,ca,da,eb,bb,cb,ec,cc,ed,dd,ee,e，则A,R为偏序集。,解：由R的关系矩阵可以看出自反性（对角线都为1）；反对称性（rij与rji不同时为1）；并可验证R是传递的，因此R是偏序关系，A,R是偏序集。,约定：若A的子集只有单个元素，则此集合既是链又是反链。,113,3-12序关系（续）,COVA=a,bb,cc,ea,dd,e由此可画出哈斯图。集合a,b,c,e，a,b,c，b,c，a，a,d,e等都是A的链。b,d，c,d，a等都是反链。,e,d,c,b,a,注：,（1）在每个链中总可从最高结点出发沿着盖住方向遍历该链中所有结点。,（2）每个反链中