离散数学第二版邓辉文编著第一章第二节习题答案

离散数学第二版邓辉文编著第一章第二节习题答案

1.2 映射的有关概念

习题1.2

1. 分别计算 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) x3 1.

(4)f:N N N,f(x1,x2) x1 x2 1.

(5)f:N N N,f(x) (x,x 1).

解 (1)对于任意对x1,x2 Z，若f(x1) f(x2)，则3x1 3x2，于是x1 x2，所以f是单射. 由于对任意x Z，f(x) 2 Z，因此f不是满射，进而f不是双射.

(2)由于2, 2 Z且f(2) f( 2) 3，因此f不是单射. 又由于0 N，而任意x Z均有f(x) |x| 1 0，于是f不是满射. 显然，f不是双射.

(3)对于任意对x1,x2 R，若f(x1) f(x2)，则x1 1 x2 1，于是x1 x2，所以f是单射. 对于任意y R，取x (y 1)，这时

1 3f(x) x 1 (y 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不是单射. 又由于0 N，而任意(x1,x2) N N均有f(x1,x2) x1 x2 1 0，于是f不是满射. 显然，f就不是双射.

(5)由于x1,x2 N，若f(x1) f(x2)，则(x1,x1 1) (x2,x2 1)，于是x1 x2，因此f是单射. 又由于(0,0) N N，而任意x N均有f(x) (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是单射.

对于无限集合，上述结论不成立. 例如f:N N，f(x) 2x，f是单射，但f不是满射.

4.设f:A B,试证明:

(1)f IB f.

(2)IA f f.

特别地，若f:A A，则f IA IA f f.

证 (1)对于任意x A，由于f(x) B，所以(f IB)(x) IB(f(x)) f(x)，因此f IB f.

(2)对于任意x A，由于IA(x) x，所以(IA f)(x) f(IA(x)) f(x)，于是有IA f f.

由(1)和(2)知，若f:A A，则f IA IA f f.

5.试举出一个例子说明f f f成立，其中f:A A且f IA. 若f的逆映射存在，满足条件的f还存在吗?

解 令A {a,b,c}，f(a) f(b) f(c) a，即对于任意x A，f(x) a，显然f:A A且f IA. 而对于任意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 IA，所以

1 1于是利用定理7有(f f) f (f f) IA，f 1 (f f) f 1 (f IA)，

离散数学第二版邓辉文编著第一章第二节习题答案

进而IA f IA IA，因此f IA. 所以若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) g(f(x)) g(y) z，所以f g是A到C的满射.

7.设f:A B,g:B C. 试证明: 若f g是单射，则f是单射. 试举例说明，这时g不一定是单射.

证 对于任意x1,x2 A，假定f(x1) f(x2)，则显然g(f(x1)) g(f(x2))，即(f g)(x1) (f g)(x2). 因为f g是单射，所以x1 x2，于是f是单射.

例如A {a,b}，B {1,2,3}，C { , , , }，令f(a) 1,f(b) 2，g(1) ,g(2) ,g(3) ，则显然有(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 IA且g f IB，试证明: f是双射且f 1 g.

证 因为f g IA，而IA是单射，所以f是单射. 又因为g f IB，而IB是满射，所以f是满射. 因此f是双射.

由于f是双射，所以f

而(f 1 1存在. 因为f g IA，于是f 1 (f g) f 1 IA. f) g f 1 IA且IB 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 IB f 1 f f 1 IA， (g 1 f 1) (f g) g 1 (f 1 f) g g 1 IB g g 1 g IC， 在上面的推导中多次利用了定理7. 由第7题知，(f g) 1 g 1 f

10.设G是集合A到A的所有双射组成的集合，证明

(1)任意f,g G，有f g G.

(2)对于任意f,g,h G，有(f g) h f (g h).

(3)IA G且对于任意f G，有IA f f IA f.

(4)对于任意f G，有f 1 1. G且f f 1 f 1 f IA.

证 (1)由定理5.

(2)由定理7.

(3)由第3题.

(4)由定理4.

11.若A = {a, b, c}, B = {1, 2}, 问A到B的满射、单射、双射各有多少个? 试推广你的结论.

解 将A中的3个元素对应到B中的2个元素，相当于将3个元素分成2部分，共有3种分法; 在计算A到B的满射个数时还需要将B中元素进行排列，共有2种排列方式，于是A到B的满射共有3 2 6个(请自己分别写出A到B的6个满射).

由于|A| 3,|B| 2，所以A到B的单射没有，进而A到B的双射也没有. 假设|A| m,|B| n.

(1) A到B的满射 若m n，不存在满射；若m n，先将m个元素划分成n个块(参见1.5节)，共有S(m,n)种方式；再将B中元素进行全排列，共有n!种方式，于是A到B的满射共有S(m,n) n!个.

(2) A到B的单射 若m n，不存在单射；若m n，由于B中任意选取m个

m元素，再将其进行全排列都得到A到B的单射，故A到B的单射共有Cn m!个.

(3)A到B的双射 若m n，不存在双射；若m n，此时B中元素的任意一个排列均可得到一个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是双射.

证 对于任意(a1,c1) A C，(a2,c2) A C，假定h(a1,c1) h(a2,c2)，即(f(a1),g(c1)) (f(a2),g(c2))，于是f(a1) f(a2)且g(c1) g(c2)，根据

离散数学第二版邓辉文编著第一章第二节习题答案

已知条件有a1 a2且c1 c2，进而(a1,c1) (a2,c2)，因此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 IA，g h f IB，h f g IC，则f,g,h均可逆，并求出f 1,g 1,h 1.

证 因为恒等映射是双射，多次使用定理6即可得结论.

由于f g h IA，所以f是单射且h是满射. 由于g h f IB，所以g是单射且f是满射. 由于h f g IC，所以h是单射且g是满射. 于是f,g,h是双射，因此f,g,h均可逆.

由于f g h IA，所以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( …… 此处隐藏：2999字，全部文档内容请下载后查看。喜欢就下载吧 ……