发布时间 : 星期二 文章哈工大《离散数学》教科书习题答案更新完毕开始阅读
?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