离散数学

📚 内容概要

一门面向数学与计算机科学专业学生的离散数学入门课程。课程涵盖逻辑、集合、证明技巧、算法、数论、组合学、图论和自动机等基本主题。课程强调数学推理和解决问题的能力，为计算机科学的高级学习奠定基础。

掌握构成计算机科学基础的逻辑与结构。

作者： 理查德·约翰逊鲍格

致谢： 审稿人包括文卡塔·迪纳瓦希、马修·埃尔西、克里斯托夫·吉拉德-卡里埃、叶夫根尼·科维奇、菲利克斯·迈施、泰勒·麦克米伦、克里斯托弗·斯托姆、唐纳德·韦斯塔尔以及赵广华。感谢培生公司工作人员的支持：戴尔德丽·林奇、杰夫·威登纳、劳伦·莫尔斯等。

🎯 学习目标

1. 执行集合运算（包括差集和补集），并使用文氏图和定理 1.1.22 验证集合恒等式。
2. 构造并评估包含否定、析取和条件命题的命题真值表。
3. 应用推理规则和演绎推理来判断逻辑论证的有效性。
4. 定义并应用数学系统的组成部分，包括公理、定义和定理。
5. 构造代数和集合论命题的直接证明、反证法和分类讨论证明。
6. 利用数学归纳法原理和强归纳法证明恒等式、可除性性质及算法正确性。
7. 定义并分类函数（单射、满射、双射），并执行复合与逆运算。
8. 运用序列记号、字符串连接和递归规则来建模离散数据集。
9. 使用有向图和矩阵表示法分析二元关系的自反性、对称性和传递性等性质。
10. 定义一个算法，并验证其七个核心属性（输入、输出、精确性、确定性、有限性、正确性和普遍性）。

🔹 第一课：逻辑与集合论基础

概述： 本课建立离散数学的基本构建模块，重点在于集合的严格操作和逻辑的形式结构。学生将从集合运算与恒等式出发，逐步掌握逻辑论证的构建、条件命题的评估以及嵌套量词的分析。这些概念为算法设计、数据库理论以及计算机科学与工程中的形式化验证提供了必要框架。

学习成果：

• 执行集合运算（包括差集和补集），并使用文氏图和定理 1.1.22 验证集合恒等式。
• 构造并评估包含否定、析取和条件命题的命题真值表。
• 应用推理规则和演绎推理来判断逻辑论证的有效性。

🔹 第二课：数学证明技巧

概述： 本课介绍用于确立数学命题有效性的正式方法，以及在计算机科学与数学中所需的逻辑严谨性。学生将从基础数学系统和直接证明出发，逐步掌握如归结证明、数学归纳法（包括强归纳法），以及循环不变量在算法验证中的应用等复杂技术。

学习成果：

• 定义并应用数学系统的组成部分，包括公理、定义和定理。
• 构造代数和集合论命题的直接证明、反证法和分类讨论证明。
• 利用数学归纳法原理和强归纳法证明恒等式、可除性性质及算法正确性。

🔹 第三课：函数、序列与关系

概述： 本课涵盖计算机科学中用于建模数据与过程的基本数学结构。内容从函数的定义及其各类类型（单射、满射、双射）开始，深入研究序列、字符串以及二元关系的形式属性。学生将探索哈希函数、ISBN校验位、偏序下的任务调度，以及通过矩阵和数据库表示关系的实际应用。

学习成果：

• 定义并分类函数（单射、满射、双射），并执行复合与逆运算。
• 运用序列记号、字符串连接和递归规则来建模离散数据集。
• 使用有向图和矩阵表示法分析二元关系的自反性、对称性和传递性等性质。

🔹 第四课：算法分析与复杂度

概述： 本课涵盖算法的基本定义与属性，其在搜索与排序（特别是文本搜索和插入排序）中的实现，以及用于分析效率的严格数学框架。学生将探索渐近符号、函数增长速率，以及递归问题求解机制，包括分治策略如棋盘铺砖和基于斐波那契数列的序列。

学习成果：

• 定义一个算法，并验证其七个核心属性（输入、输出、精确性、确定性、有限性、正确性和普遍性）。
• 运用大 O、大 Ω 和大 Θ 符号表达算法的时间与空间复杂度。
• 使用重复二分法和多项式排序等技术分析最好情况、最坏情况和平均情况。

🔹 第五课：数论与密码学导论

概述： 本课探讨数论的基础原理，从因数与素数的基本性质到支撑现代安全通信的复杂算法。学生将掌握最大公约数（GCD）、进制转换和模幂运算的数学机制，以理解并实现 RSA 公钥加密系统。

学习成果：

• 定义并应用可除性、素性及算术基本定理的概念。
• 实现十进制、二进制与十六进制之间的高效转换。
• 执行欧几里得算法及其扩展形式，以求出 GCD 及线性组合（sa + tb）。

🔹 第六课：计数方法与离散概率

概述： 本课探讨有限结构的计数基本技术及其在离散概率中的应用。学生将从加法与乘法原理出发，逐步掌握卡塔兰数、斯特林数和二项式定理等高级概念。课程最后介绍鸽巢原理及其各种形式，为证明离散系统中特定配置的存在性提供严谨框架。

学习成果：

• 应用加法、乘法和容斥原理解决复杂的计数问题。
• 区分并计算排列与组合，包括相同对象和重复情况。
• 使用字典序生成算法实现排列与组合的生成。

🔹 第七课：递推关系

概述： 本课探讨递推关系在数学与计算机科学中的理论与应用。学生将学习使用迭代法和特征方程求解齐次与非齐次递推关系。此外，课程还展示了递推关系在分析选择排序、二分查找和归并排序等递归算法时间复杂度中的关键作用。

学习成果：

• 使用迭代法和特征方程（含不同根与重根）求解递推关系。
• 建模并求解经典数学问题，包括汉诺塔、斐波那契数列（黄金比例）和错排问题。
• 使用递推关系分析递归算法的最坏情况时间复杂度。

🔹 第八课：图论与最短路径算法

概述： 本课探讨图论的基础原理，从简单图与加权图的基本定义，到复杂算法解决方案如最短路径与环路识别。学生将研究平面性、连通性与同构等结构性质，并将其应用于经典问题，如柯尼斯堡桥问题、旅行商问题（TSP）和“瞬间疯狂”拼图。

学习成果：

• 定义并区分图的类型，包括简单图、加权图、完全图、二分图和 n-立方体。
• 分析图的连通性，识别欧拉回路、哈密顿回路，并使用 Dijkstra 算法确定最短路径。
• 应用矩阵表示法（邻接矩阵与关联矩阵）和图不变量验证同构性与平面性。

🔹 第九课：树与搜索算法

概述： 本课涵盖树在计算机科学与数学中的基本性质、特征与应用。学生将探索根树与二叉树、生成树算法（BFS/DFS）、最小生成树优化技术（如普里姆算法），以及回溯、锦标赛排序和博弈树中的极小极大算法等决策框架。

学习成果：

• 定义并识别根树，及其层级、高度和现实世界系统中的层次结构。
• 根据连通性、无环性及边与顶点数量比来刻画树。
• 实现并追踪生成树算法（BFS、DFS）、最小生成树算法（普里姆算法）和二叉搜索树的构建。

🔹 第十课：网络模型与流优化

概述： 本课探讨运输网络的数学建模，重点研究资源（流量）如何在有向图中从源点流向汇点。课程详细说明流量守恒规则、最大化吞吐量的算法步骤、网络割与流量容量的关系，以及这些原则在二分图匹配问题中的应用。

学习成果：

• 定义并验证运输网络及其有效流量分配的属性。
• 执行最大流算法（算法 10.2.4）以找到最优吞吐量。
• 应用最大流-最小割定理，通过网络划分证明流量最优性。

🔹 第十一课：布尔代数与逻辑电路

概述： 本课探讨数字逻辑的数学基础，重点研究布尔代数如何为设计与简化组合电路提供形式语言。学生将学习在逻辑门、开关电路与布尔表达式之间进行转换，最终运用这些工具合成复杂函数，并构建加法器和二进制补码逻辑等关键算术组件。

学习成果：

• 使用标准逻辑门（与、或、非）和开关配置设计与分析组合电路。
• 应用布尔代数定律与对偶定理证明电路等价性并简化表达式。
• 从真值表合成布尔函数为析取范式（DNF）和合取范式（CNF）。

🔹 第十二课：自动机、语法与形式语言

概述： 本课探讨计算的数学基础，从具有内部记忆的时序电路与有限状态机开始，通过单位时间延迟模拟状态。课程涵盖短语结构语法（类型 1、2、3）的形式定义与分类，背诵正则形式（BNF）的应用，以及林登迈尔语法在分形生成中的特殊用途。最后，阐明确定性与非确定性有限状态自动机之间的关键关系，以及它们所接受的形式语言。

学习成果：

• 使用状态转移图和状态函数分析与设计有限状态机（FSM）和自动机（FSA/NFA）。
• 在乔姆斯基层级中对语法进行分类，并使用产生式规则与 BNF 表示推导字符串。
• 使用林登迈尔语法和同步替换规则建模自相似结构，如科赫雪花。