普遍化
普遍化(generalization)是数理逻辑里一条极为常用的规则,直观来说,这条规则在满足一条件下,可以将原合式公式推广成被全称量化的版本。
视为元定理
在谓词演算里,若承认以下的量词公理模式:(以下的 为任意变数, 、 为任意合式公式)
- (A4) 是一个项, 为 中出现的任意变数;若 里,所有 的的范围里都没有自由的 (这个情况称为 里项 对 是自由的),则
- 为公理
- 其中 代表把 里自由的 都取代为 所得到的新公式。
- (A5)如果 在 里完全被约束则
- 为公理
- (A6) 为公理
- (A7) 若 是公理, 是任意变数则
- 也是公理。
可以得到以下的元定理
在 里变数 都完全被约束,若
则有
这个元定理就是一般所称的普遍化。
视为推理规则
普遍化可以视为谓词演算的一条推理规则,也就是说:( 以下的 为任意变数, 为任意合式公式)
- 可以推出 。
也可以用相继式表记为
但这个推理规则会严苛地限制演绎定理的适用范围,如
不成立,因为无法确定变数 在 有没有完全被约束(参见上面元定理一节)。这就破坏了元语言的"十字旋转门"“ ”跟逻辑语言的“ ”间的联系。也就是说,直观上“ 以合式公式 为前提,根据推理规则和公理可以推出合式公式 ”跟“根据推理规则和公理可以推出合式公式 ”是等价的,但将普遍化视为推理规则就不免打破这个直观联系。
证明的例子
以下的证明是基于将普遍化视为推理规则 。
证明:
编号 | 公式 | 理由 |
---|---|---|
1 | 假设 | |
2 | 假设 | |
3 | 公理 PRED-1 | |
4 | 从 (1) 和 (3) 通过肯定前件 | |
5 | 公理 PRED-1 | |
6 | 从 (2) 和 (5) 通过肯定前件 | |
7 | 从 (6) 和 (4) 通过肯定前件 | |
8 | 从 (7) 通过普遍化 | |
9 | 总结 (1) 到 (8) | |
10 | 从 (9) 通过演绎定理 | |
11 | 从 (10) 通过演绎定理 |
步骤(10)中,因为 里 完全被约束,所以可以套用演绎定里,步骤(11)也是基于类似的理由。