离 散 数 学
教 学 内 容
第一章 集合
要点：集合的基本概念。集合的基本运算。集合恒等式。
要求：
null 能够正确表示集合。
null 熟练掌握集合的基本运算。
null 掌握证明集合恒等式或包含关系的方法。
第二章 二元关系
要点：集合的笛卡尔积和二元关系，关系的运算，关系的性质，关系的闭包，等价关系
和偏序关系
要求：
null 熟练掌握二元关系的多种表示方法。
null 熟练掌握关系的定义域、值域、逆、合成、限制、像、幂、闭包的计算方法。
null 能够证明含有关系运算的集合恒等式。
null 熟练掌握判断关系五种性质的方法，能证明关系的性质。
null 深刻理解等价关系、等价类、商集、划分、偏序关系、偏序集、哈斯图、偏序集
中的特定元素等概念，并能熟练地求出等价关系的等价类、商集、偏序关系的哈
斯图及特定元素。
第三章 函数
要点：函数定义、函数性质、函数运算
要求：
null 理解函数、集合 A 到 B 的函数、B
A
、函数的像、完全原像的概念。
null 熟练掌握判断和证明函数单射、满射、双射性质的方法。会构造双射函数。
null 会求函数合成和反函数。了解合成函数的性质。
第四章 自然数
要点：自然数与自然数集合定义、传递集、自然数运算、N 上的序关系
要求：
null 熟悉自然数及自然数集合定义以及自然数运算。
null 理解传递集合的性质。
null 了解自然数的运算及其比较。
第五章 基数
要点：集合等势与优势、有穷集与无穷集、基数比较与运算
要求：
null 会证明集合等势以及优势。
null 了解有穷集与无穷集的性质。
null 会基数运算和比较。
第六章 序数*（可以不讲）
要点：序数的概念、超限递归定理
要求：
null 了解序数概念
null 了解超限递归定理及其应用
第七章 图
要点：无向图和有向图中的基本概念，握手定理、通路与回路、图的连通性
要求：
null 理解无向图与有向图的定义及其相关的概念（度、零图、平凡图、简单图、完全图、
正则图、子图、补图、图的同构等） 。
null 熟练掌握握手定理及推论的应用。
null 深刻理解无向与有向图的通路与回路的相关概念（通路、回路、连通度、割集、连
通分支、可达等） 。
null 掌握图中性质的简单证明方法。
第八章 欧拉图与哈密顿图
要点：欧拉图及其判别、哈密顿图及其判别、欧拉图与哈密顿图的应用
要求：
null 理解欧拉通路、回路和欧拉图的概念。
null 熟练掌握判定和证明欧拉图的方法。
null 理解哈密尔顿通路、回路和哈密尔顿图的概念。
null 会判断或证明某些图是或不是哈密尔顿图。
null 能够应用欧拉图或者哈密顿图解决实际问题。
第九章 树
要点：无向树、生成树、环路空间与断集空间、根树
要求：
null 熟练掌握无向树及其性质。
null 理解图的环路空间、断集空间。
null 掌握根树中的相关概念。
null 熟练掌握根树的行遍方法。
第十章 图的矩阵表示
要点：关联矩阵、邻接矩阵、相邻矩阵、可达矩阵、连通矩阵
要求：
null 熟练掌握的关联矩阵及其生成树的求法。
null 会利用邻接矩阵或相邻矩阵求图的通路和回路。
null 理解可达矩阵、连通矩阵的概念及其应用。
第十一章 平面图
要点：平面图的基本概念、平面图的判断、平面图的对偶图
要求：
null 理解平面图中相关的概念。
null 熟练掌握欧拉公式及相关定理的内容。会应用欧拉公式证明图中的命题。
null 会判断或证明一个图是否为平面图或极大平面图。
null 了解平面图的对偶图及其应用。
第十二章 图的着色
要点：图顶点的着色、色多项式、地图的着色与平面图点着色、边着色
要求：
null 理解点着色、点色数等概念。会求阶数 n 较小的无向简单图的点色数。
null 了解色多项式及其相关结果。
null 理解地图的面着色定义。
null 了解平面图的 5 色定理和 4 色猜想。
null 理解边着色与边色数的概念，会求一些无向简单图的边色数。
第十三章 支配集、覆盖集、独立集与匹配
要点：支配集、点独立集、点覆盖集、边覆盖集、匹配
要求：
null 掌握支配集、点独立集、点覆盖集、边覆盖集、匹配等概念。
null 会求图的支配数、点独立数、点覆盖数、边覆盖数。
null 掌握边覆盖与匹配之间的关系、最大匹配或完美匹配存在的条件。
null 理解 Hall 定理及其应用。
第十四章 带权图及其应用
要点：最短路径、关键路径、中国邮递员问题、最小生成树、最优树、货郎担问题
要求：
null 熟练掌握 Dijkstra 标号法求最短路径的算法及其应用。
null 掌握 PERT 图的关键路径求法及其应用。
null 理解中国邮递员问题中的最优投递路线的求法及其应用。
null 熟练掌握最小生成树的 Kruskal 算法、逐步短接法、破圈法及其应用。
null 熟练掌握 Huffman 最优树算法及其应用。
第十五章 代数系统
要点：二元运算及其性质、代数系统、子代数与积代数、代数系统的同态与同构、同余
关系与商代数
要求：
null 能够正确表示一个代数系统。
null 能够判断或证明代数系统的性质。
null 理解子代数与积代数的概念、构成方法以及与原代数之间的关系。
null 熟练掌握代数系统的同态和同构映射的判别和证明方法。
null 熟练掌握同态和同构映射的性质。
null 理解同余关系的构成和商代数的产生。
null 掌握商代数的性质。
第十六章 半群与群
要点：半群、独异点
要求：
null 能够判断一个代数系统是否为半群、独异点。
null 能够证明半群与独异点的性质。
第十七章 群
要点：群的定义、群的性质、子群、循环群、变换群与置换群、群的分解、正规子群与
商群、群的同态与同构、群的直积
要求：
null 理解群的定义，熟练掌握群的判别方法，了解群中的有关基本概念。
null 熟练掌握群的性质及其应用（群方程的解、消去律、结合律等） 。
null 熟练掌握子群的判定定理及其应用。
null 掌握有关循环群的生成元和子群的定理。
null 能够以不同的方法正确的表示 n 元置换。
null 熟练掌握置换的乘法、求逆等运算。
null 掌握陪集的定义及其性质。
null 会使用 Lagrange 定理证明群中的有关命题。
null 了解群的分类方程及其应用。
null 掌握正规子群的判别方法。
null 理解商群的构成及其性质。
null 能够证明映射是否为群同态映射，是否为单同态、满同态、同构。
null 了解群的直积。
第十八章 环与域
要点：环的定义及其性质、整环与域的定义、子环与商环
要求：
null 理解环、整环、域的定义。
null 了解商环的概念及其性质。
null 了解环同态定义。
第十九章 格与布尔代数
要点：格的定义、格的性质、子格与格同态、特殊的格
要求：
null 熟练掌握格的定义。
null 能够证明格的性质。
null 会判断子格。
null 能够证明格的同态与同构。
null 能判断模格、分配格、有补格、布尔格。
null 能证明格中的等式。
第二十章 组合存在性定理
要点：鸽巢原理、Ramsey 定理
要求：
null 能够使用鸽巢原理证明组合存在性的命题。
null 了解 Ramsey 定理的内容及其有关 Ramsey 数的结果。
第二十一章 基本的计数公式
要点：加法法则与乘法法则、排列与组合、二项式定理与组合恒等式、多项式定理
要求：
null 能够熟练使用加法法则和乘法法则。
null 能够熟练处理集合的排列与组合、多重集排列与组合（部分情况）的计数问题。
null 掌握二项式定理与多项式定理的内容。
null 熟练证明组合恒等式或者进行组合数的求和。
null 学习处理组合问题的一一对应的技巧。
第二十二章 组合计数方法
要点：递推方程及其求解方法、生成函数及其应用、指数生成函数及其应用、Catalan
数、两类 Stirling 数
要求：
null 熟练掌握求解递推方程的公式法、换元法、迭代法。
null 能够使用递推方程求解实际的计数问题。
null 熟练掌握典型的组合计数模型。
null 熟练掌握生成函数及指数生成函数的应用。
null 掌握 Catalan 数、两类 Stirling 数的定义及其组合意义。
第二十三章 组合计数定理
要点：包含排斥原理、对称筛公式、Burnside 引理、Polay 定理
要求：
null 能够使用包含排斥原理解决组合计数问题。
null 能够使用 Burside 引理和 Polay 定理解决组合计数问题。
第二十六章 命题演算
要点：命题联结词，命题演算形式推演系统 N 与 P 中的推演，可靠性与完全性定理
要求：
null 熟练掌握命题及联结词的概念，五个常用的联结词（与、或、非、蕴涵、等价）
及其真假性定义；
null 掌握自然语言命题的符号化。
null 熟练掌握命题形式，指派的概念，命题真值表及其构造作方法。
null 了解哑元及命题的真假值与哑元的无关性。
null 熟练掌握真值函数，联结词完全性的概念。联结词与、或、非、蕴涵、等价构
成的集合及其子集合的完全性。与、或、非、蕴涵、等价之间的互相表示（如
果能够的话）
null 掌握 2 元真值函数构成的的集合及其子集合的完全性。
null 熟练掌握有效推理形式的定义及其证明方法
null 熟练掌握 N 的构成，包括 N 的公式的形成规则、公理集和形式推理规则。N 中
形式证明序列和内定理的定义。N 中内定理的证明技巧，如一些辅助定理（增
加前提律，传递率）和常见的内定理。
null 掌握 N 中公式的括号的省略规则。
null 了解 N 的证明序列的斜形和树形书写方式。
null 熟练掌握 P 的构成，包括 P 的公式的形成规则、公理集和形式推理规则。P 中
形式证明序列和内定理的定义。 P 中内定理的证明技巧。 P 中常见内定理的证明。
null 掌握 P 中公式的简写规则。
null 了解 N 的证明序列的斜形书写方式。
null 熟练掌握 P 中有前提的证明序列的定义。演绎定理的内容和证明和使用。
null 熟练掌握 N 和 P 的构成方式的差别。N 和 P 的等价性定理的内容及其证明。
null 掌握 N 和 P 的等价性定理的使用。
null 熟练掌握指派，公式的真值及其求法，公式的分类（永真式，可满足式，永假
式）及其关系。逻辑蕴涵和逻辑等价（等值）概念。等值演算，包括基本等值
式和两个替换定理
null 了解限制性公式及其性质。
null 熟练掌握合取范式和析取范式的定义，范式存在性定理，范式的两种求法（真
值表法和等值算法） 。
null 掌握范式的不唯一性
null 了解联结词完全集的另一证明方式。
null 熟练掌握可靠性、和谐性和完备性的内容及其证明。
第二十七章 一阶谓词演算
要点：量词，边元的约束与自由，一阶谓词演算形式推演系统 N L与K L中的推演，可靠
性与完全性定理
要求：
null 熟练掌握个体变元、个体常元、谓词、函数、量词（全称和存在）等概念。
null 掌握自然语言命题的符号化。
null 熟练掌握逻辑符号非逻辑符号，项，一阶公式。
null 掌握常见数学对象的一阶语言公式的描述，包括代数结构等
null 了解公式的括号的省略规则。
null 熟练掌握辖域，自由（约束）出现，自由（约束）变元，项对变元在公式中自
由（可代入） 。
null 了解闭项，闭式，全称闭式。
null 熟练掌握 N L的构成，包括 N L的公式的形成规则、公理集和形式推理规则。N L中
形式证明序列和内定理的定义。N L 中内定理的证明技巧，如一些辅助定理（代
入实例，增加前提律，传递率， ）和常见的内定理（如换名规则） 。
null 了解 N L的证明序列的斜形和树形书写方式。
null 熟练掌握前束范式的定义，范式存在性定理，范式的求法（包括所用的几个内
定理）
null 了解根据范式对一阶公式进行分类。
null 熟练掌握 K L 的构成，包括 K L 的公式的形成规则、公理集和形式推理规则。KL
中形式证明序列和内定理的定义。K L 中内定理的证明技巧。K L 中常见内定理的
证明。
null 掌握 K L中公式的简写规则。
null 了解 K L的证明序列的斜形书写方式。
null 熟练掌握 P 中有前提的证明序列的定义。演绎定理的内容和证明和使用。
null 熟练掌握 N L和K L的构成方式的差别。N L和K L的等价性定理的内容及其证明。
null 掌握 N L和K L的等价性定理的使用。
null 熟练掌握论域，解释，指派，项的值、公式的满足、真、永真的定义及其符号
表示。
null 掌握公式（项）的值与约束变元取值的无关性。可代入性定理。命题代入实例
的性质。
null 了解公式为假的等价性定义。
null 熟练掌握可靠性、和谐性和完备性的内容及其证明。和谐公式集、极大和谐公
式集的概念及其性质。
null 掌握一阶逻辑完备性证明的常量构作法——Henkin 方法。
第二十八章 消解原理 *（可以不讲）
要点：命题公式与一阶谓词公式的消解
要求：
null 熟练掌握文字、子句等概念
null 熟练掌握命题公式的消解。
null 熟练掌握 Herbrand 定理
null 掌握 Robinson 合一算法
null 掌握一阶谓词公式的消解
