1.1 数理逻辑与集合论预备

1.1 数理逻辑与集合论预备

本节摘要：要谈计算，先谈推理。本节讲清楚数理逻辑（命题/一阶逻辑）和集合论（集合/基数/对角线论证）这两个计算理论的数学地基。读完你能理解为什么"计算"能被严格定义、为什么存在不可判定问题（根源在对角线论证）。

一、为什么需要形式化逻辑

日常推理用自然语言，模糊多义。"所有人是会死的，苏格拉底是人，所以苏格拉底会死"——这个三段论自然语言能懂，但要让机器推理，必须把"所有""所以"这些词变成严格符号。

数理逻辑就是把推理形式化：用符号代替自然语言，用推理规则保证从真前提推出真结论。这是计算理论的语言基础——图灵机、可计算性、复杂性，全用这套符号表述。

二、命题逻辑

最简单的逻辑，处理"命题"（能判断真假的陈述句）和连接词。

命题：能判断真假的句子，如"2 是质数"（真）、"雪是黑的"（假）。

连接词：

• 非（¬）：¬p 真 iff p 假
• 与（∧）：p∧q 真 iff 都真
• 或（∨）：p∨q 真 iff 至少一真
• 蕴含（→）：p→q 假 iff p 真 q 假
• 等价（↔）：p↔q 真 iff 同真同假

命题逻辑能表达"如果...那么..."这种推理，但表达不了"所有""存在"这种量词。要表达"所有人是会死的"，需要一阶逻辑。

三、一阶逻辑

在命题逻辑上加量词和谓词，能表达更丰富的陈述。

量词：

• 全称（∀）：∀x P(x) 表示"对所有 x，P(x) 成立"
• 存在（∃）：∃x P(x) 表示"存在 x 使 P(x) 成立"

谓词：表示性质或关系，如 Man(x)（x 是人）、Mortal(x)（x 会死）。

"所有人是会死的"形式化为：∀x(Man(x) → Mortal(x))。

一阶逻辑是数学的标准语言——皮亚诺算术、ZFC 集合论都用它表述。计算理论里，图灵机的定义、复杂性的陈述，都基于一阶逻辑。

四、哥德尔不完备定理

1931 年哥德尔证明：任何包含初等算术的一致形式系统，存在真命题但系统内无法证明。

这震撼了数学界——原来"可证明"和"真"不是一回事，形式系统有内在局限。

哥德尔用编码（哥德尔数）把"这个命题不可证"编码成系统内的命题，构造出自指悖论。这个技巧直接启发了后面的对角线论证和不可判定性证明——停机问题不可判定的证明，本质是哥德尔方法的变体。

意义：计算理论继承了哥德尔的洞察——计算系统有内在局限，存在不可计算的问题。这是可计算性理论的哲学源头。

五、集合论基础

集合论是现代数学的地基，也是计算理论的语言。

集合：无序不重复元素的汇集。{1, 2, 3} 是集合。

关系：集合间的对应。R ⊆ A×B 表示 A 到 B 的关系。

函数：特殊的关系，每个输入对应唯一输出。f: A→B。

等价关系：自反、对称、传递的关系。如"模 2 同余"把整数分成奇偶两类。

这些是基础工具，后面定义图灵机（状态集、转移函数）、复杂性类（按资源关系分类），都用这些。

六、基数与可数性

康托尔把"无穷"分了层级——不是所有无穷一样大。

可数无穷（ℵ₀）：能和自然数一一对应的集合。如整数、有理数都是可数无穷。

不可数无穷：比可数无穷大。实数是不可数的——康托尔用对角线论证证明。

图 1-1 对角线论证

对角线论证的精髓：假设实数可数（能列成表），构造一个新数，它的第 i 位和表中第 i 个数的第 i 位不同——这个新数和表中每个数都至少差一位，所以不在表里，矛盾。

这个论证是计算理论的基石——停机问题不可判定、存在不可计算函数，都用对角线论证的变体证明。理解对角线论证，就理解了为什么存在不可计算的问题。

七、对角线论证的通用形式

对角线论证不只证明实数不可数，它是通用技巧：

假设要证明"存在 X 不能被 Y 枚举"。构造一个对角线对象 d，d 的第 i 个属性和 Y 中第 i 个对象的第 i 个属性不同。这样 d 和每个 Y 都不同，所以 d 不在 Y 的枚举里，矛盾。

计算理论里反复用这个：

• 停机问题：假设有判定停机的程序 H，构造程序 D 在 H 说它停机时不停、说不停时停，D 对自己运行产生矛盾。
• 存在不可计算函数：假设所有函数可计算，用对角线构造一个不在表里的函数。

对角线论证是"自指悖论"的数学化——构造一个对象，它引用自己的定义来否定自己。哥德尔不完备、停机问题不可判定、存在不可计算函数，本质都是这个套路。

八、为什么这些是计算理论的地基

数理逻辑给了计算理论语言——用一阶逻辑定义图灵机、表述复杂性类。

集合论给了工具——基数区分可数/不可数，对角线论证证明不可判定。

哥德尔不完备给了哲学——计算系统有内在局限，预示了不可计算的存在。

没有这些，后面"图灵机""不可判定""P vs NP"都无从谈起。所以这门理论从逻辑和集合论开始，不是凑数，是真正的地基。

⚠️ 常见误区：以为"无穷都一样大"。整数、有理数可数（ℵ₀），实数不可数（更大）。这个区分是计算理论的根基——可计算的问题都是可数的（算法是有限描述），但问题总数不可数，所以多数问题不可计算。

💡 关键直觉：数理逻辑给计算理论语言（一阶逻辑表述），集合论给工具（基数/对角线），哥德尔给哲学（系统有局限）。对角线论证是核心技巧——构造自指对象否定自己，证明停机问题不可判定、存在不可计算函数。可计算的问题可数，问题总数不可数，所以多数问题不可计算。

一节小结

• 数理逻辑：命题逻辑（连接词）+一阶逻辑（量词谓词），计算理论的语言基础。
• 哥德尔不完备：含算术的一致系统有真但不可证命题，预示计算系统有局限，启发对角线论证。
• 集合论：集合/关系/函数/等价关系，定义图灵机和复杂性类的工具。
• 基数：可数无穷（ℵ₀，整数/有理数）vs 不可数无穷（实数），康托尔分无穷层级。
• 对角线论证：假设可枚举，构造第 i 位和第 i 对象第 i 位不同的对象，不在枚举里，矛盾。
• 通用形式：自指悖论数学化，停机问题/不可计算函数/哥德尔不完备都是变体。
• 根基意义：可计算问题可数，问题总数不可数，多数问题不可计算——这是可计算性理论的出发点。