离散数学是研究离散量的结构及其相互关系的数学学科,是现代数学的重要组成部分。它在各学科领域,特别在计算机科学与技术领域有着广泛的应用,同时离散数学也是计算机专业的许多专业课程,如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习,不但可以掌握处理离散结构的描述工具和方法,为后续课程的学习创造条件,而且可以提高抽象思维和严格的逻辑推理能力,为将来参与创新性的研究和开发工作打下坚实的基础。
北京大学信息科学技术学院的离散数学课程总计144学时,分成三门课程讲授,每门课程48学时。各门课程的主要内容如下:
1. 集合论与图论-离散数学1 ,主讲教师:刘田集合论部分:集合及其运算、二元关系与函数、自然数及自然数集、集合的基数等 图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着 色、支配集、覆盖集、独立集与匹配、带权图及其应用
2. 代数系统与组合数学-离散数学2,主讲教师:屈婉玲、曹永知代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理
3. 数理逻辑部分 –离散数学3,主讲教师:王捍贫 数理逻辑部分:命题逻辑、一阶谓词演算等。
离散数学课程的教学方式以课堂讲授为主, 课后留有书面作业,通过学校网络教学平台发布课件并进行师生交流。点击上述三门课程的名称,可以进入相应的教学网。
课程负责人:屈婉玲 教 授
屈婉玲,女,北京大学信息科学技术学院教授,博士生导师,中国人工智能学会离散数学专委会委员。主要研究方向是算法设计与分析,发表多篇论文,出版教材多部,其中包含多部国家级规划教材、北京市高等教育精品教材、教育部高等教育精品教材。所讲授的离散数学课程被评为国家级精品课程,两次被评为北京大学十佳教师,并获得北京市优秀教师称号。曾主持过多项国家教材和课程建设项目,并获得北京市教育教学成果一等奖。 |
|
主讲“代数结构与组合数学”(离散数学2)与研究生必修课“算法分析与计算复杂性理论”。 独立或合作出版离散数学、组合数学等译著、教材及教学参考书18 种,其中包含1 本国家十五规划教材(《离散数学》,高教出版社,2004)和2本北京市精品教材,还有1 本在台湾儒林出版公司出版。主持教育部网络课程建设项目与高教社精品课程建设项目,所研制的《离散数学网络课件》于2003 年通过教育部主持的验收,被评为“优秀”。参加国家自然科学基金、973 基础研究等课题,主要研究方向为离散数学及其应用、算法设计与分析,发表论文10多篇。2001 年获得北京市教学成果奖一等奖,2004 年被评为北京市优秀教师。 |
一、授课学时安排
(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年
|
|
- Paul R. Halmos Na?ve Set Theory, Springer,1998.
- Reinhard Diestel, Graph Theory, Springer-Verlag, 2000.
- 张锦文,公理集合论导引,科学出版社,1999.
- 徐俊明,图论及其应用(2版),中国科技大学出版社,2005.
- J.A.邦迪,U.S.R.墨蒂,图论及其应用,科学出版社,1984.
- Kenneth H. Rosen, Discrete Mathematics and Its Applications(fifth Edition), Mc GrawHill (机工出版社影印版)2003.
- 陆钟万,面向计算机科学的数理逻辑,北京大学出版社,(第二版,科学出版社,1998)
- 王元元,计算机科学中的逻辑学,科学出版社, 1989.
- 哈密尔顿,数理逻辑,朱水林译,华东师大出版 社,1986.
- H. B.Enderton, A Mathematical Introduction to Logic (2ed Edition), Elsevier Press, 2001.