二、考试参考书目：左孝凌编《离散数学》，上海科技文献出版社 1982年9月第一版

　　三、考试方式：考试采用笔试方式。考试时间为120分钟，试卷满分为100分。

　　四、考查的知识范围：

　　1、前言离散数学课程研究生入学考试主要测试考生对该门课程的掌握情况。考试分两方面进行测试：一是测试考生对该门课程的基本概念、基本理论的掌握情况；二是测试考生对该门课程的综合应用能力。从而对考生产生一个较全面的评价。

　　2、题型说明离散数学课程考试采用闭卷考试。题型为选择题、填空题、简答题和证明题。其中各题所占比例为：

　　3、考试内容：

　　第一章   命题逻辑

　　一、命题的概念、联结词及命题公式（次重点）

　　识记：命题、原子命题、复合命题、命题的真值、命题公式的递归定义等概念。

　　理解：五种逻辑联结词的定义、真值表、命题公式的类型及命题公式的等价式与蕴涵式。

　　应用：命题的符号化与翻译、构造真值表证明命题公式的等价、不构造真值表证明蕴涵式与等价式及命题公式的化简。

　　二、命题公式的主范式表示（重点）

　　识记：大项、小项的概念。

　　理解：命题公式的主析取范式、主合取范式的概念及二者的联系。

　　应用：命题公式的主析取范式、主合取范式的求法。

　　三、命题演算的推理理论（重点）

　　识记：P规则、T规则、CP规则。

　　理解：推理证明的直接证法和间接证法的应用条件。

　　应用：推理证明的直接证法和间接证法。

　　第二章    谓词演算一、n元谓词与量词（一般）

　　识记：客体、个体域、全总个体域、谓词、命题函数、n元谓词、全称量词、存在量词、量词的辖域、约束变元、自由变元等概念。

　　二、谓词公式及其翻译、谓词演算的等价式与蕴涵式（次重点）

　　识记：谓词公式及谓词公式的赋值的概念、理解：前束范式及谓词演算的等价式与蕴涵式。

　　应用：谓词公式的翻译，求公式的前束范式。

　　三、谓词演算的推理理论（重点）

　　识记：谓词演算的US规则、UG规则、ES规则、EG规则。

　　应用： 应用US规则、UG规则、ES规则、EG规则进行谓词演算的推理证明。

　　第三章    集合与关系一、集合的概念与运算（一般）

　　识记：集合的概念及其交、并、补和对称差运算。

　　理解：集合的幂集的概念。

　　应用：集合的幂集的求法。

　　二、关系的概念及性质（次重点）

　　识记：序偶与笛卡尔积的概念。

　　理解：关系的概念及其表示、关系的性质；复合关系与逆关系的概念。

　　应用：关系的性质的判定、复合关系与逆关系的求法。

　　三、关系的闭包运算（次重点）

　　理解：关系的矩阵表示；关系的自反闭包、对称闭包、传递闭包的概念。

　　应用：自反闭包、对称闭包、传递闭包求法。

　　四、等价关系与划分（重点）

　　理解：划分、等价关系、等价类及商集的概念；等价关系与划分之间的联系。

　　应用：  给定集合A上的等价关系R确定集合A的划分（或A关于R的商集）及给定集合A的划分确定集合A上的等价关系。

　　五、偏序关系（重点）

　　理解：偏序关系、偏序集的概念及其哈斯图表示；偏序集中的特殊元素。

　　应用：会证明一个关系是偏序关系；会画偏序关系的哈斯图；会求偏序集中的特殊元素。

　　六、相容关系（一般）

　　识记：覆盖、相容关系及最大相容类的概念。

　　理解：相容关系与覆盖之间的联系。

　　第四章    函数一、函数（重点）

　　识记：函数的前域、函数的值域、函数的相等。

　　理解：函数、入射、满射、双射、复合函数和逆函数的概念及其性质；函数与一般关系、逆函数与逆关系的区别。

　　应用：会证明一个函数是入射、满射、双射。

　　二、 集合的基数（一般）

　　识记：集合的基数、可数集和不可数集的概念及集合基数的比较。

　　第五章 代数结构一、代数系统及运算（次重点）

　　识记：代数运算的概念与性质。

　　理解：代数系统中的幺元、零元、逆元及其性质。

　　应用：求代数系统中的幺元、零元、逆元。

　　二、群与子群（重点）

　　理解：半群、独异点、群、子群、交换群、循环群、循环群的生成元的概念及其性质。

　　应用：会证明一个代数系统构成独异点、群、交换群。

　　三、代数系统的同构（重点）

　　理解：两个代数系统同构的概念。

　　应用：会证明两个代数系统同构。

　　四、环与域（一般）

　　识记：环与域的概念。

　　第六章 格与布尔代数

　　一、 格的概念（重点）

　　识记：格对偶原理。

　　理解：格与格所诱导的代数系统、子格的概念及格的基本性质。

　　应用：会判断一个偏序集是否构成格。

　　二、 几种特殊的格（重点）

　　理解：分配格、有界格、全上（下）界、补元、有补格、等概念；。

　　应用：会判断一个偏序集是否构成分配格、有界格、有补格。

　　三、 布尔代数（重点）

　　识记：原子的概念及关于有限布尔格结构的Stone表示定理。

　　理解：布尔格、原子、布尔代数、布尔表达式及布尔表达式的析（合）取范式等概念。

　　应用：会判定一个偏序集是否构成布尔格；会判定一个代数系统是否构成布尔代数；会求布尔表达式的析（合）取范式。

　　第五章   图论一、图的基本概念及连通性（重点）

　　识记：图、有向图、无向图、简单图、多重图、零图、完全图等概念。

　　理解：结点的度数、出度及入度等概念；弱连通、单侧连通、强连通等概念。

　　应用：图的结点的度数与边数的关系及其应用；图的连通性的判别。

　　二、图的矩阵表示（次重点）

　　理解：图的邻接矩阵及可达性矩阵的概念及其性质。

　　应用：求图的邻接矩阵及可达性矩阵；根据图的邻接矩阵求结点的度数、出度、入度及由一个结点到另一个结点长度为k的路径的条数。

　　三、Euler图与Hamilton图（次重点）

　　理解：Euler图与Hamilton图的概念及其充分条件和必要条件。

　　应用： Euler图与Hamilton图的判定。

　　四、树及应用（重点）

　　理解：无向树的等价定义、无向图的生成树与最小生成树、根树、m叉树、完全m叉树等概念。

　　应用：最小生成树的Kruscal算法及最优二叉树的构造方法。最小生成树及根树的应用。

　　五、平面图（次重点）

　　理解：平面图的概念、有限平面图面的次数与其边数的关系。

　　应用：会判别一些简单的图是否是平面图。

　　第三部分    有关说明与实施要求

　　考核目标的能力层次表述本课程的考核目标共分为三个能力层次：识记、理解、应用，它们之间是递进等级的关系，后者必须建立在前者基础上。

　　其具体含义为：

　　识记：能知道有关的名词、概念、知识的含义，并能正确认识和表述，是低层次的要求。

　　理解：在识记的基础上，能全面把握基本概念、基本原理、基本方法，能掌握有关概念、原理、方法的区别与联系，是较高层次的要求。

　　应用：在理解的基础上，能运用基本概念、基本原理、基本方法联系学过的多个知识点分析和解决有关的理论问题和实际问题，是最高层次的要求。