《离散数学第二版邓辉文编著第一章第二节习题答案》由会员分享，可在线阅读，更多相关《离散数学第二版邓辉文编著第一章第二节习题答案（7页珍藏版）》请在金锄头文库上搜索。
1、离散数学第二版邓辉文编著第一章第二节习题答案1.2 映射的有关概念习题1.21. 分别计算1. 5，-1，-1. 5，1. 5，-1，-1. 5.解 1. 5=2，-1=-1，-1. 5=-1，1. 5=1，-1=-1，-1. 5=-2.2. 下列映射中，那些是双射? 说明理由.(1)f :Z Z , f (x ) =3x .(2)f :Z N , f (x ) =|x |+1.(3)f :R R , f (x ) =x 3+1.(4)f :N N N , f (x 1, x 2) =x 1+x 2+1.(5)f :N N N , f (x ) =(x , x +1).解 (1)对于任意对x
2、1, x 2Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x Z ，f (x ) 2Z ，因此f 不是满射，进而f 不是双射.(2)由于2, -2Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0N ，而任意x Z 均有f (x ) =|x |+10，于是f 不是满射. 显然，f 不是双射.(3)对于任意对x 1, x 2R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y R ，取x =(y -1) ，这时13f (x ) =x +1=(y
3、-1) 3+1=(y -1) +1=y ，33313所以f 是满射. 进而f 是双射.(4)由于(1, 2), (2, 1) N N 且(1, 2) (2, 1) ，而f (1, 2) =f (2, 1) =4，因此f 不是单射. 又由于0N ，而任意(x 1, x 2) N N 均有f (x 1, x 2) =x 1+x 2+10，于是f 不是满射. 显然，f 就不是双射.(5)由于x 1, x 2N ，若f (x 1) =f (x 2) ，则(x 1, x 1+1) =(x 2, x 2+1) ，于是x 1=x 2，因此f 是单射. 又由于(0, 0) N N ，而任意x N 均有f (x
4、 ) =(x , x +1) (0, 0) ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.3. 对于有限集合A 和B ，假定f :A B 且|A |=|B |，证明: f 是单射的充要条件是f 是满射. 对于无限集合，上述结论成立吗？举例说明.证() 因为f 是单射，所以|A |=|f (A ) |. 由于|A |=|B |，所以|f (A ) |=|B |. 又因为B 有限且f (A ) B ，故f (A ) =B ，即f 是满射.() 若f 是满射，则f (A ) =B . 由于|A |=|B |，于是|A |=|f (A ) |. 又因为A 和B 是有限集合，因此f 是单射.
5、对于无限集合，上述结论不成立. 例如f :N N ，f (x ) =2x ，f 是单射，但f 不是满射.4. 设f :A B , 试证明:(1)f I B =f .(2)I A f =f .特别地，若f :A A ，则f I A =I A f =f .证 (1)对于任意x A ，由于f (x ) B ，所以(f I B )(x ) =I B (f (x ) =f (x ) ，因此f I B =f .(2)对于任意x A ，由于I A (x ) =x ，所以(I A f )(x ) =f (I A (x ) =f (x ) ，于是有I A f =f .由(1)和(2)知，若f :A A ，则f
6、I A =I A f =f .5. 试举出一个例子说明f f =f 成立，其中f :A A 且f I A . 若f 的逆映射存在，满足条件的f 还存在吗?解 令A =a , b , c ，f (a ) =f (b ) =f (c ) =a ，即对于任意x A ，f (x ) =a ，显然f :A A 且f I A . 而对于任意x A ，有(f f )(x ) =f (f (x ) =f (a ) =a ，因此f f =f .若f f =f 且f 的逆映射f -1存在，由第3题知f f =f =f I A ，所以-1-1于是利用定理7有(f f ) f =(f f ) I A ，f -1 (f
7、 f ) =f -1 (f I A ) ，进而I A f =I A I A ，因此f =I A . 所以若f 的逆映射存在，满足条件的f 不存在.6. 设f :A B , g :B C . 若f 和g 是满射，则f g 是满射，试证明.证 因为f 是满射，所以f (A ) =B . 又因为g 是满射，所以g (B ) =C . 于是(f g )(A ) =g (f (A ) =g (B ) =C ，因此f g 是A 到C 的满射.另证 对于任意z C ，因为g 是满射，于是存在y B 使得g (y ) =z . 又因为f 是满射，存在x A 使得f (x ) =y . 因此，(f g )(x
8、) =g (f (x ) =g (y ) =z ，所以f g 是A 到C 的满射.7. 设f :A B , g :B C . 试证明: 若f g 是单射，则f 是单射. 试举例说明，这时g 不一定是单射.证 对于任意x 1, x 2A ，假定f (x 1) =f (x 2) ，则显然g (f (x 1) =g (f (x 2) ，即(f g )(x 1) =(f g )(x 2) . 因为f g 是单射，所以x 1=x 2，于是f 是单射.例如A =a , b ，B =1, 2, 3，C =, , , ，令f (a ) =1, f (b ) =2，g (1) =, g (2) =, g (3)
9、 =，则显然有(f g )(a ) =g (f (a ) =g (1) =, (f g )(b ) =g (f (b ) =g (2) =, 于是f g 是A 到C 的单射，但g 显然不是单射.8. 设f :A B , 若存在g :B A ，使得f g =I A 且g f =I B ，试证明: f 是双射且f -1=g .证 因为f g =I A ，而I A 是单射，所以f 是单射. 又因为g f =I B ，而I B 是满射，所以f 是满射. 因此f 是双射.由于f 是双射，所以f而(f -1-1存在. 因为f g =I A ，于是f -1 (f g ) =f -1 I A . f ) g
10、=f -1 I A 且I B g =f -1，所以有f -1=g .9. 设f :A B , g :B C . 若f 和g 是双射，则f g 是双射且(f g ) -1=g -1 f -1.-1-1证 根据定理4(1)(2)知，f g 是双射. 下证(f g ) =g f -1. 因为(f g ) (g -1 f -1) =f (g g -1) f -1=f I B f -1=f f -1=I A ， (g -1 f -1) (f g ) =g -1 (f -1 f ) g =g -1 I B g =g -1 g =I C ， 在上面的推导中多次利用了定理7. 由第7题知，(f g ) -1=
11、g -1 f10. 设G 是集合A 到A 的所有双射组成的集合，证明(1)任意f , g G ，有f g G .(2)对于任意f , g , h G ，有(f g ) h =f (g h ).(3)I A G 且对于任意f G ，有I A f =f I A =f .(4)对于任意f G ，有f -1-1. G 且f f -1=f -1 f =I A .证 (1)由定理5.(2)由定理7.(3)由第3题.(4)由定理4.11. 若A = a , b , c , B = 1, 2, 问A 到B 的满射、单射、双射各有多少个? 试推广你的结论.解 将A 中的3个元素对应到B 中的2个元素，相当于将3
12、个元素分成2部分，共有3种分法; 在计算A 到B 的满射个数时还需要将B 中元素进行排列，共有2种排列方式，于是A 到B 的满射共有32=6个(请自己分别写出A 到B 的6个满射).由于|A |=3, |B |=2，所以A 到B 的单射没有，进而A 到B 的双射也没有. 假设|A |=m , |B |=n .(1) A到B 的满射 若m (2) A到B 的单射 若m n ，不存在单射；若m n ，由于B 中任意选取m 个m 元素，再将其进行全排列都得到A 到B 的单射，故A 到B 的单射共有C n m ! 个.(3)A 到B 的双射 若m n ，不存在双射；若m =n ，此时B 中元素的任意一
13、个排列均可得到一个A 到B 的双射，因此A 到B 的双射共有m ! 个.12. 设A , B , C , D 是任意集合，f 是A 到B 的双射， g 是C 到D 的双射，令h :A C B D ，对任意(a , c ) A C , h (a , c ) =(f (a ), g (c ). 证明:h 是双射.证 对于任意(a 1, c 1) A C ，(a 2, c 2) A C ，假定h (a 1, c 1) =h (a 2, c 2) ，即(f (a 1), g (c 1) =(f (a 2), g (c 2) ，于是f (a 1) =f (a 2) 且g (c 1) =g (c 2) ，
14、根据已知条件有a 1=a 2且c 1=c 2，进而(a 1, c 1) =(a 2, c 2) ，因此h 是单射.任意(b , d ) B D ，则b B , d D ，由于f 是A 到B 的双射且g 是C 到D 的双射，于是存在a A , c C 使得f (a ) =b , g (c ) =d ，因此h (a , c ) =(f (a ), g (c ) =(b , d ) ，所以h 是满射.故h 是双射.13. 设f :A B , g :B C , h :C A ，若f g h =I A ，g h f =I B ，h f g =I C ，则f , g , h 均可逆，并求出f -1, g
15、-1, h -1.证 因为恒等映射是双射，多次使用定理6即可得结论.由于f g h =I A ，所以f 是单射且h 是满射. 由于g h f =I B ，所以g 是单射且f 是满射. 由于h f g =I C ，所以h 是单射且g 是满射. 于是f , g , h 是双射，因此f , g , h 均可逆.由于f g h =I A ，所以f -1=g h 且h -1=f g ，进而g -1=h f .14. 已知Ackermann 函数A :N N N 的定义为(1)A (0, n ) =n +1, n 0;(2)A (m , 0) =A (m -1, 1), m 0;(3)A (m , n ) =A (m -1, A (m , n -1), m 0, n 0.分别计算A (2, 3) 和A (3, 2) .解 由已知条件有A (0, 1) =2，A (1, 0) =A (0, 1) =2，于是A (1, 1) =A (0, A (1, 0) =A (0, 2) =2+1=3，A (1, 2) =A (0, A (1, 1) =A (0, 3)
