有效性判定定理

概述

有效性判定定理（Validity Criterion）：一个命题逻辑论证是有效的，当且仅当在它的完备真值表中，不存在任何一行使得所有前提都为真而结论为假。这一定理将有效性的语义概念转化为一种可操作的算法判定程序。

定理陈述

形式化陈述

定理（有效性判定定理）：设一个命题逻辑论证由前提 $P_{1}, P_{2}, \dots, P_{n}$ 和结论 $C$ 组成。则该论证是有效的，当且仅当：

在 $P_{1}, P_{2}, \dots, P_{n}, C$ 中出现的所有命题变项的完备真值表中，不存在任何一行满足以下条件：

$P_{1} = T, P_{2} = T, \dots, P_{n} = T, C = F$

即：不存在所有前提为真而结论为假的真值指派。

各项说明：

证明思路（有效性的语义定义直接推导）

本定理本质上是有效性语义定义在命题逻辑中的具体化。有效性的一般语义定义是：一个论证是有效的，当且仅当不可能所有前提为真而结论为假。在命题逻辑中，“不可能”可以通过穷举所有真值指派来检验。

第一步：从语义定义出发

有效性的定义：论证 ${P_{1}, \dots, P_{n}} ⊢ C$ 是有效的，当且仅当在任何使得所有前提为真的解释下，结论也为真。

第二步：命题逻辑中”解释”的含义

在命题逻辑中，一个”解释”（interpretation）就是对所有命题变项的一个真值指派（truth assignment）。由于命题逻辑是真值函项的，复合命题的真值完全由其组成部分的真值决定。

第三步：有限性保证完备性

设有 $k$ 个不同的命题变项，则共有 $2^{k}$ 种可能的真值指派。这是一个有限的数目，因此可以穷举所有可能性。

第四步：等价性建立

充分性（有效 $\Rightarrow$ 无反例行）：如果论证有效，则在任何使前提为真的解释下结论为真。完备真值表的每一行对应一种解释，因此不存在前提全真而结论为假的行。
必要性（无反例行 $\Rightarrow$ 有效）：如果不存在反例行，则在每一种使前提为真的真值指派下结论都为真，这正是有效性的定义。

证毕。 $■$

推论1（可判定性）：命题逻辑的有效性是可判定的（decidable），因为完备真值表方法提供了一个有限步内终止的算法。这是命题逻辑区别于谓词逻辑的重要特征——谓词逻辑的有效性是不可判定的（丘奇定理）。
推论2（简化真值表方法）：由于只需要检查是否存在反例行，可以反向操作：假设所有前提为真且结论为假，反推各命题变项的真值。如果导致矛盾，则论证有效；如果得到一致的赋值，则论证无效。这就是简化真值表方法。
推论3（重言式与有效性的关系）：论证 $P_{1}, \dots, P_{n} ⊢ C$ 有效，当且仅当条件式 $(P_{1} \land \dots \land P_{n}) \to C$ 是重言式。这建立了论证有效性与命题重言性之间的桥梁。