离散数学（国家级）-北京大学  主教材 离散数学教程 ISBN: 978-7-301-05366-9 主编: 耿素云 屈婉玲 王捍贫 北京大学出版社 辅助教材 离散数学习题解析 ISBN: 978-7-301-09801-1 主编: 屈婉玲 耿素云 王捍贫 刘田 北京大学出版社

 离散数学（Discrete Mathematics）是计算机科学与技术专业的一门重要的专业基础课，也是该专业的核心课程之一。教育部高等学校计算机科学与技术教学指导委员会在2006年出版的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》中提到：“离散结构是计算机科学的基础内容，可以为计算机系统提供其处理对象的状态及其变换的有效描述。

教学单元

• 第1章 集合（教材第一章）

• 01-01 引言

• 01-02 预备知识（命题逻辑）

• 01-03 预备知识（一阶逻辑）

• 01-04 集合的概念和集合之间的关系

• 01-05 集合的运算

• 01-06 基本的集合恒等式

• 第2章 二元关系（教材第二章）

• 02-01 有序对与卡氏积

• 02-02 二元关系

• 02-03 关系的表示和关系的性质

• 02-04 关系的幂运算和闭包

• 02-05 等价关系和划分

• 02-06 序关系

• 第3章 函数（教材第三章）

• 03-01 函数的基本概念、性质、合成、反函数

• 第4章 自然数（教材第四章）

• 04-01 自然数的定义

• 04-02 自然数的性质

• 第5章 基数（教材第五章）

• 05-01 集合的等势、有穷集合与无穷集合

• 05-02 基数和基数的比较与运算

• 05-03 习题课

• 第6章 图（教材第七章）

• 06-01 图的基本概念

• 06-02 通路与回路

• 06-03 无向图和有向图的连通性

• 06-04 无向图的连通度

• 第7章 欧拉图与哈密顿图（教材第八章）

• 07-01 欧拉图

• 07-02 哈密顿图

• 第8章 树（教材第九章）

• 08-01 树

• 第9章 图的矩阵表示（教材第十章）

• 09-01 图的矩阵表示

• 第10章 平面图（教材第十一章）

• 10-01 平面图的基本概念

• 10-02 欧拉公式与平面图的判断

• 10-03 平面图的对偶图与外平面图

• 10-04 平面图与哈密顿图

• 10-05 习题课

• 第11章 图的着色（教材第十二章）

• 11-01 点着色和色多项式

• 11-02 平面图着色和边着色

• 第12章 支配集、覆盖集、独立集与匹配（教材第十三章）

• 12-01 支配集、点覆盖集、点独立集

• 12-02 边覆盖数与匹配

• 12-03 二部图中的匹配

• 第13章 带权图及其应用（教材第十四章）

• 13-01 中国邮递员问题和货郎问题

• 13-02 图论12-14章习题课

• 13-03 课程总结

• 第14章 离散数学（1）期末考试

• 第15章 代数系统（教材第十五章）

• 15-01 引言

• 15-02 二元运算及其性质

• 15-03 代数系统、子代数和积代数

• 15-04 代数系统的同态与同构

• 15-05 同余关系与商代数

• 第16章 半群与独异点（教材第十六章）

• 16-01 半群与独异点

• 第17章 群（教材第十七章）

• 17-01 群的定义和性质、子群

• 17-02 习题课

• 17-03 循环群、变换群与置换群

• 17-04 群的分解、正规子群与商群、群的同态与同构

• 17-05 习题课、小测验

• 第18章 环与域（教材第十八章）

• 18-01 环与域

• 第19章 格与布尔代数（教材第十九章）

• 19-01 格的定义和性质、子格、格同态与直积

• 19-02 模格、分配格、有补格与布尔代数

• 第20章 组合存在性定理（教材第二十章）

• 20-01 鸽巢原理和Ramsey定理

• 第21章 基本的计数公式（教材第二十一章）

• 21-01 两个计数原则、排列组合

• 21-02 二项式定理与组合恒等式

• 21-03 多项式定理

• 第22章 组合计数方法（教材第二十二章）

• 22-01 递推方程的公式解法

• 22-02 递推方程的其他求解方法

• 22-03 生成函数的定义和性质

• 22-04 生成函数、指数生成函数及应用

• 22-05 Catalan数与Stirling数

• 22-06 小测验

• 第23章 组合计数定理（教材第二十三章）

• 23-01 包含排斥原理与对称筛公式

• 23-02 Burnside引理与Polya定理

• 23-03 课程总结

• 第24章 离散数学（2）期末考试

• 第25章 命题逻辑（教材第二十六章）

• 25-01 引言

• 25-02 命题与联结词

• 25-03 命题形式和真值表

• 25-04 联结词的完全集

• 25-05 推理形式

• 25-06 命题演算的自然推理系统N

• 25-07 命题演算形式系统P

• 25-08 N与P的等价性

• 25-09 赋值与等值演算

• 25-10 命题范式

• 25-11 可靠性、和谐性与完备性

• 25-12 期中考试

• 第26章 一阶谓词逻辑（教材第二十七章）

• 26-01 一阶谓词演算的符号化

• 26-02 一阶语言

• 26-03 一阶谓词演算的自然推演形式系统NL

• 26-04 一阶谓词演算的形式系统KL

• 26-05 NL与KL的等价性

• 26-06 KL的解释与赋值

• 26-07 KL的可靠性与和谐性

• 26-08 习题课

• 第27章 离散数学（3）期末考试