2012年研究生入学考试自命题科目

《离散数学》考试大纲

第一部分  考试说明

一、考试性质

离散数学是计算机科学与技术学院硕士生入学选考的自命题数学课程之一。考试对象为参加本校计算机科学与技术学院全国硕士研究生入学考试的准考考生。

二、考试形式与试卷结构

（一）答卷方式：闭卷，笔试

（二）答题时间：180分钟

（三）考试题型及比例（满分150分）：

选择题                   20%

填空题              20%

计算题                      30%

证明题              30%

第二部分  考查要点

（一）数理逻辑

命题逻辑：逻辑与证明，命题和命题连接词，命题公式，命题公式的等值关系和蕴涵关系，范式，命题演算的推理理论。

谓词逻辑：谓词、个体和量词，谓词演算公式，谓词演算的永真公式，前束范式，谓词演算的推理理论。

（二）集合论

集合：集合的基本概念，集合的运算，有序对与笛卡儿积，包含排斥原理。

关系：关系及其表示，关系的运算，关系的性质，等价关系，偏序关系。

函数：函数的概念，复合函数和逆函数，集合的特征函数，集合的基数。

（三）代数结构

代数结构：二元运算及其性质，代数系统，特殊元，同态和同构。

群：半群和独异点，群的定义，群的性质，子群及其陪集，正规子群与满同态。

格：格的基本概念，格的性质。

（四）图论

图的基本概念、图的矩阵表示、图的连通性、欧拉图和哈密尔顿图、树、二叉树、有向树、二部图、平面图、有向图。

第三部分  考试样题（略）