发布时间 : 星期一 文章哈工大《离散数学》教科书习题答案更新完毕开始阅读
所以假设不成立。 也可以用如下方法：
f满射?f右可逆??h:Y?X，使得f?h?IY?假设g1?f?g2?f得到
g1?g2，命题得证。
?f:X?Y，假设f不是满射，则?y0?Y，使得?x?X,f(x)?y0。构造两个映射g1,g2:Y?Z，
当y?y0时，g1(y0)?g2(y0)； 当y?y0时，g1(y)?g2(y)。 因为Z?2，故此时g1?g2，但
?x?X,g1?f(x)?g1(y?y0)?g2(y?y0)?g2?f(x)
即g1?f＝g2?f，与假设不存在g1?g2，但g1?f?g2?f矛盾，故f一定是满射。 3.设X,Y,Z是三个非空的集合，X?2，证明：f:X?Y是单射当且仅当不存在从Z到X的映射g1,g2，使得g1?g2，但f?g1?f?g2。
证：?f是单射，则?x1,x2,x1?x2，有f(x1)?f(x2)。假设存在g1和g2：
Z?X,g1?g2，因为X?2，于是?z0?Z，使得g1(z0)?g2(z0)。
而由于f为单射，故f(g，，故?f(g)即f?g?g1(z0))2(z0)1(z0)?f2(z0)f?g1?f?g2矛盾。
可以用：f单射?f左可逆的??h使得hf?IX?由f?g1?f?g2?g1?g2得证。
逆否命题：g1?g2?fg1?fg2。
则?x1,x2?X,x1?x2，但f(x1)?f(x2)。构造两个映射g1?假设f不是单射，
和g2:Z?X,?z?Z,令g1(z)?x1,g2(z)?x2，由于X?2，故若x1?x2，则有
g1?g2。但?z?Z,f?g1(z)?f(x1)?f(x2)?f?g2(z)，于是有f?g1?f?g2矛盾。
25
P55习题
1. 设N?{1,2,3,?}，试构造两个映射f和g：N?N，使得
（1）fg?IN，但gf?IN； （2）gf?IN，但fg?IN。
解：（1）fg?IN但gf?IN，故f是满射，但f不是单射。于是令：
f:N?N,f(1)?1,f(n)?n?1,n?2，g:N?N,?n?N,g(n)?n?1，则
fg?IN但gf?IN。事实上，当n＝1时，gf(1)?g(f(1))?g(1)?2，故gf?IN。
（2）自己做。 2.设f:X?Y则
（1）若存在唯一的一个映射g:Y?X，使得gf?IX，则f是可逆的吗？ （2）若存在唯一的一个映射g:Y?X，使得fg?IY，则f是可逆的吗？ 答案：（1）f不一定可逆。 当X?1时，f不一定可逆。 当X?2时，f可逆。 （2）f一定可逆。
证：由fg?IY，得f是单射。假设f不是满射，则g不唯一，矛盾。 3.设f:X?Y,X?m,Y?n，则
（1）若f是左可逆的，则f有多少个左逆映射？ （2）若f是右可逆的，则f有多少个右逆映射？ 解：令X?(x1,x2,?,xm),Y?(y1,y2,?,yn)，则 （1）如图1(a)所示：有mn?m；（2）如图1(b)所示：有
f?1(y1)?f?1(y2)???f?1(yn)。
26
x1x2x3xmy1y2y3ymn-m个y1y2y3yn（a） (b)
图1
5. 是否有一个从X到X的一一对应f，使得f?f?1，但f?IX？ 解：存在。f为对换即可。
P63习题
?12345??12345??1?11.设?1???，?2＝??，求?1?2,?2?1,?1,?2。
?43215??32514?解：
?12345??12345??1?2???,?2?1???15234???23541??1?1???12345??1?12345??,?2???43215???42153?
?123456789?2.将置换??分解成对换的乘积。
?791652348??123456789?解： ????173??29846?
791652348??=(1 7)(1 3)(2 9)(2 8)(2 4)(2 6)
3.设?是任一n次置换，试证：?与??1的奇偶性相同。
证：假设?与??1的奇偶性不同，不妨设?为奇置换，??1为偶置换。因为
???1?I（I为恒等置换），又I?(ij)(ij)，因而I是偶置换。
??1是奇置换与I是偶置换矛盾。 而??因而假设不成立，故?与??1奇偶性相同。
27
5.任一偶置换均可被分解成3－循环置换（123），（124）…（12n）中若干之乘积。
证：?i,j,s,t?{1,2,?,n}, i?j,s?t
(ij)(st)?(1i)(1j)(1i)(2s)(2t)(2s)?(1i)(1j)(2s)(1j)(2t)(2s)
?(1i)(2s)(1j)(2t)(1i)(2s)
?(12s)(12i)(12t)(12j)(1 2 s)(1 2 i)
?12s??12i??12si?因为(12s)(12i)?????????(1i)(2s)
2s12i1is21???????12t??12(12t)(12j)?????2t1??2j因此本题得证。 6. 证明下列置换等式
（1）(ac1?chbd1?dk)(ab)?(ac1?ch)(bd1?dk)
j??12tj??????(1j)(2t) 1??jt21??ac1c2?chbd1?dk?证：(ac1?chbd1?dk)(ab)???(ab)
?c1c2c3?bd1d2?a??ac1c2?chbd1?dk?＝??
ccc?add?b12?123??(ac1?ch)(bd1?dk)
?ac1?chbd1?dk?（2）(ac1?ch)(bd1?dk)(ab)???(ab)
?c1c2?ad1d2?b??ac1?chbd1?dk?????(ac1?chbd1?dk) cc?bdd?a?1212?8.在所有的n次置换中，有多少个n—循环置换？
?ii?in?解：(i1,i2,?,in)??12?
?i2i3?i1?对i1，有n种选择 对i2，有（n-1）种选择 ??
对in有1种选择
28