命题逻辑的完备性证明 我们先从命题逻辑的语言讲起。命题逻辑使用原子命题（如 \(p, q, r\)）和逻辑联结词（如 \(\land, \lor, \neg, \to\)）构建公式。例如，\((p \to q) \land p\) 是一个公式。 第一步：语义与真值赋值 一个真值赋值 \(v\) 为每个原子命题分配真值（真 \(\mathrm{T}\) 或假 \(\mathrm{F}\)）。 通过递归规则扩展 \(v\) 到所有公式： \(v(\neg A) = \mathrm{T}\) 当且仅当 \(v(A) = \mathrm{F}\)。 \(v(A \land B) = \mathrm{T}\) 当且仅当 \(v(A) = \mathrm{T}\) 且 \(v(B) = \mathrm{T}\)。 类似定义 \(\lor, \to\) 等。 若对所有真值赋值 \(v\) 都有 \(v(A) = \mathrm{T}\)，则称 \(A\) 为重言式。 第二步：语法证明系统（以自然演绎为例） 证明系统包含一组推理规则（如肯定前件、引入假设、反证法等）。 称公式 \(A\) 可证（记作 \(\vdash A\)），若存在从公理或假设出发的有限证明序列。 系统需满足可靠性：若 \(\vdash A\)，则 \(A\) 是重言式（即语义正确性）。 第三步：完备性目标 完备性定理断言：若 \(A\) 是重言式，则 \(\vdash A\)（即语法可证）。 证明的关键是构造一个模型，使得不可证的公式可被证伪。 第四步：极大一致集（Lindenbaum 引理） 一个公式集 \(\Gamma\) 是一致的，若不存在有限子集 \(\{\gamma_ 1, \dots, \gamma_ n\} \subseteq \Gamma\) 使得 \(\vdash \neg (\gamma_ 1 \land \dots \land \gamma_ n)\)。 通过逐步添加公式（若保持一致性），可将一致集扩张为极大一致集 \(\Delta\)，满足： 对任意公式 \(A\)，要么 \(A \in \Delta\)，要么 \(\neg A \in \Delta\)。 且若 \(\vdash A\)，则 \(A \in \Delta\)。 第五步：从极大一致集构造真值赋值 定义真值赋值 \(v\)： \[ v(p) = \mathrm{T} \quad \text{当且仅当} \quad p \in \Delta \quad (\text{对原子命题 } p). \] 通过结构归纳可证：对任意公式 \(A\)，有 \(v(A) = \mathrm{T}\) 当且仅当 \(A \in \Delta\)。 第六步：完备性证明 假设 \(A\) 不是可证公式（即 \(\nvdash A\)）。则 \(\{\neg A\}\) 是一致的（否则由爆炸原理可证 \(A\)）。 将 \(\{\neg A\}\) 扩张为极大一致集 \(\Delta\)，并构造对应的真值赋值 \(v\)。由于 \(\neg A \in \Delta\)，有 \(v(\neg A) = \mathrm{T}\)，即 \(v(A) = \mathrm{F}\)。因此 \(A\) 不是重言式。 逆否命题成立：若 \(A\) 是重言式，则 \(A\) 可证。 总结 该证明通过极大一致集桥梁，将语法不可证性转化为语义可假性，从而建立语法与语义的等价性。此框架可推广至一阶逻辑，但需处理量词和模型结构。