离散数学(第三版)课后习题答案 下载本文

内容发布更新时间 : 2024/3/29 1:50:39星期一 下面是文章的全部内容请认真阅读。

精品文档

?A′∪B=(A∪A′)∪B (∪的交换律) ?A′∪B=X∪B (互补律) ?A′∪B=X (零壹律)

方法三:因为A′?X且B?X,所以根据定理2的3?)就有A′∪B?X;

另一方面,由于B?A′∪B 及根据换质位律可得B′?A′?A′∪B,因此,由互补律及再次应用定理2的3?),可得X=B∪B′?A′∪B,即X?A′∪B;

所以,A′∪B=X。 (2)次证A′∪B=X?A∩B′=?;

A′∪B=X?(A′∪B)′=X′ (两边同时取补运算′)

?(A′)′∩B′=X′ (de Morgan律) ?A∩B′=X′ (反身律) ?A∩B′=X′ (零壹律)

(3)再证A∩B′=??A?B;

方法一:A=A∩X (零壹律)

=A∩(B∪B′) (互补律) =(A∩B)∪(A∩B′) (分配律) =(A∩B)∪? (条件A∩B′=?) =A∩B (零壹律) ?B (定理2的3))

方法二:A∩B′=??B=B∪? (零壹律)

=B∪(A∩B′) (条件A∩B′=?) =(B∪A)∩(B∪B′) (分配律) =(A∪B)∩(B∪B′) (∪的交换律) =(A∪B)∩X (互补律) =A∪B (零壹律) ?A?B (定理4的2))

10. 对于任意集合A,B,C,下列各式是否成立,为什么?

1) A∪B=A∪C?B=C 2) A∩B=A∩C?B=C

[解] 1)不一定。例如:A={a},B={a,b},C={b}。显然有

A∪B=A∪C,但B≠C。

2)不一定。例如:A={a},B={a,b},C={b,c}。显然有

.

精品文档

A∩B=A∩C,但B≠C。

11.设A,B为集合,给出下列等式成立的充分必要条件:

1) A\\B=B 2) A\\B=B\\A 3) A∩B=A∪B 4) A?B=A

[解] 1)A\\B=A∩B′,由假设可知A\\B=B,即A∩B′=B。由此可知B=A∩B′?B′,

故此B=B∩B′=?。

由假设可知A=A\\?=A\\B=B=?。所以当A\\B=B时有A=B=??。 反之,当A=B=?时,显然A\\B=B。 因此A\\B=B的充分必要条件是A=B=?。

2)设A\\B≠∈?,则有元素a∈A\\B,那么,a∈A,而由假设A\\B=B\\A。所以a∈B\\A,从而a?A,矛盾。所以A\\B=,故A?B。另一方面由B\\A=A\\B=?。可得B?A。因此当A\\B=B\\A时,有A=B。 反之,当A=B时,显然A\\B=B\\A=? 因此,A\\B=B\\A的充要条件是A=B。

3)由于A∪B=A∩B,从而A?A∪B=A∩B?B,以及B?A∪B=A∩B?A故此A∪B=A∩B,有A=B。

5) 根据定理6的1)有A??=A,由已知条件A?B=A,可得A?B=A??。 从而由对称差的消去律可得B=?。 反之,若B=?,则A?B=A??=A。 所以A?B=A的充分必要条件为B=?。 12. 对下列集合,画出其文图:

1) A′∩B′ 2) A\\(B∪C)′ 3) A∩(B′∪C) [解]

.

A B X B A C X A B C X A′∩ B′

A \\ (B∪ C ) ′ A∩ (B′∪ C )

精品文档

13. 用公式表示出下面图中的阴影部分 [解]

14. 试用成员表法证明

1)(A?B)?C=A(B?C) 2)(A∪B)∩(B∪C)?AB′ [解] 1)成员表如下 A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 10 1 1 1

成员表中运算结果?C及A?(B?C)的两列状态表明,全集中的每一个体对它俩有相同的从属关系,故 (A?B)?C=A?(B?C) 1) 成员表如下:

A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 10 1 1 1

.

x A C (A∩C) \\B

B A

C B

x

(A∪B∪C)∪(A∩B∩C)′

A?B 0 0 1 1 1 1 0 0 (A?B)?C 0 1 1 0 1 0 0 1 B?C 0 1 1 0 0 1 1 0 A?(B?C) 0 1 1 0 1 0 0 1 A∪B (B∪C) (B∪C)′ 1 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 (A∪B)∩(B∪C)′ 0 0 0 0 1 0 0 0 B′ 1 1 0 0 1 1 0 0 A∩B′ 0 0 0 0 1 1 0 0 精品文档

成员表中运算结果(A∪B)∩(B∪C)′及A∩B′的两列状态表明,全集中的每一个体,凡是从属(A∪B)∩(B∪C)′的,都从属A∩B′,故 (A∪B)∩(B∪C)′?A∩B

注:自然数集N取为{1,2,3,……,n,……}

.

精品文档

习题二(第二章 关系)

1.设A={1,2,3,},B={a,b}求

1)A×B 2)B×A 3)B×B 4)2B×B [解] 1)A×B={(1,a),(1,b),(2,a),(2,a),(3,a),(3,b)}

2)B×A={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)} 3)B×B={(a,a),(a,b),(b,a),(b,b)} 4)2B={?,{a},{b},{a,b}}

2B×B{(?,{a}),(?,b),({a},a),({a},b),({b},a),({b},b),({a,b},b)}

2.使A?A×A成立的集合A存在吗?请阐明理由。

[解] 一般地说,使A?A×A成立的集合A不存在,除非A=?。

否则 A≠?,则存在元素x∈A×A,故有y1,y2∈A,使x=(y1,y2),从而y1,y2∈A×A,故此有y1,y2,y3,y4,使y1=(y1,y2),y2=(y3,y4),……。这说明A中每个元素x,其结构为元组的无穷次嵌套构成,这不可能。我们讨论的元素的结构必须是由元组的有限次嵌套构成。 3.证明A×B=B×A?A=?∨B=?∨A=B

[证] 必要性:即证A×B=B×A?A=?∨B=?∨A=B

若A×B=?,则A=?或者B=?

若A×B≠?,则A≠?且B≠?,因此对任何x∈A及任何y∈B就有(x,y)∈A×B,根据A×B=B×A,可得(x,y)∈B×A,故此可得x∈B,y∈A,因此而得A?B且B?A,所以由?的反对称性A=B。

充分性:即证A=?∨B=?∨A=B?A×B=B×A 这是显然的。 4.证明(A∩B)×(C∩D)=(A×C)∩(B×D)

[证]证法一:(元素法)对任一(x,y)∈(A∩B)×(C∩D) 有x∈A∩B,y∈C∩D,于是x∈A,x∈B,y∈C,y∈D。因而(x,y)∈A×C,且(x,y)∈B×D,所以(x,y)∈(A×C)∩(B×D)。因而(A∩B)×(C∩D)?(A×C)∩(B×D)

另一方面,对任一(x,y)∈(A×C)∩(B×D),于是有(x,y)∈A×C且(x,y)∈B×D,因而x∈A,y∈C,x∈B y∈D。所以x∈A∩B,y∈(C∩D)。所以(x,y)∈(A∩B)×(C∩D)。因而(A×C)∩(B×D)?(A∩B)×(C∩D)。

.