《离散数学》PPT课件 王捍贫 北京大学

 
课件内容： 
第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-05Catalan数与Stirling数 
22-06小测验 
第23章组合计数定理（教材第二十三章） 
23-01包含排斥原理与对称筛公式 
23-02Burnside引理与Polya定理 
23-03课程总结 
第24章离散数学（2）期末考试 
第25章命题逻辑（教材第二十六章） 
25-01引言 
25-02命题与联结词 
25-03命题形式和真值表 
25-04联结词的完全集 
25-05推理形式 
25-06命题演算的自然推理系统N 
25-07命题演算形式系统P 
25-08N与P的等价性 
25-09赋值与等值演算 
25-10命题范式 
25-11可靠性、和谐性与完备性 
25-12期中考试 
第26章一阶谓词逻辑（教材第二十七章） 
26-01一阶谓词演算的符号化 
26-02一阶语言 
26-03一阶谓词演算的自然推演形式系统NL 
26-04一阶谓词演算的形式系统KL 
26-05NL与KL的等价性 
26-06KL的解释与赋值 
26-07KL的可靠性与和谐性 
26-08习题课 
第27章离散数学（3）期末考试