复试《离散数学》科目考试大纲

一、考查目标

理解命题逻辑的基本概念及应用方法；掌握谓词逻辑的基本概念及应用方法；熟练掌握集合、关系函数的基本概念及运算、论证方法；理解代数结构的基本概念及研究方法；掌握图论的概念及应用。

二、考试形式与试卷结构

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

复试科目满分均为100分，考试时间为2小时。

（二）答题方式

答题方式为闭卷、笔试。

（三）试卷内容结构

命题逻辑：20%左右

谓词逻辑：10%左右

集合与关系：20%左右

函数：10%左右

代数系统：15%左右

格：10%左右

图论：15%左右

（四）试卷题型结构

客观题：选择题20%左右，填空题20%左右；

证明30%左右；

综合应用30%左右

三、考查范围

1、命题逻辑

2、谓词逻辑

3、集合与关系

4、函数

5、代数系统

6、格

7、图论

四、考试内容及要求

1.数理逻辑

（1）命题逻辑

1）理解下列基本概念：

命题，联结词，合式公式，真值指派和真值表，永真式、永假式和可满足式，等价式与蕴涵式，规范式。

2)掌握命题符号化的方法；

3)熟练掌握基本等价式和蕴涵式及其应用；

4)理解和掌握推理规则（P、T、CP规则），直接证法和间接证法。

（2）谓词逻辑

1)理解下列基本概念：谓词，量词，变元的约束，谓词公式；

2)能用谓词公式表达自然语句表述命题；

3)熟练掌握基本谓词的演算式和蕴涵式及其应用；

4)理解和掌握谓词演算的推理理论（推论规则US、ES、UG、EG）；

5)了解前束范式。

2.集合、关系与函数

（3）理解下列基本概念：

集合，基数，序偶与笛卡尔集；关系，二元关系，逆关系，复合关系，序关系，关系的性质及闭包，等价关系 ，等价类，覆盖与划分；映射与函数，逆函数，复合函数。

（4）了解可数无限集与不可数无限集的势的概念；

（5）掌握集合运算；

（6）熟练掌握集合相互包含和相等的论证方法；

（7）掌握关系闭包运算；

（8）理解等价关系与划分的内在联系；

（9）能正确区分单（入）射、满射和双射。

3.代数结构

(10)理解下列基本概念：

代数系统，幺元，零元，逆元，同态与同构，同余关系，商代数，积代数；半群，独异点，群（包括Abel群，循环群，置换群），子群，陪集，正规子群，商群，环和域；偏序及哈斯图，格分配格，有补格，布尔代数。

(11)理解拉格郎日定理及其推论；

(12)掌握哈斯图的作法；

(13)了解代数系统的分类及研究方法。

4.图论

(14)理解下列基本概念：

图，结点的度数，路径、回路与连通性，赋权图，欧拉图，哈密尔顿图，平面图，对偶图与着色，树、生成树、根树及最优树。

(15)掌握图的矩阵表示；

(16)掌握赋权图的最短路径求法；

(17)了解和掌握关于平面图的 欧拉公式及其应用；

(18)能求边赋权图的最小生成树；

(19)能将n元树转换为二叉树来表示；

(20)能画出带有一组权值的最优树，并给出哈夫曼编码 。

五、考试用具说明

考生应自带必需的文具，如2B铅笔、蓝（黑）色字迹钢笔、圆珠笔或签字笔。

考生将试题答案写在答题纸上，标清题号，无需抄题。