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
