离散数学第四版课后答案(第3章)

离散数学课后答案第3章习题解答3.1A：③；B：④；C：⑤；D：⑦；E：⑧3.2A：③；B：①；C：⑤；D：⑥；E：⑦3.3A：①；B：③；C：⑧；D：⑤；E：⑩分析对于给定的集合或集合公式，比如说是A和B，判别B是否被A包含，可以有下述方法：1°若A和B是通过列元素的方式给出的，那么依次检查B中的每个元素是否在A中出现，如果都在A中出现，则,AB否则不是。例如，3.3题给的答案中有{{1，2}}和{1}，谁是}}2,1{},1{,{S的子集呢?前一个集合的元素是{1,2},要S中出现,但后一个集合的元素是1,不在S中出现,因此,{{1,2}}.S2°若A和B是通过用谓词概括元素性质的主试给出的,B中元素的性质为P,A中元素的性质为Q,那么,“如果P则Q”意味着,AB“只有P才Q”意味着,BA“除去P都不Q”意味着,BA“P且仅P则Q”意味着.BA例如，3.1题（1）是“如果P则Q”的形式，其中“计算机专业二年级学生”是性质P，“学《离散数学》课”是性质；题（2）是“P且仅P则Q”的形式，此外“如果P就非Q”则意味着BA。例如，3.1题（3）和3.2题（3）都是这种形式。3°通过集合运算差别,AB如果ABA，BAB，AB三个等式中有任何一个成立，则有.AB。4°通过文氏图观察，如果代表B的区域落在代表A的区域内部，则.AB。这后两种方法将在后面的解答中给出实例。3.4A：②；B：④；C：⑦；D：⑥；E：⑧3.5A：②；B：④；C：⑤；D：⑥；E：⑨3.6A：①；B：⑨；C：④；D：⑦；E：⑧3.7A：④；B：⑨；C：①；D：⑧；E：①分析设只买1本、2本及3本书的学生集合分别为21,SS和3S，它们之间两两不交，由题意可知，.55||,20||323SSS又知||32SS,所以,.352055||||||3322SSSS然后列出下面的方程:140||3||2||321SSS求得10||1S.因此,没有买书的人数是75-(10+35+20)=10.3.8(1)和(4)为真,其余为假.分析这里可以应用集合运算的方法来差别集合之间的包含或相等关系.如题(3)中的条件TS意味着,TS,这时不一定有S=T成立.而对于题(4),由条件~ESUT可推出.)()()~()(~STSSTSSTSSSESSUTS这是TS的充公必要条件,从而结论为真.对于假命题都可以找到反例,如题(2)中令}2{},1{},2,1{MzTS即可;而对于题(5),只要S即可.3.9(2),(3)和(4)为真,其余为假.3.10(1)}.2,1,0{A(2)}5,4,3,2,1{A(3)}1{A(4),3,0,0,2,1,1,2,0,0,11,0,0,0{A}0,4,1,3,2,2,3,2,3,1,4,00,3,1,2,2,13.11(1)ca或bc(2)任何ba,(3)dcb(4)cba(5)ca且}{b.3.12(1),(2)和(6)都是,AB而(3),(4),(5)是A=B.分析对于用谓词给定的集合先尽量用列元素的方法表示,然后进行集合之间包含关系的判别.如果有的集合不能列元素,也要先对谓词表示尽可能化简.如题(3)中的A可化简为};2|{xNxx题(5)中的A和B都可以化简为}2,1{;题(6)中的}.21,1{},22|{BxNxxA而对于题(4),不难看出A=B=R,是实数集合.3.13(1)}.{},,},,{{cBAdcbaBA}},,{{baBA}.}},,{{dbaBA(2)}}.{},,{},{,}},{{{bbaccbaBA},},,{{cbaBA}},{}},{,{{cbaBA}}.{},{},{{{bcbaBA(3)}1,0{},2{,BABANBA}2{NBA(4)观察到,AB故}.1|{,,xZRxxBABABBAABA(5)观察到BA,故BAZBA}1,0{ABA}1,0{NBA3.14(1)}}.{,{)(AP(2)}}.1},1{{},1{}},1{{,{)(AP(3)}},2,1{,{}},2{{}},2{{}},2,1{{}},2{{}},1{{},{,{)(AP}}2{},1{,{}},2,1{},2{{}},2,1{},2{{}},2,1{},1{{}},2{},1{{}}2,1}{2{},1{{}},2,1{},2{,{}},2,1{},1{{}},2{},1{,{,}}}.2,1{},2{},1{,{(4)}}2,1{{}},1{{}},2,1{{}},1{{,{)(AP(5)}.2,1,1}{2,1}{2,1{},1,1{},2{},1{},1{,{)(AP分析在做集合运算前先要化简集合,然后再根据题目要求进行计算.这里的化简指的是元素,谓词表示和集合公式三种化简.元素的化简——相同的元素只保留一个，去掉所有冗余的元素。谓词表示的化简——去掉冗余的谓词，这在前边的题解中已经用到。集合公工的化简——利用简单的集合公式代替相等的复杂公式。这种化简常涉及到集合间包含或相等关系的判别。例如，题（4）中的}}1,2,1{},1,2{},1,1{{A化简后得}}2,1{},1{{A，而题（5）中的}022|{23xxxRxxA化简为}2,1,1{A。3．153．16（1），（2），（3）和（6）为真。（4）和（5）不为真。分析如果给出的是集合恒等式，可以用两种方法验证。一是分别对等式两边的集合画出文氏图，然后检查两个图中的阴影区域是否一致。二是利用集合恒等式的代入不断对等式两边的集合公式进行化简或者变形，直到两边相等或者一边是另一边的子集为止。例如，题（1）中的等式左边经恒等变形后可得到等式右边，即CBACBA~)()()()()~()~(CBCACBCA类似地，对题（2）和（3）中的等式分别有)~(~)(CBACBBA)()~()(~CABACBA))(CABA)()()(CABACBACABACABA~))(()~()(CBACBA)(~)(但对于等式（4），左边经变形后得))(())()(()()(BACBABABACBA=).())((BACBAC易见，,)(CBAC但不一定有.)(CBAC如令}.1{CBA时，等式（4）不为真。类假地，等式（5）的左边经化简后得BCA)(，而BCA)(不一定恒等于A-C。3．17（1）不为真。（2），（3）和（4）都为真。对于题（1）举反例如下：令},1{A},1{A},3,2{},2{},4,1{DCB则BA且BC，但DBCA，与结论矛盾。分析（2）由于,~~CDDC又由BA可得,~~CBDCA即CBDA成立。（3）由于BAABA)(，故有BABABABAB)(。这里用到BA的充要条件为BAB或BAB或.BA（4）易见，当A=B成立时，必有A-B=B-A。反之，由A-B=B-A得BABBBA)()(化简后得AB，即AB，同理，可证出BA，从而得到A=B。3．18由64|)(|BP可知|B|=6。又由256|)(|BAP知8||BA，代入包含排斥原理得|,|638BA从而有.752||,2||,1||BABABA3．19令}.10000001|{xNxxSxSxxA|{是完全平方数}，xSxxB|{是完全立方数}，从而有.10||,100||,1000||,1000000||BABAS代入包含排斥原理得|||)||(|||||BABASBA10)1001000(1000000=998910