完全性也是逻辑系统的一个重要的性质.它表明：一个系统是（语义）完全的，如果系统中的所有真语句都是在系统中可证的.即：如果，那么0α.

在本节中，我们将证明FPC系统的完全性.由于PC系统与FPC系统等价，所以，在PC系统中，完全性也成立.或者用类似于下面的方法，证明PC系统的完全性定理.

定理4.1（完全性定理） 在FPC系统中，（1）如果Φ0α，那么Φ0α.（2）特别是，当Φ=∅时，如果0α，那么0α.

因为Φ0α，那么对任意的真值赋值σ，若σΦ，则σα，即σ（α）=1.即对任意的真值赋值σ都不满足Φ，⇁α.由第四章第二节定理2.2的（1）知：Φ0α，当且仅当Φ，⇁α不相容.因此，要证明完全性定理，只需证以下结论：

如果Φ相容，那么Φ可满足.这一结论又等价于：

如果Φ不可满足，那么Φ不相容.由Φ，⇁α不可满足可得：Φ，⇁α不相容.再由第四章第二节定理2.2的（1）得：Φ0α.于是，完全性定理获证.

根据上面的分析，我们只需构造一个真值赋值σ，使得σΦ.为此，我们需要

定义 如果公式集Φ是相容的，但不是任一相容集的真子集，则称Φ是极大相容的.

定理4.2 公式集Φ是极大相容的，当且仅当下面两个条件同时成立.

（1）Φ相容；

（2）对任意的公式α，α∈Φ或者⇁α∈Φ.

证明 如果Φ是极大相容的，由定义，（1）成立.

如果存在一个公式α，使得α/∈Φ并且⇁α/∈Φ，由极大相容的定义得：Φ，α和Φ，⇁α都不相容.再由第四章第二节定理2.2得：Φ0α并且Φ0⇁α.根据第四章第二节定义得：Φ不相容，此与条件（1）矛盾.故对任意公式α，α∈Φ或者⇁α∈Φ.

反之，如果（1）和（2）成立，并假设Φ是Ψ的真子集，令α∈Ψ且α/∈Φ，根据（2）得，⇁α∈Φ，所以，⇁α∈Ψ.因此，Ψ不相容，故Φ是一极大相容集.

定理4.3 如果Φ是极大相容的公式集，那么

（1）α→β∈Φ，当且仅当，⇁α∈Φ或β∈Φ.

（2）α∧β∈Φ，当且仅当，α∈Φ且β∈Φ.

（3）α∨β∈Φ，当且仅当，α∈Φ或β∈Φ.

（4）α↔β∈Φ，当且仅当，α∈Φ且β∈Φ或α/∈Φ且β/∈Φ.

证明 （1）的证明：

因为α→β∈Φ，设⇁α/∈Φ且β/∈Φ，那么由定义，Φ，⇁α和Φ，β皆不相容.由第四章第二节定理2.3的（1）得：Φ不相容.此与已知矛盾.故⇁α∈Φ或β∈Φ.

反之，如果⇁α∈Φ或β∈Φ，那么，由Φ的极大性可得：①α/∈Φ或⇁β/∈Φ；②Φ，α，⇁β不相容.由第四章第二节定理2.2（1）得：Φ，α0β.再由第四章第一节演绎的性质11得：Φ0α→β.假设α→β/∈Φ，那么由定理4.2得：⇁（α→β）∈Φ.由第四章第一节演绎的性质2得：Φ0⇁（α→β）.因此，Φ不相容，矛盾.故α→β∈Φ.

（2）的证明：

假设α/∈Φ或β/∈Φ成立，由Φ的极大性可得：Φ，α或Φ，β不相容.又α∧β∈Φ，根据第四章第二节定理2.4得：Φ不相容，矛盾.故α∈Φ且β∈Φ.

反之，如果α∈Φ且β∈Φ，并设α∧β/∈Φ，由Φ的极大性可得：⇁（α∧β）∈Φ，⇁α/∈Φ，⇁β/∈Φ并且Φ，⇁α及Φ，⇁β不相容.由第四章第二节定理2.4得：Φ不相容，矛盾.故α∧β∈Φ.

（3）的证明：

如果α/∈Φ且β∈Φ，那么由Φ的极大性得：Φ，α及Φ，β均不相容.又α∨β∈Φ，根据第四章第二节定理2.5（1）得：Φ不相容，矛盾.故α∈Φ或β∈Φ.

反之，如果α∈Φ或β∈Φ，并且假设α∨β/∈Φ，由Φ的极大性可得：⇁（α∨β）∈Φ，⇁α/∈Φ或⇁β/∈Φ并且Φ，⇁α或Φ，⇁β不相容.由第四章第二节定理2.5（2）知：Φ不相容，矛盾.故α∨β∈Φ.

（4）的证明：

因为α↔β∈Φ，假设“α∈Φ且β∈Φ或α/∈Φ且β/∈Φ”不成立，得：α∈Φ且β/∈Φ或α/∈Φ且β∈Φ成立.由Φ的极大性可得：Φ，⇁α及Φ，β皆不相容或Φ，α及Φ，⇁β皆不相容.那么由第四章第二节定理2.6（1）得：Φ不相容，矛盾.故α∈Φ且β∈Φ或α/∈Φ且β/∈Φ.

反之，如果α↔β/∈Φ，由Φ的极大性可得：⇁（α↔β）∈Φ，又α∈Φ且β∈Φ或α/∈Φ且β/∈Φ，那么⇁α/∈Φ且⇁β/∈Φ或α/∈Φ且β/∈Φ，所以，再由Φ的极大性可得：Φ，⇁α，β及Φ，α，⇁β皆不相容.由第四章第二节定理2.6（2）得：Φ不相容，矛盾.故α↔β∈Φ.

定理4.4 如果Φ是一个相容的公式集，那么存在一个极大相容公式集Ψ，使得Φ⊆Ψ.

证明 因为LFPC是可数的，所以W0也可数。于是，令LFPC的所有公式为：

φ1，φ2，φ3，…，φn，…。

为了构造Ψ，定义相容公式集链Φn如下：

（1）令Φ0=Φ；

（2）当n＞0时，令

由定义知：Φn相容，并且

Φ=Φ0⊆Φ1⊆Φ2⊆…⊆Φn⊆…

令，则Φ⊆Ψ.

以下只需证Ψ相容且极大相容.

首先，对Ψ的任意有穷子集Ψ′，必有某个n，使得Ψ′⊆Φn.因为Φn相容，由第四章第二节性质1得Ψ′相容，再由性质1得Ψ相容.(www.daowen.com)

其次，设任意公式φΨ，并设φ是FPC系统中第n个公式，则φΦn.由Φn的定义知：Φn-1∪{φ}不相容，因而Ψ∪{φ}也不相容.所以，Ψ极大相容.

定理4.5 如果Φ是一个相容的公式集，那么Φ是可满足的.即存在一个满足Φ的真值赋值σ.

证明 因为Φ相容，由定理4.4知：存在一个极大相容集Ψ，使得Φ⊆Ψ.现在，我们构造一个真值赋值σ，满足对每个原子公式α有：

在这样的规定下，施归纳于α的结构证明：（*）式对每个公式α都成立.

（1）设α是原子公式，由（*）式得：

σ（α）=1当且仅当α∈Ψ.

（2）设α=⇁β，则

σ（α）=σ（⇁β）=1当且仅当σ（β）=0（由真值赋值的定义）；

当且仅当β/∈Ψ（由归纳假设）；

当且仅当⇁β∈Ψ（由Ψ的极大性）.

即α∈Ψ.

（3）设α=β∧γ，则

σ（α）=σ（β∧γ）=1当且仅当σ（β）=1且σ（γ）=1

（真值赋值的定义）；

当且仅当β∈Ψ且γ∈Ψ（由归纳假设）；

当且仅当β∧γ∈Ψ（由定理4.3（2））.

即α∈Ψ.

（4）设α=β∨γ，则

σ（α）=σ（β∨γ）=1当且仅当σ（β）=1或σ（γ）=1

（由真值赋值的定义）；

当且仅当β∈Ψ或γ∈Ψ（由归纳假设）；

当且仅当β∨γ∈Ψ（由定理4.3（3））.

即α∈Ψ.

（5）设α=β→γ，则

σ（α）=σ（β→γ）=1当且仅当σ（β）=0或σ（γ）=1

当且仅当β/∈Ψ或γ∈Ψ（归纳假设）；

当且仅当⇁β∈Ψ或γ∈Ψ（Ψ的极大性）；

当且仅当β→γ∈Ψ（由定理4.3（1））.

即α∈Ψ.

（6）设α=β↔γ，则

σ（α）=σ（β↔γ）=1当且仅当σ（β）=σ（γ）=1或σ（β）=σ（γ）=0

（由真值赋值的定义）；

当且仅当β∈Ψ且γ∈Ψ或βΨ且γΨ

（由归纳假设）；

当且仅当β↔γ∈Ψ（由定理4.3（4））.

即α∈Ψ.

综上（1）～（6）得：对一切公式α，（*）式成立.由于Φ⊆Ψ，因此有σΦ，即Φ是可满足的.

最后，关于定理4.1的证明：

因为Φ0α，所以，对任意的真值赋值σ，若σ0Φ，那么，σ0α，即σ（α）=1.所以，σ（⇁α）=0.即：没有真值赋值可以满足Φ∪{⇁α}.由定理4.5得：Φ∪{⇁α}不相容，由第四章第二节定理2.3得：Φ0α.从而（1）获证.

当Φ=∅时，即得（2）.