川大离散数学习题6

习题6 1. 设A={1，2，3，4}，B=A×A。确定下述集合是否为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,n2 N,0<2n1-n2<5}。 (2) {(n1,n2)|n1,n2 N,n2是n1的正因子个数}。 (3) {(S1,S2)|S1,S2 {a,b,c,d}且S1 S2=?}。 (4) {(a,b)|a,b N,gcd(a,b)=3}. (5) {(x,y)|x,y Z,y=x2}. 解： (1) {(n1,n2)|n1, n2 N, 0<2 n1-n2<5} 不是函数，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）表示出A B，A B，A-B， 以及A B对应的特征函数。 解：（略） 4. 试确定在含n个元素的集合上可以定义多少个二元关系，其中有多少个是全函数。 解:  可以定义nn个二元关系，n！个全函数 5. 设 ，： 。 证明：bf(A)-f(C)bf(A) bf(C) (x)[xA xC f(x)=b] (x)[xA-C f(x)=b] bf(A-C) 所以f(A)-f(C)f(A-C) 7. 设f：X Y，A和B是X的子集。 证明， 证明： （1）y∈f(A∪B) (x)[x∈(A∪B)∧f(x)=y] (x)[x∈A ∧ f(x)=y]∪(x)[x∈∪B ∧ f(x)=y] y∈f(A)∪y∈f(B) ∴f(A∪B)=f(A)∪f(B) （2）y∈f(A∩B) (x)[x∈(A∩B)∧f(x)=y] (x)[x∈A∧f(x)=y]∩(x)[x∈B∧f(x)=y] y∈f(A)∩y∈f(B) ∴f(A∩B)f(A)∩f(B) 8. 确定下例映射是否单射、满射或双射： （1） f1:N R,f1(n)= n. （2） f2:N N,f2(n)为不超过n的素数数目。 （3） f3:N N N,f3(n,n)=(n+1). （4） f4:R R,f4(x)=x2+2x-15. （5） f5:Z Z,f5(x)=1+2x3. （6） A是集合，f6:2A 2A 2A 2A,f6(x,y)=(x y,x y). （7） f7:R R R,f7(x,y)=x+y.  F8:R R R,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)非单: ({a}{b}, {a}{b}) = ({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：X X。证明： (1)如果f是单射时，f必是双射。 (2)如果f是满射时，f必是双射。 证明： (1).当f是单射时，根据单射定义，对所有任意t,s∈X,当t≠s时f(t)≠f(s),则f(x)中的元素个数与X中的元素个数相同； 又∵f:X→X，所以，f(x)是一个满射 ∴f必是双射。 (2)当f是满射时，根据满射定义及f的定义，对所有y∈X，都存在x∈X，使f(x)=y，再根据函数的单值性，对所有t,s∈X,当t≠s时，f(t)≠f(s)。 ∴f必是双射。 10. 设f是有限集X上的一个函数，满足 x X，f2（x）=x。证明：f是双射。 证明： 设x,y是有限集X上的2个元素，如果f(x)=f(y),则x= f2(x)= f2(y)= y ，说明是单射，由上题结果知f是双射。 11.设f:A B，g：B 2A，满足 b B，g（b）={x A|f(x)=b}.证明：当f为满射时g为单射。问g为单射时，f是否必是满射？ 证： 1）对任意b1、b2∈B，且b1≠b2。 ∵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：R R，这里f(x)=2x，g(x)=x2+x-1，h(x)=x-2。写出f g，g f h，h h g。 解：f g=f(g(x)) =2x2+2x-2 g f h= (g(f(h(x))) = 4(x-2)2+2(x-2)-1 h h g= (h(h(g(x))) = x2+x-5 14. 设f，g，h都是集合A上的函数。如果f=g，是否必有h f=h g或f h=g h？ 解： （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))，而此种情况下f≠g 综上，当h。f=h。g时，f不一定等于g 15. 设f，g是实数集R上的函数，其中f(x)=x2+2，g(x)=2x-1。确定f g和g f是否满射、单射或双射？ 解：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) 当g f为单射时，f必为单射； (2) 当g f为满射时，g必为满射； (3) 当g f为双射时，g为满射，f为单射。 证明：设 f: A→B, g: B→C。 （1）（反证法）设f不是单射，存在x1≠x2∈A,且f(x1)=f(x2)， 即：g f(x1)= g(f(x1))= g(f(x2))= g f(x2),与g f为单射矛盾。因此，f必为单射。 （2）对于任意z∈C，由于g f为满射，那么存在x∈A使得g f(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、n∈N ∧ m n}. 证明：（思路：想构造一个双射函数即可） （1）f(x)=2tan( ) (2）（略） (3)f(x)= (4)(略) 20.设A～B，C～D。证明：A C～B D。 证明：（略） 21.证明：非空有限集A与可数集B的笛卡尔积A B也是可数集。 证明：非空有限集A与可数集B的笛卡尔积A×B也是可数集。 证明：设A={a1,a2,…,an｝ B={b1,b2,…,bn,…} 令Bi ={(ai,b1),(ai,b2),…,(ai,bn),…} (i≤n),则 A×B=        , 因为B为可数集，所以Bi为可数集。A×B为有限个可数集的并集。下面用归纳法证明有限个(m个)可数集的并集为可数集。 设Cm={cm1,cm2, …,cmn, …} 当m=2时， 构造双射f:N→C1∪C2, 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(k≥3)时结论成立，即k-1个可数集的并集为可数集，记为D。 则m=k时，可以构造类似的双射g:N→D∪Ck,所以为可数集。因而有限个可数集的并集为可数集。所以A×B是可数集。 补充： 1.  设 和 是两个有限集合，它们的元数都是 ，则 是单射的充分必要条件是 为满射 证  必要性，当 是单射时， 的元数是 ，而 的元数也是 ，故 ，因此 是满射。 充分性，若 为满射时，有 ，则 的元数为 ， 的元数也是 ， 个原象对应 个象，即不同元素对应不同的象，因此 是 到 的单射。 2．设 为实数集， 试证明 和 都是满射，而不是单射。 证  对于任意 ，可以使 成立的 有无数对，且 ，也就是说值域 中每个元素都有无数原象在 中，所以 是满射，而不是单射。