精品文档

.

离散数学辅助教材

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

第一部分

集合论

刘国荣

交大电信学院计算机系

精品文档

离散数学习题解答

习题一 （第一章集合）

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 （∪的结合律）

.