条件证明定理

概述

条件证明定理（Conditional Proof Theorem / Deduction Theorem）：如果要证明条件式 $P\to Q$，可以先假设 $P$ 为真，然后在此假设下证明 $Q$ 为真。如果成功，则 $P\to Q$ 得证。条件证明定理是自然演绎系统中最重要的证明策略之一，它将蕴涵命题的证明转化为归约证明。

定理陈述

形式化陈述

定理（条件证明定理 / 演绎定理）：设 $\Gamma$ 为一组命题（前提），$P$、$Q$ 为命题。则

$\Gamma \cup \{P\}⊢Q\text{当且仅当}\Gamma ⊢P\to Q$

即：如果在前提 $\Gamma$ 和附加假设 $P$ 下可以推出 $Q$，则从前提 $\Gamma$ 可以推出 $P\to Q$；反之亦然。

作为推论规则的表述： 在形式证明中，可以随时引入一个临时假设 $P$，在该假设下推导出 $Q$ 后，通过条件证明规则（CP）得出 $P\to Q$，并解除假设 $P$。

各项说明：

• 条件证明定理建立了语法推导与蕴涵命题之间的桥梁
• 临时假设 $P$ 在条件证明完成后必须被”解除”——它不是论证的真正前提
• 条件证明可以嵌套使用：在一个条件证明内部可以开始另一个条件证明

证明概要

证明思路（基于演绎定理的元逻辑证明）

核心思想

演绎定理的证明需要对形式证明的长度进行归纳，验证每个推论规则都与条件证明规则兼容。

详细步骤

第一步：充分性（$\Gamma \cup \{P\}⊢Q\Rightarrow \Gamma ⊢P\to Q$）

对从 $\Gamma \cup \{P\}$ 到 $Q$ 的形式证明的长度 $n$ 进行归纳。

• 基础情况（$n=1$）：$Q$ 要么是 $\Gamma$ 的成员，要么是 $P$，要么是公理/重言式。

  • 若 $Q\in \Gamma$：则 $\Gamma ⊢Q$，再由蕴涵引入规则可得 $\Gamma ⊢P\to Q$。
  • 若 $Q=P$：需要证明 $\Gamma ⊢P\to P$。$P\to P$ 是重言式，可以直接证明。
  • 若 $Q$ 是公理/重言式：$\Gamma ⊢Q$，同理可得 $\Gamma ⊢P\to Q$。

• 归纳步骤（$n>1$）：$Q$ 是通过某个推论规则从前面步骤推出的。需要针对每个规则分别验证。以肯定前件为例：

  • 假设 $Q$ 由 $R\to Q$ 和 $R$ 通过肯定前件推出。
  • 由归纳假设，$\Gamma ⊢P\to (R\to Q)$ 和 $\Gamma ⊢P\to R$。
  • 利用假言三段论：$(P\to R)\to ((P\to (R\to Q))\to (P\to Q))$ 是重言式。
  • 因此 $\Gamma ⊢P\to Q$。

第二步：必要性（$\Gamma ⊢P\to Q\Rightarrow \Gamma \cup \{P\}⊢Q$）

这一方向更为简单：

• 已知 $\Gamma ⊢P\to Q$。
• 在 $\Gamma \cup \{P\}$ 中，$P$ 是前提之一。
• 由 $\Gamma ⊢P\to Q$，在 $\Gamma \cup \{P\}$ 中也有 $P\to Q$。
• 由肯定前件：$P\to Q$ 和 $P$ 可推出 $Q$。
• 因此 $\Gamma \cup \{P\}⊢Q$。

证毕。$■$

自然演绎中的使用示例

1. | P → (Q → R)       前提
2. | | P                假设（条件证明开始）
3. | | Q → R            1, 2, 肯定前件
4. | | | Q              假设（嵌套条件证明开始）
5. | | | R              3, 4, 肯定前件
6. | | Q → R            4-5, 条件证明（解除假设Q）
7. | P → (Q → R)        2-6, 条件证明（解除假设P）

关键推论

• 推论1（嵌套条件证明）：条件证明可以嵌套使用，用于证明多重蕴涵命题 $P_1\to (P_2\to (\cdots \to P_n)\cdots )$。每一层条件证明对应一层蕴涵。
• 推论2（与间接证明的关系）：间接证明（归谬法）可以看作条件证明的特殊应用：要证明 $P$，假设 $\neg P$，推出矛盾，从而证明 $\neg P\to \text{矛盾}$，再得出 $P$。
• 推论3（简化证明的作用）：条件证明极大地简化了许多证明。例如，要证明 $P\to (Q\to P)$，使用条件证明只需假设 $P$ 和 $Q$，然后直接重述 $P$ 即可，无需展开完整的真值表。

应用场景

1. 蕴涵命题的证明：在 自然演绎 中，条件证明是证明蕴涵命题的标准方法。几乎所有涉及”如果…那么…”的证明都会使用条件证明。
2. 数学证明：数学中”假设…，则…”的证明结构就是条件证明的直接体现。例如，“要证明若 $n$ 是偶数则 $n^2$ 是偶数，假设 $n$ 是偶数…”
3. 程序验证：在霍尔逻辑（Hoare Logic）中，条件语句的验证规则本质上就是条件证明定理在程序逻辑中的应用。
4. 元逻辑研究：演绎定理是数理逻辑中最重要的元定理之一，它连接了语法推导和蕴涵命题，是证明可靠性定理和完备性定理的关键工具。

参见

• 自然演绎 — 条件证明在形式证明系统中的使用
• 推论规则 — 条件证明作为基本推理规则（CP）
• 间接证明 — 条件证明与间接证明的关系
• 条件证明 — 条件证明的详细说明
• 假言三段论 — 条件证明中常用的辅助推理规则