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

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

精品文档

.

离散数学辅助教材

概念分析结构思想与推理证明

第一部分

集合论

刘国荣

交大电信学院计算机系

精品文档

离散数学习题解答

习题一 (第一章集合)

1. 列出下述集合的全部元素:

1)A={x | x ∈N∧x是偶数∧ x<15}

2)B={x|x∈N∧4+x=3} 3)C={x|x是十进制的数字} [解] 1)A={2,4,6,8,10,12,14}

2)B=?

3)C={0,1,2,3,4,5,6,7,8,9} 2. 用谓词法表示下列集合:

1){奇整数集合}

2){小于7的非负整数集合}

3){3,5,7,11,13,17,19,23,29} [解] 1){n?n?I?(?m?I)(n=2m+1)};

2){n?n?I?n?0?n<7};

3){p?p?N?p>2?p<30??(?d?N)(d?1?d?p?(?k?N)(p=k?d))}。 3. 确定下列各命题的真假性: 1)??? 2)?∈? 3)??{?} 4)?∈{?}

5){a,b}?{a,b,c,{a,b,c}} 6){a,b}∈(a,b,c,{a,b,c}) 7){a,b}?{a,b,{{a,b,}}} 8){a,b}∈{a,b,{{a,b,}}} [解]1)真。因为空集是任意集合的子集; 2)假。因为空集不含任何元素; 3)真。因为空集是任意集合的子集; 4)真。因为?是集合{?}的元素;

5)真。因为{a,b}是集合{a,b,c,{a,b,c}}的子集; 6)假。因为{a,b}不是集合{a,b,c,{a,b,c}}的元素;

.

精品文档

7)真。因为{a,b}是集合{a,b,{{a,b}}}的子集; 8)假。因为{a,b}不是集合{a,b,{{a,b}}}的元素。 4. 对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B∈C,则A∈C。 2)如果A∈B∧B∈C,则A∈C。 3)如果A?B∧B∈C,则A∈C。

[解] 1)假。例如A={a},B={a,b},C={{a},{b}},从而A∈B∧B∈C但A∈C。 2)假。例如A={a},B={a,{a}},C={{a},{{a}}},从而A∈B∧B∈C,但、A

∈C。

3)假。例如A={a},B={a,b},C={{a},a,b},从而ACB∧B∈C,但A∈C。 .5.对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B?C,则A∈C。 2)如果A∈B∧B?C,则A?C。 3)如果A?B∧B∈C,则A∈C。 3)如果A?B∧B∈C,则A?C。

[解] 1)真。因为B?C??x(x∈B?x∈C),因此A∈B?A∈C。

2)假。例如A={a},B={{a},{b}},C={{a},{b},{c}}从而A∈B∧B?C,但

A?C。

3)假。例如A={a},B={{a,b}},C={{a,{a,b}},从而A?B∧B∈C,但A?C。 4)假。例如A={a},B={{a,b}},C={{a,b},b},从而A?B∧B∈C,但A?C。 6.求下列集合的幂集:

1){a,b,c} 2){a,{b,c}} 3){?} 4){?,{?}}

5){{a,b},{a,a,b},{a,b,a,b}}

[解] 1){?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

2){,{a},{{b,c}},{a,{a,b}}} 3){?,{?}}

4){?,{?},{{?}},{?,{?}}} 5){?,{{a,b}}}

7.给定自然数集合N的下列子集:

.

精品文档

A={1,2,7,8} B={ x|x2<50}

C={x|x可以被3整除且0≤x≤30} D={x|x=2K,K∈I∧O≤K≤6} 列出下面集合的元素: 1) A∪B∪C∪D 2) A∩B∩C∩D 3) B\\(A∪C) 4) (A′∩B)∪D

[解] 因为B={1,2,3,4,5,6,7},C={3,6,9,12,15,18,21,24,27,30},

D={1,2,4,8,16,32,64,},故此

1)A∪B∪C∪D={1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,

30,32,64}

2)A∩B∩C∩D=? 3)B\\(A∪C)={4,5}

4)(A′∩B)∪D={1,2,3,4,5,6,7,8,16,32,64} 8.设A、B、C是集合,证明:

1)(A\\B)=A\\(B\\C)

2)(A\\B)\\C=(A\\C)\\(B\\C) 3)(A\\B)\\C=(A\\C)\\B [证明] 1)方法一:(A\\B)\\C

=(A∩B′)∩C′ (差集的定义) =A∩(B′∩C′) (交运算的结合律) =A∩(B∪C)′ (deMorgan律) =A\\(B∪C) (差集的定义) 方法二:对任一元素x∈(A\\B)\\C,则x?C,同时,x∈A\\B,x∈A,x?B,

所以,x∈A,x?B∪C,即x∈A\\(B∪C),由此可见(A\\B)\\C?A\\(B∪C)。 反之,对任一元素x∈A\\(B∪C),则x∈A,且x?B∪C,也就是说x?A,x?B,x?C。所以x∈(A\\B)\\C,由此可见A\\(B∪C)?(A\\B)\\C。 因此A\\(B\\C)。 2)方法一:(A\\B)\\C

=A\\(B∪C) (根据1))

.

精品文档

=A\\(C∪B) (并运算交换律) =A\\((C∪B)∩Ⅹ) (0—1律) =A\\((C∪B)∩(C∪C′)) (0—1律) =A\\(C∪(B∩C′) (分配律) =(A\\C)\\(B∩C′) (根据1) =(A\\C)\\(B∩C) (差集的定义) 方法二:对任一元素x∈(A\\B)\\C,可知x∈A,x?B,x?C,x∈A\\C。又由x?B,x?B\\C,x∈(A\\C)\\(B\\C)\\(B\\C)。所以(A\\B)\\C?(A\\C)\\(B\\C)。 反之,对任x∈(A\\C)\\(B\\C),可知x∈A\\C,x?B\\C。由x∈A\\C,可知x∈A, x?C。又因为x?B\\C及x?C,可知x?B。所以,x∈(A\\B)\\C。因此(A\\B)\\C?(A\\B)\\C。

由此可得(A\\B)\\(B\\C)?(A\\B)\\C。

3)方法一:(A\\C)\\C

=A\\(B∪C) (根据1)) =A\\(C∪B) (并运算交换律) =(A\\C)\\B (根据1))

方法二:对任一元素x∈(A\\B)\\C,可知x∈A,x?B,x?C。由为x∈A,x?C,所以,x∈A\\C。又由x?B,x∈(A\\C)\\B。所以,(A\\B)\\C?(A\\C)\\B。 同理可证得 (A\\C)\\B?(A\\B)\\C。 9. 设A、B是Ⅹ全集的子集,证明: A?B?A′∪B=X?A∩B′=? [解](采用循环证法) (1)先证A?B?A′∪B=X;

方法一:A′∪B=A′∪(A∪B) (因为条件A?B及定理4)

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

方法二:A?B?A∪B=B (定理4)

?B=A∪B (等号=的对称性) ?A′∪B=A′∪(A∪B) (两边同时左并上A′) ?A′∪B==(A′∪A)∪B (∪的结合律)

.