2019年硕士研究生招生考试

初试离散数学科目考试大纲

一、考查目标

离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。考核的内容是计算机专业需要的重要基础部分，包括：

1. 数理逻辑部分，要求掌握命题及其表示法、连接词、重言式与蕴含式、对偶与范式、推理证明、谓词逻辑等；

2. 集合论部分，要求掌握关系及其表示、复合关系和逆关系、集合的划分和覆盖、等价关系与等价类、特征函数与模糊子集、可数集与不可数集等；

3. 代数结构部分，要求掌握群、环和域、阿贝尔群和循环群、置换群、陪集与拉格朗日定理、同态与同构等；

4. 布尔代数部分，要求掌握格、布尔代数、布尔表达式等；

5. 图论部分，要求掌握图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、树等；

二、考核形式与试卷结构

（一）试卷满分及考试时间

满分为150分，考试时间为3小时。

（二）答题方式

答题方式为闭卷、笔试。

（三）试卷内容结构

客观题，包括判断题、填空题、选择填空题。主观题，包括计算题和证明题。其中：

数理逻辑和集合论部分（65分）

代数结构和布尔代数部分（50分）

图论部分（35分）

（四）试卷题型结构

客观题40分，计算题和证明题110分。

其中：

选择、判断和填空题（30分）

简答题（10分）

计算题（70分）

证明题（40分）

三、考查内容及要求

（一）数理逻辑

1. 命题逻辑

2. 谓词逻辑

（二）集合论

1. 集合与关系

2. 函数

（三）代数系统

1. 代数结构

2. 格与布尔代数

（四）图论

四、考试用具说明

考试使用黑色笔作答。

五、参考书目

1. 左孝凌、李为鑑、 刘永才编，《离散数学》，上海科学技术文献出版社，1982年9月。

2.袁崇义译，《离散数学》，机械工业出版社，2011年7月。

3.屈婉玲等编，《离散数学》，清华大学大学出版社，2008年2月。

4.谢美萍等，《离散数学》（第二版），清华大学出版社，2014年3月。