发布时间 : 星期日 文章最新洪帆《离散数学基础》(第三版)课后习题答案更新完毕开始阅读
精品文档
第3章 函数
1. 以下关系中哪一个构成函数？ (1) {(n1,n2)|n1,n2?N,n1?n2?10}
答：不构成函数。象的唯一性不能满足，因为(1,2),(1,3)都属于这个集合。而12,13等这样的数在N中无像，所以象的存在性也不能满足。 (2) {(n1,n2)|n1,n2?N,n2?小于n1的素数的个数} 答：是函数，象的唯一性和存在性都能满足。
2. 设A?2U?2U，B?2U，给定由A到B的关系：
S,1?S|1S,? f?{(( U}1,S2)S2)S2f是函数吗？若是的话，f的值域Rf?2U吗？为什么？
答：f是函数。f的值域Rf?2U。因为对?C?2U，则C?U，则对(C,C)，
C?C?C，因此象C的像源为(C,C)。
3. 下列集合能够定义函数吗？如果能，试指出它们的定义域和值域？ (1) {(1,(2,3)),(2,(3,4)),(3,(1,4)),(4,(1,4))}
答：能定义函数。Df?{1,2,3,4}，Rf?{(2,3),(3,4),(1,4)} (2) {(1,(2,3)),(2,(3,4)),(3,(3,2))}
答：能定义函数。Df?{1,2,3}，Rf?{(2,3),(3,4),(3,2)} (3) {(1,(2,3)),(2,(3,4)),(1,(2,4))}
答：不能定义函数。因为有一对多的情况。 (4) {(1,(2,3)),(2,(2,3)),(3,(2,3))}
答：能定义函数。Df?{1,2,3}，Rf?{(2,3)}
4. 设函数f:A?B,S?A，等式f(A)?f(S)?f(A?S)成立吗？为什么？ 答：不成立。因为f(A)?f(S)?f(A?S)成立，但是f(A?S)?f(A)?f(S)不成立。下面证明f(A)?f(S)?f(A?S)。
设b?f(A)?f(S)，则b?f(A)且b?f(S)，所以必存在a?A使f(a)?b。由于所以a?S，于是a?A?S，因此b?f(A?S)，故fAb?f(S)，()f?S()f?A(S)?f(A?S)?f(A)?f(S)不成立，反例如下：
。
设A?{a1,a2,a3,a4}，S?{a2,a3}，则A?S?{a1,a4}，函数f:A?B的定义为：
f?{(a1,b1),(a2,b1),(a3,b2),(a4,b3)}。显然f(A)?{b,2b,3b，}f(S)?{b1,b2}，1f(A?S)?{b1,b3}，f(A)?f(S)?{b3}，f(A?S)?f(A)?f(S)。由上可知f(A)?f(S)?f(A?S)不成立。
精品文档
精品文档
5 设有函数f:A?B，试证明等式f(A?B)?f(A)?f(B)，等式?Cf(A?B)?f(A)? f(成立吗？为什么？B)证明：设c?f(A)?f(B)，则c?f(A)或者c?f(B)。若c?f(A)，则存在a?A使得f(a)?c，因此有a?A?B，所以c?f(A?B)。若c?f(B)，类似地，有
c?f(A?B)，故f(A)?f(B)?f(A?B)。
反之，若c?f(A?B)，则存在b?A?B，使得f(b)?c。由并集的定义b?A或者b?B，因此c?f(A)或者c?f(B)，于是c?f(f(A?B)?f(A)?A)?f(，B)故
。由上得证f(Bf(A?B)?f(A)?f(B)。
f(A?B)?f(A)?f(B)不成立，因为f(A?B)?f(A)?f(B)，反之不成立。
证明：设c?f(A?B)，则存在a?A?B使得f(a)?c。因为a?A且a?B，所以c?f(A)且c?f(B)，因此c?f(A)?f(B)，故f(A?B)?f(A)?f(B)。 反例如下：
设A?B?{a,b,e,d}，其中A?{a,e,d}，B?{b,e}，C?{c1,c2,c3}，函数于是：A?B?{e}，f:A?B?C定义为f(a)?f(b)?c1，f(e)?c2，f(d)?c3，
f(A?B)?{c2}，f(A)?{c1,c2,c3}，f(B)?{c1,c2}，f(A)?f(B)?{c1,c2}，这里
元素c1?f(A)?f(B)，但是c1?f(A?B)。
6. 设有函数f:A?B和g:B?C，使得g?f是一个内射，且f是满射。证明g是一个内射。举出一个例子说明，若f不是满射，则g不一定是内射。 证明：任取b1,b2?B，并设b1?b2。因为f是满射，所以必有a1,a2?A，使得
f(a1)?b1，f(a2)?b2，根据函数象的唯一性的条件，由b1?b2可得a1?a2。又
因为g是由B到C的函数，所以有c1,c2?C，使得g(b1)?c1，。于是根据复合函数的定义，得：
a)?g(1b)?， g?f(11cg?f(a2)?g(b2)?c2
因为g?f是内射，所以由a1?a2，可知c1?c2。此即g(b1)?g(b2)，故g是内射。 例子：
图3-1
精品文档
精品文档
图3-1中的例子可说明当f不是满射时，g不一定是内射。
7. 在下列函数中，确定哪些是内射，哪些是满射，哪些是双射。 (1) f1:N?Z,f1(n)?小于n的完全平方数的个数；
答：f1(2)?1,f2(3)?1，因此f1不是内射，是满射，因此不是双射。 (2) f2:R?R,f2(r)?2r?15; 答：是内射，是满射，因此是双射 (3) f3:R?R,f3(r)?r2?2r?15
答：因为f3(?5)?f3(3)?0，所以不是内射，f3(r)?(r?1)2?16。显然对于任意的r?R，f3(r)??16。因此不是满射，因此不是双射。 (4) f4:N2?N,f4(n1,n2)?n1n2
答：因为f4(4,1)?f4(2,2)?41?22?4，所以f4不是内射。
对于任意的n?N，有f4(n,1)?n1?n。即对于任意的n?N，n有像源(n,1)，所以f4是满射，但是不是双射。 (5) f5:N?R,f5(n)?log10n
答：因为n?N，所以n?1，因此log10n?0，因此不是满射。是内射(函数的单调性)。因此不是双射。
(6) f6:N?Z,f6(n)?等于或大于log10n的最小整数；
答：因为f6(3)?1,f6(4)?1，因此不是内射是满射。因此不是双射。(Z是非负整数集合)
(7)f7:(2U)2?(2U)2，f(S1,S2)?(S1?S2,S1?S2)
答：对任意S1,S2?2U,S1?S2，(S1,S2)?(S2,S1)，但是f(S1,S2)?f(S2,S1)，因此不是内射。又(?,U)?(2U)2，但是找不到S1?2U,S2?2U，使得S1?S2??，
S1?S2?U。
因此不是满射，因此也不是双射。
8. 设A,B都是有限集，#A?n,#B?m，问存在着多少个不同的内射f:A?B？存在多少个不同的双射？
答：若要使得函数f:A?B成为内射，必须满足#A?#B，即n?m，否则由Am!n?到B不可能存在内射。当n?m时，由A到B可定义Am个不同的内射。(m?n)!此即为从B的m个元素中取出n个元素的排列数。要使函数f:A?B成为双射，必须满足#A?#B，即n?m。否则，由A?B不可能存在双射。当n?m时，
m?m!个不同的双射。 由A到B可定义Am
精品文档
精品文档
9. 下列函数中，确定哪些是内射，哪些是满射，哪些是双射。
ii是偶数?2(1) f1:I?I，f1(i)??
?(i?1)/2i是奇数答：因为f1(2)?1,f1(3)?1，因此不是内射。是满射，因此不是双射。 (2) f2:Z7?Z7,f2(x)?res7(3x)
答：res7(3x)表示3x被7除后的非负余数，于是按照函数f2的定义，得：
f2(0)?0,f2(1)?3,f2(2)?6,f2(3)?2,f2(3)?5,f2(4)?5,f2(5)?1,f2(6)?4
显然f2又是内射，又是满射，因此是双射。 (3) f3:Z6?Z6,f3(x)?res6(3x)
答：f3(0)?res6(0)?0，f3(1)?res6(3)?3，f3(2)?res6(6)?0，f3(3)?res6(9)?3，
f3(4)?res6(12)?0，f3(5)?res6(15)?3。因此f3不是内射不是满射，因此也不
是双射。
10. 设A?{a1,a2,,an}，试证明任何从A到A的函数，如果它是内射，则它必
是满射，反之亦真。
答：反证法。已知f:A?A是内射，假设f不是满射，则在A中至少有一个元素没有像源，即集合A中的元素至多只有n?1个像。但是#(A)?n，因此A中至少有两个元素对应同一个像，这与f是内射相矛盾。
反之，已知f:A?A是满射，假设f不是内射，则A中至少有两个元素对应同一个像，即A在A中至多有n?1个像，这与f是满射矛盾，所以f是内射。
11. 设有函数f:A?B，定义函数g:B?2A，使得： g(b)?{x|x?A,f(x?) b试证明如果f是满射，则g是内射；其逆成立吗？
答：设b1,b2?B，b1?b2，因为f是满射，存在x?A，使得f(x)?b1?b2，因此
x?g(b1)，x?g(b2)，因此g(b1)?g(b2)，因此g是内射。其逆不成立。因为当g是内射时，可能有一个元素b，使g(b)??，这意味着元素b?B在A中没有像源，因此f不是满射。举例如下：A?{a1,a2,a3},B?{b1,b2,b3}，函数f和g的定义如下，此时g是内射，但是f不是满射。
精品文档