2020年硕士研究生入学考试大纲

考试科目名称：离散数学     考试时间：120分钟， 满分：100分

一、考试要求

1．掌握命题逻辑和谓词逻辑中的基本概念、基本定理和证明方法。了解数理逻辑在计算机科学与技术和人工智能中的应用。

2．掌握集合、关系及函数中的基本概念、基本定理和证明方法。了解集合与关系、函数在计算机科学与技术中的应用。。

3．掌握群、环、域和格中的基本概念、基本定理和证明方法。了解群、环、域及布尔代数在计算机科学与技术中的应用。。

4．掌握图、赋权图、欧拉图、哈密顿图、二部图、平面图和树中的基本概念、基本定理和证明方法。理解图论在计算机科学与技术和人工智能中的应用。。

5．能够运用离散数学的知识和技能进行问题的分析与求解，即能对问题进行抽象建模，能熟练使用高级语言（C或C++或MATLAB等）进行模型的具体实现（编程）。

二、考试内容

1．集合与计数

（1）集合的概念及表示

（2）特殊集合（子集合、幂集合、补集合）

（3）集合的运算

（4）计数问题

①基本计数原理

②排列与组合

③容斥原理

（5）集合的应用

2．关系

（1）关系的概念及表示

①序偶与笛卡尔积

②关系的定义

③关系的表示

（2）关系的性质

（3）关系的运算

①基本运算

②复合运算

③逆运算

④幂运算

⑤闭包运算

⑥关系性质运算的封闭性

（4）特殊关系

①等价关系

②相容关系

③偏序关系

（5）关系的应用

3．函数

（1）函数的概念

（2）函数的运算

（3）函数的应用

4．命题逻辑

（1）命题逻辑的基本概念

（2）命题逻辑公式

①命题公式及解释

②命题公式的分类

③命题公式的等值式

④命题公式的范式

（3）命题逻辑推理

①推理的基本概念

②简单证明推理

③构造证明推理

（4）命题逻辑的应用

5．谓词逻辑

（1）谓词逻辑的基本概念

①个体词

②谓词

③函词

④量词

（2）谓词逻辑公式

①谓词逻辑公式及解释

②谓词逻辑公式的分类

③谓词逻辑公式的等值式

④谓词逻辑公式的范式

（3）谓词逻辑推理

（4）谓词逻辑的应用

6．代数系统

（1）代数系统的基本概念

（2）代数系统的性质

（3）相互联系的的代数系统

①同构代数系统

②同态代数系统

③商代数系统

7．典型代数系统

（1）半群和群

①半群的定义及性质

②群的定义及性质

③特殊群

④群的应用

（2）环和域

①环的定义及性质

②域的定义及性质

③域的应用

（3）格和布尔代数

①格的定义及性质

②特殊格

③布尔代数的概念及性质

④格的应用

8．图

（1）图的概念与表示

①基本概念

②图的连通性

③图的操作

④图的表示

（2）赋权图

①赋权图的定义

②最短通路问题

（3）欧拉图

①欧拉图的定义

②欧拉图的判定

③中国邮路问题

（4）哈密顿图

①哈密顿图的定义

②哈密顿图的判定

③货郎担问题

（5）二部图

①二部图的定义

②二部图的判定

③匹配问题

（6）平面图

①平面图的定义

②平面图的判定

③图的着色问题

9．树

（1）无向树

①基本概念

②生成树

③最小生成树问题

（2）有向树

①基本概念

②根树

③二叉树

④最优树问题

三、参考书目

1. 离散数学. 古天龙、常亮编著. 北京：清华大学出版社.2012.7

2. 离散数学（第2版）.屈婉玲、耿素云、张立昂编著. 北京：高等教育出版社. 2015.3

3. 离散数学教程. 王元元 等编著. 北京：高等教育出版社.2010.7