离散数学第二版邓辉文编著第一章第二节习题答案
- 格式：doc
- 大小：18.00 KB
- 文档页数：7
离散数学第二版邓辉文编著第一章第二节习题
答案
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 )
=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) =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 =(y1)
3⎡+1=(y1存在，由第3题知f f =f =f I A ，所以-1-1于是利用定理7有(f f )
f =(f f )
I A ，f1 (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 )
=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 =I A 且g f =I
B ，试证明: f 是双射且f1-1存在、因为f g =I A ，于是f1 I
A 、 f )
g =f1，所以有f1=g1、-1-1证根据定理4(1)(2)知，f g 是双射、下证(f g )
=g f1 f1)
f1=f f1 f1 (f1 I B g =g1=g1-1、∈G 且f f1 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个元素分成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 (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 中元素的任意一个排列均
可得到一个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 =I
A ，g h f =I
B ，h f g =I
C ，则f , g , h 均可逆，并求出f1, h1=g h 且h1=h f 、
14、已知Ackermann 函数A :N ⨯N →N 的定义为(1)A (0, n )
=n +1, n ≥0;(2)A (m , 0)
=A (m1, 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)
=3+1=4，由此可进一步得出A (1, n ) =n +2，A (2, 0)
=A (1,1)
=3，A (2,1)
=A (1, A (2, 0))
=A (1,3)
=3+2=5，A (2,2)
=A (1, A (2,1))
=A (1,5)
=5+2=7， A (2,3)
=A (1, A (2,2))
=A (1,7)
=7+2=9、因此有A (2, n )
=2n +3，A (3, 0)
=A (2,1)
=2⋅1+3=5，A (3,1) =A (2, A (3, 0))
=A (2,5)
=2⋅5+3=13， A (3,2) =A (2, A (2,2))
=A (2,13)
=2⋅13+3=
29、所以有A (2,3) =9, A (3,2)
=
29、。
