一、考试科目：离散数学

二、基本要求

离散数学的基本概念、基本理论和基本算法。主要内容包括命题逻辑、谓词逻辑、集合与关系、函数、图论等知识。在内容的组织上，力求提供培养学生抽象思维、慎密概括和严密的逻辑推理能力知识的同时，注重展现离散数学在计算机科学及信息科学中的应用。

三、考试范围

1、命题逻辑的基本概念、理论及方法

（1）理解命题的概念，掌握常用的命题联结词。

（2） 理解命题的合式公式概念，会用真值表来判别公式的真假。

（3） 知道公式的等价关系和蕴含关系,会利用真值表和常用的基本等值式作等值演算。

（4）会用真值表法及等值演算求合式公式的主析取范式和主合取范式。

（5）知道命题演算的推理理论，掌握直接证明、条件证明、反证法，能进行一些简单推理。

2、谓词逻辑的基本概念、理论及方法

（1）熟悉一阶谓词逻辑的谓词、量词等概念。知道谓词公式的概念。

（2） 知道谓词演算中关于量词的等值式。

（3） 熟悉常见谓词演算的基本规则；掌握谓词演算的推理理论。。

3、集合论的基本概念、理论及方法。

（1）理解集合的概念，掌握集合和元素间的关系。

（2） 熟悉集合与集合之间的关系（相等、包含）。

（3）熟练掌握集合之间的运算及基本运算规律。

（4）掌握幂集及笛卡尔积的计算。

4、关系与函数的基本概念、理论及方法。

（1）理解关系的基本概念，掌握关系的图及其矩阵表示方法。

（2）掌握关系的运算，理解关系的几种特性。

（3）掌握关系的闭包运算。

（4）了解函数的基本概念，掌握复合函数、逆函数的计算。

（5）了解基数、无限集合的理解和区分

（6）理解等价关系、等价类、商集、会根据等价关系求等价类,理解并掌握等价关系与集合划分之间的重要关系会求出等价关系所产生的一个集合的划分。

（7）偏序关系的概念，会用哈斯图表示偏序关系

5、图的基本理论

（1）理解图的基本概念；

（2）理解图同构。

（3）掌握通路和回路的概念。

（4）掌握图的矩阵表示法（邻接矩阵、关联矩阵）。

（5） 理解图的连通性，掌握连通性的判别方法，对简单有向图会判断强连通、单向连通还是弱连通。能熟练地求图的点割集、边割集，割点、割边。

（6）了解权图中的最短路问题及一些算法。

6、特殊图基本概念、理论及方法。

（1）理解欧拉图、欧拉通路、欧拉回路的概念

（2）知道哈密顿图的概念及哈密顿图与欧拉图的区别，掌握相关的重要结论，会判断一个图是否是欧拉图或哈密顿图。

（3）理解二分图的概念,会求最大匹配.

（4）了解平面图的基本概念，掌握欧拉公式，了解相关的重要结论。

（5）了解平面图的点着色, 了解四色定理。

（6） 理解有向树、生成树、最小生成树的概念，会由连通图来寻找生成树,掌握最小生成树的构造方法。

（7）理解带权树、二元树等概念，掌握Huffman算法，熟悉前缀码及其应用。

三、参考书目

（1）吴明芬，张先勇，朱铁丹等，离散数学，人民邮电出版社，2014，9787115365439

（2）屈婉玲，耿素云，张立昂，离散数学，高等教育出版社，2008，9787040231250