第1章：启程与逻辑基石——命题逻辑与集合论

当主角推开数学王国那扇刻满符号的青铜大门时，一位手持逻辑之杖的守卫拦住了去路。“欲入此门，须先解开我心中的谜题。”守卫的声音如钟声般回荡，“若你能证明：在所有可能的命题世界中，以下表达式永真……”守卫在空中划出一道闪光的公式：$(p \rightarrow q) \lor (q \rightarrow p)$。主角凝视着这看似简单的表达式，意识到这不仅是入口的钥匙，更是整个数学王国的语言基石——命题逻辑。数学的征程始于如此纯粹的推理，而真正的探险，往往从最基础的逻辑与集合公理出发。本章将深入形式逻辑系统的核心，剖析命题逻辑的语法与语义，揭示真值表背后的机械确定性，探索逻辑等价的精妙对称，并概览完备性定理的深刻内涵；随后，我们将转入集合论的公理化基础，审视ZFC公理如何从悖论中崛起，构建起现代数学的承载框架。通过实践案例，我们将用Python实现命题逻辑求值器，以代码验证逻辑定律；更将用集合运算模型破解王国入口的谜题，体验抽象概念解决实际问题的力量。这些内容不仅是后续代数结构、拓扑空间与范畴理论的基石，更是贯穿整个数学秘境的通用语言。

逻辑守卫的谜题：命题逻辑的召唤

守卫的谜题——$(p \rightarrow q) \lor (q \rightarrow p)$——表面平凡，却暗藏玄机。它要求证明该公式在命题逻辑中永真（tautology），即无论原子命题$p$与$q$取何真值，整个表达式恒为真。这引出了命题逻辑的基本问题：如何精确描述“命题”、如何组合它们形成“公式”，以及如何定义“永真”。在数学王国，一切推理最终可归约为命题间的逻辑关系，而命题逻辑正是这种关系的初级形式化。

考虑一个更复杂的守卫谜题：“若我所说为真，则金门开放；若金门开放，则银门关闭。但银门确实关闭。因此，我所说是否为真？”用命题符号化：设$P$表示“我所说为真”，$Q$表示“金门开放”，$R$表示“银门关闭”。守卫陈述：$P \rightarrow Q$，$Q \rightarrow R$，且$R$为真。问题：$P$是否为真？这实际涉及假言推理（Modus Ponens）与逻辑等价转换，但首先需建立命题逻辑的严格系统。

命题逻辑的形式系统

语法：符号、公式形成规则

命题逻辑（Propositional Logic）的语法定义其符号与良构公式（well-formed formula, wff）的构造规则。我们从一个可数集$\mathcal{P} = \{p_1, p_2, p_3, \ldots\}$的原子命题（atomic propositions）开始，每个原子命题被视为一个基本真值载体。接着，引入逻辑连接子（logical connectives）：

• 否定（negation）：$\neg$
• 合取（conjunction）：$\land$
• 析取（disjunction）：$\lor$
• 蕴含（implication）：$\rightarrow$
• 双条件（biconditional）：$\leftrightarrow$

这些连接子的元数（arity）分别为：$\neg$为一元，其余为二元。有时引入常量$\top$（真）与$\bot$（假），但可由原子命题与连接子表达。

形式语法：良构公式递归定义如下： 1. 每个原子命题$p \in \mathcal{P}$是wff。 2. 若$\phi$是wff，则$\neg \phi$是wff。 3. 若$\phi$和$\psi$是wff，则$(\phi \land \psi)$、$(\phi \lor \psi)$、$(\phi \rightarrow \psi)$、$(\phi \leftrightarrow \psi)$是wff。 4. 仅由以上规则生成的字符串是wff。

括号用于消除歧义，实际中可根据优先级省略：$\neg$最高，$\land$与$\lor$次之（$\land$高于$\lor$），$\rightarrow$与$\leftrightarrow$最低。例如，$p \land q \rightarrow r$意为$(p \land q) \rightarrow r$。

语法仅关心符号串的结构，不涉及意义。这种符号操作正是后来计算机科学中布尔电路与编程语言语法的基础。

语义：真值赋值与真值表

语义赋予公式意义。一个真值赋值（truth assignment）是一个函数$v: \mathcal{P} \rightarrow \{0, 1\}$（0表假，1表真），它将每个原子命题映射到真值。此赋值可唯一扩展至所有wff，记作$\bar{v}(\phi)$，递归定义：

• 若$\phi = p$为原子，则$\bar{v}(p) = v(p)$。
• 若$\phi = \neg \psi$，则$\bar{v}(\neg \psi) = 1 - \bar{v}(\psi)$（即逻辑非）。
• 若$\phi = (\psi \land \chi)$，则$\bar{v}(\psi \land \chi) = \min(\bar{v}(\psi), \bar{v}(\chi))$（即逻辑与）。
• 若$\phi = (\psi \lor \chi)$，则$\bar{v}(\psi \lor \chi) = \max(\bar{v}(\psi), \bar{v}(\chi))$（即逻辑或）。
• 若$\phi = (\psi \rightarrow \chi)$，则$\bar{v}(\psi \rightarrow \chi) = \max(1 - \bar{v}(\psi), \bar{v}(\chi))$（即假言判断：前件假或后件真）。
• 若$\phi = (\psi \leftrightarrow \chi)$，则$\bar{v}(\psi \leftrightarrow \chi) = 1$当且仅当$\bar{v}(\psi) = \bar{v}(\chi)$。

对于$n$个不同原子命题，有$2^n$种可能的真值赋值。每个赋值对应一个解释（interpretation）或真值指派。

真值表（truth table）枚举所有赋值下公式的真值。例如，对$p \rightarrow q$：

| $p$ | $q$ | $p \rightarrow q$ | |-----|-----|-------------------| | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 1 |

可见$p \rightarrow q$仅在$p$真$q$假时为假，其余为真。这符合日常“若…则…”的直觉：承诺仅在前提成立而结论不成立时被违背。

守卫的公式$(p \rightarrow q) \lor (q \rightarrow

守卫的公式$(p \rightarrow q) \lor (q \rightarrow p)$可通过真值表验证其永真性：

| $p$ | $q$ | $p \rightarrow q$ | $q \rightarrow p$ | $(p \rightarrow q) \lor (q \rightarrow p)$ | |-----|-----|-------------------|-------------------|------------------------------------------| | 0 | 0 | 1 | 1 | 1 | | 0 | 1 | 1 | 0 | 1 | | 1 | 0 | 0 | 1 | 1 | | 1 | 1 | 1 | 1 | 1 |

在所有四种真值指派下，公式取值均为1，故为永真式（tautology）。这一结果揭示了二值逻辑中一个深刻事实：对任意两个命题，至少存在一个方向的有效蕴含。其直觉根源在于，若$p$与$q$同真或同假，则双向蕴含成立；若真值不同，则必有一方为真而另一方为假，此时从假命题可推出任何命题（$p \rightarrow q$当$p$假时恒真），故析取式仍真。这实际是经典逻辑中“矛盾律”与“排中律”的衍生表现。

逻辑等价与重写律

两公式$\phi$与$\psi$称为逻辑等价（logically equivalent），记作$\phi \equiv \psi$，若对所有真值赋值$v$，有$\bar{v}(\phi) = \bar{v}(\psi)$。等价于复合公式$\phi \leftrightarrow \psi$为永真式。逻辑等价是公式重写的核心，允许在证明中替换而不改变真值。

关键等价定律（均可通过真值表验证）：

1. 双重否定律：$\neg \neg p \equiv p$ 2. 德·摩根律（De Morgan's Laws）：

• $\neg (p \land q) \equiv \neg p \lor \neg q$
• $\neg (p \lor q) \equiv \neg p \land \neg q$

3. 分配律：

• $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
• $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

4. 结合律：

• $(p \land q) \land r \equiv p \land (q \land r)$
• $(p \lor q) \lor r \equiv p \lor (q \lor r)$

5. 交换律：

• $p \land q \equiv q \land p$
• $p \lor q \equiv q \lor p$

6. 幂等律：

• $p \land p \equiv p$
• $p \lor p \equiv p$

7. 吸收律：

• $p \land (p \lor q) \equiv p$
• $p \lor (p \land q) \equiv p$

8. 蕴含等价：$p \rightarrow q \equiv \neg p \lor q$ 9. 逆否命题等价：$p \rightarrow q \equiv \neg q \rightarrow \neg p$ 10. 双条件等价：$p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p) \equiv (p \land q) \lor (\neg p \land \neg q)$

这些定律构成布尔代数的等式公理系。事实上，命题逻辑的代数结构正是布尔代数：集合$\{0,1\}$上定义运算$\land$（交）、$\lor$（并）、$\neg$（补），满足交换律、结合律、分配律、同一律（$p \land 1 \equiv p$，$p \lor 0 \equiv p$）、互补律（$p \land \neg p \equiv 0$，$p \lor \neg p \equiv 1$）。布尔代数是数字电路设计、数据库查询优化乃至集合运算的抽象基础。

示例：简化公式$(p \rightarrow q) \land (p \lor q)$。 步骤：

• 将蕴含替换：$(\neg p \lor q) \land (p \lor q)$
• 提取公因子$q$：$(\neg p \lor q) \land (p \lor q) \equiv ((\neg p \lor q) \land p) \lor ((\neg p \lor q) \land q)$？更优用分配律：

$(\neg p \lor q) \land (p \lor q) \equiv ((\neg p \lor q) \land p) \lor ((\neg p \lor q) \land q)$ 不简洁。 注意：$A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$，但此处是$(\neg p \lor q) \land (p \lor q)$，可视为$(X) \land (Y)$，其中$X=\neg p \lor q$，$Y=p \lor q$。 尝试：$(\neg p \lor q) \land (p \lor q) \equiv ((\neg p \lor q) \land p) \lor ((\neg p \lor q) \land q)$ 由分配律$A \land (B \lor C) = (A \land B) \lor (A \land C)$，但这里$Y$是析取，所以$X \land Y = X \land (p \lor q) = (X \land p) \lor (X \land q)$。 计算： $X \land p = (\neg p \lor q) \land p \equiv (p \land \neg p) \lor (p \land q) \equiv 0 \lor (p \land q) \equiv p \land q$ $X \land q = (\neg p \lor q) \land q \equiv (\neg p \land q) \lor (q \land q) \equiv (\neg p \land q) \lor q \equiv q$（因$q \land q = q$，且$(\neg p \land q) \lor q = q$由吸收律） 故整体$\equiv (p \land q) \lor q \equiv q$（吸收律）。 因此原公式等价于$q$。 验证：当$q$真时，无论$p$如何，$p \rightarrow q$真（后件真），且$p \lor q$真，故合取真；当$q$假时，$p \rightarrow q$要求$p$假，但$p \lor q$要求$p$真，矛盾，故整体假。确实等价于$q$。

此例展示逻辑等价作为重写系统的力量：通过应用定律逐步简化公式，最终得到最简形式（如合取范式或析取范式），这在自动定理证明与逻辑综合中至关重要。

永真式、矛盾式与可满足式

基于语义，公式分类：

• **永真式**（tautology）：对所有赋值真值为1。如$p \lor \neg p$（排中律）、$p \rightarrow p$（同一律）、守卫公式。
• **矛盾式**（contradiction）：对所有赋值真值为0。如$p \land \neg p$（矛盾律）。
• **可满足式**（satisfiable）：存在至少一个赋值使其为真。永真式是可满足的，但可满足式未必永真。如$p$可满足（当$p$真时），但非永真。

判定问题：给定公式$\phi$，是否存在赋值使其为真？这是可满足性问题（SAT）。对于命题逻辑，可通过真值表（$2^n$种赋值）判定，但为NP完全问题。然而，实践中存在高效算法（如DPLL）处理大规模实例，这是计算机科学的核心问题。

示例：公式$(p \rightarrow q) \land (q \rightarrow r) \land p \land \neg r$是否可满足？ 假设$p$真，由$p \rightarrow q$得$q$真；由$q \rightarrow r$得$r$真；但$\neg r$要求$r$假，矛盾。故无满足赋值，为矛盾式。这实际是经典的三段论推理：若$p \rightarrow q$，$q \rightarrow r$，$p$真，则$r$必真；现附加$\neg r$，故前提集合不一致。

推理规则与证明系统

逻辑不仅关注公式真值，更关注推理：从前提集合$\Gamma$推导结论$\phi$。形式证明系统提供推理规则。

希尔伯特系统（Hilbert system）通常取少量公理模式与推理规则（如肯定前件）。例如，经典命题逻辑的以下公理：

• (A1) $p \rightarrow (q \rightarrow p)$
• (A2) $(p \rightarrow (q \rightarrow r)) \rightarrow ((p \rightarrow q) \rightarrow (p \rightarrow r))$
• (A3) $(\neg p \rightarrow \neg q) \rightarrow (q \rightarrow p)$

规则：Modus Ponens（MP）：从$p$和$p \rightarrow q$推出$q$。

可证明所有永真式。例如，证明$p \rightarrow p$： 1. 实例化(A1)：$p \rightarrow ((p \rightarrow p) \rightarrow p)$ 2. 实例化(A1)：$(p \rightarrow ((p \rightarrow p) \rightarrow p)) \rightarrow ((p \rightarrow (p \rightarrow p)) \rightarrow (p \rightarrow p))$ 3. 由1,2 MP：$(p \rightarrow (p \rightarrow p)) \rightarrow (p \rightarrow p)$ 4. 实例化(A1)：$p \rightarrow (p \rightarrow p)$ 5. 由3,4 MP：$p \rightarrow p$

自然演绎（Natural deduction）更接近实际推理，引入假设与消去规则。例如：

• 假设引入：若从假设$p$可推出$q$，则得$p \rightarrow q$（→-引入）
• 假设消去：若有