第四章 謂詞演算的推理理論-永真推理系統(tǒng)

1、第四章 謂詞演算的推理理論4.1 謂詞演算的永真推理系統(tǒng)謂詞演算的永真推理系統(tǒng) 4.1.1 公理系統(tǒng)的組成部分公理系統(tǒng)的組成部分 4.1.2 公里系統(tǒng)的推理過程公里系統(tǒng)的推理過程4.2謂詞演算的假設(shè)推理系統(tǒng)謂詞演算的假設(shè)推理系統(tǒng)4.3謂詞演算的歸結(jié)推理系統(tǒng)謂詞演算的歸結(jié)推理系統(tǒng)4.1.1 公理系統(tǒng)的組成部分公理系統(tǒng)的組成部分一、語法部分一、語法部分 (一一) 基本符號基本符號 (二二) 公理公理 (三三) 規(guī)則規(guī)則二、語義部分二、語義部分三、關(guān)于公理的幾點說明三、關(guān)于公理的幾點說明（一） 基本符號公理系統(tǒng)所允許出現(xiàn)的全體符號的集合。公理系統(tǒng)所允許出現(xiàn)的全體符號的集合。(1) 命題變元：命題變元

2、：P，Q，R，等字母表示命題變元等字母表示命題變元(2) 個體變元：個體變元：x，y，等小寫字母表示個體變元等小寫字母表示個體變元(3) 謂詞變元：謂詞變元：X，Y，等大寫字母表示謂詞變元等大寫字母表示謂詞變元(4) 聯(lián)結(jié)詞：聯(lián)結(jié)詞： 、 、 、是聯(lián)結(jié)詞是聯(lián)結(jié)詞(5) 量詞：全稱量詞量詞：全稱量詞 、存在量詞、存在量詞 (6) 括號：括號：(，)是括號是括號(7) 全稱封閉符：全稱封閉符：基本符號（續(xù)）(8) 合式公式：合式公式： (i) 原子命題原子命題P是合式公式；是合式公式； (ii) 謂詞填式謂詞填式A(x1，x2，x3，xn)是合式公式；是合式公式； (iii) 若若A是公式，則是公

3、式，則 A是合式公式；是合式公式； (iv) 若若A和和B是合式公式，則是合式公式，則 (A B)，(A B)，(AB)，(AB)為公式；為公式； (v) 若若A是合式公式，是合式公式，x是是A中出現(xiàn)的任何個體變元，中出現(xiàn)的任何個體變元， 則則 xA(x)， xA(x)為合式公式；為合式公式； (vi) 只有有限次使用只有有限次使用(i)、(ii)、(iii)、(iv)、(v)所得到所得到的式子才是合式公式。的式子才是合式公式?；痉枺ɡm(xù)）(9) 全稱封閉式：設(shè)全稱封閉式：設(shè) 為含有為含有n個自由變元的公個自由變元的公式，如果在式，如果在 前用全稱量詞把前用全稱量詞把n個自由變元個自由變元約

4、束起來后所得到的公式，稱為約束起來后所得到的公式，稱為 的的全稱全稱封閉式封閉式。記為。記為 。 例例 寫出下式的全稱封閉式寫出下式的全稱封閉式 = xP(x，y)uQ(u，v)解：解： =( xP(x，y)uQ(u，v) = y v( xP(x，y)uQ(u，v)（二） 公理公理公理1 (PP)公理公理2 (P(QR)(Q(PR)公理公理3 (PQ)(QR)(PR)公理公理4 (P(PQ)(PQ)公理公理5 (PQ)(PQ)公理公理6 (PQ)(QP)公理公理7 (PQ)(QP)(PQ)調(diào)頭調(diào)頭傳遞傳遞凝縮凝縮與與有關(guān)有關(guān)（二） 公理公理公理8 (P Q)P)公理公理9 (P Q)Q)公理公

5、理10 (P(Q(P Q)公理公理11 (P(P Q)公理公理12 (Q(P Q)公理公理13 (PR)(QR)(P Q)R)公理公理14 (PQ)(QP)公理公理15 (PP)與與有關(guān)有關(guān)與與 有關(guān)有關(guān)與與有關(guān)有關(guān)（二） 公理公理公理20 ( xP(x) P(x)公理公理21 (P(x)x P(x)如果只有一個自由變元，公理如果只有一個自由變元，公理20與公理與公理21可以分可以分別理解如下：別理解如下： x( yP(y) P(x) x(P(x)y P(y)與與量詞有關(guān)量詞有關(guān)（三） 規(guī)則(1)分離規(guī)則：分離規(guī)則：如果如果(AB)且且A，則，則B。(2)全稱規(guī)則：全稱規(guī)則：( P(x)(x

6、P(x)(其中其中 中不含自由的中不含自由的x)(3)全稱量詞消去規(guī)則：全稱量詞消去規(guī)則： xP(x)P(x)(x可以為任意的變元可以為任意的變元)(4)存在量詞引入規(guī)則：存在量詞引入規(guī)則：(P(x)( x P(x)(其中其中 中不含自由的中不含自由的x)回顧: 量詞作用域的收縮與擴張設(shè)公式設(shè)公式 中不含有自由的中不含有自由的x，則下面的公式成立，則下面的公式成立: x( (x) )= ( x (x) ) x( (x) = ( x (x) x( (x) )= ( x (x) ) x( (x)= ( x (x)存在量詞引入全稱量詞引入二、語義部分 (1) 公理是永真公式。公理是永真公式。(2)

7、規(guī)則規(guī)定如何從永真公式推出永真公式。規(guī)則規(guī)定如何從永真公式推出永真公式。 分離規(guī)則指明，如果分離規(guī)則指明，如果(AB)永真且永真且A永真，則永真，則B也為永真公式。也為永真公式。(3) 定理為永真公式，它們是從公理出發(fā)利用定理為永真公式，它們是從公理出發(fā)利用上述規(guī)則推出來的公式。上述規(guī)則推出來的公式。三、關(guān)于公理的幾點說明(1) 本系統(tǒng)中本系統(tǒng)中不引入代入規(guī)則不引入代入規(guī)則，它的作用由下，它的作用由下面的面的(2)來實現(xiàn)；來實現(xiàn)；(2) 本系統(tǒng)中的所有公理我們把它看作本系統(tǒng)中的所有公理我們把它看作公理模公理模式式，即只要形如某一公理，我們就稱其為，即只要形如某一公理，我們就稱其為某一公理。某一

8、公理。 如如 (PP)、 (P(QR)(P(QR)、 ( xP(x)x P(x) 等均為公理等均為公理1。第四章 謂詞演算的推理理論4.1 謂詞演算的永真推理系統(tǒng)謂詞演算的永真推理系統(tǒng) 4.1.1 公理系統(tǒng)的組成部分公理系統(tǒng)的組成部分 4.1.2 公里系統(tǒng)的推理過程公里系統(tǒng)的推理過程4.2謂詞演算的假設(shè)推理系統(tǒng)謂詞演算的假設(shè)推理系統(tǒng)4.3謂詞演算的歸結(jié)推理系統(tǒng)謂詞演算的歸結(jié)推理系統(tǒng)例例1 (p41)已知已知定理定理(P(QP), 求證求證: 全全0規(guī)則規(guī)則 (x) x (x)證明：證明：(1) (x)(2) ( (x)(PP)(x) 引用定理引用定理 (3) (PP)(x) (2)(1)分離分

9、離(4) (PP)x (x) 全稱規(guī)則全稱規(guī)則(3)(5) (PP) 公理公理(1)(6) x (x) (4)(5)分離分離則有全則有全0規(guī)則規(guī)則 (x) x (x)全n規(guī)則、存n規(guī)則全全n規(guī)則：規(guī)則： ( 1( 2( n(x) ( 1( 2( nx (x)存存n規(guī)則：規(guī)則： ( 1( 2( n( (x) ( 1( 2( n( x (x)全1規(guī)則=全稱規(guī)則存0規(guī)則=存在規(guī)則例例 試?yán)么嬖嚴(yán)么?規(guī)則求證存規(guī)則求證存1規(guī)則規(guī)則( 1( (x) ( 1( x (x)證明：證明：(1) ( 1( (x) ) (2) ( 1( (x) ) ( (x) ( 1 ) 公理公理2 (3) ( (x) (

10、1 ) 分離分離(1)(2)(4) ( x (x) ( 1 ) 存存0規(guī)則規(guī)則(5) ( x (x) ( 1 ) ( 1( x (x) ) 公理公理2(6) ( 1 ( x (x) ) 分離分離(5)(6)兩次運用調(diào)頭公理兩次運用調(diào)頭公理2例例(練習(xí)練習(xí)4.1(1) x(P(x)(xP(x) 證明: (1) x(P(x) ( P(x) )公理公理20 : P(x)與與P(x)同形同形(2) x(P(x) ( x P(x) )全全2規(guī)則規(guī)則( 1( 2(x) ( 1( 2x (x)例例(續(xù)續(xù)) x(P(x)(x P(x)再證明再證明 ( x P(x) x( P(x) ) 證明: (3) xP(x

11、)P(x) 公理公理20(4) ( xP(x)P(x)( xP(x)( P(x) 定理定理(5) ( xP(x)( P(x) 分離(3)(4)(6) ( xP(x) x( P(x) 全全1規(guī)則規(guī)則定理定理 (PQ)(RP)(RQ) 例例 (再續(xù)再續(xù)) x(P(x)(x P(x)已經(jīng)證得已經(jīng)證得(2)(6)兩式兩式(2) x(P(x) ( x P(x)(6) ( xP(x) x( P(x)于是于是(7) ( x(P(x) ( x P(x) ( xP(x) x( P(x) ( x(P(x)(x P(x) 公理公理7(8) ( xP(x) x( P(x) ( x(P(x)(x P(x) 分離分離(2

12、)(7)(9) x(P(x)(x P(x) 分離分離(6)(8)例例(練習(xí)練習(xí)4.1(2) x(P(x)( x P(x)先證明先證明 x(P(x) ( x P(x) 證明: (1) x(P(x) (P(x) 公理公理20(2) x(P(x) ( x P(x) 存存1規(guī)則規(guī)則 1(P(x) 1( xP(x)例例(續(xù)續(xù)) x(P(x)( x P(x)再證明再證明 ( x P(x) x(P(x)證明: (3) P(x) xP(x) 公理公理21(4) (P(x) xP(x) ( xP(x)(P(x) 公理公理3(5) ( xP(x)(P(x) 分(3)(4)(6) ( xP(x) x(P(x) 全稱

13、規(guī)則例例(再續(xù)再續(xù)) x(P(x)( x P(x)已經(jīng)證得已經(jīng)證得(2)(6)兩式兩式(2) x(P(x) ( x P(x)(6) ( xP(x)x(P(x)于是有于是有(7) ( x(P(x) ( x P(x) ( ( xP(x) x(P(x) ( x(P(x)( x P(x) 公理公理7(8) ( xP(x) x(P(x) ( x(P(x)( x P(x) 分離分離(2)(7)(9) x(P(x)( x P(x) 分離分離(6)(8)例例 (練習(xí)練習(xí)4.2)已知公理已知公理 (A) (P(QP) (B) (PP) 及分離規(guī)則和全稱規(guī)則，全稱規(guī)則為：及分離規(guī)則和全稱規(guī)則，全稱規(guī)則為： ( 1

14、( 2(x)( 1( 2x (x)試證：全試證：全0規(guī)則規(guī)則 (x) x (x)證證: (1) (x) (2) (P(QP) 公理公理A (3) ( (x) (PP) (x) 代入代入(1) (4) (PP) (x) (1)(3)分離分離 (5) (PP) (x) (PP) (PP) (x) 代入代入(2) (6) (PP) (PP) (x) (4)(5)分離分離 (7) (PP) (PP) x (x) 全稱規(guī)則全稱規(guī)則 (8) (PP) 公理公理B (9) (PP) x (x) (7)(8)分離分離 (10) ( x (x) (9)(8)分離分離例例2 (p42) 試證明：試證明：(A) (

15、 x P(x) xP(x)證證(A)(1) ( x P(x)P(x) 公理公理20(2) ( x P(x)P(x) (P(x)x P(x) 公理公理14(3) (P(x)x P(x) (2)(1)分離分離(4) ( xP(x)x P(x) 存在量詞引入規(guī)則存在量詞引入規(guī)則(3)(5) ( xP(x)x P(x)( x P(x)xP(x) 公理公理14(6) ( x P(x)xP(x) (5)(4)分離分離 例例2 (p42) 已知定理：已知定理：(PQ)( QP)試證明：試證明： (B) (xP(x)x P(x)證證(B)(7) (P(x)xP(x) 公理公理21(8) (P(x)xP(x)

16、(xP(x) P(x) 已知定理已知定理(9) (xP(x) P(x) (8)(7)分離分離(10) (xP(x)x P(x) 全稱規(guī)則全稱規(guī)則(9)例例2 (p42) 試證明：試證明：( x P(x)xP(x)證明：已經(jīng)分別證出如下證明：已經(jīng)分別證出如下(6)(10)兩式兩式(6)( x P(x)xP(x)(10) (xP(x)x P(x)(11)( x P(x)xP(x) (xP(x)x P(x) ( x P(x)xP(x) 公理公理7(12)(xP(x)x P(x) ( x P(x)xP(x) (11)(6)分離分離(13)( x P(x)xP(x) (12)(10)分離分離例例4 (p43) (PQ(x) (P xQ(x)證明：證明：(1)(Q(x)xQ(x)公理公理21(2)(PQ(x)(Q(x) xQ(x)(P xQ(x)公理公理3(3)(PQ(