文档摘要

离散数学 离散数学（discrete maths）研究的是可数、分离的结构，是整个计算机科学的基石。本文件涵盖命题逻辑与谓词逻辑、证明技术、集合、关系、函数、图论基础以及递推关系。 在前面的章节里，我们打交道的主要是连续数学：微积分（第 3 章）、概率分布（第 5 章）、对实值参数的优化（第 6 章）。但计算机本质上是离散的机器。它存储比特（0 或 1），处理整数，遵循分支逻辑，操作有限的数据结构。离散数学为推理这些结构提供了形式化语言。 本章随后所有内容都建立在离散数学之上：处理器的逻辑门就是布尔代数，调度算法需要正确性证明，内存管理用到集合运算，而算法分析离不开递推关系。 命题逻辑 命题逻辑（propositional logic）是关于真/假陈述的代数。

---