离散数学（2023）

南京大学苏州校区，本科生课程

任课教师：戴望州

课程信息

• 地点：馆3-201, 鼓楼校区
• 时间：周二第3-4节 & 周四第1-2节
• 助教：
  • 黎运泽：yunzeli@smail.nju.edu.cn, 18252070509
  • 王子龙：zilongwang@smail.nju.edu.cn, 18252070211
  • 赵晶婵：zhaojingchan@163.com, 13830793328
  • 赵晓颖：522022320216@smail.nju.edu.cn, 18602565253

最新通知

• 「6 月 8 日」 本学期课程正式结束，最后一次答疑安排在6月10日（星期六）下午2:00，地点在鼓楼教学楼102。祝大家能够取得理想的成绩！

课程材料

以下电子版书籍仅供修读本课程且买不起正版的同学使用，请勿随意传播。

• 参考教材：
  • K.H.Rosen著，《离散数学及其应用》，机械工业出版社（英文版/中文版）
• 数理逻辑参考书目：
  • Michael Huth and Mark Ryan, LOGIC IN COMPUTER SCIENCE: Modelling and Reasoning about Systems, Cambridge. (英文版)
• 集合论参考书目：
  • Karel Hrbacek and Thomas Jech, Introduction to Set Theory, 3rd Eds. Marcel Dekker. (英文版)
  • Thomas Jech, Set Theory: The Third Millennium Edition, revised and expanded. Springer. (英文版) （注：这是进阶版的集合论教材，主要讲 ZFC 相关内容，一般面向数学系高年级学生或研究生）
• 数论参考书目：
  • 潘承洞，潘承彪，《初等数论》，北京大学出版社（中文版）
• 抽象代数参考书目：
  • 耿素云，屈婉玲，《离散数学》，清华大学出版社（中文版）
  • John B. Fraleigh, A First Course in Abstract Algebra, Pearson. （英文版） （本课程内容相关部分主要位于 Section 1~14）
• 图论参考书目：
  • Reinhard Diestel, Graph Theory, 5th Eds., Graduate Texts in Mathematics. Springer. (英文版)
  • Douglas B. West. 图论导引. 2nd Eds., 机械工业出版社. ( 中文版 ) ( 英文版 )

课后作业

• 数理逻辑初步：
  • HW01, ddl. Feb. 28. Solution 01
  • HW02, ddl. Mar. 07. Solution 02
  • HW03, ddl. Mar. 14. Solution 03
• 集合论初步：
  • HW04, ddl. Mar. 16. Solution 04
  • HW05, ddl. Mar. 21. Solution 05
  • HW06,ddl. Mar. 23. Solution 06
  • HW07,ddl. Mar. 28. Solution 07
• 数论初步：
  • HW08, ddl. Mar. 30. Solution 08
• 计数与离散概率
  • HW09, ddl. Apr. 4. Solution 09
  • HW10, ddl. Apr. 6. Solution 10
  • HW11, ddl. Apr. 13. Solution 11
• 抽象代数初步
  • HW12, ddl. Apr. 18. Solution 12
  • HW13, ddl. Apr. 18. Solution 13
  • HW14, ddl. Apr. 25. Solution 14
  • HW15, ddl. Apr. 27. Solution 15
  • HW16, ddl. May. 4. Solution 16
  • HW17, dl. May. 9. Solution 17
  • HW18, ddl. May. 11. Solution 18
  • HW19, ddl. May. 23. Solution 19
  • HW20, ddl. May. 23. Solution 20
  • HW21, ddl. May. 25. Solution 21
  • HW22, ddl. May. 25. Solution 22
  • HW23, ddl. May. 30. Solution 23
  • HW24, ddl. Jun. 1. Solution 24
  • HW25, ddl. Jun. 6. Solution 25
  • HW26, ddl. Jun. 8. Solution 26
  • HW26, ddl. N.A. Solution 26
  • HW27, ddl. Jun. 8. Solution 27
  • HW28, ddl. N.A. Solution 28
  • HW29, ddl. N.A. Solution 29

课程课件

1. 绪论
2. 数理逻辑初步
   • 命题逻辑 （Handout 1: 自然演绎与范式）
   • 谓词逻辑初步 （Handout 2: 谓词逻辑的语法和语义）
   • 证明方法导引
3. 集合论初步
   • 集合及其运算
   • 函数及其运算
   • 自然数与数学归纳法
   • 集合的基数
4. 数论初步
5. 计数与离散概率
   • 计数和组合
   • 离散概率
6. 抽象代数初步
   • 二元关系. Part 1
   • 二元关系. Part 2 (Ver. 2)
   • 偏序集 (Ver. 2) (Mirsky’s Theorem) (Dilworth’s Theorem)
   • 代数系统引论
   • 群论. Part 1 （Handout 3: 群论导引）
   • 群论. Part 2
   • 群论. Part 3
   • 格
   • 布尔代数
7. 图论初步
   • 基本概念
   • 图的表示与图同构
   • 连通性
   • 欧拉图
   • 哈密尔顿图
   • 带权图与最短路
   • 二部图与匹配 （Another Proof of Hall’s Theorem）
   • 树的基本概念
   • 树的应用
   • 生成树

习题课课件

• Tutorial 1

期中考试参考答案

• Mid-Term Exam