逻辑之门：命题与证明的起点

探险者的脚步在雾气弥漫的智域入口处停住了。眼前并非想象中宏伟的拱门，而是一面光滑如镜的黑色石壁，壁上没有任何缝隙或把手，只在中央浮现出一行由光点组成的古老铭文：“凡欲入此门者，必先证其思之无谬。” 话音未落，石壁本身仿佛活了过来，光影流转，凝聚成一个由纯粹逻辑结构构成的人形——逻辑守卫。它没有面容，只有一双由不断生成与湮灭的真值表构成的眼睛。

“欢迎，寻求严谨之人，” 守卫的声音直接回荡在探险者的意识中，清晰、冰冷、毫无情绪波动，“智域之根基，非感官之幻象，乃推理之必然。欲通此门，须过我三问。第一问，最为朴素：请用我们的语言，精确表达‘并非所有探索者都抵达了此处’这一判断。”

这便是逻辑的起点：将混沌的现实世界陈述，转化为可被纯粹形式系统审视、操纵的命题。探险者意识到，守卫所求的，并非一个模糊的答案，而是一个符合命题逻辑句法规则的、结构正确的合式公式。这面石壁本身，便是一个巨大的语义解释装置：它将探险者输入的符号序列，与“抵达”这一关系在特定模型（即当前场景）中的真值进行比对，真则门开，谬则石壁固守。

---

一、 命题逻辑的语法：构建形式语言的骨架

命题逻辑（Propositional Logic），又称语句逻辑，是研究复合命题如何由更简单的原子命题（Atoms）通过逻辑联结词（Logical Connectives）组合而成，并考察其逻辑性质的学科。它是一阶逻辑的基石，也是整个现代符号逻辑的出发点。

1.1 原子命题与合式公式

原子命题（通常用 $p, q, r, \dots$ 表示）是逻辑语法中最基本的、不可再分解的陈述单位。它必须是一个有确定真值的陈述句（在经典二值逻辑中，真值仅为“真”或“假”）。例如，“今天下雨”、“2是素数”、“智域存在”。需要注意的是，原子命题关注的是其真值承载功能，而非内容实质。因此，“如果2是素数，则雪是白的”在句法上可视为一个由两个原子命题通过联结词构成的复合命题，其内容在逻辑形式分析中被暂时悬置。

合式公式（Well-Formed Formula, wff）是命题逻辑中合法的符号表达式，其构造遵循严格的递归定义： 1. 任何原子命题是 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$ 次之，$\rightarrow, \leftrightarrow$ 最后）。例如，$p \land q \rightarrow r$ 是歧义的，必须写作 $(p \land q) \rightarrow r$ 或 $p \land (q \rightarrow r)$，二者逻辑意义不同。

> 侧边栏：逻辑联结词的自然语言对应与陷阱 > 自然语言中的“与”、“或”、“如果…那么…”等词与逻辑联结词存在系统性的偏差。例如，逻辑“或”（$\lor$）是相容的（inclusive），即 $p \lor q$ 在 $p, q$ 同真时仍为真；而自然语言的“或”常为排斥的（exclusive）。逻辑“蕴含”（$\rightarrow$）的真值表定义为：仅当前件真而后件假时为假，其余情况（包括前件假）均为真。这导致了著名的实质蕴含悖论（Paradox of Material Implication），如“如果2+2=5，则雪是白的”在经典逻辑中被判定为真，因其前件为假。这种反直觉性正是形式化抽象所付出的代价，它剥离了因果、关联等语用内容，仅保留真值函数关系。

1.2 五种基本联结词的语义：真值表

联结词的语义由其真值表（Truth Table）定义，即规定在所有可能的真值赋值下，复合命题的真值如何由其组成部分的真值真值函数地决定。

设原子命题集合为 $\text{Atoms}$，一个赋值（Interpretation/Assignment）$v$ 是从 $\text{Atoms}$ 到 $\{T, F\}$（真，假）的函数。wff $\phi$ 在赋值 $v$ 下的真值 $v(\phi)$ 递归定义如下：

• $v(p) = v(p)$，对任意原子命题 $p$。
• $v(\neg \phi) = T$ 当且仅当 $v(\phi) = F$。
• $v(\phi \land \psi) = T$ 当且仅当 $v(\phi) = T$ 且 $v(\psi) = T$。
• $v(\phi \lor \psi) = T$ 当且仅当 $v(\phi) = T$ 或 $v(\psi) = T$（或两者）。
• $v(\phi \rightarrow \psi) = F$ 当且仅当 $v(\phi) = T$ 且 $v(\psi) = F$；其余为 $T$。
• $v(\phi \leftrightarrow \psi) = T$ 当且仅当 $v(\phi) = v(\psi)$。

下表汇总了五种基本联结词的真值表：

| $p$ | $q$ | $\neg p$ | $p \land q$ | $p \lor q$ | $p \rightarrow q$ | $p \leftrightarrow q$ | | :--: | :--: | :------: | :---------: | :--------: | :---------------: | :------------------: | | T | T | F | T | T | T | T | | T | F | F | F | T | F | F | | F | T | T | F | T | T | F | | F | F | T | F | F | T | T |

mermaid ```mermaid graph TD A[命题逻辑语义框架] --> B[原子命题 p, q, r...] A --> C[逻辑联结词] B --> D[真值赋值 v: Atoms → {T, F}] C --> E[¬ 非] C --> F[∧ 与] C --> G[∨ 或] C --> H[→ 蕴含] C --> I[↔ 等价] D --> J[递归定义复合命题真值] J --> K[生成真值表] K --> L[判定 wff 在特定赋值下的真值] ```

---

二、 逻辑守卫的第一问：从自然语言到合式公式

守卫的第一问：“请用我们的语言，精确表达‘并非所有探索者都抵达了此处’。”

探险者必须完成两个转换：自然语言 → 命题逻辑形式，以及未量化的命题逻辑 → 引入量词的命题（预示一阶逻辑）。

1. 识别核心结构：该陈述是一个对全称判断的否定。“所有探索者都抵达了此处”是一个全称肯定命题，形式为“对于所有 $x$，$x$ 是探索者且 $x$ 抵达此处”。其否定即为“并非（对于所有 $x$，$x$ 是探索者且 $x$ 抵达此处）”。 2. 命题逻辑的局限：若仅用命题逻辑，我们只能设 $P$ = “所有探索者都抵达了此处”，则原句为 $\neg P$。但这完全丢失了内部结构，无法进行更细粒度的推理（例如，无法从中推出“存在某个探索者未抵达此处”）。 3. 通往一阶逻辑的桥梁：守卫的“我们的语言”显然指代一个更强大的系统。探险者意识到，必须引入个体词（如探索者 $a, b, c$ 或变量 $x$）、谓词（如 $S(x)$: “$x$ 是探索者”，$A(x)$: “$x$ 抵达了此处”）和量词（$\forall$ 全称，$\exists$ 存在）。因此，精确的表达式应为： $$\neg \forall x (S(x) \rightarrow A(x))$$ 或者，利用量词等价关系，转换为更直观的形式： $$\exists x (S(x) \land \neg A(x))$$ 这二者在标准一阶逻辑中是等价的，都表达了“存在至少一个探索者，它不是抵达者”。

探险者将后者输入石壁。石壁表面波纹微动，显然认可了这个结构。第一道关卡，通过。

---

三、 逻辑等价与定律：变换的艺术

守卫的第二个问题随之浮现：“给定命题公式 $(p \rightarrow q) \land (r \rightarrow q)$，请证明它与 $q \lor (\neg p \land \neg r)$ 逻辑等价。展示你的推导路径。”

这考验的是对逻辑等价（Logical Equivalence）的掌握。两个公式 $\phi$ 和 $\psi$ 逻辑等价（记作 $\phi \equiv \psi$），当且仅当在所有可能的赋值下，它们真值相同。即 $\phi \leftrightarrow \psi$ 是逻辑有效（Tautology）的。

证明等价有多种方法： 1. 真值表法：穷举所有原子命题的真值组合，计算两边的真值列。 2. 已知等价定律代换：运用一系列已证实的等价式进行逐步变换。 3. 语义论证：基于联结词定义进行推理。

探险者选择展示已知定律代换法，这更符合“证明”的要求，也更能体现系统性。

常用逻辑等价定律（命题逻辑层面）：

• **双重否定律**： $\neg \neg p \equiv p$
• **交换律**： $p \land q \equiv q \land p$； $p \lor q \equiv q \lor p$
• **结合律**： $(p \land q) \land r \equiv p \land (q \land r)$； $(p \lor q) \lor r \equiv p \lor (q \lor r)$
• **分配律**： $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)$
• **德·摩根律**： $\neg (p \land q) \equiv \neg p \lor \neg q$； $\neg (p \lor q) \equiv \neg p \land \neg q$
• **蕴含等值式**： $p \rightarrow q \equiv \neg p \lor q$
• **假言易位**： $p \rightarrow q \equiv \neg q \rightarrow \neg p$
• **等价等值式**： $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p) \equiv (p \land q) \lor (\neg p \land \neg q)$
• **零一律**： $p \lor T \equiv T$； $p \land F \equiv F$
• **同一律**： $p \lor p \equiv p$； $p \land p \equiv p$
• **吸收律**： $p \lor (p \land q) \equiv p$； $p \land (p \lor q) \equiv p$

证明过程： 目标： $(p \rightarrow q) \land (r \rightarrow q) \equiv q \lor (\neg p \land \neg r)$

步骤： 1. 对左边两个蕴含式应用蕴含等值式： $$ (p \rightarrow q) \land (r \rightarrow q) \equiv (\neg p \lor q) \land (\neg r \lor q) $$ 2. 利用交换律调整 $q$ 的位置，并应用分配律（注意，分配律对 $\lor$ 和 $\land$ 有两种形式，此处需将 $q$ 视为公共因子）： $$ (\neg p \lor q) \land (\neg r \lor q) \equiv (q \lor \neg p) \land (q \lor \neg r) $$ （因为 $A \lor B \equiv B \lor A$） 3. 应用分配律的另一种形式： $ (q \lor \neg p) \land (q \lor \neg r) \equiv q \lor (\neg p \land \neg r) $ 4. 结论：左边经变换后与右边完全相同，故等价。

mermaid ```mermaid graph LR A[目标: (p→q) ∧ (r→q) ≡ q ∨ (¬p ∧ ¬r)] --> B[步骤1: 应用蕴含等值式<br/>(p→q) ≡ ¬p ∨ q] B --> C[(¬p ∨ q) ∧ (¬r ∨ q)] C --> D[步骤2: 交换律<br/>调整 q 位置] D --> E[(q ∨ ¬p) ∧ (q ∨ ¬r)] E --> F[步骤3: 分配律<br/>提取公因子 q] F --> G[q ∨ (¬p ∧ ¬r)] G --> H[与目标式一致<br/>证毕] ```

守卫的石壁上，代表左边公式的光流经过一系列符合定律的变换，最终与右边公式的光流完全重合，发出清脆的共鸣声。第二关，过。

---

四、 形式证明方法：严谨性的两种范式

守卫的第三问，也是最后一问，最为严峻：“证明：若 $p \rightarrow q$ 且 $q \rightarrow r$，则 $p \rightarrow r$。但你必须使用两种不同的证明方法：直接证明法 与 反证法。展示你的推理链条。”

这引入了形式证明的概念。在命题逻辑中，证明是从一组前提（axioms或hypotheses）出发，应用一系列推理规则，推导出结论的过程。一个推理规则是有效的，当且仅当“前提真则结论真”是逻辑有效的。这里，探险者需要展示的，正是两种核心的证明策略。

4.1 直接证明法

直接证明法（Direct Proof）的思路是：假设所有前提为真，通过一系列逻辑等价变换或推理规则的应用，直接推导出结论的形式。

前提： $1. \ p \rightarrow q \quad \text{(Premise)}$ $2. \ q \rightarrow r \quad \text{(Premise)}$ 结论： $p \rightarrow r$

证明： 1. 假设 $p$ 为真（为证明 $p \rightarrow r$，我们假设其前件 $p$ 成立，旨在推导出后件 $r$）。 2. 由前提1 $p \rightarrow q$ 和假设 $p$，根据假言推理（Modus Ponens, MP）规则：从 $p \rightarrow q$ 和 $p$ 可推出 $q$。 > 推理规则：假言推理 (MP) > $$\frac{\phi \rightarrow \psi, \phi}{\psi}$$ > 该规则有效，因为若 $\phi \rightarrow \psi$ 和 $\phi$ 同真，则 $\psi$ 必真。 3. 由前提2 $q \rightarrow r$ 和步骤2得出的 $q$，再次运用 MP，推出 $r$。 4. 我们在假设 $p$ 为真的条件下，成功推导出了 $r$。因此，根据条件证明（Conditional Proof, CP）的原理，我们证明了 $p \rightarrow r$。

CP 原理：若在将 $\phi$ 作为附加前提的演绎中能推出 $\psi$，则无附加前提时可推出 $\phi \rightarrow \psi$。这实质上是证明蕴含式的一种元策略。

代码块：自然演绎系统片段 (Fitch Style) ```text 1. p → q Premise 2. q → r Premise │ │ 3. p Assumption (for CP) │ 4. q →E 1,3 (Modus Ponens) │ 5. r →E 2,4 │ 6. p → r →I 3-5 (Conditional Proof) ```

4.2 反证法

反证法（Proof by Contradiction, Reductio ad Absurdum）的思路是：要证明结论 $\phi$，先假设 $\neg \phi$ 为真，然后从这一假设和已知前提推导出一个矛盾（Contradiction，如 $q \land \neg q$，或逻辑常量 $\bot$）。由于矛盾不可能为真，故假设 $\neg \phi$ 必假，从而 $\phi$ 必真。

前提： $1. \ p \rightarrow q$ $2. \ q \rightarrow r$ 结论： $p \rightarrow r$

证明： 1. 假设结论的否定为真，即 $\neg (p \rightarrow r)$。 2. 根据蕴含等值式 $p \rightarrow r \equiv \neg p \lor r$，有 $\neg