《哈工大《离散数学》教科书习题答案》由会员分享，可在线阅读，更多相关《哈工大《离散数学》教科书习题答案（39页珍藏版）》请在金锄头文库上搜索。
1、教材习题解答第一章 集合与其运算习题3.写出方程的根所构成的集合.解：的根为,故所求集合为4.下列命题中哪些是真的,哪些为假a对每个集A,；b对每个集A,；c对每个集A,；d对每个集A,；e对每个集A,；f对每个集A,；g对每个集A,；h对每个集A,；i对每个集A,；j对每个集A,；k对每个集A,；l对每个集A,；m对每个集A,；n；o中没有任何元素；p若,则q对任何集A,；r对任何集A,；s对任何集A,；t对任何集A,；答案：假真真假真假真假真假真真假假假真真真真真5.设有n个集合且,试证：证明：由,可得且,故.同理可得：因此6.设,试求？解：7.设S恰有n个元素,证明有个元素.证明：1当n
2、0时,命题成立.2假设当时命题成立,即时.那么对于,中的元素可分为两类,一类为不包含中某一元素的集合,另一类为包含的集合.显然,这两类元素个数均为.因而,亦即命题在时也成立.由1、2,可证得命题在时均成立.习题1.设A、B是集合,证明:证：当时,显然,得证.假设,则必存在,使得但,故与题设矛盾.所以假设不成立,故.2.设A、B是集合,试证证：显然.反证法：假设,则,若,则左,但右,矛盾.若,则左,但右,矛盾.故假设不成立,即.3.设A,B,C是集合,证明：证：由上式可以看出此展开式与A、B、C的运算顺序无关,因此,4.设A,B,C为集合,证明证：因为=.5.设A,B,C为集合,证明：证：.6.
3、设A,B,C为集合,证明：证明： =7.设A,B,C都是集合,若且,试证B=C.证：证1：,则若,则.由于,故,即；若,则,由于,故.又,只能有.因此,总有,故.同理可证,.因此.证2：8.设A,B,C为集合,试证：证：证,有,因此,.故,即.反之,有,.因此.故,即.所以.证：9.设,证明证：证1：,有且或.则若且,则,于是.若且,则,从而.反之,则或.若,则由有,故,因此.若,则但,故,因此.从而.由集合相等的定义,.证2：,因为,所以.10.下列命题是否成立？；.解：1,2,3都不成立.反例如下：1任意,则.2,则.3,则.11下列命题哪个为真？a对任何集合A,B,C,若,则A=C.b设
4、A,B,C为任何集合,若,则B=C.c对任何集合A,B,.d对任何集合A,B,.e对任何集合A,B,.f对任何集合A,B,.答案：d是真命题.12设R,S,T是任何三个集合,试证：1；2；3；4证：1,则若,则.因而且,故；若,则,同理可得.故.反之,因为,故.,有.若,则,故；若,则,故.因此.所以.2证：,有且.则若,则且,故,.若,则且.故,因此.于是.3证：,有且.则若,则,故,因此；若,则,故,.于是反之,则若,则,故,因而.即；若,则,故或.因此或,从而.综上可得：.于是证：,则若,则,因而.故,于是；若,则,与上同理可得.综上可得：.14设A为任一集,为任一集族,证明：证：,则若
5、,则,因而；若,则,因而,故.于是.反之,设,则.若,显然；若,则,因而,即.所以,.综上可得,.15填空：设A,B是两个集合._； _；_；_；解：且； 或或； 且或且16设A,B,C为三个集合,下列集合表达式哪一个等于？a；bc；de答案：c.习题1设A,B,C为集合,并且,则下列断言哪个成立？；.答案：d.在两边同时并上A即得.2设A,B,C为任意集合,化简证：证1：原式证2：令原式T,全集为S,则且,故 .3证明：1；2； 3证：12证： 根据13证： 根据24设和是集合S的子集的两个序列,对,有.令.试证：.证： 当n1时,故当n2时,设有或.则1.若,则但,因此有.于是1若且,有；
6、2若且,由,有且,于是.2.若,则但.于是.综上可得：5设X是一个非空集合,试证：,有.证明：由于,故.因为,故,显然有.对于,假设存在,使得,必可找到其中最小的值,使得,故；假如不存在p,则,故.综上可得：.所以.6设V是任一集合,证明：有当且仅且且.证：因为,故.先证.设,则若,则,故且,矛盾.所以,即.其次,证明.设,则有两种情况：若.则,故.若.由,知.总之,有,故.7设为一集序列,记为这样的元素的全体形成的集合：当且仅当在序列中有无穷多项含有.集合称为集序列的上极限,记为,即.又记为这样的元素全体形成的集合；序列中只有有限项不含有这样的元素.称为序列的下极限,并记.证明；1；2.证：
7、 1,在序列中只有有限项不含x,在不含x的项中必可找到下标最大的一项若各项均含x,则令p0,有,故,即.反之,必使得,即时,.而集合中即使都不含有x,但也仅有有限项不含x,故.因此.综上可得：.2,因为中有无穷多项含有x,故,当时,因此,从而,即反之,则,即中有无穷多项多含x,所以,即综上可得：.8证明：证：,由定义可知：序列中只有有限项不含x,故必可找到不含x的下标最大的一项,可见此时均含x,即有无限项含x,故.因此.习题1设.求.解：2设A,B为集合,试证：ABBA的充要条件是下列三个条件至少一个成立：1；2；3.证：若1成立,.若2成立,同上.若3成立,AB=BB=BA.假设必要性不成立
8、,即.故不妨设使得.设,则,矛盾.于是,假设不成立.因而必要性成立.必要性也可以如下证明：1.若,则或.2.若,则,有.于是,因此且,故A=B.3设A,B,C,D为任四个集合,证明：证：,有,即.所以,因此,从而.反之,有.即,从而.因此,.4设为任意集合,试证：证：,有且或.则若,则,故,即.若,同理可证.从而.反之,则或,即,但或,但.从而有,但,即,从而.综上可得：.5设,试证：证：,则,故或.于是1.若,则.因此若,则. 若,则,即.2.若,则必有,故.综上可得：.反之,则或或,于是,若,则且,即,于是.若,则且,即,于是.若,则且,即,于是.综上可得：.于是.7设是三个任意集合,证明
9、：证：8设A,B为集合,下列命题哪些为真？1且2或34若,则.5若,则.答案：2,5为真.9设A有m个元素,B有n个元素,则AB是多少个序对组成的？AB有多少个不同的子集？答：AB有mn个序对；AB有个不同子集.10设是两个集合,试证：若,则.证：,因为,故在B中任取一元素y,必有,因而,故.从而.反之,因为,故在中任取一元素y,必有,因而,故.从而.于是.习题1.某班学生中有45正在学德文,65正在学法文.问此班中至少有百分之几的学生正同时学德文和法文？解：设A,B分别为正在学德文和法文的学生的集合,班级总人数为n,则,于是同时学习德文和法文的人数为,故.于是全班至少百分之十的学生同时学德文
10、和法文.2求1到250之间不能被2,3,5,7中任一数整除的数的个数.解：设,在S上的定义性质,n具有性质相应地当且仅当.令为S中具有性质之集,则所求为：3设A,B是两个有限集,试求解：4马大哈写n封信,n个信封,把n封信放入到n个信封中,求全部装错的概率是多少？解：,令表示所有信都装错的集合,即.令表示第个信封恰好装对的集合,则.所以全部装错的集合为：.于是,易得. 对于,有 .又答案：0.3679,当n10时,概率都近似等于0.3679.5毕业舞会上,小伙子与姑娘跳舞,已知每个小伙子至少与一个姑娘跳过舞,但未能与所有姑娘跳过.同样地,每个姑娘也至少与一个小伙子跳舞,但也未能与所有的小伙子跳
11、过舞.证明：在所有参加舞会的小伙与姑娘中,必可找到两个小伙子和两个姑娘,这两个小伙子中的每一个只与这两个姑娘中的一个跳过舞,而这两个姑娘中的每一个也只与这两个小伙中的一个跳过舞.证：设是小伙的集合,是姑娘的集合.与跳舞的姑娘的集合用表示；与跳舞的姑娘的集合用表示；与跳舞的姑娘的集合用表示；于是,由题意：且且,.若存在,使得且,则结论成立.反证法：假设不存在和满足且.于是应满足：或必有一个成立.因此把重新排列有：.从而与所有的姑娘都跳过舞,矛盾.因此假设不成立,本题得证.第二章 映射习题1.设A,B是有穷集,1计算；2从A到A有多少个双射？解：1；2从A到A共有m!个双射.2.设X是一个有穷集合
12、,证明：从X到X的部分映射共有个.证：设,则f是X到X的一个部分映射.设当时,f的个数为当A是单元素集时,f的个数为当A中有2个元素时,f的个数为当A中有k个元素时,f的个数为当A中有n个元素时,f的个数为因此f的总个数为+即从X到X的部分映射共有个.4.设是一个两两不相交的整数构成的数列,则必有长至少为的递增子序列或有长至少为的递减子序列.证：令,则.设以为首项的最长递增子序列的长度为,设以为首项的最长递减子序列的长度为.反证法：假设题中结论不成立,则.令,则是单射.实际上,且,则若,则,所以；即.若,则,所以；即.故为单射,从而就有矛盾.习题1.证明：从一个边长为1的等边三角形中任意选5个
13、点,那么这5个点中必有2个点,它们之间的距离至多为1/2,而任意10个点中必有2个点其距离至多是1/3.证： 将边长为1的等边三角形4等分,得到4个边长为1/2的小等边三角形.任给5个点,由鸽巢原理可知必有一个小等边三角形里面至少有2个点,又因为小等边三角形中任意两个点之间的距离至多为1/2,因此5个点中必有2个点,它们之间的距离至多为1/2. 连接各边的三等分点,则可得到9个边长都为1/3的小等边小角形,每个小等边三角形中任意两个点之间的距离至多为1/3.将10个点放入该大等边三角形中,则由鸽洞原理,必有一个小等边三角形中至少有2个点,因此任意10个点中必有2个点其距离至多为1/3.2.已知个整数,试证：存在两个整数,使得能被整除.证：考察下式：若第式能被整除,则显然成立,此时；若任一式都不能被整除,则
