Notes on _CS103 Mathematical Foundations of Computing_
内容提要
本文介绍集合势与可数性，用对角线法证明程序可数而问题不可数，从而存在不可计算问题；同时讲解命题逻辑、一阶逻辑、图论中的点覆盖、独立集、鸽巢原理、Ramsey定理，以及有限状态自动机DFA与NFA，并说明正则语言的定义与等价性。
延伸解读
可数性与不可计算性的核心论证
文章通过势的比较，构建了从程序到问题的链式不等式：程序作为有限字符串是可数的，而字符串集合的幂集不可数，问题又至少与字符串集合一样多，因此必然存在不可计算的问题。这一论证的关键在于对角线法，它表明任何试图枚举所有程序或所有可计算函数的尝试都会遗漏某些对象。理解这一点有助于把握计算理论中“可计算”与“不可计算”的根本界限。
实质蕴涵的“空真”设计及其工程意义
文章解释了为何在数学逻辑中，当前件为假时，蕴涵式自动为真。这种“空真”规定并非逻辑漏洞，而是为了简化推理规则，使证明过程无需额外讨论前件为假的情况。在编程中，这一逻辑等价于将蕴涵转换为“非或”形式，例如用“!p || q”替代“!(p && q)”，从而利用短路求值提高效率。这体现了逻辑设计与计算实践之间的紧密联系。
图论中的对偶关系与鸽巢原理
文章指出，顶点覆盖的补集必为独立集，反之亦然，这种对偶关系为图论问题提供了相互转化的视角。同时，广义鸽巢原理给出了分配问题的定量下界：将m个物品放入n个盒子，必有一个盒子至少含⌈m/n⌉个物品，且必有一个盒子至多含⌊m/n⌋个物品。这些结论在算法分析和组合证明中具有基础性作用，而Ramsey定理则进一步揭示了足够大的结构中必然出现有序子结构的哲学思想。
DFA与NFA的等价性及其意义
文章介绍了确定性有限自动机（DFA）和非确定性有限自动机（NFA）的基本概念，并指出两者在识别语言的能力上是等价的：一个语言是正则语言当且仅当存在某个NFA识别它。NFA通过ε-转移和多重选择提供了更灵活的描述方式，而DFA则更便于确定性计算。这种等价性使得我们可以根据具体需求选择更简洁的模型进行推理，同时也为正则语言的闭包性质等研究奠定了基础。
Q&A
什么是集合的势？如何比较两个集合的大小？
集合的势反映集合的大小。如果两个集合之间存在双射，就称它们等势。例如自然数集和偶数集等势，因为n与2n一一对应。康托定理指出，任何集合的势都小于其幂集的势。
对角线法如何证明存在不可计算的问题？
对角线法通过假设所有程序（或字符串）可枚举，构造一个不在列表中的子集D，从而证明问题集合的势大于程序集合。由于程序是可数的，而问题不可数，因此必然存在不可计算的问题。
为什么在逻辑中假命题可以推出任何命题？
这是实质蕴涵的定义：当前件为假时，整个蕴含式自动为真。这样做是为了使推理规则简单一致，避免在证明中额外讨论前件为假的情况，从而让数学体系顺畅运转。
点覆盖和独立集之间有什么关系？
点覆盖是包含每条边至少一个端点的顶点集合；独立集是任意两点不相邻的顶点集合。一个集合是点覆盖当且仅当它的补集是独立集，反之亦然。
Ramsey定理R(3,3)=6的实际意义是什么？
R(3,3)=6意味着在任意6个人的聚会中，要么有3个人互相认识，要么有3个人互相不认识。这体现了结构足够大时必然出现秩序。
DFA和NFA的主要区别是什么？它们识别的语言有何关系？
DFA的每一步转移是确定性的，而NFA在每一步有有限个选择，且允许ε-转移。一个语言是正则语言当且仅当存在DFA或NFA识别它，因此DFA和NFA识别的语言类相同。
