研究生入学考试《离散数学》考试大纲

一、考查目标

1、掌握命题逻辑与谓词逻辑基本概念，理解逻辑公式等价证明、范式求解、推理证明并能用其解决实际问题；

2、掌握集合、二元关系、函数等基本概念，理解集合的运算、二元关系相关操作、等价关系的性质与构造以及偏序关系的性质与构造并能用其解决实际问题；

3、掌握图论相关概念，理解图的矩阵表示形式、最短路径算法以及欧拉图、哈密顿图、二部图、平面图等特殊图的应用；

4、掌握代数系统的基本概念，理解二元运算封闭性以及特异性元素。

二、考查知识点解析

1、命题逻辑

命题逻辑是以命题为中心研究逻辑问题。要求掌握命题、真值、联结词、命题公式、赋值、等值式、范式、推理形式结构等基本概念。能够判别命题的真值，区分简单命题和复合命题、符号化命题、构造真值表、等值演算、判别公式类型、求解命题公式的主析取范式和主合取范式以及应用直接证明法、附加前提证明法、归谬法进行推理证明。能够运用主范式解决诸如电路设计、任务分派等实际问题，能够运用相关推理证明方法证明结论的有效性。

2、一阶逻辑

在一阶逻辑中，继续对简单命题进行分解，分离出主语和谓语，分别进行符号化，同时引入了量词。要求掌握个体词、谓词、量词、一阶逻辑公式、解释、赋值、一阶逻辑等值式、置换规则、前述范式等基本概念。能够对含有量词的命题进行符号化、确定量词的辖域、区分个体变元的两种出现形式（自由变元和约束变元）、根据解释与赋值判别谓词公式真值、判别谓词公式类型，判别谓词公式的是否等值、求解谓词公式的前束范式。能够运用相关推理证明方法证明结论的有效性。

3、集合代数

集合是一个不能精确定义的概念。要求掌握集合、集合运算、集合恒等式等基本概念。能够利用枚举法、谓词法、树形结构等方法表示集合，理解集合的交运算、并运算、补运算、差运算以及对称差运算，理解子集、真子集、相等三种集合之间的关系，能够利用基本恒等式、集合相等的定义证明新的恒等式，能够利用文氏图、包含排斥定理解决有穷集计数问题。

4、二元关系和函数

二元关系是一种特殊的集合，函数是一种特殊的二元关系。要求掌握有序对、笛卡尔积、二元关系、关系运算、关系性质、关系闭包、等价关系、偏序关系、函数、复合函数、反函数等基本概念。能够利用关系图、关系矩阵表示二元关系，能够判断二元关系具有的性质并正确求解关系的自反、对称和传递闭包，理解等价关系具有的性质、关系图、关系矩阵具有的特点，能够根据等价关系得到集合的一种划分同时能够根据集合的划分构造等价关系，理解偏序关系具有的性质，能够画出偏序关系的哈斯图同时根据哈斯图计算偏序关系中的特殊元素。

5、图的基本概念

图是一种重要的数据结构。要求掌握有向图、无向图、度、完全图、补图、简单图、多重图、同构、通路、回路等基本概念。理解握手定理、简单图的判别条件，能够判断给出的一个整数序列是否能做图、简单图的度数序列，能够正确判断区分简单通路、简单回路、初级通路以及初级回路，能够利用邻接矩阵、关联矩阵、可达矩阵表示图，能够根据邻接矩阵构造可达矩阵。

6、特殊的图

特殊的图包括欧拉图、哈密顿图、平面图以及二部图。要求掌握欧拉通路、欧拉回路、哈密顿通路、哈密顿回路，平面图、二部图等相关概念。理解欧拉通路、欧拉回路的判别条件，并能用其解决手机解锁图案、一笔画等实际问题，理解哈密顿通路、哈密顿回路的判别条件，并能用其解决实际问题，理解平面图中点、线、面之间的关系，能够画出平面图的对偶图，理解二部图的判别条件、完备匹配、完美匹配的判别条件并能用其解决实际问题，理解最短路径算法并能用其解决实际问题。

7、代数系统

近似代数也称为抽象代数，代数系统是由集合以及集合上的运算构成。要求掌握二元运算与性质、代数系统、特异性元素等基本概念。能够判别给出的运算是否具有封闭性、交换律、结合律等性质，能够正确计算二元运算的特异性元素，包括单位元、零元以及逆元。

三、教材选择

《离散数学（第2版）》，屈婉玲、耿素云、张立昂编著，高等教育出版社。

考试分值为100分，考试时间为120分钟。