形式证明 vs 真值表
概述
形式证明（自然演绎）和真值表是命题逻辑中两种互补的有效性判定方法。形式证明是语法方法（基于推论规则），真值表是语义方法（基于真值指派）。完备性定理保证：一个论证是有效的（语义），当且仅当它可以被形式证明（语法）。
共同点
- 都可以判定命题逻辑论证的有效性
- 都具有能行性（可以机械地执行）
- 都只适用于真值函项论证
关键区别
| 维度 | 形式证明（自然演绎） | 真值表 |
|---|---|---|
| 方法类型 | 语法方法（推论规则） | 语义方法（真值指派） |
| 基本操作 | 从前提出发逐步推导结论 | 穷举所有真值组合 |
| 变元增多时 | 证明长度通常线性增长 | 行数指数增长（） |
| 洞察力要求 | 需要选择合适的规则和策略 | 无需洞察，机械执行 |
| 无效性判定 | 无法直接证明无效（只能尝试后放弃） | 可以直接找到反例 |
| 可读性 | 展示推理过程，易于理解 | 只显示最终结果 |
| 适用范围扩展 | 可扩展到谓词逻辑（第10章） | 谓词逻辑中不适用 |
深层联系
完备性定理
形式证明和真值表方法的等价性由完备性定理保证：
- 可靠性（Soundness）：如果可以用形式证明推出结论，则论证是有效的
- 完备性（Completeness）：如果论证是有效的，则一定可以用形式证明推出结论
这意味着两种方法在判定能力上是完全等价的，只是适用场景不同。