离散数学第二版邓辉文编著第一章第五节习题答案

1.5集合的划分与覆盖习题1.51.设},,,{d c b a A =，求出集合A 的所有不同的划分.解 可以按照划分的块的数目依次求出A 的所有不同的划分共15个. 仅一个划分块:}},,,{{1d c b a =π.有两个划分块: }},,{},{{2d c b a =π，}},,{},{{3d c a b =π，}},,{},{{4d b a c =π，}},,{},{{5c b a d =π；}},{},,{{6d c b a =π，}},{},,{{7d b c a =π，}},{},,{{8c b d a =π. 有三个划分块: }},{},{},{{9d c b a =π，}},{},{},{{10d b c a =π，}},{},{},{{11c b d a =π，}},{},{},{{12d a c b =π，}},{},{},{{13c a d b =π，}},{},{},{{14b a d c =π.有四个划分块: }}{},{},{},{{15d c b a =π.2.对于整数集合Z ，令}Z |3{1∈=k k A ，}Z |13{2∈+=k k A ，}Z |23{3∈+=k k A , 则},,{321A A A 是Z 的划分. 试验证之.解 因为(1)≠i A ∅，3,2,1=i .(2)=⋂j i A A ∅，3,2,1,,=≠j i j i .(3)=⋃⋃321A A A Z.所以，},,{321A A A 是Z 的划分.3.设}|{I i A i ∈=π是集合A 的一种划分，对于集合B ，所有≠⋂B A i ∅的B A i ⋂组成的集合是B A ⋂的划分. 试证明之.证 对于任意j i ≠，因为=⋂j i A A ∅，于是=⋂⋂=⋂⋂⋂B A A B A B A j i j i )()(∅=⋂B ∅.又因为A AI i i =∈ ，所以B A B A B A Ii iI i i ⋂=⋂=⋂∈∈ )(. 故≠⋂⋂B A B A i i |{∅},I i ∈是B A ⋂的划分.4.设集合A 有两种划分}|{1I i A i ∈=π和}|{2J j B j ∈=π，问21ππ⋃是否必是A 的划分，为什么？21ππ-呢?解21ππ⋃及21ππ-均不一定是A 的划分. 例如},,,{d c b a A =，取A 的划分为 }},,{},{{1d c b a =π，}},{},{},{{2c b d a =π，这时}},,{},,{},{},{{21d c b c b d a =⋃ππ，}},,{{21d c b =-ππ，它们都不是A 的划分.5.证明: 设1≥n ，则(1).1)1,(=n S(2).1),(=n n S(3).12)2,(1-=-n n S证 (1)和(2)显然.(3)将n 个元素的集合A 划分成2个块1A 和2A ，先将A 中的第一个放在第一个块1A 中，对于其余的1-n 个元素分别考虑是否与第一个元素在同一个块1A 中，只有两种情况发生: 1A x ∈或1A x ∉，于是共有1122...22--=⋅⋅⋅n n 种放的方式，但要排除所有元素都在1A 中而2A 为空的情形. 故.12)2,(1-=-n n S 6.设},,,,,,,,,,{j i h g f e d c b a A =},,,,{1d c b a A = },,,{2g f e A = },,,,{3i g e d A =},,,{4j h d A =},,,{5j i h A =},,,,,,{6j h f c b a A =分别判定下列集合是否是A 的划分、覆盖: (1)},,{521A A A . (2)},,{531A A A . (3)}.,{63A A(4)}.,,{432A A A解 显然对于任意61≤≤i ，有≠i A ∅.(1)因为=⋂21A A ∅，=⋂51A A ∅，=⋂52A A ∅且A A A A =⋃⋃521，所以},,{521A A A 是A 的划分.(2)由于A f ∈而531A A A f ⋃⋃∉，所以},,{531A A A 不是A 的覆盖.(3)因为=⋂63A A ∅，且A A A =⋃63，所以},{63A A 是A 的划分.(4)由于A a ∈而432A A A a ⋃⋃∉，所以},,{432A A A 不是A 的覆盖.7.写出集合},{b a A =的所有不同的覆盖.解 由A 得到的非空子集为},{},{},{b a b a ，于是},{b a A =的所有不同的覆盖分别为(1)}},{{b a .(2)}}{},{{b a .(3)}},{},{{b a a .(4)}},{},{{b a b .(5)}},{},{},{{b a b a .。

习题参考解答习题1.11、（3）P：银行利率降低Q：股价没有上升P∧Q（5）P：他今天乘火车去了北京Q：他随旅行团去了九寨沟PQ（7）P：不识庐山真面目Q：身在此山中Q→P，或～P→～Q（9）P：一个整数能被6整除Q：一个整数能被3整除R：一个整数能被2整除T：一个整数的各位数字之和能被3整除P→Q∧R ，Q→T2、（1）T （2）F （3）F （4）T （5）F（6）T （7）F （8）悖论习题 1.31（3）)()()()()()(R P Q P R P Q P R Q P R Q P →∨→⇔∨⌝∨∨⌝⇔∨∨⌝⇔∨→（4）()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右2、不， 不， 能习题 1.41(3) (())~((~))(~)()~(~(~))(~~)(~)P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、主合取范式)()()()()()()()()()()()()()())(())(()()(())()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∧∧∨⌝∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∨⌝∧∧∨∨⌝∧⌝∧∨∨⌝∧∨⌝∧⌝=∧∨⌝∧∨⌝=∨⌝∧∨⌝=→∧→ ————主析取范式(2) ()()(~)(~)(~(~))(~(~))(~~)(~)(~~)P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨ 2、()~()(~)(~)(~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价3、解：根据给定的条件有下述命题公式：（A →（C ∇D ））∧～（B ∧C ）∧～（C ∧D ）⇔（～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ∧～C ）） ∧（～C ∨～D ）⇔（～A ∧～B ∧～C ）∨（C ∧～D ∧～B ∧～C ）∨（～C ∧D ∧～B ∧～C ）∨ （～A ∧～C ∧～C ）∨（～C ∧D ∧～C ∧～C ）∨（～A ∧～B ∧～D ）∨（C ∧～D ∧～B ∧～D ）∨（～C ∧D ∧～B ∧～D ）∨（～A ∧～C ∧～D ）∨ （～C ∧D ∧～C ∧～D ）（由题意和矛盾律）⇔（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ）∨（C ∧～D ∧～B ）⇔（～C ∧D ∧～B ∧A ）∨ （～C ∧D ∧～B ∧～A ）∨ （～A ∧～C ∧B ）∨ （～A ∧～C ∧～B ）∨ （～C ∧D ∧A ）∨ （～C ∧D ∧～A ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～A ∧～C ∧B ∧～D ）∨（～A ∧～C ∧～B ∧D ）∨ （～A ∧～C ∧～B ∧～D ）∨（～C ∧D ∧A ∧B ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ）∨ （～C ∧D ∧～A ∧～B ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ） ⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ） ∨（C ∧～D ∧～B ∧A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨（C ∧～D ∧～B ∧A ） 三种方案：A 和D 、 B 和D 、 A 和C习题 1.51、 （1）需证()(())P Q P P Q →→→∧为永真式()(())~(~)(~())~~(~)(()(~))~(~)(~)()P Q P P Q P Q P P Q P P P Q P Q TP Q P Q T P Q P P Q →→→∧=∨∨∨∧∨=∨∨∧∨=∨∨∨=∴→⇒→∧（3）需证S R P P →∧⌝∧为永真式SR P P T S F S R F S R P P ⇒∧⌝∧∴⇔→⇔→∧⇔→∧⌝∧3A B A B ⇒∴→ 、为永真式。

1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。

⑴中国有四大发明。

⑵计算机有空吗?⑶不存在最大素数。

⑷ 21+3＜5。

⑸老王是山东人或河北人。

⑹ 2与3都是偶数。

⑺小李在宿舍里。

⑻这朵玫瑰花多美丽呀!⑼请勿随地吐痰!⑽圆的面积等于半径的平方乘以p。

⑾只有6是偶数，3才干是2的倍数。

⑿雪是黑色的当且仅当太阳从东方升起。

⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。

⑴李辛与李末是兄弟。

⑵因为天气冷，所以我穿了羽绒服。

⑶天正在下雨或湿度很高。

⑷刘英与李进上山。

⑸王强与刘威都学过法语。

⑹如果你不看电影，那么我也不看电影。

⑺我既不看电视也不过出，我在睡觉。

⑻除非天下大雨，否则他不乘班车上班。

解：⑴本命题为原子命题；⑵p：天气冷；q：我穿羽绒服；⑶p：天在下雨；q：湿度很高；⑷p：刘英上山；q：李进上山；⑸p：王强学过法语；q：刘威学过法语；⑹p：你看电影；q：我看电影；⑺p：我看电视；q：我外出；r：我睡觉；⑻p：天下大雨；q：他乘班车上班。

3. 将下列命题符号化。

⑴他一面吃饭，一面听音乐。

⑵ 3是素数或2是素数。

⑶若地球上没有树木，则人类不克不及生存。

⑷ 8是偶数的充分需要条件是8能被3整除。

⑸停机的原因在于语法错误或程序错误。

⑹四边形ABCD是平行四边形当且仅当它的对边平行。

⑺如果a和b是偶数，则a+b是偶数。

解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q⑵p：3是素数；q：2是素数；原命题符号化为：p∨q⑶p：地球上有树木；q：人类能生存；原命题符号化为：p→q⑷p：8是偶数；q：8能被3整除；原命题符号化为：p↔q⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p↔q。

离散数学第二版邓辉文编著第一章第二节习题答案1.2 映射的有关概念习题1.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 ) =x 3+1.(4)f :N ⨯N →N , f (x 1, x 2) =x 1+x 2+1.(5)f :N →N⨯N , f (x ) =(x , x +1).解 (1)对于任意对x 1, x 2∈Z，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z，f (x ) ≠2∈Z，因此f 不是满射，进而f 不是双射.(2)由于2, -2∈Z且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N，而任意x ∈Z均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射.(3)对于任意对x 1, x 2∈R，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R，取x =(y -1) ，这时1⎡⎤3f (x ) =x +1=⎢(y -1) 3⎥+1=(y -1) +1=y ，⎣⎦33313所以f 是满射. 进而f 是双射.(4)由于(1, 2), (2, 1) ∈N⨯N 且(1, 2) ≠(2, 1) ，而f (1, 2) =f (2, 1) =4，因此f 不是单射. 又由于0∈N，而任意(x 1, x 2) ∈N⨯N 均有f (x 1, x 2) =x 1+x2+1≠0，于是f 不是满射. 显然，f 就不是双射.(5)由于x 1, x 2∈N，若f (x 1) =f (x 2) ，则(x 1, x 1+1) =(x 2, x 2+1) ，于是x 1=x 2，因此f 是单射. 又由于(0, 0) ∈N⨯N ，而任意x ∈N均有f (x ) =(x , x +1) ≠(0, 0) ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.3. 对于有限集合A 和B ，假定f :A →B且|A |=|B |，证明: f 是单射的充要条件是f 是满射. 对于无限集合，上述结论成立吗？举例说明.证(⇒) 因为f 是单射，所以|A |=|f (A ) |. 由于|A |=|B |，所以|f (A ) |=|B |. 又因为B 有限且f (A ) ⊆B ，故f (A ) =B ，即f 是满射.(⇐) 若f 是满射，则f (A ) =B . 由于|A |=|B |，于是|A |=|f (A ) |. 又因为A 和B 是有限集合，因此f 是单射.对于无限集合，上述结论不成立. 例如f :N →N，f (x ) =2x ，f 是单射，但f 不是满射.4. 设f :A →B , 试证明:(1)f I B =f .(2)I A f =f .特别地，若f :A →A，则f I A =I A f =f .证 (1)对于任意x ∈A，由于f (x ) ∈B，所以(f I B )(x ) =I B (f (x )) =f (x ) ，因此f I B =f .(2)对于任意x ∈A，由于I A (x ) =x ，所以(I A f )(x ) =f (I A (x )) =f (x ) ，于是有I A f =f .由(1)和(2)知，若f :A →A，则f I A =I A f =f .5. 试举出一个例子说明f f =f 成立，其中f :A →A且f ≠I A . 若f 的逆映射存在，满足条件的f 还存在吗?解令A ={a , b , c }，f (a ) =f (b ) =f (c ) =a ，即对于任意x ∈A，f (x ) =a ，显然f :A →A且f ≠I A . 而对于任意x ∈A，有(f f )(x ) =f (f (x )) =f (a ) =a ，因此f f =f .若f f =f 且f 的逆映射f -1存在，由第3题知f f =f =f I A ，所以-1-1于是利用定理7有(f f ) f =(f f ) I A ，f -1 (f f ) =f -1 (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 不一定是单射.证对于任意x 1, x 2∈A，假定f (x 1) =f (x 2) ，则显然g (f (x 1)) =g (f (x 2)) ，即(f g )(x 1) =(f g )(x 2) . 因为f g 是单射，所以x 1=x 2，于是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 是双射且f -1=g .证因为f g =I A ，而I A 是单射，所以f 是单射. 又因为g f =I B ，而I B 是满射，所以f 是满射. 因此f 是双射.由于f 是双射，所以f而(f -1-1存在. 因为f g =I A ，于是f -1 (f g ) =f -1 I A . f ) g =f -1 I A 且I B g =f -1，所以有f -1=g .9. 设f :A →B , g :B →C . 若f 和g 是双射，则f g 是双射且(f g ) -1=g -1 f -1.-1-1证根据定理4(1)(2)知，f g 是双射. 下证(f g ) =g f -1. 因为(f g ) (g -1 f -1) =f (g g -1) f -1=f I B f -1=f f -1=I A ， (g -1 f -1) (f g ) =g -1 (f -1 f ) g =g -1 I B g =g -1 g =I C ，在上面的推导中多次利用了定理7. 由第7题知，(f g ) -1=g -1 f10. 设G 是集合A 到A 的所有双射组成的集合，证明(1)任意f , g ∈G，有f g ∈G .(2)对于任意f , g , h ∈G，有(f g ) h =f (g h ).(3)I A ∈G且对于任意f ∈G，有I A f =f I A =f .(4)对于任意f ∈G，有f -1-1. ∈G且f f -1=f -1 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 是双射.证对于任意(a 1, c 1) ∈A⨯C ，(a 2, c 2) ∈A⨯C ，假定h (a 1, c 1) =h (a 2, c 2) ，即(f (a 1), g (c 1)) =(f (a 2), g (c 2)) ，于是f (a 1) =f (a 2) 且g (c 1) =g (c 2) ，根据已知条件有a 1=a 2且c 1=c 2，进而(a 1, c 1) =(a 2, c 2) ，因此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 均可逆，并求出f -1, g -1, h -1.证因为恒等映射是双射，多次使用定理6即可得结论.由于f g h =I A ，所以f 是单射且h 是满射. 由于g h f =I B ，所以g 是单射且f 是满射. 由于h f g =I C ，所以h 是单射且g 是满射. 于是f , g , h 是双射，因此f , g , h 均可逆.由于f g h =I A ，所以f -1=g h 且h -1=f g ，进而g -1=h f .14. 已知Ackermann 函数A :N ⨯N →N的定义为(1)A (0, n ) =n +1, n ≥0;(2)A (m , 0) =A (m -1, 1), m >0;(3)A (m , n ) =A (m -1, 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.。

1.2 映射的有关概念习题1.21. 分别计算⎡⎤5.1，⎡⎤1-，⎡⎤5.1-，⎣⎦5.1，⎣⎦1-，⎣⎦5.1-.解 ⎡⎤25.1=，⎡⎤11-=-，⎡⎤15.1-=-，⎣⎦15.1=，⎣⎦11-=-，⎣⎦25.1-=-.2.下列映射中，那些是双射? 说明理由.(1).3)(,Z Z :x x f f =→(2).1||)(,N Z :+=→x x f f(3).1)(,R R :3+=→x x f f(4).1),(,N N N :2121++=→⨯x x x x f f(5)).1,()(,N N N :+=⨯→x x x f f解 (1)对于任意对∈21,x x Z ，若)()(21x f x f =，则2133x x =，于是21x x =，所以f 是单射. 由于对任意∈x Z ，∈≠2)(x f Z ，因此f 不是满射，进而f 不是双射.(2)由于∈-2,2Z 且3)2()2(=-=f f ，因此f 不是单射. 又由于∈0N ，而任意∈x Z 均有01||)(≠+=x x f ，于是f 不是满射. 显然，f 不是双射.(3)对于任意对∈21,x x R ，若)()(21x f x f =，则113231+=+x x ，于是21x x =，所以f 是单射. 对于任意∈y R ，取31)1(-=y x ，这时y y y x x f =+-=+⎥⎦⎤⎢⎣⎡-=+=1)1(1)1(1)(3313，所以f 是满射. 进而f 是双射.(4)由于∈)1,2(),2,1(N ⨯N 且)1,2()2,1(≠，而4)1,2()2,1(==f f ，因此f 不是单射. 又由于∈0N ，而任意∈),(21x x N ⨯N 均有01),(2121≠++=x x x x f ，于是f 不是满射. 显然，f 就不是双射.(5)由于∈21,x x N ，若)()(21x f x f =，则)1,()1,(2211+=+x x x x ，于是21x x =，因此f 是单射. 又由于∈)0,0(N ⨯N ，而任意∈x N 均有)0,0()1,()(≠+=x x x f ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.3.对于有限集合A 和B ，假定B A f →:且||||B A =，证明: f 是单射的充要条件是f 是满射. 对于无限集合，上述结论成立吗？举例说明.证(⇒)因为f 是单射，所以|)(|||A f A =. 由于||||B A =，所以|||)(|B A f =. 又因为B 有限且B A f ⊆)(，故B A f =)(，即f 是满射.(⇐)若f 是满射，则B A f =)(. 由于||||B A =，于是|)(|||A f A =. 又因为A 和B 是有限集合，因此f 是单射.对于无限集合，上述结论不成立. 例如N N :→f ，x x f 2)(=，f 是单射，但f 不是满射.4.设,:B A f →试证明:(1).f I f B =(2).f f I A =特别地，若A A f →:，则f f I I f A A == .证 (1)对于任意A x ∈，由于B x f ∈)(，所以)())(())((x f x f I x I f B B == ，因此.f I f B =(2)对于任意A x ∈，由于x x I A =)(，所以)())(())((x f x I f x f I A A == ，于是有.f f I A =由(1)和(2)知，若A A f →:，则f f I I f A A == .5.试举出一个例子说明f f f = 成立，其中A A f →:且A I f ≠. 若f 的逆映射存在，满足条件的f 还存在吗?解 令},,{c b a A =，a c f b f a f ===)()()(，即对于任意A x ∈，a x f =)(，显然A A f →:且A I f ≠. 而对于任意A x ∈，有a a f x f f x f f ===)())(())(( ，因此f f f = .若f f f = 且f 的逆映射1-f 存在，由第3题知A I f f f f ==，所以)()(11A I f f f f f --=，于是利用定理7有A I f f f f f )()(11--=，进而A A A I I f I =，因此A I f =. 所以若f 的逆映射存在，满足条件的f 不存在.6.设C B g B A f →→:,:. 若f 和g 是满射，则g f 是满射，试证明.证 因为f 是满射，所以B A f =)(. 又因为g 是满射，所以C B g =)(. 于是C B g A f g A g f ===)())(())(( ，因此g f 是A 到C 的满射.另证 对于任意C z ∈，因为g 是满射，于是存在B y ∈使得z y g =)(. 又因为f 是满射，存在A x ∈使得y x f =)(. 因此，z y g x f g x g f ===)())(())(( ，所以g f 是A 到C 的满射.7.设C B g B A f →→:,:. 试证明: 若g f 是单射，则f 是单射. 试举例说明，这时g 不一定是单射.证 对于任意A x x ∈21,，假定)()(21x f x f =，则显然))(())((21x f g x f g =，即))(())((21x g f x g f =. 因为g f 是单射，所以21x x =，于是f 是单射.例如},{b a A =，}3,2,1{=B ，},,,{δγβα=C ，令2)(,1)(==b f a f ，ββα===)3(,)2(,)1(g g g ，则显然有,)1())(())((α===g a f g a g f ,)2())(())((β===g b f g b g f 于是g f 是A 到C 的单射，但g 显然不是单射.8.设,:B A f →若存在A B g →:，使得A I g f = 且B I f g = ，试证明: f 是双射且.1g f =-证 因为A I g f = ，而A I 是单射，所以f 是单射. 又因为B I f g = ，而B I 是满射，所以f 是满射. 因此f 是双射.由于f 是双射，所以1-f存在. 因为A I g f = ，于是A I f g f f 11)(--=.而A I f g f f 11)(--=且1-=f g I B ，所以有.1g f =-9.设C B g B A f →→:,:.若f 和g 是双射，则g f 是双射且111)(---=f g g f .证 根据定理4(1)(2)知，g f 是双射. 下证111)(---=f g g f . 因为A B I f f f I f f g g f fg g f ====------111111)()()( ， C B I g g g I g g f f g g f f g ====------ 111111)()()(，在上面的推导中多次利用了定理7. 由第7题知，111)(---=f g g f .10.设G 是集合A 到A 的所有双射组成的集合，证明(1)任意G g f ∈,，有G g f ∈ .(2)对于任意G h g f ∈,,，有).()(h g f h g f =(3)G I A ∈且对于任意G f ∈，有f I f f I A A == .(4)对于任意G f ∈，有G f ∈-1且A I f f f f ==-- 11.证 (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 的满射共有623=⨯个(请自己分别写出A 到B 的6个满射).由于2||,3||==B A ，所以A 到B 的单射没有，进而A 到B 的双射也没有. 假设n B m A ==||,||.(1) A 到B 的满射 若n m <，不存在满射；若n m ≥，先将m 个元素划分成n 个块(参见1.5节)，共有),(n m S 种方式；再将B 中元素进行全排列，共有!n 种方式，于是A 到B 的满射共有!),(n n m S ⋅个.(2) A 到B 的单射 若n m >，不存在单射；若n m ≤，由于B 中任意选取m 个元素，再将其进行全排列都得到A 到B 的单射，故A 到B 的单射共有!m C m n ⋅个.(3)A 到B 的双射 若n m ≠，不存在双射；若n m =，此时B 中元素的任意一个排列均可得到一个A 到B 的双射，因此A 到B 的双射共有!m 个.12.设A , B , C , D 是任意集合，f 是A 到B 的双射， g 是C 到D 的双射，令D B C A h ⨯→⨯:，对任意,),(C A c a ⨯∈)).(),((),(c g a f c a h = 证明:h 是双射.证 对于任意C A c a ⨯∈),(11，C A c a ⨯∈),(22，假定),(),(2211c a h c a h =，即))(),(())(),((2211c g a f c g a f =，于是)()(21a f a f =且)()(21c g c g =，根据已知条件有21a a =且21c c =，进而),(),(2211c a c a =，因此h 是单射.任意D B d b ⨯∈),(，则D d B b ∈∈,，由于f 是A 到B 的双射且g 是C 到D 的双射，于是存在C c A a ∈∈,使得d c g b a f ==)(,)(，因此),())(),((),(d b c g a f c a h ==，所以h 是满射.故h 是双射.13.设A C h C B g B A f →→→:,:,:，若A I h g f = ，B I f h g = ，C I g f h = ，则h g f ,,均可逆，并求出111,,---h g f .证 因为恒等映射是双射，多次使用定理6即可得结论.由于A I h g f = ，所以f 是单射且h 是满射. 由于B I f h g = ，所以g 是单射且f 是满射. 由于C I g f h = ，所以h 是单射且g 是满射. 于是h g f ,,是双射，因此h g f ,,均可逆.由于A I h g f = ，所以h g f =-1且g f h =-1，进而f h g =-1.14.已知Ackermann 函数N N N :→⨯A 的定义为(1);0,1),0(≥+=n n n A(2);0),1,1()0,(>-=m m A m A(3).0,0)),1,(,1(),(>>--=n m n m A m A n m A分别计算)3,2(A 和)2,3(A .解 由已知条件有2)1,0(=A ，2)1,0()0,1(==A A ，于是312)2,0())0,1(,0()1,1(=+===A A A A ，413)3,0())1,1(,0()2,1(=+===A A A A ，由此可进一步得出2),1(+=n n A ，3)1,1()0,2(==A A ，523)3,1())0,2(,1()1,2(=+===A A A A ，725)5,1())1,2(,1()2,2(=+===A A A A ， 927)7,1())2,2(,1()3,2(=+===A A A A . 因此有32),2(+=n n A ，5312)1,2()0,3(=+⋅==A A ，13352)5,2())0,3(,2()1,3(=+⋅===A A A A ， 293132)13,2())2,2(,2()2,3(=+⋅===A A A A . 所以有29)2,3(,9)3,2(==A A .。

第一章 集合、关系与函数 习题答案1、用列举法表示下列集合。

（1）{x|x 是小于20的正偶数}={2，4，6，8，10，12，14，16，18}（2）{x|x 是整数，x 2＜80}={0，±1，±2，±3，±4，±5，±6，±7，±8} （3）{x|x=3k ，k 是小于10的素数}={6,9,15,21}（4）{x|x 是能整除30的正整数}={1，2，3，5，6，10，15，30}（5）{x|x 是小于30的素数}={2，3，5，7，11，13，17，19，23，29}2、用特征法表示下列集合。

（1）{1，3，5，…，99}={x|x 是正奇数，x ≤99}（2）{1，4，9，16，25}={x|x=k 2,k 是正整数，k ≤5}（3）{5，10，15，…，100}={x|x=5k,k 是正整数，k ≤20}（4）{1，23，2，25，3，27，4}={x|x=21+k ，k 是正整数，k ≤7} 3、设A ，B ，C 是集合，确定下列命题是否正确，并说明理由。

（1）如果A ∈B,B ⊆C,则A ⊆C 。

解：不正确。

例如，A={a}，B={{a},b}，C={{a},b }。

易见A ∈B,B ⊆C 但A C。

（2）如果A ∈B,B ⊆C,则A ∈C 。

解：正确。

因为B ⊆C ，所以B 中元素都属于C ，而A ∈B ，所以A ∈C 。

（3）如果A ⊆B,B ∈C,则A ∈C 。

解：不正确。

例如，A={a}，B={a,b}，C={{a,b}}。

易见A ⊆B,B ∈C 但A ∉C 。

（4）如果A ⊆B,B ∈C,则A ⊆C 。

解：不正确。

例如，A={a}，B={a,b}，C={{a,b}}。

易见A ⊆B,B ∈C 但A C。

4、确定下列命题是否正确。

（1）φ⊆φ 正确。

（2）φ∈φ 错误。

（3）φ⊆{φ} 正确。

离散数学第二版课后答案pdf选择题：1. 以下哪个函数不是单射？A. f(x)=x+1B. f(x)=x²C. f(x)=sin(x)D. f(x)=|x|2. 设 A={1,2,3},B={2,3,4},则A∪B=？A. {1,2,3,4}B. {2,3}C. {1,2,3}D. {1,2,3,4,5}3. 若 5n+1 是完全平方数，则 n 的取值范围是？A. n 是任意自然数B. 1、3、11C. 2、3、7D. 0、2、84. 若 P(A)=0.4，P(B)=0.3，P(AB)=0.1，则P(A∪B)=？A. 0.2B. 0.3C. 0.4D. 0.55. 在一个 10 个点的完全图中，不同颜色的边有红、蓝、绿三色，其中红边有 3 条，蓝边有 2 条，绿边有 5 条，则将这 10 个点分成涂3 种颜色的三部分的方案数为？A. 6552B. 1260C. 3150D. 5040选择题答案：1. C2. D3. B4. A5. C填空题：1. 用 1,2,3,4,5 这 5 个数字，能组成多少个长度为 3 的无重复的数字串？答：602. 已知 a+b=7，a-b=3，则 a²-b²=？答：203. 一个无向图有 8 条边，则它的图的边数有多大范围？答：4≤边数≤284. 在一组含有 5 个正整数的数列中，最大值是最小值的 3 倍，则这5 个数中的最小值不能小于多少？答：55. 若 G 是一个有 n 个点的简单无向图，且 G 不是完全图，则 G 中边的数量最少是多少？答：n填空题答案：1. 602. 203. 4≤边数≤284. 55. n解答题：1. 一张简单无向图 G 有 10 个顶点和 20 条边，证明 G 中至少有 3 个度数为偶数的顶点。

答：设 G 中度数为奇数的点的个数为 x，度数为偶数的点的个数为 y，则 x+y=10，2x+4y=40，化简得 x=2y-10，由于每个点的度数都是偶数或奇数，所以 2x+20-y 是偶数，即 2(2y-10)+20-y=3y-10 是偶数，即 y 是奇数。