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

离散数学课后答案

第3章习题解答

3.1 A：③； B：④； C：⑤； D：⑦；E：⑧

3.2 A：③；B：①； C：⑤； D：⑥； E：⑦

3.3 A：①；B：③； C：⑧； D：⑤； E：⑩ 分析对于给定的集合或集合公式，比如说是A和B，判别B是否被A包含，可以有下述方法：

1° 若A和B是通过列元素的方式给出的，那么依次检查B中的每个元素是否在A中出现，如果都在A中出现，则BA,否则不是。例如，3.3题给的答案中有{{1，2}}和{1}，

S谁是S{,{1},{1,2}}的子集呢?前一个集合的元素是{1,2},要

中出现,但后一个集合的元素是1,不在S中出现,因此,{{1,2}}S.

2° 若A和B是通过用谓词概括元素性质的主试给出的,B中元素的性质为P,A中元素的性质为Q,那么,

“如果P则Q”意味着BA,

“只有P才Q”意味着AB,

“除去P都不Q”意味着AB,

“P且仅P则Q”意味着AB.

例如，3.1题（1）是“如果P则Q”的形式，其中“计算机专业二年级学生”是性质P，“学《离散数学》课”是性质；题（2）是“P且仅P则Q”的形式，此外

“如果P就非Q”则意味着AB。

例如，3.1 题（3）和3.2题（3）都是这种形式。 3° 通过集合运算差别B

BAA,如果ABA，BAB，三个等式中有任何一个成立，则有BA.。

4° 通过文氏图观察，如果代表B的区域落在代表A的区域内部，则BA.。这后两种方法将在后面的解答中给出实例。

3.4 A：②； B：④； C：⑦； D：⑥；E：⑧

3.5 A：②；B：④； C：⑤； D：⑥； E：⑨

3.6 A：①；B：⑨； C：④； D：⑦； E：⑧

3.7 A：④；B：⑨； C：①； D：⑧； E：① 分析设只买1本、2本及3本书的学生集合分别为S和S，它们之间两两不交，由题意可知， 31,S2

|S3|20,|S2S3|55.

又知|S2S3|,所以,

|S2||S2S3||S3|552035.

然后列出下面的方程:

|S1|2|S2|3|S3|140

求得|S1|10.因此,没有买书的人数是

75-(10+35+20)=10.

3.8 (1)和(4)为真,其余为假.

分析这里可以应用集合运算的方法来差别集合之间

的包含或相等关系.如题(3)中的条件ST意味着, ST,

E这时不一定有S=T成立.而对于题(4),由条件~SUT

S(~SUT)SE(S~S)(ST)S

(ST)SSTS.可推出

这是ST的充公必要条件,从而结论为真.

对于假命题都可以找到反例,如题(2)中令S{1,2},Tz{1},M{2}即可;而对于题(5),只要S即可.

3.9 (2),(3)和(4)为真,其余为假.

3.10 (1) A{0,1,2}.

(2) A{1,2,3,4,5}

(3) A{1}

(4)A{0,0,0,11,0,0,2,1,1,2,0,0,3,

1,2,2,1,3,00,4,1,3,2,3,2,2,3,1,4,0}

3.11 (1) ac或 cb

(2) 任何a,b

(3) bcd

(4) abc

(5) ac且b{}.

3.12 (1),(2)和(6)都是BA,而(3),(4),(5)是A=B. 分析对于用谓词给定的集合先尽量用列元素的方法表示,然后进行集合之间包含关系的判别.如果有的集合不能列元素,也要先对谓词表示尽可能化简.如题(3)中的A可化简为

{x|xNx2};

题(5)中的A和B都可以化简为{1,2};题(6)中的

而对于题(4),不难看出A=B=R,是实数集合.

3.13 (1) AB{{a,b},c,d},AB{c}. A{x|xN2x12},B{1,2

AB{{a,b}}, AB{{a,b}},d}.

(2) AB{{a{b}},c,{c},{a,b},{b}}.

AB{{a,b},c}, AB{{a,{b}},{c}},

AB{{a{b},{c},{b}}.

(3) ABN,AB{2},AB{0,1}

ABN{2}

(4)观察到BA,故

ABA,ABB,ABAB{x|xRZx1}.

(5) 观察到AB,故

ABZ{0,1}

ABAAB ABN{0,1}

3.14 (1) P(A){,{}}.

(2) P(A){,{{1}},{1},{{1},1}}.

(3) P(A){,{},{{1}},{{2}},{{1,2}},{{2}},{{2}},{,{1,2}},

{{1},{2}},{{1},{1,2}},{{2},{1,2}},{{2},{1,2}},{,{1},{2}} {,{1},{2}},{{1},{1,2}},{,{2},{1,2}},{{1},{2}{1,2}},

{,{1},{2},{1,2}}}.

(4) P(A){,{{1}},{{1,2}},{{1}},{{1,2}}

(5) P(A){,{1},{1},{2},{1,1},{1,2}{1,2}{1,1,2}.

分析在做集合运算前先要化简集合,然后再根据题目要求进行计算.这里的化简指的是元素,谓词表示和集合公式三种化简.

元素的化简——相同的元素只保留一个，去掉所有冗余的元素。

谓词表示的化简——去掉冗余的谓词，这在前边的题解中已经用到。

集合公工的化简——利用简单的集合公式代替相等的复杂公式。这种化简常涉及到集合间包含或相等关系的判别。

例如，题（4）中的A{{1,1},{2,1},{1,2,1}}化简后得A{{1},{1,2}}，而题（

352）中的化A{x|xRx2xx20}

简为A{1,1,2}。

3．15

3．16 （1），（2），（3）和（6）为真。（4）和（5）不为真。

分析

如果给出的是集合恒等式，可以用两种方法验

证。一是分别对等式两边的集合画出文氏图，然后检查两个图中的阴影区域是否一致。二是利用集合恒等式的代入不断对等式两边的集合公式进行化简或者变形，直到两边相等或者一边是另一边的子集为止。例如，题（1）中的等式左边经恒等变形后可得到等式右边，即

(AB)C(AB)~C

(A~C)(B~C)(AC)(BC)

类似地，对题（2）和（3）中的等式分别有

AB(BC)A~(B~C)

A(~BC)(A~B)(AC)

(AB)AC)

A(BC)(AB)(AC)

(AB)(A~C)((AB)A)~C

(AB)~C(AB)C

但对于等式（4），左边经变形后得

(ABC)(AB)((AB)(AB))(C(AB))

=(C(AB))C(AB).

易见，C(AB)C,但不一定有C(AB)C.如令ABC{1}.时，等式（4）不为真。类假地，等式（5）的左边经化简后得(AC)B，而(AC)B不一定恒等于A-C。

3．17 （1）不为真。（2），（3）和（4）都为真。对于题（1）举反例如下：令A{1},

A{1},B{1,4},C{2},D{2,3},则AB且CB，但ACBD，与结论矛盾。

分析（2）由于CD~D~C,又由AB可得AC~DB~C,即ADBC成立。

（3）由于A(BA)AB，故有

BA(BA)BABAB。

这里用到

AB.AB的充要条件为BAB或BAB或

（4）易见，当A=B成立时，必有A-B=B-A。反之，由A-B=B-A得

(AB)B(BA)B

化简后得BA，即BA，同理，可证出AB，从而得到A=B。

3．18 由|P(B)|64可知|B|=6。又由|P(AB)|256知|AB|8，代入包含排斥原理得

836|AB|,

从而有|AB|1,|AB|2,|AB|257.

3．19 令S{x|xN1x1000000}.

A{x|xSx是完全平方数}，

B{x|xSx是完全立方数}，

从而有|S|1000000

原理得 ,|A|1000,|B|100,|AB|10.代入包含排斥

|AB||S|(|A||B|)|AB|

1000000(1000100)10

=998910