离散数学

每周二1-3pm 每周四10-noon 理教103 (2026年)

授课老师

刘天任 [email protected] 静园五院103-2

Office hour 周五2:30-4pm

助教

徐睿 [email protected]
施畅 [email protected]
孙培轩 [email protected]
朱家庆 [email protected]
咸浩哲 [email protected]
罗思远 [email protected]
葛子越 [email protected]
高致远 [email protected]
严绍恒 [email protected]
翟锦程 chinese_zjc_@stu.pku.edu.cn

教材和参考资料

大纲参考邓小铁和王畅写的《离散数学与结构》而这本书又是基于 Rafael Pass 和 Wei-Lung Dustin Tseng 的 “A Course in Discrete Structures”。

按章节分, 可以参考

• 逻辑部分: Logic and Structure (Dirk van Dalen)
• 抽象代数: 抽象代数学 (姚慕生); Abstract Algebra (Dummit-Foote)
• 信息论: Information Theory: From Coding to Learning (Polyanskiy-Wu)
• 离散傅里叶: Fourier Transforms in Computer Science (Daniel Štefankovič)
• 马尔可夫链: Markov Chains and Mixing Times (Levin)
• 概率方法: Probabilistic Method (Alon-Spencer); Probabilistic Method (Matoušek-Vondrák)

参考资料。

成绩

成绩（调分前）= 40% 作业（排除成绩最低的10%） + 30% 期中考试 + 30% 期末考试 + 笔记额外加分

作业

大致一周一次, 周四出作业, 下周四收纸质版, 再下周反馈批改后的作业以及参考答案。

授课内容

今年有严绍恒助教和几位同学提供的笔记 (last updated Oct 9)

• Sep 8 朴素集合论, 命题逻辑, 自然演绎
• Sep 10 自然演绎的完备性, RAA, 一阶逻辑
• HW1 参考答案
• Sep 15 一阶逻辑的自然演绎, Peano 算术, 一阶逻辑的完备性
• Sep 17 ZFC 集合论, Gödel 不完备定理
• HW2 参考答案
• Sep 22 初等数论
• Sep 24 群, 正规子群, 群同态, 群同构
• HW3 参考答案
• Sep 29 群同态, 群同构定理, 有限生成Abel群
• Oct 8 群作用, 共轭类方程, Sylow定理
• HW4
• Dec 29 下午 期末考试

2025年的授课内容：

今年有李新年助教和几位同学提供的笔记 (last updated Dec 29)

• Sep 9 朴素集合论
• Sep 11 命题逻辑, 自然演绎
  • Natural Deduction 在 Logic and Structure 中有介绍
  • System K 在 Sequents and Trees 中有介绍
• HW1
• Sep 16 自然演绎的完备性, RAA, Kripke model
  • 网上有很多关于 Kripke model 和直觉主义的材料, 我参考的是 A Brief Introduction to the Intuitionistic Propositional Calculus
• Sep 18 一阶逻辑, 一阶逻辑的自然演绎
• HW2
• Sep 23 Peano 算术, 一阶逻辑的完备性
• Sep 25 ZFC 集合论, Gödel 不完备定理
• HW3
• Sep 30 初等数论
• Oct 9 群, 正规子群
• HW4
• Oct 14 群同态, 群同构定理, 有限生成Abel群
• Oct 16 群作用, 共轭类方程, Sylow定理
• HW5
• Oct 21 环, 环同态, 理想, 环同构定理
• Oct 23 有特殊性质的整环
• HW6
• Oct 28 域
• Oct 30 Galois理论 (王迪)
• Nov 4 期中考试 可以带2张A4纸小抄 试卷
• Nov 6 基本计数, 容斥原理, 鸽笼原理
• HW7
• Nov 11 生成函数
• Nov 13 Burnside & Polya
• HW8
• Nov 18 概率, 概率生成函数
• Nov 20 熵, 散度
• HW9
• Nov 25 集中不等式, Sanov & Chernoff
• Nov 27 离散傅里叶变换
  • 离散傅里叶变换主要参考“Fourier Transforms in Computer Science”
• HW10
• Dec 2 压缩
• Dec 4 信道编码
  • 信息论的部分主要参考 MIT 6.441 课程笔记和据此整理的教材“Information Theory: From Coding to Learning”
• HW11
• Dec 9 马尔可夫链, 稳态分布
• Dec 11 马尔可夫链, 混合时间
  • 建议参考 Markov Chain and Mixing Time
• HW12
• Dec 16 图论, 图矩阵表示
• Dec 18 平面图, 谱图论
  • 可以参考“Spectral and Algebraic Graph Theory”
• HW13
• Dec 23 and Dec 25 概率方法
  • 可以参考两本名为“Probabilistic Method”教材中的任意一本
• HW14 (不提交)
• Dec 30 下午 期末考试 二教411 可以带4张A4纸小抄 试卷
• HW 题库, 包括往年考试题

2024年的授课内容：

• Sep 10 朴素集合论
• Sep 12 命题逻辑
• Sep 19 自然演绎的完备性, RAA, Kripke model
• Sep 24 and Sep 26 一阶逻辑, ZFC 集合论, Gödel 不完备定理
• Oct 8 and Oct 10 类型论（李翰禹）
• Oct 15 初等数论
• Oct 17 群
• Oct 22 群同构, 正规子群, 有限生成Abel群
• Oct 24 群作用, 共轭类方程, Sylow定理
• Oct 22 环, 环同态, 理想, 环同构定理
• Oct 24 有特殊性质的整环
• Nov 5 域
• Nov 7 期中考试 可以带2张A4纸小抄 试卷
• Nov 12 组合计数
• Nov 14 概率
• Nov 19 生成函数
• Nov 21 Burnside & Polya
• Nov 26 熵, 散度
• Nov 28 Sanov & Chernoff
• Dec 3 压缩
• Dec 5 信道编码
  • 信息论的部分主要参考 MIT 6.441 课程笔记和据此整理的教材“Information Theory: From Coding to Learning”
• Dec 10 离散傅里叶变换
• Dec 12 马尔可夫链
• Dec 17 马尔可夫链
  • 建议参考 Markov Chain and Mixing Time
• Dec 19 图
• Dec 24 and Dec 26 概率方法
  • 可以参考两本名为“Probabilistic Method”教材中的任意一本
• Dec 31 期末考试 可以带4张A4纸小抄 试卷

2023年的授课内容：