可靠性和完全性

1、第七章 可靠性和完全性（提纲）1. 可靠性与完全性现在逻辑基本上都是采用如下结构:形式语言语义语法语义与语法的关系形式语言：从初始符号出发，形成主要对象公式。（可能需要一些其它辅助对象，如在一阶逻辑，就有项的概念）。公式是一种特殊的 符号串（由初始符号组成的符号串）。语义:给出某种结构，通过某种定义，定义出刻画逻辑规律的有效式。（如在一阶逻辑,我们从结构和赋值出发，给出解释、公式在解释下的真值，用在所有解释下都真定义出有效 式）。有效式是一种特殊的公式，所有有效式的集合是全体公式的一个子集。语法：由公理和推导规则 组成。按某种标准的方法给出 证明序列 和内定理。（可以有- 些推广的概念，最重要

2、的是 推演）。有效式是一种特殊的公式，所有内定理的集合是全体公式的一个子集。语义与语法的关系：最重要的有两个，可靠性和完全性。可靠性 所有的内定理都是有效式。完全性 所有的有效式都是内定理。2. 一阶推演系统的可靠性 可靠性有标准的证明方法：1. 证明每个公理都是有效的。2. 证明推导规则保持有效性不变。3归纳证明证明序列中的每个公式都是有效式，所以内定理是有效式。= T当且仅当（如果 4 ） = T ,则;r（-） = T）。（2）-（ i:n 八：）=T 当且仅当（如果.?（ 1）= T,.?（ -n） = T,则 c（-） = T）。证 （1）由定义得；（j） = T当且仅当 H ） =

3、 F或;"J = T。十）=F或匚（ ） = T就是 （如果d中=T,则氏屮）=T ）。所以，&T） = T当且仅当（如果氏附=T，则n（屮）=T ）。（2）对n作归纳。1. n = 1。由（1）得;fi；于）=T 当且仅当（如果 c（ i） = T,则 4'-） = T）。2. n = k+1。 1） T申k+1T屮也就是 申1TT申kT （申k+1T屮），由归纳假设 CT（申I TPkT（联+1T屮）=T当且仅当（如果厲韓）=,0（半k） = T,则CT（®k+1T屮）=T）。由（1）得 0（湫+1T屮）=T当且仅当（如果 g k+1） = T,则0（的

4、=T）。所以,T® I屮）=T当 且仅当（如果 0（9） = T,<J（®n） = T ,则 0（屮）=T）。(1) 如果；:(J：' ) = T 且;tJ = T ,则- ) = T。 如果)=T 且 口)= T ,贝U '-) = T。证（1）如果;十二）=T,则;:（J = F 或;：= T,又二（）=T,所以 cC-） = T。一阶推演系统的公理都是有效式。证A4 。任给解释二，如果） = T, 4'- ） = T ,则;r（ :） = To由定理，任给解释；二都有人）=T oA2 （"门）j：'） r任给解释 c,如

5、果;（ ' ） = T, ；（ J： ） = T, -（ ） = T ,则由:） = T 和二（ ） = T 得口'-：门）=T ,由 ） = T 和珥< ）=T 得；（'-：） = T ,再由'-：） = T 和口 ） = T 得;:（刃= T o由定理，任给解释；，都有；（-'-：门）（J"）：心）=T oA3 （）（_ f任给解释G如果口） = T, ） = T,则用反证法证明；（）= To假设 口） = F，则二（一 ）=T,由；：（ ） = T 和 口 一 - ） = T 得二（T = T,由二（）=T 和 门一 ） = T 得

6、 '- ） = T,所以 cC ：） = F。二（T = T 和;:（T = F，矛盾。由定理，任给解释 二，都有c（）一；（）-: ） = T oA4-X（t / x）,在：中t对x代入自由。任给解释o，如果o（X/x勺=T ,则任给a*，都有Ox, a（叭=T ,取a = a（t），由代入引理 得;（ （t / x）=；二,a（ ） = T o由定理，任给解释 G都有-x；：（t / x） = T oA5一x（：r-：'）任给解释 G如果 _x）'- ） = T, ；:（-x ） = T ,则任给 a A ,都有 c a（：' ） = T 且二x, a（）

7、=T,所以任给 a A，都有Q, aC"） = T,因此q-x） = T。由定理，任给解释 G 都有c（-x（一-：'）kx'-：） = T oA- x ;, x不是的自由变项。任给解释二，如果d J = T,则任给a"，由合同引理得ex, a( ) = 4 ) = T,所以；(-x：)=T。由定理，任给解释；，都有-x ') = T。一阶推演系统的推导规则保持有效性不变。(1) 如果2和：都是有效式，则 也是有效式。(2) 如果是有效式，则-x :也是有效式。 证(1) 任给解释G因为 和：都是有效式，所以)=T且;H = T，因此;r(-) =

8、T。 这就证明了任给解释；二都有'- ) = T ,所以 是有效式。(2) 任给解释匚，任给a A，因为：是有效式，所以ex, a( :) = T，因此-x ) = T。这就 证明了任给解释 二，都有rx) = t,所以-x是有效式。一阶推演系统可靠性定理一阶推演系统的内定理都是有效式。证设9是内定理，9,电(=®)是它的证明序列，归纳证明任给 k (1*9),叭都是有效式，当k = n时，就是说是有效式。1. i是公理，由定理2.1 存在 j, k：i_n，使得= 尸二2由归纳假设得j和k = j y-' i都是有效式，由定理2.2 存在j :i,存在变项 x，使得

9、'i = _x :j。由归纳假设得j是有效式，由定理 =-x j是有效式。A7和A8是有效式。证A7 t 三 t。任给解释CT,如果O(t) = O(t)，所以G(t三t)。A8 t 三 A (旳t / x)T®(s / x)。任给解释 ct,如果 cr( t 三 s) = T, cr(申(t / x) = T，则 o(t) = o(s)，取 a = cr(t) = o(s)，则由代入 引理得 (s / x) = g, a( ) = C( ：(t / x) = T。由定理，任给解释CT,都有0( t三I (申(t / xl® (s / x) = T o带等词的一阶推

10、演系统可靠性定理带等词的一阶推演系统的内定理都是有效式。 证略。3. 和谐和极大和谐和谐 门是公式集。如果存在公式 使得门|-且门|-一，则称是不和谐的。否则 称是和谐的。由定义，门是和谐的条件是：不存在公式 ，使得门-且门| -。和谐集等价条件是不和谐的 当且仅当(任给公式 日，都有-日)。:.:是和谐的 当且仅当(存在公式 K使得G - -)o证 如果(任给公式 日，都有-日)，当然存在公式 半，使得且Fo 如果存在公式 甲，使得-申且卑，则任给公式 也由PF | -6得10(2) 由(1)直接可得。和谐集的性质(1) 单调性二&。如果是不和谐，则？也是不和谐的。所以如果 7是和谐

11、的，则G也是和谐的。(2) 有限性G是和谐的 当且仅当 门的每个有限子集是和谐的。(3) G当且仅当：_. - 是和谐的。 门| /- 当且仅当，_. 是和谐的。证(1)如果是不和谐，则任给公式 匕都有门| -二，所以任给公式都有？ | -匕因 此？是不和谐的。(2) 证明：门是不和谐的 当且仅当 存在门的有限子集？是不和谐的。设门是不和谐的，则存在公式，使得G | -且G | -。取门到的推演序列为 1, 令:.：“ = 1,:n T，则叮是叮啲有限子集且1 | -，类似地存在有限 门的有限子集叮2, 使得:2 | - - 所以存在：啲有限子集？=门1：2，使得7-且？ |-，因此存在门的有

12、限 子集7,使得？是不和谐的。设存在门的有限子集？是不和谐的，由单调性得门是不和谐的。(3) 证明：| -当且仅当：_.是不和谐的。设住| -，则：_. | -，又，一一 | -，所以：； - 是不和谐的。设：_.是不和谐的，则；一. ：: | -，由演绎定理得 门r“，由"" |八 得门|-。(4) 类似于(3)，留给读者。极大和谐 门是和谐的公式集。如果任给公式W 都有；_. 是不和谐的，则称 g是极大和谐的。极大和谐集的性质：: 是极大和谐的公式集。(1)推演封闭性 如果G -，则门弐。内定理封闭性如果是内定理，y工门。(3) 分离规则 如果 W且,则 化门。-：当且

13、仅当二滤(5) 门-齐 当且仅当汽事或；化小。证 反证法。如果滤，则二. 是不和谐的，由定理 一，又G | -：,所以G是不和谐的，矛盾。(2) 如果是内定理，则由-,由得W。(3) 如果门琉且门：寺，则门|,由(i)得m(4) 如果：，由：.:啲和谐性得 门沂。心如果 3左，则：_. 是不和谐的，由定理 |一，由得一(5) 如果 n、y.，分两种情况证明凉或；S。情况1，鞋。显然有申苣或屮忘。情况2，苗。由(3)得一三事，也有稣或；化小。如果匚汽或，则分两种情况证明 三情况1，心。由得心，因为"一；()是内定理，所以"一；(),S再由(3)得情况2，一三处。类似情况1,由

14、内定理r)°由和得：(4) - 当且仅当(5) 浣当且仅当且；今：。处是极大和谐的公式集。(1) 当且仅当仃三处且化。(2) 匚；n当且仅当仃三住或；.当。证 (1)宀；f 当且仅当 d© 当且仅当 仃；厲事 当且仅当 上且 当且仅当心三且s。(2)门；当且仅当-当且仅当一或;n 当且仅当工或m4. Hintikka 集Hintikka集：'；'是公式集。如果任给 存在公式衣三，都存在项t，使得-：(t/x)旳，则称:是 Hintikka 集。极大和谐Hintikka集存在定理门是有限公式集，则存在极大和谐的Hintikka集？，使得h。证 注意，我们的语言

15、是可数的，所以全体公式也是可数的，将全体公式排成序列：%,%,任给n,归纳定义有限Gn如下：(1) 门0 =匚:。(2) 匚：乍+1分三种情况定义如下：2.1 :：_ ；不和谐。令:A+1 = :A°2.2 ：. k和谐，-k不是 x-形式。令：:知=：%_. -k。2.3心 财和谐严k = »即。取不在2旳出现的变元y(这是可以做到的，因为2旳 是有限公式集)，令叮=(仇一 k) _ '-(y/x)。令？ = U 讥 | n N。证明一：每个Gn都是和谐的。:/0 = :.:是和谐的。(2) Gk+1分三种情况证明如下：2.1 ：. k不和谐。由归纳假设，Gk是和

16、谐的，所以 仇+1 =：加是和谐的。2.2 ： k和谐。令叮k+i = ->k_. 和谐的。2.3 ： k和谐，-k = X- o 反证法。假设:.：佔=(：.：. :k) 一'-(y/x)是不和谐的，则:.:忙 :k | - (y/x)o 由概括规则得 心财| -旳一屮(y/x)(注意y不是心孤的自由变项)。由内定理 |-y (y/x) - x-得 _y (y/x) | -x，所以 Q_. -k |-x- 由内定理|-朮一叫厂日x屮得朮一屮 | 3x屮，所以2淋 屮o 这就是Jk_. k |- - k，由演绎定理得 “k |- k ko再由内定理|-( -k)L . k 得:k

17、 k|-一k，所以 ” k |-一 k，因此” k_. ；：k不和谐，矛盾。证明二：总n二住n+1,所以 % |门刖是单调的。显然。证明三：？ = U n | nN是和谐的。反证法。如果？ = U n I nN是不和谐的，则存在 宇的有限子集",'-s，存在公式7使得 "，'-s | -。因为 f-；1,'-s '-U n I n N，所以存在：:n1,Gns,使得 T 门 n1,"ns,取 Gn1,，门ns中最大的集合nt (这个最大集合的存在是由 n | n N的单调性保证的)，则 ",'-s二乍nt，所以叮X

18、 | -，因此:nt不和谐，矛盾。证明四：弓=U n I nN Hi ntikka 集。任给存在公式X-?, X，定是某个；,因为宇一：n='汀和谐，所以叮n_.为和谐(注意匚:纭一 : n是宇- 'n的子集)。由定义2.3，存在变项y,使得'-(y/xn+1。所以，存在变项y,使得'- (y/x?5. 一阶推演系统的完全性可满足(1) 是公式。如果存在解释 G使得-()=T，则称是可满足的。(2) 门是公式集。如果存在解释G使得任给公式门珂:，都有门)= T，则称是可满足的，记为；f)=T o(1) 可满足 当且仅当 不是有效的。:是公式集。如果 门可满足，则任给公式 门琉，：都是可满足的。 证略。注意，任给公式 工门，：都是可满足的，并不保证 门是可满足的。完全性是说：任给公式，如果是有效式，则是内定理。等价地说：任给公式，如果：不是内定理，则不是有效式。完全性证明思路：(1) 不是内定理，贝y 和谐。(在定理(