哈工大《离散数学》教科书习题答案 下载本文

所以假设不成立。 也可以用如下方法:

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