川大离散数学习题.doc

习题61. 设A=1，2，3，4，B=AA。确定下述集合是否为A到B的全函数或部分函数。(1) (1,(2,3),(2,(2,2),(3,(1,3),(4,(4,3).(2) (1,(1,2),(1,(2,3),(3,(2,4).(3) (1,(3,3),(2,(3,3),(3,(2,1),(4,(4,1).解：（1）、全函数（2）、不符合单值（3）、全函数要点： 根据全函数定义，X中每个元素x都在Y中有唯一元素y与之对应。2. 判别以下关系中那些是全函数。(1) (n1,n2)|n1,n2N,02n1-n25。(2) (n1,n2)|n1,n2N,n2是n1的正因子个数。(3) (S1,S2)|S1,S2a,b,c,d且S1S2=。(4) (a,b)|a,bN,gcd(a,b)=3.(5) (x,y)|x,yZ,y=x2.解： (1) (n1,n2)|n1, n2 N, 02 n1-n25不是函数，n1=0时无定义，且(3,4),(3,5)在其中。(2) (n1,n2)|n1, n2 N, n2是n1的正因子个数部分函数，n1=0时无定义(3) (S1,S2)|S1, S2 a,b,c,d且 S1 S2= 不是函数，因为(a,b) ,(a,c)均在其中。(4) (a, b)|a, b N, gcd(a,b)=3不是函数，因为(3, 3) ,(3, 6), (3, 9)均在其中。(5) (x, y)|x, y Z, y=x2全函数3. 在3.1中已经定义了集合的特征函数。请利用集合A和B的特征函数A（x）和B（x）表示出AB，AB，A-B，以及AB对应的特征函数。解：（略）4. 试确定在含n个元素的集合上可以定义多少个二元关系，其中有多少个是全函数。解: 可以定义nn个二元关系，n！个全函数5. 设f：AB，CA，证明：f（A）-f（C）f（A-C）。证明：bf(A)-f(C)bf(A) bf(C)($x)xA xC f(x)=b($x)xA-C f(x)=bbf(A-C)所以f(A)-f(C)f(A-C)7. 设f：XY，A和B是X的子集。证明，证明：（1）yf(AB)(x)x(AB)f(x)=y(x)xA f(x)=y(x)xB f(x)=yyf(A)yf(B)f(AB)=f(A)f(B)（2）yf(AB)(x)x(AB)f(x)=y($x)xAf(x)=y($x)xBf(x)=yyf(A)yf(B)f(AB)f(A)f(B)8. 确定下例映射是否单射、满射或双射：（1） f1:NR,f1(n)=n.（2） f2:NN,f2(n)为不超过n的素数数目。（3） f3:NNN,f3(n,n)=(n+1).（4） f4:RR,f4(x)=x2+2x-15.（5） f5:ZZ,f5(x)=1+2x3.（6） A是集合，f6:2A2A2A2A,f6(x,y)=(xy,xy).（7） f7:RRR,f7(x,y)=x+y. F8:RRR,f8(x,y)=xy.解： (1)单射(2)满射，非单。如f(5)=f(6)=3(3)非单,非满。f(0,1)=f(1,0)=1,且f(x,y)=0无解。(4)非单,非满。(5)单,非满。如： 1+2x3=5无解。(6)非单: (ab, ab) = (a,b , a,b ) 非满: (x y,x y)=(a, a,b)无解。(7) f7: 非单,满，如： f(1,3)=f(2,2)f8: 非单,满，如： f(1,3)=f(3,1)9. 设X是有限集合，f：XX。证明：(1) 如果f是单射时，f必是双射。(2) 如果f是满射时，f必是双射。证明： (1).当f是单射时，根据单射定义，对所有任意t,sX,当ts时f(t)f(s),则f(x)中的元素个数与X中的元素个数相同； 又f:XX，所以，f(x)是一个满射 f必是双射。 (2)当f是满射时，根据满射定义及f的定义，对所有yX，都存在xX，使f(x)=y，再根据函数的单值性，对所有t,sX,当ts时，f(t)f(s)。 f必是双射。10. 设f是有限集X上的一个函数，满足xX，f2（x）=x。证明：f是双射。证明：设x,y是有限集X上的2个元素，如果f(x)=f(y),则x= f2(x)= f2(y)= y ，说明是单射，由上题结果知f是双射。11.设f:AB，g：B2A，满足bB，g（b）=xA|f(x)=b.证明：当f为满射时g为单射。问g为单射时，f是否必是满射？证：1）对任意b1、b2B，且b1b2。 f(x)是满射 。 12. 设A和B都是有限集合，试确定A到B有多少个单射？多少个满射？多少个双射？解：设A、B中元素个数分别为：m、n,则单射个数为：n(n-1)(n-2)(n-m)满射个数为：nm,双射个数为：n!或m!13.设有函数f，g，h：RR，这里f(x)=2x，g(x)=x2+x-1，h(x)=x-2。写出fg，gfh，hhg。解：fg=f(g(x) =2x2+2x-2gfh= (g(f(h(x) = 4(x-2)2+2(x-2)-1 hhg= (h(h(g(x) = x2+x-514. 设f，g，h都是集合A上的函数。如果f=g，是否必有hf=hg或fh=gh？解：（1）f=g，则对于所有xA，都有f(x)=g(x), 所以，对于所有的xA，h(f(x)=h(g(x),f(h(x)=g(h(x)即h。f=h。g（2）h。f=h。g则，h(f(x)=h(g(x), 当对于A中任意两个不同的元素x,y都有h(x)h(y)时，f=g； 当A中存在两个不同的元素x,y有h(x)=h(y)，即对于同一个元素z,当f(z)=x ,g(z)=y，则有h(f(z)=h(g(z)，而此种情况下fg 综上，当h。f=h。g时，f不一定等于g15. 设f，g是实数集R上的函数，其中f(x)=x2+2，g(x)=2x-1。确定fg和gf是否满射、单射或双射？解：f。g=(2x-1)2 +2,函数图形为以x=1/2为对称轴的一个抛物线，由题，f,g都是实数上的函数，则f。g不是单射，不是满射，也不是双射； g。f=2(x2+2)-1=2x2+3,函数图形为以Y坐标为对称轴的抛物线，f(x)=f(-x)，所以，g。f不是单射，不是满射，也不是双射。16. 设f和g都是函数。证明：(1) 当gf为单射时，f必为单射；(2) 当gf为满射时，g必为满射；(3) 当gf为双射时，g为满射，f为单射。证明：设 f: AB, g: BC。（1）（反证法）设f不是单射，存在x1x2A,且f(x1)=f(x2)，即：gf(x1)= g(f(x1)= g(f(x2)= gf(x2),与gf为单射矛盾。因此，f必为单射。（2）对于任意zC，由于gf为满射，那么存在xA使得gf(x)=z，因此存在y=f(x)B,使得z=g(y)，因此g是满射。（3）由（1）、（2）可得证。17. 设A=1，2，3，4。（1）找出一个A上的非单位置换的置换，计算=2，2=3，以及-1。（2）若A上置换满足=（1），称为幂幺置换，求出A上的全部幂幺置换。解：(提示，按照定义求解即可) （1）任定义为：(2,1,3,4) （2）（略）18. 计算有限集合X可以定义出多少个函数f，使得f=f-1。解：（略）19.证明下列集合A和B等势。1) A=(0,1),B=(-2,2).2) A=(-,+),B=(0,+).3) A=(0,1),B=(，).4) A=N, B= (m, n) |m、nN mn.证明：（思路：想办法构造一个双射函数即可）（1）f(x)=2tan() (2）（略）(3)f(x)=(4)(略)20.设AB，CD。证明：ACBD。证明：（略）21.证明：非空有限集A与可数集B的笛卡尔积AB也是可数集。证明：非空有限集A与可数集B的笛卡尔积AB也是可数集。证明：设A=a1,a2,an B=b1,b2,bn,令Bi =(ai,b1),(ai,b2),(ai,bn), (in),则 AB= ,因为B为可数集，所以Bi为可数集。AB为有限个可数集的并集。下面用归纳法证明有限个(m个)可数集的并集为可数集。设Cm=cm1,cm2, ,cmn, 当m=2时，构造双射f:NC1C2, N 1 2 3 4 5 6 n-1 n f(N) c11 c21 c12 c22 c13 c23 c1(n/2) c2(n/2) 所以2个可数集的并集为可数集。假设m=k-1(k3)时结论成立，即k-1个可数集的并集为可数集，记为D。则m=k时，可以构造类似的双射g:NDCk,所以为可数集。因而有限个可数集的并集为可数集。所以AB是可数集。补充：1. 设和是两个有限集合，它们的元数都是，则是单射的充分必要条件是为满射证 必要性，当是单射时，的元数是，而的元数也是，故，因此是满射。充分性，若为满射时，有，则的元数为，的元数也是，个原象对应个象，即不同元素对应不同的象，因此是到的单射。2设为实数集，试证明和都是满射，而不是单射。证 对于任意，可以使成立的有无数对，且，也就是说值域中每个元素都有无数原象在中，所以是满射，而不是单射。对于任意，能使成立的也不止一对实数存在。例如，而，或，即象集中每一元素都有原象，而且原象不唯一，所以是满射，而不是单射。 证毕。说明：欲证明一个映射为满射时，通常采用取值域中任意元素，按映射对应都有原象存在时，则可确定该映射为满射，或者直接证得。 欲证一个映射为单射时，按定义一般有两种方法，一是任取属于定义域，能证得。另一种方法是：取属于值域，证得。3. 设为实数集，都是的映射。（1） 求，并分别判定是否为的满射，单射，双射？（2）