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

?n??n?个为奇数,一个为偶数。而n为奇数,故奇数个数为???1比偶数??多一个,

?2??2?这是不可能的。

P46习题

1.设f:X?Y,C,D?Y,证明f?1(C\\D)?f?1(C)\\f?1(D)

证1:?x?f?1(C\\D),则f(x)?C\\D,即f(x)?C但f(x)?D。于是

x?f?1(C)但x?f?1(D),因此x?f?1(C)\\f?1(D), 故f?1(C\\D)?f?1(C)\\f?1(D)

反之,设x?f?1(C)\\f?1(D),有x?f?1(C)且x?f?1(D) 因此f(x)?C且f(x)?D,即f(x)?C\\D 从而x?f?1(C\\D)

故f?1(C)\\f?1(D)?f?1(C\\D)

因而f?1(C\\D)?f?1(C)\\f?1(D)

证2:f?1(C\\D)?f?1(C?Dc)?f?1(C)?f?1(DC)

?f?1(C)?(f?1(D))C?f?1(C)\\f?1(D)

2. 设f:X?Y, A,B?X,证明

(1)f(A?B)?f(A)?f(B) (2)f(A?B)?f(A)?f(B) (3)f(A)\\f(B)?f(A\\B)

证:(1)设y?f(A?B),则?x?A?B使得y?f(x)。于是,x?A或x?B。因此,y?f(A)或y?f(B),所以y?f(A)?f(B),故

f(A?B)?f(A)?f(B)

21

反之,设y?f(A)?f(B),则y?f(A)或y?f(B)。于是?x?A或x?B,使得f(x)?y。因此不论何种情况都?x?A?B,使得f(x)?y。因此y?f(A?B),故

f(A)?f(B)?f(A?B)

因此,f(A)?f(B)?f(A)?(B)

(2)设y?f(A?B),则?x?A?B,使得y?f(x)。于是,x?A且x?B。 从而,y?f(A)且y?f(B),所以y?f(A)?f(B),故

f(A?B)?f(A)?f(B)

(3)设y?f(A)\\f(B),则y?f(A)但y?f(B)。于是?x?A使得f(x)?y,且x?B,从而?x?A\\B,使得f(x)?y。

故y?f(x)?f(A\\B),即

f(A)\\f(B)?f(A\\B)。

3.设f:X?Y,A?X,B?Y,证明:

f(f?1(B)?A)?B?f(A)

证:设y?f(f?1(B)?A),则?x?f?1(B)?A,使得f(x)?y。于是x?f?1(B)且x?A,即f(x)?B且f(x)?f(A),因此y?f(x)?B且y?f(A),即

y?B?f(A),从而

f(f?1(B)?A)?B?f(A)。

反之,设y?B?f(A),则y?B且y?f(A)。于是?x?A且x?f?1(B),使得f(x)?y。从而?x?f?1(B)?A,使得f(x)?y,因此y?f(f?1(B)?A)。从而

B?f(A)?f(f?1(B?A)) 因此,f(f?1(B?A))?B?f(A)。

4.设f:X?Y,A?X,B?Y。以下四个小题中,每个小题均有四个命题,这四个

22

命题有且仅有一个正确,请找出正确的那个。

(1)(a)若f(x)?f(A),则x未必在A中 (b)若f(x)?f(A),则x?A (c)若f(x)?f(A),则x?A

(d)若f(x)?f(A),则x?Ac

(2)(a)f(f?1(B))?B (b)f(f?1(B))?B

(c)f(f?1(B))?B (d)f(f?1(B))?Bc (3)(a)f?1(f(A))?A (b)f?1(f(A))?A

(c)f?1(f(A))?A (d)上面三个均不对 (4)(a)f(A)?? (b)f(B)??

(c)若y?Y,则f?1(y)?x (d)若y?Y,则f?1(y)?x 答案:(a)(b)(c)(d)

7.设f:X?Y,A?X,则(f(A))c?f(Ac)成立吗?

解:不成立。

反例:设X?{1,2,3},Y?{a,b,c}。

f:X?Y,f(1)?a,f(2)?a,f(3)?b。

1 o 2 o o a o b o c X Y 令A?{1,2},则Ac?{3}。

f(A)?{a},(f((A))?{b,c},但f(A)?b。

cc3 o 8.设X是一个无穷集合,f:X?Y。证明:存在X的一个真子集E使得f(E)?E。

证:取x0?X,令x1?f(x0),x2?f(x1),?,xn?f(xn?1),?。若到某一位与前面有重复项,设为第k项,即f(xk)?xi(i?k)。令E?{x0,x1,x2,?,xk}?X,则

f(E)?E且E?X。

若xi互不相同,令E1?X\\{x0}?X,则f(E1)?E1。 [不去掉x0可能就会有E1?X]

23

9.设f:A?B,证明?T?2B,都有f(f?1(T))?T?f(A)

证;若T??,则f(f?1(T))??,T?f(A)??,因而f(f?1(T))?T?f(A)。 若T??,设y?f(f?1(T)),则?x?f?1(T),使得f(x)?y且x?A,于是

y?f(x)?T且y?f(x)?f(A),因此y?T?f(A)。

故f(f?1(T))?T?f(A)

反之,设y?T?f(A),则y?T且y?f(A)。于是?x?f?1(T)且x?A,使得f(x)?y。从而,f(x)?f(f?(T)且f(x)?f(A),因此y?f(x)?f(f?1(T)?A)),而f?1(T)?A,所以f(f?1(T)?f(A),于是y?f(f?1(T)),故

T?f(A)?f(f?1(T))

从而T?f(A)?f(f?1(T))

P50习题

1.设X?{a,b,c},Y?{0,1},Z?{2,3},f:X?Y,f(a)?f(b)?0,

f(c)?1;g:Y??,g(0)?2,g(1)?3,试求g?f。

解:

g?f(a)?g(0)?2g?f(b)?g(0)?2 g?f(c)?g(1)?3因此g?f:X?Z,g?f(a)?2,g?f(b)?2,g?f(c)?3。

2.设X,Y,Z是三个非空集合,Z?2。证明:f:X?Y是满射当且仅当不存在从Y到Z的映射g1和g2,使得g1?g2,但g1?f?g2?f。

证:?因f:X?Y且f为满射,故?y?Y,?x?X,使得f(x)?y。 假设存在g1,g2,g1?g2,但g1?f?g2?f。因为g1?g2,所以?y0?Y,使得对于上面的y0,?x0?X(f是满射),使得g1(f(x0))?g2(f(x0)) g1(y0)?g2(y0)。

[g1(y0)?g2(y0)],即g1f(x0)?g2f(x0)。故g1?f?g2?f与g1?f?g2?f,矛盾。

24