离散数学--第三章--集合与关系---习题课

离散数学,第三章集合与关系,3-2（9）在什么条件下，下面命题为真？a)(A-B)(A-C)=A(A-B)(A-C)=(AB)(AC)=A(BC)=A(BC)=A-(BC)=A所以满足此式的充要条件是：A(BC)=或A(BC)b)(A-B)(A-C)=(A-B)(A-C)=A(BC)=A-(BC)=所以满足此式的充要条件是：ABCc)(A-B)(A-C)=(A-B)(A-C)=(AB)(AC)=A(BC)=A(BC)=A-(BC)=所以满足此式的充要条件是:ABCd)(A-B)(A-C)=因为当且仅当A=B，才有AB=所以满足此式的充要条件是:A-B=A-C,3-2（4）集合的证明a)证明(AB)C=A(BC)iffCA证明；CA(AB)C=A(BC)(AB)C=(AC)(BC)=A(BC)(CAAC=A)(AB)C=A(BC)CAxC，xCx(AB)CxA(BC)xA所以CA所以(AB)C=A(BC)iffCA,3-2（5）b)证明(A-B)-C=(A-C)-B,(A-B)-C=(AB)C=(AC)B=(A-C)-B所以(A-B)-C=(A-C)-B,x：x(A-B)-Cx(A-B)xC(xAxB)xC(xAxC)xBx(A-C)xBx(A-C)-B所以(A-B)-C=(A-C)-B,第104页b)A=0,1B=1,2求A2B。AB=|xAyBA2=AA=,A2B=,1,1,1,1,2,2,2,2注意：A2B=(AA)B=AAB第105页设A=a,b,构成集合P(A)AP(A)=,a,b,a,bP(A)A=,第109页X=a,b,cY=sX到Y的所有关系：XY=,XY的任何一个子集都是一个从X到Y的关系。如果|X|=m|Y|=n则有2mn个从X到Y的关系,故,有23=8个关系:R0=R1=R2=R3=R4=,R5=,R6=,R7=,设|A|=n，有多少个A上的关系？因为RAA,所以AA有多少个子集就有多少个A上关系,由集合的幂集就是该集合的子集构成的,所以A上关系个数就是AA的幂集P(AA)的元素个数|P(AA)|,而2|AA|=2nn=。所以有个不同的A上关系。,P1093-5（5）,注意：A上的关系，结点数为A中元素的个数。,第113页A=1,2,3，A上五个关系如下：,R,S,T,AA,R,AA,T,S,自反反自反对称反对称传递,NNNYY,YNYNY,NNNYN,NYYYY,YNYNY,上述五个关系中，哪些是等价关系？如果是等价关系，求其商集。哪些是相容关系？如果是相容关系，求其完全覆盖。哪些是偏序关系？如是偏序关系,画Hasse图,并求的极小(大)元、最小(大)元、上界与下界、上确界和下确界。等价关系：S和AA，对应的商集分别是：A/S=1,2,3A/A=1,2,3相容关系:S和AA，对应的完全覆盖分别是：CS(A)=1,2,3CAA(A)=1,2,3偏序关系:T的极小元、最小元、下界、下确界都是：1的极大元、最大元、上界、上确界都是：3,T,1,2,3,P113（3）举出A=1,2,3上关系R的例子，使其具有下述性质：a)既是对称的，又是反对称的；b)既不是对称的，又不是反对称的；c)是可传递的,1,2,3,1,2,3,1,2,3,归纳：关系性质证明方法,设R是A上关系，一.证明R的自反性：方法1用自反定义证：任取xA,证出R.方法2用恒等关系IA证：证出IAR.(P119(2)b)方法3用自反闭包证：证出r(R)=R,即RIA=R.二.证明R的反自反性：方法1用反自反定义证：任取xA,证出R。方法2用RIA=证三.证明R的对称性：方法1用对称定义证：任取x,yA,设R,证出R.方法2用求逆关系证：证出Rc=R.方法3用对称闭包证：证出s(R)=R,即RRc=R.,四.证明R的反对称性方法1用定义1证：任取x,yA,设R,R.证出x=y。方法2用定义2证：任取x,yA,xy,设R,证出R.方法3用定理证：证出RRcIA.(见教材P118)五.证明R的传递性：方法1用传递定义证：任取x,y,zA,设R,R,证出R.方法2用传递闭包证：证出t(R)=R,即RR2R3.=R.方法3用定理证：证出RRR(P119(2)a)下面证明第113页(4),证明：一.证明RS的自反性方法1用自反定义证：任取xA,(证出RS)因R和S都自反，所以有R，S，于是有RS，所以RS也自反。方法2用恒等关系IA证：(证出IARS)因R和S都自反，所以IAR，IAS，所以IARS所以RS也自反。方法3用自反闭包证：(证出r(RS)=RS,即(RS)IA=RS)因R和S都自反，所以r(R)=R,r(S)=S,r(RS)=(RS)IA=(RIA)(SIA)=r(R)r(S)=RS所以RS也自反。,P113(4)R和S都A上是自反、对称、传递的，求证RS也是自反、对称和传递的。,二.证明RS的对称性：方法1用对称定义证：任取x,yA,设RS,(证出RS.)则R，S，因为R和S对称，所以有R，S，于是RS。RS对称。方法2用求逆关系证：(证出(RS)c=RS.)因为R和S对称，所以有Rc=R，Sc=S，而(RS)c=RcSc=RS，RS对称。方法3用对称闭包证：(证出s(RS)=RS,即(RS)(RS)c=RS.)因为R和S对称，所以s(R)=R,s(S)=Ss(RS)=(RS)(RS)c=(RS)(RcSc)=(RRc)(RSc)(SSc)(SRc)=(s(R)(RSc)(s(S)(SRc)=(R(RSc)(S(SRc)=RS(吸收律)RS对称。,五.证明R的传递性：方法1用传递定义证：任取x,y,zA,设RS,RS,(证出RS)RSRSRSRS(RR)(SS)RS（因为R、S传递）RS所以RS传递。方法2用传递闭包证：证出t(RS)=RS,即(RS)(RS)2(RS)3.=RS.方法3用定理证：证出用方法2、方法3证明此题的传递性有很大难度。R(ST)(RS)(RT)希望同学们灵活掌握证明关系性质的方法。,P127(1)R的有向图如图所示，求r(R)、s(R)、t(R)。,P1273-9(5),设R1和R2是非空集合A上的关系,且R2R1则(1)r(R2)r(R1)(2)s(R2)s(R1)(3)t(R2)t(R1)证明：(1)R2R1R2IAR1IAr(R2)r(R1)(2)R2R1R2CR1CR2R2CR1R1Cs(R2)s(R1)(3)R2R1R22R12R23R13R2R22R23R1R12R13t(R2)t(R1)因为R2R1，而R1t(R1)，所以R2t(R1)，且又因为t(R1)具有传递性，t(R2)是包含R2的最小传递关系，所以t(R2)t(R1)。,集合与关系的结构图,枚举法有向图矩阵,等价关系,有向图,等价类,商集,划分,偏序关系,相容类,最大相容类,完全覆盖,简化图,全序,哈斯图,计算方法,运算性质,重要元素,第130页(1).X是集合，且|X|=4，X有多少个不同的划分？解.第134页(2).X是集合，且|X|=4，X上有多少个不同的等价关系？解.此题的答案与上题一样。因为每个划分对应一个等价关系。,P134(4).R是A上关系，设S=|cARR求证若R是等价关系，则S也是等价关系。证明：a)证S自反：任取aA，R是自反的，有R,由S定义得S,(S定义中c就是a)S自反。b)证S对称:任取a,bA，且有S,由S定义得cARR,由R对称得cARR,由S定义得S,S对称。c)证S传递:任取a,b,cA,有S,S,由S定义得(dARR)(eARR),由于R传递,所以有R,R,由S定义得S,所以S传递.所以S是A上等价关系。,P135(6).R是A上对称和传递的关系，证明如果aA，bA,使得R,则R是一个等价关系。证明:任取aA,由已知得bA，使得R,由R对称得R，又由R的传递性得，R，R是自反的,R是等价关系。,P135(7).R和S都是A上等价关系,下面哪个是A上等价关系?证明或举反例说明.a)R(即AA-R)b)R-Sc)R2d)r(R-S)解.a)b)d)不是。请看反例:,R,b。,b。,S,b。,AA-R,b。,R2,b。,R-S,b。,r(R-S),c)证R2自反,任取aA,因为R自反,所以R,根据关系的复合得,RR,即R2,R2自反。证R2对称,(R2)c=(Rc)2=R2(由R对称得Rc=R)R2对称证R2传递，任取a,b,cA,设有R2,R2,根据关系的复合得，(dARR)(eARR),由于R传递，所以有R，R，R2所以R2传递。最后得R2是等价关系。,相容关系1.定义:给定集合X上的关系r,若r是自反的、对称的,则r是A上相容关系。2.图的简化：不画环；两条对称边用一条无向直线代替。3.矩阵的简化：因为r的矩阵是对称阵且主对角线全是1，用下三角矩阵(不含主对角线)代替r的矩阵。4.相容类：设r是集合X上的相容关系，CA,如果对于C中任意两个元素x,y有r,称C是r的一个相容类.5.最大相容类:设r是集合X上的相容关系，C是r的一个相容类，如果C不能被其它相容类所真包含，则称C是一个最大相容类。-最大完全多边形.6.完全覆盖：r是中的相容关系，由r的所有最大相容类为元素构成的集合，称之为X的完全覆盖。记作Cr(X)。,第139页(2).X=x1,x2,x3,x4,x5,x6,R是X上相容关系，其简化关系矩阵如下：求X的完全覆盖。解.R的简化图为：CR(X)=x1,x2,x3,x1,x3,x6,x3,x4,x5,x3,x5,x6,o,偏序关系判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.1.定义：R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称是偏序集。2.x与y是可比较的：是偏序集，x,yA，如果要么xy,要么yx,则称x与y是可比较的。3.定义：是偏序集，任何x,yA，如果x与y都是可比较的，则称是全序关系(线序、链)。4.偏序集Hasse图的画法：令是偏序集，1).用“”表示A中元素。2).如果xy,且xy，则结点y要画在结点x的上方。从最下层结点(全是射出的边与之相连，逐层向上画，直到最上层结点(全是射入的边与之相连)。,第145页(1)