命题逻辑的可靠性定理

本文证明了命题逻辑系统的可靠性：若一个公式在系统中可证，则它在语义上是永真的。

我们将证明命题逻辑系统的可靠性（Soundness）。

对于任意公式集合 \Gamma 和公式 A，若 \Gamma \vdash A，则 \Gamma \models A。

证明. 我们对推导 \Gamma \vdash A 的长度 n 进行归纳证明。 假设任给真值指派 v 使得 v(\gamma) = T 对所有 \gamma \in \Gamma 成立。我们需要证明 v(A) = T。

根据推导定义，\Gamma \vdash A 意味着存在一个公式序列 A_1, ..., A_n = A，其中每一个 A_i 要么是公理，要么属于 \Gamma，要么是由前面的公式通过分离规则（MP）得到的。

（1）A 是公理 若 A 是公理模式的实例，根据公理的性质，公理在任意真值指派下均为真（重言式）。 故 v(A) = T，即 \Gamma \models A 成立。

（2）A \in \Gamma 若 A \in \Gamma，由假设 v 满足 \Gamma，则显然有 v(A) = T。 故 \Gamma \models A 成立。

（3）A 是由 B 和 B \to A 通过 MP 规则得到的 假设在推导序列中，B 和 B \to A 出现在 A 之前。 由归纳假设，我们有 \Gamma \models B 且 \Gamma \models B \to A。 这意味着对于满足 \Gamma 的任意赋值 v，有 v(B) = T 且 v(B \to A) = T。 根据蕴含词 \to 的真值表定义，如果 v(B) = T 且 v(B \to A) = T，则必然有 v(A) = T。 因此 \Gamma \models A 成立。

综上所述，由数学归纳法可知，可靠性定理得证。 \square