数理逻辑（讲义）(9)

完备性定理

定理1. (完备性定理1) 设??Form(L)，A?Form(L)。

（1）如果?|?A，则?|?A。（2）如果|?A，则|?A。 定理2. (完备性定理2) 设??Form(L)，A?Form(L)。

（1）如果?协调，则?可满足。（2）如果A协调，则A可满足。

由定理1证明定理2：

（1）假定A协调，证明A可满足。

假设A不可满足，则对于任意赋值v, Av?0.从而?A有效。即，|??A。由定理1，|??A。 于是，A|?A(Ref),A|??A(单调性)。所以，A不协调。与假设矛盾。 （2）假定?协调，证明?可满足。

假定?不可满足，则对于任意赋值v,有?v?0。从而必有一个公式A??，对于任意赋值v，如果(??{A})v?1，必有Av?0。此即，对于任意赋值v，(??{A})v?1，必有(?A)v?1。由定义，(??{A})|??A。

由定理1，(??{A})|??A。从而，(??{A}),A|?A，(??{A}),A|??A。即，?不协调。与假设矛盾。■ 由定理2证明定理1： （1） 假定?|?A，证明?|?A。

由?|?A，则??{?A}不可满足。由定理2，??{?A}不协调。从而存在公式B，

??{?A}|?B,??{?A}|??B。

使用规则(??)，有?|?A。

（2） 假定|?A，证明|?A。在（1）的证明中取???。

完备性定理的一般性证明是证明它的等价定理：协调一定可满足。 在命题逻辑中，当?为有限命题公式集时，可以直接证明。

40

命题逻辑中完备性定理的有限形式：设A?Form(LP)，??Form(LP)为一个有限命题公式集合，则(1) 如果 |?A，则 |?A。(2) 如果?|?A，则?|?A。 引理. 设A?Form(LP)含有变元p1,......,pn，v为一个赋值。令

?piAi????pipiv?1 i?1,....,n，则 piv?0 (1) 如果Av?1， 则A1,......,An|?A。 (2) 如果Av?0， 则A1,......,An|??A。 证明：对命题公式A的结构进行归纳。 （1）原子命题情形A?p。pv?1，p|?p。 （2）A??A'。

v 如果A?1，则A'v?0，则归纳假设，A1,......,An|??A'。

如果Av?0，则A'v?1，则归纳假设，A1,......,An|?A'。

由于??A'|?A'，有A1,......,An|???A'，从而A1,......,An|??A。 （3）A?B?C。

C含有命题变元pk',......,pn(k'?k)。假定B含有命题变元p1,......,pk，重复部份为：pk',......,pk。

如果Av?1，则Bv?Cv?1。由归纳假设：

A1,......,Ak|?B,A1,......,Ak,Ak?1,......,An|?BAk',......,An|?C,A1,......,Ak'?1,Ak',......,An|?C

从而，A1,......,An|?B?C。

如果Av?0，则Bv?0orCv?0。设Bv?0，由归纳假设： A1,......,Ak|??B,A1,......,Ak,Ak?1,......,An|??B。进一步，A1,......,An|??B??C。由于?(B?C)|?|?B??C，我们有：A1,......,An|??(B?C)。 （4）A?B?C,B?C,B?C的情形类似证明。■ 定理的证明：

(1) 设|?A，则A为重言式。从而，任意一个赋值v使得A?1。由引理，任一组A1,......,An，均有A1,......,An|?A。

41

v 特别：A1,......,An?1,pn|?A， A1,......,An?1,?pn|?A。 于是，A1,......,An?1|?pn?A，A1,......,An?1|??pn?A。 所以，A1,......,An?1|?A。

由A1,......,An?1的任意性，重复上述过程 n-1次，|?A。 注： 若?|?A?B,?|??A?B，则?|?B。

?|?A?B,?|??B??A,?,?B|??A ?|??A?B,?|??B???A,?,?B|???A

?|?B(2) 设?|?A。由?有限，令??{B1,......,Bm}，B1,......,Bm|?A。 从而，B1,......,Bm?1|?Bm?A，……, |?B1?(B2?......(Bm?A)...)。

由(1) |?B1?(B2?......(Bm?A)...)

B1|?B1?(B2?......(Bm?A)...)B1|?B1B1|?B2?(B3?......(Bm?A)...)

B1,B2|?B3?(B4?......(Bm?A)...) ……

B1,B2,......,Bm|?A。

即，?|?A。■

42

命题逻辑和谓词逻辑的完备性性定理

等价形式：协调公式集必可满足。

（如果?协调，则?可满足）

证明方法：将协调公式集?扩充为一个极大协调集?，利用极大协调集?的临界性质，构

造一个赋值满足?。

由于命题逻辑和谓词逻辑中赋值形式上不相同，所以我们分开讨论。 极大协调集：设??Form(LP)，称?极大协调。如果

(1) ?协调。

(2) 任何命题公式A??，??{A}不协调。

极大协调集的（临界）性质：

设??Form(L)，?极大协调，公式A,B?Form(L)。有： (1) A????|?A。（边界性质） (2) A????A??。（边界性质） (3) A?B???A??且B??。 (4) A?B???A??或B??。 (5) A?B???如果A??，则B??。 (6) A?B???“A??当且仅当B??”。 证明：（1.1）A????|?A( 显然)

（1.2）设?|?A，假定A??，则由极大协调性，??{A} 不协调。

从而有公式B，??{A}|?B,??{A}|??B。由归谬律：?|??A。于是，?|?A,?|??A。得到：?不协调。矛盾。■

（2.1）设A??，如果?A??，则?不协调。

（2.2）设?A??，则??{?A}不协调。从而有公式B，??{?A}|?B,??{?A}|??B，则规

43

**则(??)，?|?A。

其它性质由（1）（2）证明。

极大协调集性质的特征：

◆A????|?A：形式可推导与集合包含元素一致。

◆A????A??：每一个公式A，A,?A恰有一个在?中。 特别，每一个命题变元p,

p,?p恰有一个在?中.这可以保证从?定义一个赋值：

p?? p???1v?(p):???0可见：v?(p)?1? ◆

p??。

性质（2）--（6）：处理联结词与（语义）赋值定义一致。从而可以保证：使用归纳法可以证明：对于命题A公式，有v?(A)?1?A??。

最终，v?可以满足?。从而可以满足?的子公式集?0

对于一个协调命题公式集?，设法将?扩充为一个极大协调集?，则?构造下个赋值

**v?*满足?。

命题逻辑中完备性定理

定理1.设A?Form(LP)，??Form(LP)。 (1) 如果?协调，则?可满足。 (2) 如果A协调，则A可满足。

证明：(1) 对?进行极大协调扩充为：极大协调?。 Form(LP):?{A0,A1,...........}（可数集） ?0??， ?n?1????n?n?{An}不协调?n?{An}协调*??n?{An}

44