前面介绍了命题逻辑系统，我们可以用它进行推理。现在的问题是，它的推理都是有效的吗？或者说，当前提为真时，它推理得到的结论都是真的吗？另一个问题是，用它能得到所有的有效推理吗？

第一个问题叫可靠性问题：从Γ⊢A，能否得到Γ⊨A？第二个叫完全性问题：从Γ⊨A，能否得到Γ⊢A？

上面的Γ表示命题集（可以是空集），Γ⊢A，表示从Γ推出A，Γ⊨A表示如果Γ中的每个命题都真，则A真。

可靠性定理

可靠性定理的证明比较简单。可以检验，三条公理都是永真的。即不管原子命题取什么值，它们都取真值。而推理规则是保真的：当p和p→q都为真时，q一定为真。从Γ推出A的过程中，只能使用Γ、逻辑公理和推理规则。所以如果Γ是真的，则推理得到的任何结果都是真的。所以可靠性定理成立。

完全性定理

这里只讨论证明思路。

要证：如果Γ⊨ A，那么Γ⊢A。所以要证：如果并非Γ⊢A，那么并非Γ⊨ A。

即要证：并非Γ⊢A，那么Γ和﹁A可以同时为真。

只需证明下面两点：

1、如果并非Γ⊢A，则Γ∪﹁A是一致集

2、任何一致集都有模型

一致集和模型的定义。Γ是一致集，当且仅当，存在一个公式R，并非Γ⊢R。一个命题或一个命题集合有模型是指，存在一个赋值使得它们为真。

先证明1。

如果Γ∪﹁A不是一致集，则Γ，﹁A ⊢ A。根据演绎定理，有Γ⊢﹁A→A。又因为 (﹁A→A)→A是定理。所以Γ⊢A，与前提相矛盾。

再证明2。

先将一致集扩展成极大一致集，然后给极大一致集找到一个模型。

极大一致集的定义：某个一致集S，对任意的公式A，A或者﹁A恰有一个属于S，则集合S是极大一致集。

现在将任意的一致集T0扩展成极大一致集。

所有的命题组成的集合是可数的，将它们排列，A1、A2、A3、……An、……。如果Tn ⊢An，则T_n+1=Tn∪{An}，如果并非Tn ⊢An，则T_n+1=Tn∪{﹁An}。令T = ∪Tn，即所有扩充集的并。可证明T是极大一致集。

给T中的每个原子命题赋真值，不在T中的原子命题赋假值。可以通过归纳法证明，这个赋值下，任意一个公式为真当且仅当它属于T。所以这个赋值是T的模型。