离散习题(附答案) (5).doc

第5章 习题解答习题 5.11.设A=a,b,c，B=1,2,3，试说明下列A到B二元关系，哪些能构成A到B的函数？ f1=, f2=, f3=, f4=, f5=,解：不能构成函数。因为f1且f1能构成函数不能构成函数。因为domf3A不能构成函数。因为f4且f4能构成函数。2.试说明下列A上的二元关系，哪些能构成A到A的函数？ A=N(N为自然数集合)，f1=| aAbAab10 A=R(R为实数集合)，f2=| aAbAb=a2 A=R(R为实数集合)，f3=| aAbAb2=a A=N(N为自然数集合)，f4=| aAbAb为小于a的素数的个数 A=Z(Z为整数集合)，f5=| aAbAb=|2a|1解：不能构成函数。由于1+110且1+210，所以f1且f1。能构成函数。不能构成函数。由于12=1且(-1)2=1，所以f3且f3。能构成函数。能构成函数。3. 回答下列问题。 设A=a,b，B=1,2,3。求BA，验证|BA|= |B|A|。 设A=a,b，B=1,2。求BAA，验证|BAA|=|B|A|A|。解：f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,f8=,BA=f0, f1, f2, f3, f4, f5, f6, f7,f8|BA|=9=32= |B|A| AA=,f0=,1,1,1,1f1=,1,1,1,2f2=,1,1,2,1f3=,1,1,2,2f4=,1,2,1,1f5=,1,2,1,2f6=,1,2,2,1f7=,1,2,2,2f8=,2,1,1,1f9=,2,1,1,2f10=,2,1,2,1f11=,2,1,2,2f12=,2,2,1,1f13=,2,2,1,2f14=,2,2,2,1f15=,2,2,2,2BAA=f0, f1, f2, f3, f4, f5, f6, f7,f8,f9 f10, f11, f12, f13, f14, f15|BAA |=16=24=|B|A|A|4.下列函数中，哪些是单射？哪些是满射？哪些是双射？为什么？ f：NN，f(x)= x21 f：ZZ， f(x)=(x mod 3)(函数值为x除以3的余数) f：NN， f：N0,1， f：ZR，f(x)=3x f：RR，f(x)=x3解：是单射，不是满射，不是双射。当x,yA，xy，x2y2，x21y21，f(x)f(y)。所以f：NN是单射。因为xN，f(x)0N。所以f：NN不是满射。因为不是满射，所以不是双射。不是单射，不是满射，不是双射。因为69，而f(6)=(6 mod 3)=0=(9 mod 3)=f(9)。所以f：ZZ不是单射。因为xZ，f(x)3Z。所以f：ZZ不是满射。因为不是单射且不是满射，所以不是双射。不是单射，不是满射，不是双射。因为13，而f(1)=f(3)。所以f：NN不是单射。因为xZ，f(x)2N。所以f：NN不是满射。因为不是单射和不是满射，所以不是双射。不是单射，是满射，不是双射。因为13，而f(1)=1=f(3)。所以f：N0,1不是单射。显然，f：N0,1是满射。因为不是满射，所以不是双射。是单射，不是满射，不是双射。f：ZR，f(x)=3x是单调递增函数，所以是单射。因为xZ，f(x)0R。所以f：ZR不是满射。因为不是满射，所以不是双射。是单射，是满射，是双射。f：RR，f(x)=x3是单调递增函数，所以是单射。因为yR，有x=R，使f(x)= f()=()3=y。所以f：RR，f(x)=x3是满射。因为是单射和满射，所以是双射。5.设A=1,2,3,4，A上的等价关系R为： R=,IA求自然映射f：AA/R解：A/R=1,4,2,3f=,6.设f: ZZZ(Z为整数集合)，f(x,y)= xy；g: ZZZ，g(x,y)= xy。 试证明f 和g是满射函数，但不是单射函数。证明：xZ，ZZ，f (0,x)= 0x=x，所以f: ZZZ，f(x,y)=xy是满射。ZZ，f (1,x)= 1x=x，所以g: ZZZ，g(x,y)=xy是满射。对于ZZ，ZZ，f(1,2)=3=f(2,1)，但，所以f: ZZZ，f(x,y)= xy不是单射函数。对于ZZ，ZZ，g(3,2)=6= g(2,3)，但，所以g: ZZZ，g(x,y)= xy不是单射函数。7.设A和B是有限集合，|A|=n，|B|=m。有多少个不同的单射函数f：AB。解：要使f：AB是单射函数，必须nm，因此，当nm时，无A到B的单射函数。当nm时，共有=n(n-1)(n-m+1)有多少个不同的双射函数f：AB。解：要使f：AB是双射函数，必须n=m，此时共有m!个双射函数。请参看习题5.2的第6题。8.设f：AB，CA，证明f(A)f(C)f(AC)证明：f(x)f(A)f(C)f(x)f(A)f(x)f(C)xAxCxAC f(AC)所以, f(A)f(C)f(AC)9.设A=a1,a2,an，试证明任何从A到A的函数，如果它是单射，则它必是满射。反之亦真。证明：设f：AA是单射，下证f是满射。反证法，设f不是满射，至少有一个元素不是f的像，设这个元素为aj，则ran fA-aj，所以ran fA，从而有|ran f|A|，与f是单射矛盾。设f：AA是满射，下证f是单射。反证法，设f不是单射，$aiA，ajA，使f(ai)=f(aj)，而aiaj，构造函数f1：A-aiA，f1(x)=f(x)因为f：AA是满射，所以f1：A-aiA也是满射。故有|A-ai|A|。又因为aiA， A-aiA，|A-ai|A|，所以，|A|A-ai|A|，即|A|A|，矛盾。10.设f：AB，CA，DA，试证明： f(CD)= f(C)f(D) f(CD) f(C)f(D)证明：f(x)f(CD)xCDxCxDf(x)f(C)f(x)f(D)f(x)f(C)f(D)即f(CD)= f(C)f(D)f(x)f(CD)xCDxCxDf(x)f(C)f(x)f(D)f(x)f(C)f(D)即f(CD) f(C)f(D)11.设f：AB。g：BP(A)，定义为：对于bB，g(b)= x|xAf(x)=b。证明：如果f是A到B的满射，则g是B到P(A)的单射。证明：以下证明g：BP(A)的单射。g(b)=x|xAf(x)=b。设x1B，x2B且x1x2，因为f是A到B的满射，$y1A，使f(y1)=x1，$y2A，使f(y2)=x2。因为x1x2，所以f(y1)f(y2)，又因为f是函数，故有y1y2。由g的定义有，y1g(x1)，y2g(x2)。因为f(y2)=x2x1，所以y2g(x1)，故有g(x2)g(x1)，即g(x1)g(x2)。这就证明了g是B到P(A)的单射。12.设是偏序集，xA，令f(a)= x|xAxa ，证明： f：AP(A) 是单射。 若 ab 时，必有 f(a)f(b)证明：aA，bA且ab当ab时，因为ab，则无ba，bf(a)。又由偏序关系的自反性知bb，从而bf(b)。f(a)f(b)当ba时，类似的可以证明f(a)f(b)设ab，xf(a)xAxa，由ab和偏序关系的传递性xAxbxf(b)。即f(a)f(b)。习题 5.21.设X=x1,x2, x3, x4 ，Y= y1,y2, y3, y4, y5，Z= z1,z2, z3f：XY，定义为f=,g：YZ，定义为g=,试求函数g在函数f左边的复合关系gf，验证复合关系gf是X到Z的函数。解：gf=,mod gf=x1,x2,x3,x4=X。当x1= x2时，f(x1)=f(x2)gf：XZ2.设f,g,hRR，且f(x) =x2-2，g(x) =x4，h(x) =x3-1 试求gf和fg gf和fg是单射？满射？双射？ f,g,h中哪些有反函数？若有，求出反函数。解： gf(x)= x2+2fg(x)=x2+8x+14 gf不是单射，不是满射，不是双射。fg不是单射，不是满射，不是双射。 f不是单射，不是满射，不是双射。无反函数。g是单射，是满射，是双射。有反函数。g-1(x)= x-4h是单射，是满射，是双射。有反函数。h-1(x)=3.设f：AB，g：BC，g和f的复合函数gf：AC，试证明: 如果gf是单射，那么f是单射。 如果gf是满射，那么g是满射。 如果gf是双射，那么f是单射，g是满射。证明：x1B，x2B且f(x1)=f(x2)，因为g是函数，g(f(x1)=g(f(x2)gf(x1)=gf(x2)，由于gf是单射，所以x1=x2，f是单射。 cC，因为gf是满射，存在aA，使gf(a)=c，又因为 f：AB是函数，令b=f(a)，g(b)=g(f(a )=gf(a)=c， g是满射。 设gf是双射，由知f是单射，由知g是满射。4.设f：AB，f是双射，AA，BB，试证明 f (f -1(B)B 利用f是满射，证明f (f -1(B)=B Af -1(f (A) 利用f是单射，证明A=f -1(f (A)证明： 设f(x)f (f -1(B)xf -1(B)$yB使x=f -1(y)f -1(B) f(x)=yB所以，f (f -1(B)B yB，因为f：AB是满射，xA使f(x)=y x=f-1(y)xf -1(B)y=f(x)f(f -1(B)B f (f -1(B)由有 f (f -1(B)B所以，f (f -1(B)=B xA，因为f：AB，所以$yB使f(x)=y，而y=f(x)f(A)x=f -1(y)f -1(f (A)，即xf -1(f (A)Af -1(f (A) xf -1(f (A)，$yf (A)使x=f -1(y)，从而y=f(x)；再由$yf (A)，$xA，使y=f(x)。因为f：AB是单射，所以，x=xA，故有f -1(f (A)A又由有Af -1(f (A)这就证明了A=f -1(f (A) 5.设f：AB，g：BA，证明： gf=IA且fg=IB当且仅当g=f-1且f=g-1证明：设g=f-1且f=g-1，下证gf=IA且fg=IB因为g：BA，f-1：BA，g=f-1，所以yB，g(y)=f -1(y)。令g(y)=f -1(y)=x，则g(y)=x，y=f(x)。又由f=g-1 f：AB，g-1：AB，且xA，f(x)=g-1(x)。由此y=f(x)=g-1(x)g(y)=x所以，gf(x)=g(f(x)=g(y)=x=IA(x)，fg(y)=f(g(y)=f(x)=y=IB(x)显然，gf：AA，IA：AA；fg：BB，IB：BB这就证明了gf=IA且fg=IB设gf=IA且fg=IB，下证g=f-1且f=g-1因为恒等函数IA是双射，所以gf：AA是双射，由习题5.2的第3题，f 是单射，g是满射。同样，恒等函数IB是双射，所以fg：BB是双射，由习题5.2的第3题，g是单射，f是满射。所以，f 和g都是双射函数，他们的反函数都存在。g：BA，f-1：BAyB，由f-1：BA，令f-1(y)=xAf(x)=yg(y)=g(f (x)=gf (x)=IA(x)=x= f-1(y)，显然，g：BA，f-1：BA所以，g=f -1类似的可以证明，f=g-16.设A=a1,a2, , an，函数f：AA是双射。称双射f为集合A上的置换，n称为置换阶，常记为：由于f是双射，f(a1),f(a2),f(an)都是A的元素且互不相同。因此f(a1),f(a2),f(an)必为a1,a2, , an的一个排列。而a1,a2, , an的排列总数是n!个，因此集合A上的n阶置换的数目是n!个。即A到A是双射函数有n!个。设A=1,2,3，集合A上应有3!=6个3阶置换。写出集合A上的所有3阶置换。解： 7.如果某人营造了n个鸽舍，养了多于n只鸽子，则必有一个鸽舍住有2只或2只以上的鸽子。这就是鸽舍原理。用数学语言将这个原理抽象为：设A，B是有限集合，f是A到B的函数，如果|A|B|，则A中至少有两个元素，其函数值相等。更一般的情况是：当鸽舍为n个，鸽子数大于nm只时，必有一个鸽舍住有m十1个或多于m+1个鸽子。用数学语言抽象为：设A，B是有限集合，f是A到B的函数，如果|A|nm，|B|n，则在A中至少有m+1个元素，其函数值相等。例如，有3个鸽舍，13只鸽子。A是鸽子构成的集合，|A|=1334。B是鸽舍构成的集合，|B|3。则必有一个鸽舍，住有41=5个或5个以上鸽子。利用鸽舍原理解下列各题：任意n+1个正整数，其中必有两个数之差能被n整除。在边长为1的正三角形内，任取7个点，证明其中必有3个点联成的小三角形的面积不超过。解：由于任意正整数被n除后，其余数只能是0，1，n-1共n种，所以在n+1个正整数中，必有两个数被n除后余数相同，这两个数之差必能被n整除。 如图5.6所示，ABC是边长为1的正三角形，点O是ABC的重心，连接OA、OB，OC，则将ABC分为面积相等的3个小三角形，每个小三角形的面积都为：=。把小三角形作为“鸽舍”，点作为“鸽子”，则有7只鸽子，3个鸽舍。而INT(7/3)=2，由鸽舍原理，7个点中至少有3个点在同一个小三角形中，由这3个点联成的三角形的面积必小于小三角形的面积。习题 5.31.证明区间(0,1)和区间0,1等势。证明：设f：(0,1)0,1，f(x)=x是单射函数。|(0,1)|0,1|。又设g：0,1(0,1)，g(x)=是单射函数。|0,1|(0,1)|。故|(0,1)|=| 0,1|。2.设A,B,C,D是任意集合，AB，CD，证明AC BD证明：因为AB，所以，存在f：AB是双射函数。因为CD，所以，存在g：CD是双射函数。令h：ACBD，定义为：h()=以下证明h是单射函数：设，则有下列3种情况：a1a2且c1=c2因为，f：AB是单射函数，所以，f(a1)f(a2)，故，即h是单射函数。a1=a2且c1c2类似可以证明h是单射函数。a1a2，且c1c2，类似和可以证明h是单射函数。综上所述，h是单射函数。以下证明h是满射函数：BD，则bB，dD因为，f：AB是满射函数，所以，$aA是f(a)=b。因为，g：CD是满射函数，所以，$cC是g(c)=d。AC使h()=BD。h是满射函数。故h：ACBD是双射函数。AC BD3.设N是自然数集合，A=x|x=n5nN，证明A是可数集。证明：令ai=i5，则集合A可用列举法表示为： A=05,15,25,35, = a0,a1, A是能用自然数编号的无限集，根据定理5.3.5，A是可数集。4.设Q是有理数集合，证明叉乘积QQ是可数集。证明：由例5.13知Q是可数集，Q的元素能用自然数编号。设Q= a0,a1,a2,QQ= , , , ,即QQ可以表示为可数个可数集的并集。由定理5.3.8知，QQ是可数集。5.设N是自然数集合，证明|P(N)|=。证明：作函数h：P(N)0,1，h如下定义：SP(N) h(S)=0.x0x1x2x3(2进制小数)，其中 例如，h()=0， h(N)=0.1111，h(1,4,5)=0.010011。显然，h是单射函数。|P(N)|0,1|作函数k：0,1P(N)，k如下定义：x=0.x0x1x2x30,1 (x是2进制小数，如果x没有唯一表示，可任意选择其中之一) k(x)= i|xi=1例如，k(0)=， k(1)= k(0.1111)=N，h(0.010011)= 1,4,5。显然，k是单射函数。|0,1|P(N)|由和得|P(N)|=|0,1|6.如果A是不可数无限集，B是A的可数子集，证明(AB) A。证明：显然AB是无限集，B是可数集。因为B是A的子集，所以，A=(AB)B，从而，|A|=|(AB)B|，由习题5.3的第7题的结论得，|A|=|(AB)B|=|AB|，即(AB) A。7.如果A是任意无限集，M是一个可数集，证明 (AM) A证明：如果A是任意可数无限集，由定理5.3.8知，可数集的并集是可数集。AM是可数