北京大学视频公开课

世界文化地

一、授课学时安排
（1）集合论与图论：2学时/次，共计24次，48学时；（上学期讲授）
（2）代数结构与组合数学：2学时/次，共计24次，48学时；（下学期讲授）
（3）数理逻辑：2学时/次，共计24次，48学时；（下学期讲授）

二、教学计划大纲
第一章集合
要点：集合的基本概念。集合的基本运算。集合恒等式。
要求：
􀁺 能够正确表示集合。
􀁺 熟练掌握集合的基本运算。
􀁺 掌握证明集合恒等式或包含关系的方法。

第二章二元关系
要点：集合的笛卡尔积和二元关系，关系的运算，关系的性质，关系的闭包，等价关系
和偏序关系
要求：
􀁺 熟练掌握二元关系的多种表示方法。
􀁺 熟练掌握关系的定义域、值域、逆、合成、限制、像、幂、闭包的计算方法。
􀁺 能够证明含有关系运算的集合恒等式。
􀁺 熟练掌握判断关系五种性质的方法，能证明关系的性质。
􀁺 深刻理解等价关系、等价类、商集、划分、偏序关系、偏序集、哈斯图、偏序集
中的特定元素等概念，并能熟练地求出等价关系的等价类、商集、偏序关系的哈
斯图及特定元素。

第三章函数
要点：函数定义、函数性质、函数运算
要求：
􀁺 理解函数、集合A 到B 的函数、BA、函数的像、完全原像的概念。
􀁺 熟练掌握判断和证明函数单射、满射、双射性质的方法。会构造双射函数。
􀁺 会求函数合成和反函数。了解合成函数的性质。

第四章自然数
要点：自然数与自然数集合定义、传递集、自然数运算、N 上的序关系
要求：
􀁺 熟悉自然数及自然数集合定义以及自然数运算。
􀁺 理解传递集合的性质。
􀁺 了解自然数的运算及其比较。

第五章基数
要点：集合等势与优势、有穷集与无穷集、基数比较与运算
要求：
􀁺 会证明集合等势以及优势。
􀁺 了解有穷集与无穷集的性质。
􀁺 会基数运算和比较。

第六章序数*（可以不讲）
要点：序数的概念、超限递归定理
要求：
􀁺 了解序数概念
􀁺 了解超限递归定理及其应用

第七章图
要点：无向图和有向图中的基本概念，握手定理、通路与回路、图的连通性
要求：
􀁺 理解无向图与有向图的定义及其相关的概念（度、零图、平凡图、简单图、完全图、
正则图、子图、补图、图的同构等）。
􀁺 熟练掌握握手定理及推论的应用。
􀁺 深刻理解无向与有向图的通路与回路的相关概念（通路、回路、连通度、割集、连
通分支、可达等）。
􀁺 掌握图中性质的简单证明方法。

第八章欧拉图与哈密顿图
要点：欧拉图及其判别、哈密顿图及其判别、欧拉图与哈密顿图的应用
要求：
􀁺 理解欧拉通路、回路和欧拉图的概念。
􀁺 熟练掌握判定和证明欧拉图的方法。
􀁺 理解哈密尔顿通路、回路和哈密尔顿图的概念。
􀁺 会判断或证明某些图是或不是哈密尔顿图。
􀁺 能够应用欧拉图或者哈密顿图解决实际问题。

第九章树
要点：无向树、生成树、环路空间与断集空间、根树
要求：
􀁺 熟练掌握无向树及其性质。
􀁺 理解图的环路空间、断集空间。
􀁺 掌握根树中的相关概念。
􀁺 熟练掌握根树的行遍方法。

第十章图的矩阵表示
要点：关联矩阵、邻接矩阵、相邻矩阵、可达矩阵、连通矩阵
要求：
􀁺 熟练掌握的关联矩阵及其生成树的求法。
􀁺 会利用邻接矩阵或相邻矩阵求图的通路和回路。
􀁺 理解可达矩阵、连通矩阵的概念及其应用。

第十一章平面图
要点：平面图的基本概念、平面图的判断、平面图的对偶图
要求：
􀁺 理解平面图中相关的概念。
􀁺 熟练掌握欧拉公式及相关定理的内容。会应用欧拉公式证明图中的命题。
􀁺 会判断或证明一个图是否为平面图或极大平面图。
􀁺 了解平面图的对偶图及其应用。

第十二章图的着色
要点：图顶点的着色、色多项式、地图的着色与平面图点着色、边着色
要求：
􀁺 理解点着色、点色数等概念。会求阶数n 较小的无向简单图的点色数。
􀁺 了解色多项式及其相关结果。
􀁺 理解地图的面着色定义。
􀁺 了解平面图的5 色定理和4 色猜想。
􀁺 理解边着色与边色数的概念，会求一些无向简单图的边色数。

第十三章支配集、覆盖集、独立集与匹配
要点：支配集、点独立集、点覆盖集、边覆盖集、匹配
要求：
􀁺 掌握支配集、点独立集、点覆盖集、边覆盖集、匹配等概念。
􀁺 会求图的支配数、点独立数、点覆盖数、边覆盖数。
􀁺 掌握边覆盖与匹配之间的关系、最大匹配或完美匹配存在的条件。
􀁺 理解Hall 定理及其应用。

第十四章带权图及其应用
要点：最短路径、关键路径、中国邮递员问题、最小生成树、最优树、货郎担问题
要求：
􀁺 熟练掌握Dijkstra 标号法求最短路径的算法及其应用。
􀁺 掌握PERT 图的关键路径求法及其应用。
􀁺 理解中国邮递员问题中的最优投递路线的求法及其应用。
􀁺 熟练掌握最小生成树的Kruskal 算法、逐步短接法、破圈法及其应用。
􀁺 熟练掌握Huffman 最优树算法及其应用。

第十五章代数系统
要点：二元运算及其性质、代数系统、子代数与积代数、代数系统的同态与同构、同余
关系与商代数
要求：
􀁺 能够正确表示一个代数系统。
􀁺 能够判断或证明代数系统的性质。
􀁺 理解子代数与积代数的概念、构成方法以及与原代数之间的关系。
􀁺 熟练掌握代数系统的同态和同构映射的判别和证明方法。
􀁺 熟练掌握同态和同构映射的性质。
􀁺 理解同余关系的构成和商代数的产生。
􀁺 掌握商代数的性质。

第十六章半群与群
要点：半群、独异点
要求：
􀁺 能够判断一个代数系统是否为半群、独异点。
􀁺 能够证明半群与独异点的性质。

第十七章群
要点：群的定义、群的性质、子群、循环群、变换群与置换群、群的分解、正规子群与
商群、群的同态与同构、群的直积
要求：
􀁺 理解群的定义，熟练掌握群的判别方法，了解群中的有关基本概念。
􀁺 熟练掌握群的性质及其应用（群方程的解、消去律、结合律等）。
􀁺 熟练掌握子群的判定定理及其应用。
􀁺 掌握有关循环群的生成元和子群的定理。
􀁺 能够以不同的方法正确的表示n 元置换。
􀁺 熟练掌握置换的乘法、求逆等运算。
􀁺 掌握陪集的定义及其性质。
􀁺 会使用Lagrange 定理证明群中的有关命题。
􀁺 了解群的分类方程及其应用。
􀁺 掌握正规子群的判别方法。
􀁺 理解商群的构成及其性质。
􀁺 能够证明映射是否为群同态映射，是否为单同态、满同态、同构。
􀁺 了解群的直积。

第十八章环与域
要点：环的定义及其性质、整环与域的定义、子环与商环
要求：
􀁺 理解环、整环、域的定义。
􀁺 了解商环的概念及其性质。
􀁺 了解环同态定义。

第十九章格与布尔代数
要点：格的定义、格的性质、子格与格同态、特殊的格
要求：
􀁺 熟练掌握格的定义。
􀁺 能够证明格的性质。
􀁺 会判断子格。
􀁺 能够证明格的同态与同构。
􀁺 能判断模格、分配格、有补格、布尔格。
􀁺 能证明格中的等式。

第二十章组合存在性定理
要点：鸽巢原理、Ramsey 定理
要求：
􀁺 能够使用鸽巢原理证明组合存在性的命题。
􀁺 了解Ramsey 定理的内容及其有关Ramsey 数的结果。

第二十一章基本的计数公式
要点：加法法则与乘法法则、排列与组合、二项式定理与组合恒等式、多项式定理
要求：
􀁺 能够熟练使用加法法则和乘法法则。
􀁺 能够熟练处理集合的排列与组合、多重集排列与组合（部分情况）的计数问题。
􀁺 掌握二项式定理与多项式定理的内容。
􀁺 熟练证明组合恒等式或者进行组合数的求和。
􀁺 学习处理组合问题的一一对应的技巧。

第二十二章组合计数方法
要点：递推方程及其求解方法、生成函数及其应用、指数生成函数及其应用、Catalan
数、两类Stirling 数
要求：
􀁺 熟练掌握求解递推方程的公式法、换元法、迭代法。
􀁺 能够使用递推方程求解实际的计数问题。
􀁺 熟练掌握典型的组合计数模型。
􀁺 熟练掌握生成函数及指数生成函数的应用。
􀁺 掌握Catalan 数、两类Stirling 数的定义及其组合意义。

第二十三章组合计数定理
要点：包含排斥原理、对称筛公式、Burnside 引理、Polay 定理
要求：
􀁺 能够使用包含排斥原理解决组合计数问题。
􀁺 能够使用Burside 引理和Polay 定理解决组合计数问题。

第二十六章命题演算
要点：命题联结词，命题演算形式推演系统N 与P 中的推演，可靠性与完全性定理
要求：
􀁺 熟练掌握命题及联结词的概念，五个常用的联结词（与、或、非、蕴涵、等价）
及其真假性定义；
􀁺 掌握自然语言命题的符号化。
􀁺 熟练掌握命题形式，指派的概念，命题真值表及其构造作方法。
􀁺 了解哑元及命题的真假值与哑元的无关性。
􀁺 熟练掌握真值函数，联结词完全性的概念。联结词与、或、非、蕴涵、等价构
成的集合及其子集合的完全性。与、或、非、蕴涵、等价之间的互相表示（如
果能够的话）
􀁺 掌握2 元真值函数构成的的集合及其子集合的完全性。
􀁺 熟练掌握有效推理形式的定义及其证明方法
􀁺 熟练掌握N 的构成，包括N 的公式的形成规则、公理集和形式推理规则。N 中
形式证明序列和内定理的定义。N 中内定理的证明技巧，如一些辅助定理（增
加前提律，传递率）和常见的内定理。
􀁺 掌握N 中公式的括号的省略规则。
􀁺 了解N 的证明序列的斜形和树形书写方式。
􀁺 熟练掌握P 的构成，包括P 的公式的形成规则、公理集和形式推理规则。P 中
形式证明序列和内定理的定义。P 中内定理的证明技巧。P 中常见内定理的证明。
􀁺 掌握P 中公式的简写规则。
􀁺 了解N 的证明序列的斜形书写方式。
􀁺 熟练掌握P 中有前提的证明序列的定义。演绎定理的内容和证明和使用。
􀁺 熟练掌握N 和P 的构成方式的差别。N 和P 的等价性定理的内容及其证明。
􀁺 掌握N 和P 的等价性定理的使用。
􀁺 熟练掌握指派，公式的真值及其求法，公式的分类（永真式，可满足式，永假
式）及其关系。逻辑蕴涵和逻辑等价（等值）概念。等值演算，包括基本等值
式和两个替换定理
􀁺 了解限制性公式及其性质。
􀁺 熟练掌握合取范式和析取范式的定义，范式存在性定理，范式的两种求法（真
值表法和等值算法）。
􀁺 掌握范式的不唯一性
􀁺 了解联结词完全集的另一证明方式。
􀁺 熟练掌握可靠性、和谐性和完备性的内容及其证明。

第二十七章一阶谓词演算
要点：量词，边元的约束与自由，一阶谓词演算形式推演系统NL 与KL 中的推演，可靠
性与完全性定理
要求：
􀁺 熟练掌握个体变元、个体常元、谓词、函数、量词（全称和存在）等概念。
􀁺 掌握自然语言命题的符号化。
􀁺 熟练掌握逻辑符号非逻辑符号，项，一阶公式。
􀁺 掌握常见数学对象的一阶语言公式的描述，包括代数结构等
􀁺 了解公式的括号的省略规则。
􀁺 熟练掌握辖域，自由（约束）出现，自由（约束）变元，项对变元在公式中自
由（可代入）。
􀁺 了解闭项，闭式，全称闭式。
􀁺 熟练掌握NL 的构成，包括NL 的公式的形成规则、公理集和形式推理规则。NL 中
形式证明序列和内定理的定义。NL 中内定理的证明技巧，如一些辅助定理（代
入实例，增加前提律，传递率，）和常见的内定理（如换名规则）。
􀁺 了解NL 的证明序列的斜形和树形书写方式。
􀁺 熟练掌握前束范式的定义，范式存在性定理，范式的求法（包括所用的几个内
定理）
􀁺 了解根据范式对一阶公式进行分类。
􀁺 熟练掌握KL 的构成，包括KL 的公式的形成规则、公理集和形式推理规则。KL
中形式证明序列和内定理的定义。KL 中内定理的证明技巧。KL 中常见内定理的
证明。
􀁺 掌握KL 中公式的简写规则。
􀁺 了解KL 的证明序列的斜形书写方式。
􀁺 熟练掌握P 中有前提的证明序列的定义。演绎定理的内容和证明和使用。
􀁺 熟练掌握NL 和KL 的构成方式的差别。N L 和KL 的等价性定理的内容及其证明。
􀁺 掌握NL 和KL 的等价性定理的使用。
􀁺 熟练掌握论域，解释，指派，项的值、公式的满足、真、永真的定义及其符号
表示。
􀁺 掌握公式（项）的值与约束变元取值的无关性。可代入性定理。命题代入实例
的性质。
􀁺 了解公式为假的等价性定义。
􀁺 熟练掌握可靠性、和谐性和完备性的内容及其证明。和谐公式集、极大和谐公
式集的概念及其性质。
􀁺 掌握一阶逻辑完备性证明的常量构作法——Henkin 方法。

第二十八章消解原理*（可以不讲）
要点：命题公式与一阶谓词公式的消解
要求：
􀁺 熟练掌握文字、子句等概念
􀁺 熟练掌握命题公式的消解。
􀁺 熟练掌握Herbrand 定理
􀁺 掌握Robinson 合一算法
􀁺 掌握一阶谓词公式的消解

《离散数学习题解析》

屈婉玲，耿素云，王捍贫，刘田

北京大学出版社，2008年



《离散数学教程》

耿素云，屈婉玲, 王捍贫

北京大学出版社，2002年