课程 · 资源记录
MIT 6.042J Mathematics for Computer Science
离散数学课程，系统覆盖定义、证明、集合、函数、关系、计数与离散概率。
为什么重要
用于核对集合与函数语言、有限集合上的证明方法，以及组合计数、条件概率和离散概率的推导。
阅读前提
无特定站内先修要求。
教材中的引用位置
- C01 · 第 1 章 序列、栈、队列、树与堆
支持的主张：MIT《Mathematics for Computer Science》在本章用于验证序列与树的离散结构性质：结构归纳证明递归定义和遍历不变量，求和与递推关系计算树高、节点数和操作次数，偏序观点则区分树中层级关系与线性存储次序。因而堆、搜索树和递归遍历的复杂度结论都能追溯到明确的结构假设。
- C01 · 第 2 章 哈希表、图与并查集
支持的主张：MIT《Mathematics for Computer Science》用于支撑本章对图、树和随机散列的数学建模：顶点—边关系给出 BFS、DFS 与连通分量的定义域，等价关系解释并查集维护的集合划分，概率工具则说明哈希操作的期望界必须以随机模型和负载条件为前提。这些依据把抽象结构的性质与实现中的复杂度声明一一对应。
- C01 · 第 3 章 分治、贪心与排序
支持的主张：MIT《Mathematics for Computer Science》在这里支撑两类关键证明工具：递推式与归纳法用于把分治子问题的规模关系转成复杂度界，交换论证和不变量用于证明一次局部贪心选择可以嵌入某个全局最优解。它同时说明这些证明依赖问题结构，因而不能仅凭“每步看起来最好”推断任意贪心算法正确。
- C01 · 第 4 章 动态规划与图算法
支持的主张：MIT 6.006 的图搜索、最短路和动态规划讲义用于核对本章算法的不变量、松弛步骤与渐近代价；MIT 6.042J 则用于核对图、路径、连通性及归纳证明的离散数学定义。前者支持“算法怎样运行”，后者支持“为何这些图论条件足以推出正确性”，两类证据不互相替代。
- C01 · 第 5 章 渐近复杂度、归约与可计算性
支持的主张：MIT《Mathematics for Computer Science》为本章的可计算性论证提供离散数学基础：可数性与对角化用于说明“问题可描述”不等于“存在终止算法”，命题逻辑和归约语言用于区分判定问题、验证过程与复杂度类别。由此，本章关于不可判定性和 P、NP 的陈述被限制在已证明结论内，不把尚未解决的类别关系当作事实。
- C01 · 第 6 章 数据结构与算法综合复习
支持的主张：MIT《Mathematics for Computer Science》在本章用于支撑“算法正确性必须由离散结构上的论证保证”这一主张：图与关系给出配送网络的数学对象，归纳法和循环不变量解释最短路为何保持已确定距离，而渐近记号则把实现成本与输入规模联系起来。这些内容共同限定了综合案例中从问题合同到正确性证明的推理链。
- M00 · 第 1 章 命题、量词与逻辑联结词
支持的主张：MIT 6.042J《Mathematics for Computer Science》的基础部分把命题逻辑、谓词、量词和证明方法置于同一学习序列，并配有开放教材与习题。阅读时可对照真值表、量词否定和逆否命题，再独立完成课程中的符号化练习。
- M00 · 第 2 章 集合、映射与关系
支持的主张：MIT 6.042J 第 4 章系统处理集合、关系、函数、复合、单射、满射和有限基数；官方 课程讲义页 还把“Sets and Functions”列为独立课次，并提供课堂问题与解答。阅读时可把有限箭头图改写成定义域、陪域与有序对集合，再逐项判断函数性质。
- M00 · 第 3 章 直接证明、反证法与构造法
支持的主张：MIT 6.042J《Mathematics for Computer Science》的开放教材以定义、证明、集合、函数和关系为基础主题，并提供直接证明、反证、归纳与离散结构习题。阅读范例时，应把每一步标注为定义展开、代数变形、已知定理或见证核验，再尝试在不改变逻辑结构的前提下压缩文字。
- M00 · 第 4 章 等价关系、序关系与数学归纳法
支持的主张：麻省理工学院开放课程 6.042J（下文简称 MIT 6.042J）的集合论、关系与归纳章节用于核对等价关系、偏序、良序原理和强归纳的标准表述。正文中的模四分类、整除偏序和奇数求和仍逐步独立演算，资源卡提供的是定义与课程上下文。
- M00 · 第 5 章 有限性、可数性与基本代数结构
支持的主张：MIT 6.042J 的计数、集合与离散结构材料用于核对加法原理、乘法原理、可数编码和基础关系语言。配对函数的四个数值、模八运算表以及三道练习均在正文中给出可复算过程，不依赖资源卡代替证明。
- M00 · 第 6 章 数学语言与证明综合复习
支持的主张：MIT 6.042J 的逻辑、证明、集合、函数与关系材料用于核对量词规则、有限分类论证和等价关系语言。正文中的模四到模二映射、像与原像证明以及二进制串练习都给出了独立推导，读者可逐行检查代表元、见证和量词范围。
- M01 · 第 3 章 函数、变换与图像
支持的主张：MIT《Mathematics for Computer Science》从集合与对应关系刻画函数，OpenStax《Calculus Volume 1》则把这一抽象定义落实到实函数的图像、复合、反函数和变化率。本章据此区分定义域、陪域与像集，并说明图像变换必须同时追踪输入和输出；只有单射且像覆盖目标集合时，反函数才作为该陪域上的函数成立。
- M05 · 第 1 章 概率公理与组合概率
支持的主张：MIT 6.042J Mathematics for Computer Science 的官方课程材料覆盖加法与乘法原理、排列组合、容斥和离散概率，并配有习题材料，适合复核本章有限模型的计数路径。
- M05 · 第 2 章 条件概率、独立性与贝叶斯公式
支持的主张：MIT 6.042J Mathematics for Computer Science 的官方材料覆盖离散概率、条件概率、独立性与计数模型，为本章有限样本空间反例和练习提供可核对的课程背景。
- M05 · 第 6 章 概率模型、随机变量与极限定理综合复习
支持的主张：MIT OpenCourseWare 6.042J 的离散数学材料覆盖计数与离散概率，可用于复核组合数分母、互斥划分和有限样本空间推导。
- M07 · 第 1 章 计数原理、容斥与鸽巢原理
支持的主张：MIT OpenCourseWare 的 Mathematics for Computer Science 材料系统讨论计数、双射、容斥和鸽巢原理，适合用不同证明路线复核本章结论。
- M07 · 第 2 章 递推关系与生成函数
支持的主张：MIT OpenCourseWare 的 Mathematics for Computer Science 材料覆盖递推、计数和生成函数，可用于对照特征根与组合分解的不同解法。
- M07 · 第 3 章 图、路径、连通性与树
支持的主张：MIT OpenCourseWare 6.042J 的离散数学课程把图、树、遍历和证明方法放在统一的计算机科学数学框架内，可用于复核本章定义与典型论证。
- M07 · 第 4 章 匹配、覆盖与图着色
支持的主张：MIT OpenCourseWare 6.042J 的离散数学材料系统讨论匹配、图着色和组合证明，适合沿着“定义—极值证书—算法”核对本章结构。
- M07 · 第 5 章 偏序集、格与布尔代数
支持的主张：MIT《Mathematics for Computer Science》在本章支撑偏序与布尔结构的离散证明：关系的自反、反对称和传递性用于判定偏序，Hasse 图只省略可由传递性恢复的边，布尔格则把集合包含、交、并和补运算联系起来。该来源还为拓扑排序和 Möbius 型反演提供有限结构背景，明确有限性是若干求和公式成立的关键条件。
- M07 · 第 6 章 组合、图论与离散证明综合复习
支持的主张：MIT 6.042J 将证明、计数、递推、图、偏序和离散概率放在同一课程中，适合按本章对象账本逐项核对定义与定理条件。