离散数学专科期末复习提要.doc

1

四川电大孙继荣

2004年5月

《离散数学》是四川电大数学与应用数学专业开设的课程。使用的教材为中央电大出版

的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。

离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象

思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：

高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。

1、集合论部分（集合的基本概念和运算、关系及其性质）；

2、数理逻辑部分（命题逻辑、谓词逻辑）；

3、图论部分（图的基本概念、树及其性质）。

4、布尔代数（此部分对专科要求不高）

离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和

图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。

各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是

能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。

[复习知识点]

1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集

2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、DeMorgan

律龋氖希╒enn）图

3、序偶与迪卡尔积

本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明

[复习要求]

1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。

2、掌握集合的表示法和集合的交、并、差、补等基本运算。

3、掌握集合运算基本规律，证明集合等式的方法。

4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。

[疑难解析]

1、集合的概念

因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以

掌握，一是掌握幂集的构成，一是掌握幂集元数为2

n

。

2、集合恒等式的证明

2

通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章

命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，

尤其要求学生重视吸收律和重要等价式在BABA~???证明中的特殊作用。

[例题分析]

例1设A，B是两个集合，A={1，2，3}，B={1，2}，则??)()(BA??。

解}}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(???A

}}2,1{},2{},1{,{)(???B

于是}}3,2,1{},3,2{},3,1{},3{{)()(??BA??

例2设??????,,,,babaA，试求：

(1)??baA,?；(2)??A；(3)????A；

(4)????Aba?,；(5)A??；(6)??A??。

解(1)?????????,,,babaA(2)AA???(3)??????babaA,,,???

(4)???????Aba,(5)????A(6)??????A

例3试证明????????BABABABA~~~~???????

证明

????????????

????????????

????????

????BABA

BABA

BBBAABAA

BBAABABABA

~~

~~

~~~~

~~~~~

????

????????

????????

?????????

[复习知识点]

1、关系、关系矩阵与关系图

2、复合关系与逆关系

3、关系的性质（自反性、对称性、反对称性、传递性）

4、关系的闭包（自反闭包、对称闭包、传递闭包）

5、等价关系与等价类

6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界

7、函数及其性质（单射、满射、双射）

8、复合函数与反函数

本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射

的概念

3

[复习要求]

1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩

阵和关系图、关系的运算。

2、掌握求复合关系与逆关系的方法。

3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、

图）。

4、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。

5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/

小元、最大/小元、上/下界、最小上界、最大下界的求法。

6、理解函数概念：函数、函数相等、复合函数和反函数。

7、理解单射、满