命题逻辑的完备性和可靠性
摘要
本课程探讨了命题逻辑中完备性和可靠性之间的关系。尽管命题逻辑中的推理技巧和语义学已被广泛讨论，但很少关注这两个方面之间的关系。可靠性指的是一个逻辑系统的属性，即当表达式 G 可以从一组表达式 Γ 推导出时，G 作为 Γ 的语义结果是可靠的。另一方面，完备性指的是一个逻辑系统的属性，即如果 G 是一组表达式 Γ 的语义结果，那么存在一个包含 Γ 作为前提的形式证明，通过该证明可以推导出 G。证明了命题逻辑是可靠且完备的，并详细解释了每个属性。特别地，展示了可靠性是如何从命题逻辑的推理系统的构成中得出的，以及完备性是如何以一种简单的方式推导出来的。这一分析对于理解命题逻辑的运作方式以及在不同知识领域的有效应用具有重要意义。
学习目标：
完成本课程后，学生将能够：
- 区分逻辑系统中的可靠性和完备性。
- 应用Łukasiewicz 公理的真值表来证明命题逻辑的可靠性。
- 解释如何使用推理定理的语义版本重写演绎推理。
- 理解可靠性和完备性是相互关联的，可以相互推导。
- 分析逻辑命题中的重言式概念及其与定理的关系。
目录
命题逻辑的完备性和可靠性
命题逻辑的可靠性
命题逻辑的完备性
命题逻辑的完备性和可靠性
在这一点上，我们该谈谈命题逻辑的完备性和可靠性了。 迄今为止，已经讨论了很多关于命题逻辑的推理技巧和语义学的内容，但这些内容总是以一种方式呈现出来，似乎它们是完全独立的两个方面，没有任何联系。实际情况则完全相反。
可靠性：一方面，当表达式 G 可以从一组表达式 \Gamma 推导出时，逻辑系统是可靠的，因此 G 是 \Gamma 的（语义）结果。 |
完备性：另一方面，如果 G 是一组表达式 \Gamma 的语义结果，那么存在一个包含 \Gamma 作为前提的形式证明，通过该证明可以推导出 G。 |
通过回顾这些观点，我们会发现命题逻辑的完备性和可靠性得到了满足。
命题逻辑的可靠性
通过观察其推理系统的构成，可以轻松获得命题逻辑的可靠性。如果我们为 Łukasiewicz 公理制作真值表，我们会看到它们具有这样一种结构，即它们的真值始终为真，即：
| \models (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| \models ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))) |
| \models ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha \rightarrow \beta)) |
同样，演绎推理可以重写为 \{\alpha,(\alpha\rightarrow \beta)\}\models \beta.，这可以使用推理定理的语义版本获得。事实上，通过这种方式，我们可以得到 \{(\alpha\rightarrow \beta)\}\models (\alpha\rightarrow \beta),，然后 \models ((\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \beta)),，这显然是一种非常明显的重言式。
命题逻辑的完备性
命题逻辑的完备性告诉我们， 如果 B 是 A 的语义结果，那么 B 是从 A 推导出来的。换句话说：所有的真表达式都有一个证明。这就是我们所说的完备性。可以通过一种简单的方式推导出这一点。
可以通过一种简单的方式推导出这一点。假设 B 不能从 A 推导出来，或者更准确地说 \neg(A\vdash B)，根据推理定理，这相当于说：\neg (\vdash A\rightarrow B)；现在，如果我们求助于可靠性，这就导致 \neg(\models A \rightarrow B)，根据推理定理（语义版本）的逆定理，这相当于 \neg(A\models B)。总之，我们得到的是：
\neg(A\vdash B) \Rightarrow \neg(A\models B)
这相当于说
(A\models B) \Rightarrow (A\vdash B)
这意味着，如果 A 模型 B，那么 B 是从 A 推导出来的。如果我们使用相应的推理定理，我们可以得到
(\models A\rightarrow B) \Rightarrow (\vdash A \rightarrow B)
换句话说：如果一个表达式是重言式，那么它就是一个定理；正如我们所见，定理是证明的结果。