Math A 离散数学

离散数学模块覆盖逻辑、集合、关系、证明、递归与正确性。每个结论都写明量词和前提，因为漏掉一个条件通常比多写一页公式更贵。

先修知识

• 熟悉基本代数、函数和整数运算；集合、逻辑与证明方法会从本模块开始介绍。
• 能读简单循环与递归代码会更方便，可按需参考第一卷。

覆盖内容

第 1–2 章建立逻辑与集合语言；第 3–4 章练习证明、程序正确性、归纳与递推；第 5 章用关系和映射描述分类、依赖与对应。

第 1 章

• 1.1 命题逻辑：从需求句子到可判定公式
• 1.2 逻辑等价、范式与 SAT：让机器搜索解
• 1.3 谓词逻辑：对象、量词与程序规格

第 2 章

• 2.1 集合与运算：用成员关系描述对象范围
• 2.2 幂集、笛卡尔积与基数：集合怎样构造新空间
• 2.3 软件系统中的集合：数据结构、SQL 与近似成员查询

第 3 章

• 3.1 直接证明、逆否与分类讨论：搭出可检查的推理链
• 3.2 反例、反证与存在性：知道该找一个还是排除全部
• 3.3 程序正确性：规格、循环不变量与终止性

第 4 章

• 4.1 递归定义与数学归纳：沿构造过程证明
• 4.2 递推关系：展开、求和与特征方程
• 4.3 分治递推与主定理：先验证模型，再套结论

第 5 章

• 5.1 二元关系：性质、复合与闭包
• 5.2 等价关系与偏序：分类、依赖和格
• 5.3 函数与映射：定义域、像、单射和双射

学完能做什么

• 把自然语言条件写成逻辑公式，检查量词范围并构造反例。
• 为循环或递归给出不变量、归纳步骤与终止理由。
• 用集合、关系和函数说明对象范围、等价分类与依赖次序。

怎样使用这份目录

第一次接触证明时，从逻辑与集合按顺序读起，每个结论先试几个小例子，再检查推理为什么适用于全部对象。为算法课补基础时，可以重点看第 3–4 章；条件记不清就回查定义，不必靠记住证明的排版来过关。