《华东师范大学离散数学章炯民课后习题第6章答案》由会员分享，可在线阅读，更多相关《华东师范大学离散数学章炯民课后习题第6章答案（5页珍藏版）》请在金锄头文库上搜索。
1、P992.f：XY。对任意AcX,定义f(A)=f(x)|x,A。(1)证明f(AuB)=f(A)uf(B)；(3)举例说明f(AB)f(Af(B)。证明：(1) yUf(A5)o3xAuB,使y=f(x)o3xA或mxUB,使y=f(x)oy=f(x)ef(A)或y=f(x)ef(B)oyef(A)uf(B)f(AuB)=f(A)uf(B)(2)举例：令f(x)=x2,A=1,2,B=1,-2。则f(AB)=1，而f(A)=1,4f(B)=1,4f(A)f(B)=1,4故，f(AB)f(Af(B)基本正确。少数学生出现函数值为一个数值而不是集合的错误4. f：XY，下列命题是否成立？(1)
2、f是一对一的当且仅当对任意a,b,X,当f(a)=f(b)时，必有a=b；(2) f是一对一的当且仅当对任意a,b,X,当f(a)f(b时，必有ab解：(1) 成立(2) 不成立，如f(x)=x2,部分学生第(2)判断错误5. 下图展示了五个关系的关系图。问：这些关系中,哪些是函数？哪些是一对一的函数？哪些是到上的函数？哪些是一一对应？1 是函数,一对一,但不是到上的；2 是函数,到上的,但不是一对一；3 是函数,一一对应；4 是函数；5 不是函数。正确9(1).f：XY,g：YZ。命题电是一对一的当且仅当f和g都是一对一的是否成立？解：不成立。f是一对一的。假设f不是一对一的，不妨设f(a)
3、=B,f(b)=B(aHb)fg(a)=g(f(a)=g(B),fg(b)=g(f(b)=g(B)即fg(a)=fg(b),这与fg是一对一的相矛盾。但g不一定是一对一的。反例:如f的论域1,2:f(1)=5,f=6,g的论域4,5,6:gW=a,g(5)=a,g(6)=c,f是一对一的，fg也是一对一的,但g不是一对一的部分学生判断错误。12.集合x|XZ,且x不能被3整除是否是可数集？若是，则给出自然数集N与它之间的一个一对一对应。解：是可数的。)=是奇数，)=是偶数或=X3(x1)/2+1x是奇数3(x2)/2+2x是偶数都能判断是可数集，在给出函数时绝大部分学生给出的都是A到N的函数1
4、3.设集合簇An|nN和Bn|nN中的集合都是两两不相交的(i时A)nAj=,BinBj=且对任意nN,AB，贝IABnnnn角军：nNnNAJB则存在对应I：ATBA2B2则存在对应f2：A2tB2AB则存在一一对应f:AtBnnnnn*.*An，Bn中的集合都是两两不相交的.必存在对应f：0At0Bnn故0A0BnnnNnN部分学生用计数法判断元素的个数相等16.设F是X到Y的所有函数所组成的集合，F=f|f：XtY,|X|=n。证明FYn。证明：F是X到Y的所有函数所组成的集合，|X|=n,若Y是有限集，设|Y|=m贝l|F|=mn,而|Yn|=mn,故FYn。若Y是无限集,对于X中任意
5、x,Y中都有唯一的y与之对应，故对于任意x,f(xi)与yi也是对应的，故存在函数g：FTYn，故FYn。部分学生直接将Y看成是有限集用计数法来证明等势*18.证明可数集的所有有限子集组成一个可数集。证明：设A是无限可数集，B是有限子集uA,可数集的子集必定也是可数集，故B必定也是可数集，.B=BB2uuB,其中Bi是A的含有i个元素的集合，所以B的元素个数是可数的，12ni可数个可数集的并是可数集，所以B.也是可数集，i即无限可数集的所有有限子集组成一个可数集。基本正确*20.设集合F=f|f：M,其中M为正偶数集。证明：F中存在这样的函数f,计算f的C程序不存在。证明：采用反证法，假设对F
6、中的每个映射都可以写出计算它的C程序。设由所有C程序组成的集合为C。于是，F与C的一个子集等势，即|F|C|。容易证明：C为可列集（因为C中的程序可以按其长度排成一个无限序列）。显然，F是无限集，所以F也是可列集。（可列集是势最小的无限集）所以，可设F=f1,f2,.,fn,.。12n定义f:N-M如下：f(n)2nf(n)=2显然f(n)F,所以mUN,使f=f。m从而，VnUN,f(n)=f(n)。m特别地，f(m)=f(m)。m这与f的定义矛盾。所以，并非对F中的每个映射都可以写出计算它的C程序。大约三分之一的学生选做此题。采用的均为反证法。应交106人，实交73人。其中1-9题是上一次作业改过的。
