一階邏輯等值演算與推理

1、第第5 5章章 一階邏輯等值演算與推理一階邏輯等值演算與推理離離 散散 數(shù)數(shù) 學(xué)學(xué)大學(xué)本科生課程大學(xué)本科生課程本章說(shuō)明本章說(shuō)明q 本章的主要內(nèi)容本章的主要內(nèi)容 一階邏輯等值式與基本等值式一階邏輯等值式與基本等值式 置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則、換名規(guī)則、代替規(guī)則 前束范式前束范式 一階邏輯推理理論一階邏輯推理理論q 本章與其他各章的關(guān)系本章與其他各章的關(guān)系 本章先行基礎(chǔ)是前四章本章先行基礎(chǔ)是前四章 本章是集合論各章的先行基礎(chǔ)本章是集合論各章的先行基礎(chǔ)本章主要內(nèi)容本章主要內(nèi)容 5.1 5.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則5.2 5.2 一階邏輯前束范式一階邏輯前束范式

2、5.3 5.3 一階邏輯的推理理論一階邏輯的推理理論5.1 5.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則q 在一階邏輯中，有些命題可以有不同的符號(hào)化形式。在一階邏輯中，有些命題可以有不同的符號(hào)化形式。q 例如：沒(méi)有不犯錯(cuò)誤的人例如：沒(méi)有不犯錯(cuò)誤的人令令 M(x):x M(x):x是人。是人。 F(x):x F(x):x犯錯(cuò)誤。犯錯(cuò)誤。則將上述命題的符號(hào)化有以下兩種正確形式：則將上述命題的符號(hào)化有以下兩種正確形式：(1) (1) x(M(x)x(M(x)F(x)F(x)(2)(2) x(M(x)F(x)x(M(x)F(x)q我們稱我們稱(1)(1)和和(2)(2)是等值的。是等值的。

3、說(shuō)說(shuō)明明等值式的定義等值式的定義定義定義5.15.1 設(shè)設(shè)A A，B B是一階邏輯中任意兩個(gè)公式，若是一階邏輯中任意兩個(gè)公式，若 A AB B是永是永真式，則稱真式，則稱A A與與B B是是等值等值的。的。記做記做A AB B，稱，稱 A AB B 是是等值式等值式。G(x)G(x)x(F(x)x(F(x)G G( (x x) ) )x x( (F F( (x x) ) 例如：例如：q 判斷公式判斷公式A A與與B B是否等值，等價(jià)于判斷公式是否等值，等價(jià)于判斷公式A AB B是否為永真式。是否為永真式。q 謂詞邏輯中關(guān)于聯(lián)結(jié)詞的等值式與命題邏謂詞邏輯中關(guān)于聯(lián)結(jié)詞的等值式與命題邏輯中相關(guān)等值式

4、類似。輯中相關(guān)等值式類似。 說(shuō)說(shuō)明明一階邏輯中的一些基本而重要等值式一階邏輯中的一些基本而重要等值式q 代換實(shí)例代換實(shí)例q 消去量詞等值式消去量詞等值式 q 量詞否定等值式量詞否定等值式 q 量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式 q 量詞分配等值式量詞分配等值式 代換實(shí)例代換實(shí)例q由于命題邏輯中的重言式的代換實(shí)例都是一階邏由于命題邏輯中的重言式的代換實(shí)例都是一階邏輯中的永真式，因而第二章的輯中的永真式，因而第二章的1616組等值式模式給組等值式模式給出的代換實(shí)例都是一階邏輯的等值式的模式。出的代換實(shí)例都是一階邏輯的等值式的模式。q例如：例如：(1)(1) xF(x) xF(x) x

5、F(x) xF(x) （雙重否定律（雙重否定律A A A A）(2)F(x)G(y) (2)F(x)G(y) F(x)G(y) F(x)G(y) （蘊(yùn)涵等值式（蘊(yùn)涵等值式AB AB AB AB）(3)(3) x(F(x)G(y) x(F(x)G(y) zH(z)zH(z) x(F(x)G(y)x(F(x)G(y) zH(z)zH(z) 等值式等值式 ? ?消去量詞等值式消去量詞等值式設(shè)個(gè)體域?yàn)橛邢藜O(shè)個(gè)體域?yàn)橛邢藜疍=aD=a1 1,a,a2 2, ,a,an n,則有則有（1 1） xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （2 2）

6、xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （5.15.1）例例消去量詞消去量詞例例 設(shè)個(gè)體域?yàn)樵O(shè)個(gè)體域?yàn)镈 Da,b,ca,b,c，將下面各公式的量詞消去：，將下面各公式的量詞消去： (1) (1) x(F(x)G(x)x(F(x)G(x)(2) (2) x x yF(x,y)yF(x,y) (3) (3) x(F(x)G(x)x(F(x)G(x)解答解答(1)(1) x(F(x)G(x)x(F(x)G(x) ( (F(a)G(aF(a)G(a) () (F(b)G(bF(b)G(b) () (F(c)G(cF(c)G(c)例例消去量詞消

7、去量詞(2) (2) x x yF(x,y) yF(x,y) x(F(x,a)F(x,b)F(x,c) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) (F(c,a)F(c,b)F(c,c) 在演算中先消去存在量詞也可以，得到結(jié)果是等值的。在演算中先消去存在量詞也可以，得到結(jié)果是等值的。 x x yF(x,y) yF(x,y) yF(a,y) yF(a,y) yF(b,y) yF(b,y) yF(c,y)yF(

8、c,y) (F(a,a)F(a,b)F(a,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) (F(c,a)F(c,b)F(c,c) 例例消去量詞消去量詞例例 設(shè)個(gè)體域?yàn)樵O(shè)個(gè)體域?yàn)镈 Da,b,ca,b,c，將下面各公式的量詞消去：，將下面各公式的量詞消去： (3) (3) x(F(x)G(x)x(F(x)G(x)解答解答(3)(3)x(F(x)G(x)x(F(x)G(x) (F(a)G(a) (F(b)G(b) (F(c)G(c)(F(a)G(a) (F(b)G(b) (F(c)G(c

9、)量詞否定等值式量詞否定等值式設(shè)設(shè)A(x)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x x的公式，則的公式，則（1 1） xA(x) xA(x) xA(x)xA(x)（2 2） xA(x) xA(x) xA(x)xA(x)說(shuō)明說(shuō)明q “并不是所有的并不是所有的x x都有性質(zhì)都有性質(zhì)A”A”與與“存在存在x x沒(méi)有沒(méi)有性質(zhì)性質(zhì)A”A”是一回事。是一回事。q ”不存在有性質(zhì)不存在有性質(zhì)A A的的x”x”與與”所有所有X X都沒(méi)有性質(zhì)都沒(méi)有性質(zhì)A”A”是一回事。是一回事。（5.25.2）量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式設(shè)設(shè)A(x)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)是

10、任意的含自由出現(xiàn)個(gè)體變項(xiàng)x x的公式，的公式，B B中不含中不含x x的出現(xiàn)的出現(xiàn)，則，則（1 1） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)xA(x)（2 2） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)

11、xA(x)（5.35.3）（5.45.4）證明證明: : x(A(x)B) x(A(x)B) xA(x)BxA(x)B xA(x)B xA(x)B x(A(x)B)x(A(x)B) xA(x)B xA(x)B xA(x)BxA(x)B x xA(x)BA(x)B x(x(A(x)B)A(x)B) x(A(x)B)x(A(x)B) x x( (A(x)BA(x)B) ) x x( (A(x)BA(x)B) ) x xA(x)BA(x)B xA(x) BxA(x) B xA(x)xA(x) B B量詞分配等值式量詞分配等值式設(shè)設(shè)A(x)A(x)，B(x)B(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)是任意的含

12、自由出現(xiàn)個(gè)體變項(xiàng)x x的公式，則的公式，則（1 1） x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x)（2 2） x(A(x)B(x) x(A(x)B(x) xA(x) xA(x) xB(x)xB(x)（5.55.5）q 例如，例如，“聯(lián)歡會(huì)上所有人既唱歌又跳舞聯(lián)歡會(huì)上所有人既唱歌又跳舞”和和“聯(lián)歡會(huì)上所聯(lián)歡會(huì)上所有人唱歌且所有人跳舞有人唱歌且所有人跳舞” ” ，這兩個(gè)語(yǔ)句意義相同。故有，這兩個(gè)語(yǔ)句意義相同。故有(1)(1)式。式。q 由由(1)(1)式推導(dǎo)式推導(dǎo)(2)(2)式式 x(A(x)x(A(x)B(xB(x) ) xA(x)xA(x) xB(xx

13、B(x) )則有則有 x(x(A(x)A(x)B(xB(x) ) x xA(x)A(x) x xB(xB(x) )則有則有 x(A(x)B(xx(A(x)B(x) ) ( xA(x)xA(x) xB(xxB(x)則有則有 x(A(x)B(xx(A(x)B(x) ) xA(xxA(x) ) xB(xxB(x) )一階邏輯等值演算的三條原則一階邏輯等值演算的三條原則q 置換規(guī)則置換規(guī)則：設(shè)：設(shè)(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公式是用公式B B取代取代(A)(A)中所有的中所有的A A之后的公式，若之后的公式，若A AB B，則，則(A)(A)(B)(B)。 q 換

14、名規(guī)則換名規(guī)則：設(shè)設(shè)A A為一公式，將為一公式，將A A中某量詞轄域中某約束變項(xiàng)的中某量詞轄域中某約束變項(xiàng)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)某稍摿吭~轄域中未曾出現(xiàn)過(guò)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)某稍摿吭~轄域中未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)符號(hào)，公式的其余部分不變，設(shè)所得公式為某個(gè)體變項(xiàng)符號(hào)，公式的其余部分不變，設(shè)所得公式為AA，則則AAA A。q 代替規(guī)則代替規(guī)則：設(shè)設(shè)A A為一公式，將為一公式，將A A中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)的中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)的所有出現(xiàn)用所有出現(xiàn)用A A中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)代替，中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)代替，A A中其余部中其余部分不變，設(shè)所得公式為分不變，設(shè)所得公式為AA

15、，則，則AAA A。說(shuō)明說(shuō)明q 一階邏輯中的置換規(guī)則與命題邏輯中的置換一階邏輯中的置換規(guī)則與命題邏輯中的置換規(guī)則形式上完全相同，只是在這里規(guī)則形式上完全相同，只是在這里A A，B B是一是一階邏輯公式。階邏輯公式。例例5.15.1例例5.15.1 將下面公式化成與之等值的公式，使其將下面公式化成與之等值的公式，使其沒(méi)有既是約束沒(méi)有既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。(1)(1) xF(x,y,z)xF(x,y,z) yG(x,y,z)yG(x,y,z)(2)(2) x(F(x,y)x(F(x,y) yG(x,y,z)yG(x,y,z)(1)(1) x xF(F(x x

16、,y,z) ,y,z) yG(x,y,zyG(x,y,z) ) tF(t,y,z)tF(t,y,z) y yG(x,G(x,y y,z,z) )( (換名規(guī)則換名規(guī)則) ) tF(t,y,z)tF(t,y,z) wG(x,w,zwG(x,w,z) )( (換名規(guī)則換名規(guī)則) )或或 xF(x,xF(x,y y,z),z) yG(x,y,zyG(x,y,z) ) xF(x,t,z)xF(x,t,z) y yG(G(x x, ,y y,z,z) )( (代替規(guī)則代替規(guī)則) ) x xF(x,t,z)F(x,t,z) y yG(w,y,zG(w,y,z) )( (代替規(guī)則代替規(guī)則) )解答解答例例5

17、.15.1的解答的解答(2)(2) x(F(x,x(F(x,y y) ) yG(x,y,z)yG(x,y,z) x(F(x,t)x(F(x,t) yG(x,y,zyG(x,y,z)( (代替規(guī)則代替規(guī)則) )或或 x(F(x,y)x(F(x,y) y yG(x,y,zG(x,y,z) x(F(x,y)x(F(x,y) tG(x,t,ztG(x,t,z)( (換名規(guī)則換名規(guī)則) )解答解答例例5.25.2例例5.25.2 證明證明（1 1） x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x) xB(x) （2 2） x(A(x)B(x) x(A(x)B(x) xA(x)

18、xA(x) xB(x)xB(x)其中其中A(x)A(x)，B(x)B(x)為含為含x x自由出現(xiàn)的公式。自由出現(xiàn)的公式。只要證明在某個(gè)解釋下兩邊的式子不等值。只要證明在某個(gè)解釋下兩邊的式子不等值。取解釋取解釋I I：個(gè)體域?yàn)樽匀粩?shù)集合：個(gè)體域?yàn)樽匀粩?shù)集合N N；(1)(1)取取F(xF(x) )：x x是奇數(shù)，代替是奇數(shù)，代替A(xA(x) )；取取G(xG(x) )：x x是偶數(shù)，代替是偶數(shù)，代替B(xB(x) )。則則 x(F(x)G(xx(F(x)G(x)為真命題，為真命題，而而 xF(xxF(x) xG(xxG(x) )為假命題。為假命題。兩邊不等值。兩邊不等值。證明證明例例5.25.

19、2(2)(2) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(F(x)G(xx(F(x)G(x)：有些：有些x x既是奇數(shù)又是偶數(shù)為假命題；既是奇數(shù)又是偶數(shù)為假命題；而而 xF(x)xF(x) xG(xxG(x) )：有些：有些x x是奇數(shù)并且有些是奇數(shù)并且有些x x是偶數(shù)為真是偶數(shù)為真命題。命題。 兩邊不等值。兩邊不等值。證明證明說(shuō)明說(shuō)明q 全稱量詞全稱量詞“ ”對(duì)對(duì)“”“”無(wú)分配律。無(wú)分配律。q 存在量詞存在量詞“ ”對(duì)對(duì)“”“”無(wú)分配律。無(wú)分配律。q 當(dāng)當(dāng)B(xB(x) )換成沒(méi)有換成沒(méi)有x x出現(xiàn)的出現(xiàn)的B B時(shí)，則有時(shí)，則有 x(A(x

20、)Bx(A(x)B) ) xA(x)BxA(x)B x(A(x)x(A(x)B B) ) xA(x)xA(x)B B例例5.35.3消去量詞消去量詞例例5.3 5.3 設(shè)個(gè)體域?yàn)樵O(shè)個(gè)體域?yàn)镈 Da,b,ca,b,c，將下面各公式的量詞消去：，將下面各公式的量詞消去： (2) (2) x(F(x) x(F(x) yG(y)yG(y)說(shuō)明說(shuō)明q 如果不用公式如果不用公式(5.3)(5.3)將量詞的轄域縮小，演算過(guò)程較將量詞的轄域縮小，演算過(guò)程較長(zhǎng)。注意，此時(shí)長(zhǎng)。注意，此時(shí) yG(yyG(y) )是與是與x x無(wú)關(guān)的公式無(wú)關(guān)的公式B B。解答解答(2)(2) x(F(x) x(F(x) yG(yyG

21、(y) ) xF(x)xF(x) yG(yyG(y) ) ( (公式公式5.3) 5.3) ( (F(a)F(b)F(c)(G(a)G(b)G(cF(a)F(b)F(c)(G(a)G(b)G(c) ) 例例5.45.4例例5.45.4 給定解釋給定解釋I I如下：如下：（a a）個(gè)體域）個(gè)體域 D D2,32,3（b b）D D中特定元素中特定元素（c c）D D上的特定函數(shù)上的特定函數(shù)(x)(x)為：為：（d d）D D的特定謂詞的特定謂詞2 2a a 。，23(3)(2)f ff f。，為：0 0( (3 3, ,3 3) )1 1( (3 3, ,2 2) )( (2 2, ,3 3)

22、)( (2 2, ,2 2) )y y) )( (x x, ,G GG GG GG GG G。，為：01( (3 3, ,2 2) )( (2 2, ,3 3) )( (3 3, ,3 3) )( (2 2, ,2 2) )y y) )( (x x, ,L LL LL LL LL L。，為：10( (3 3) )( (2 2) )( (x x) )F FF FF F在解釋在解釋I I下求下列各式的值：下求下列各式的值：（1 1） x(F(x)G(x,ax(F(x)G(x,a) ) （2 2） x(F(f(x)G(x,f(xx(F(f(x)G(x,f(x)（3 3） x x yL(x,yyL(x

23、,y) ) （4 4） y y xL(x,yxL(x,y) )例例5.45.4的解答的解答（1 1） x(F(x)G(x,ax(F(x)G(x,a) (F(2)(F(2)G(2,2) G(2,2) (F(3)(F(3)G(3,2) G(3,2) (0(01) 1) (1(11)1) 0 0 （2 2） x(F(f(x)G(x,f(xx(F(f(x)G(x,f(x) (F(f(2)(F(f(2)G(2,f(2) G(2,f(2) (F(f(3)(F(f(3)G(3,f(3) G(3,f(3) (F(3)(F(3)G(2,3) G(2,3) (F(2)(F(2)G(3,2) G(3,2) (1(1

24、1) 1) (0(01)1) 1 1解答解答例例5.45.4的解答的解答（3 3） x x yL(x,yyL(x,y) ) (L(2,2)(L(2,2)L(2,3) L(2,3) (L(3,2)(L(3,2)L(3,3) L(3,3) (1(10) 0) (0(01) 1) 1 1（4 4） y y xL(x,yxL(x,y) ) y(L(2,y)y(L(2,y)L(3,y) L(3,y) (L(2,2)(L(2,2)L(3,2) L(3,2) (L(2,3)(L(2,3)L(3,3) L(3,3) (1(10) 0) (0(01)1) 0 0說(shuō)明說(shuō)明q 由由(3)(3)，(4)(4)的結(jié)果進(jìn)

25、一步可以說(shuō)明量詞的次的結(jié)果進(jìn)一步可以說(shuō)明量詞的次序不能隨意顛倒。序不能隨意顛倒。 例例5.55.5例例5.55.5 證明下列等值式。證明下列等值式。 （1 1） x(M(x)x(M(x)F(x) F(x) x(M(x)x(M(x)F(x) F(x) （2 2） x(F(x)x(F(x)G(x) G(x) x(F(x)x(F(x)G(x) G(x) （3 3） x x y(F(x)y(F(x)G(y)G(y)H(xH(x，y)y) x x y(F(x)y(F(x)G(y)G(y)H(x,y) H(x,y) （4 4） x x y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x

26、 y(F(x)y(F(x)G(y)G(y)L(x,y) L(x,y) 例例5.55.5的證明的證明（1 1） x(M(x)x(M(x)F(x) F(x) x(M(x)x(M(x)F(x)F(x) x(M(x)x(M(x)F(x)F(x) x x(M(x)(M(x)F(x)F(x) x(x(M(x)M(x)F(x)F(x) x(M(x)x(M(x)F(x) F(x) （2 2） x(F(x)x(F(x)G(x) G(x) x(F(x)x(F(x)G(x)G(x) x(F(x)x(F(x)G(x)G(x) x x(F(x)(F(x)G(x)G(x) x x( (F(x)G(x)F(x)G(x) x

27、(F(x)x(F(x)G(x) G(x) 證明證明例例5.55.5的證明的證明（3 3） x x y(F(x)y(F(x)G(y)G(y)H(xH(x，y)y) x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y) x x y y( (F(x)F(x)G(y)G(y)H(xH(x，y)y) ) xx( (y y( (F(x)F(x)G(y)G(y)H(xH(x，y)y) ) ) x x y y( (F(x)F(x)G(y)H(xG(y)H(x，y)y) ) x x y(F(x)y(F(x)G(y)G(y)H(x,y) H(x,y) 例例5.55.5的證明的證明（4 4） x

28、 x y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x y(F(x)y(F(x)G(y)G(y)L(x,y)L(x,y) x x y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x ( y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x y y(F(x)(F(x)G(y)G(y)L(xL(x，y)y) x x y(y(F(x)G(y)F(x)G(y)L(x,y) L(x,y) x x y(F(x)y(F(x)G(y)G(y)L(x,y) L(x,y) 作業(yè)作業(yè)習(xí)題五習(xí)題五2(1)2(1)、5 5（1 1）（）（2 2）復(fù)習(xí)復(fù)習(xí)設(shè)個(gè)體

29、域?yàn)橛邢藜O(shè)個(gè)體域?yàn)橛邢藜疍=aD=a1 1,a,a2 2, ,a,an n,則有則有（1 1） xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （2 2） xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （5.15.1）消去量詞等值式消去量詞等值式量詞否定等值式量詞否定等值式設(shè)設(shè)A(x)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x x的公式，則的公式，則（1 1） xA(x) xA(x) xA(x)xA(x)（2 2） xA(x) xA(x) xA(x)xA(x)說(shuō)明說(shuō)明q

30、“并不是所有的并不是所有的x x都有性質(zhì)都有性質(zhì)A”A”與與“存在存在x x沒(méi)有沒(méi)有性質(zhì)性質(zhì)A”A”是一回事。是一回事。q ”不存在有性質(zhì)不存在有性質(zhì)A A的的x”x”與與”所有所有X X都沒(méi)有性質(zhì)都沒(méi)有性質(zhì)A”A”是一回事。是一回事。（5.25.2）量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式設(shè)設(shè)A(x)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x x的公式，的公式，B B中不含中不含x x的出現(xiàn)的出現(xiàn)，則，則（1 1） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A

31、(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)xA(x)（2 2） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)xA(x)（5.35.3）（5.45.4）量詞分配等值式量詞分配等值式設(shè)設(shè)A(x)A(x)，B(x)B(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x x的公式，則的公式，則（1 1） x(A(x)x(A(x)B(x) B(x) xA(x)

32、xA(x) xB(x)xB(x)（2 2） x(A(x)B(x) x(A(x)B(x) xA(x) xA(x) xB(x)xB(x)（5.55.5）一階邏輯等值演算的三條原則一階邏輯等值演算的三條原則q 置換規(guī)則置換規(guī)則：設(shè)：設(shè)(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公式是用公式B B取代取代(A)(A)中所有的中所有的A A之后的公式，若之后的公式，若A AB B，則，則(A)(A)(B)(B)。 q 換名規(guī)則換名規(guī)則：設(shè)設(shè)A A為一公式，將為一公式，將A A中某量詞轄域中某中某量詞轄域中某約束約束變項(xiàng)的變項(xiàng)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)某稍摿吭~轄域中未曾出現(xiàn)過(guò)的所有

33、出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)某稍摿吭~轄域中未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)符號(hào)，公式的其余部分不變，設(shè)所得公式為某個(gè)體變項(xiàng)符號(hào)，公式的其余部分不變，設(shè)所得公式為AA，則則AAA A。q 代替規(guī)則代替規(guī)則：設(shè)設(shè)A A為一公式，將為一公式，將A A中某個(gè)中某個(gè)自由自由出現(xiàn)的個(gè)體變項(xiàng)的出現(xiàn)的個(gè)體變項(xiàng)的所有出現(xiàn)用所有出現(xiàn)用A A中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)代替，中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)代替，A A中其余部中其余部分不變，設(shè)所得公式為分不變，設(shè)所得公式為AA，則，則AAA A。5.2 5.2 一階邏輯前束范式一階邏輯前束范式定義定義5.25.2 設(shè)設(shè)A A為一個(gè)一階邏輯公式，若為一個(gè)一階邏輯公式，若A A具有如下形式具

34、有如下形式Q Q1 1x x1 1Q Q2 2x x2 2 Q Qk kx xk kB B則稱則稱A A為為前束范式前束范式，其中，其中Q Qi i(1ik)(1ik)為為 或或 ，B B為不含量詞為不含量詞的公式。的公式。q 前束范式的例子：前束范式的例子： x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y) y) x x y y z(F(x)G(y)H(z)L(xz(F(x)G(y)H(z)L(x，y y，z) z) q 不是前束范式的例子：不是前束范式的例子： x x( (F(x)F(x) y y(G(y)H(x(G(y)H(x，y)y) ) x x( (F(x)F(x)

35、 y y(G(y)H(x(G(y)H(x，y)y) )例例: :以下公式哪些是前束范式？以下公式哪些是前束范式？ （1 1） xF(x)xF(x) x xG(G(x x) )（2 2） x(F(x)x(F(x) y G(y) y G(y) （3 3） x x y(F(x)G(y) y(F(x)G(y) （4 4） y y x(F(x)G(y)x(F(x)G(y) 解：（解：（1 1）F F（2 2）F F（3 3）T T（4 4）T T前束范式存在定理前束范式存在定理定理定理5.1 5.1 一階邏輯中的任何公式都存在與之等值的前束范式。一階邏輯中的任何公式都存在與之等值的前束范式。求前束范式一

36、般過(guò)程求前束范式一般過(guò)程(1)(1)利用量詞轉(zhuǎn)化公式，把否定轉(zhuǎn)入到指導(dǎo)變?cè)暮竺?。利用量詞轉(zhuǎn)化公式，把否定轉(zhuǎn)入到指導(dǎo)變?cè)暮竺妗?xA(xxA(x) ) xA(xxA(x) ) xA(xxA(x) ) xA(xxA(x) )(2)(2)利用利用量詞轄域收縮與擴(kuò)張等值式，如量詞轄域收縮與擴(kuò)張等值式，如 B B xA(xxA(x) ) x(A(x)Bx(A(x)B) ) xA(x)xA(x)B B x(A(x)x(A(x)B B) ) 把量詞移到全式的最前面，這樣便得到前束范式。把量詞移到全式的最前面，這樣便得到前束范式。 例例5.6 5.6 求公式的前束范式求公式的前束范式（1 1） xF(x)

37、xF(x) x xG(G(x x) )（2 2） xF(x)xF(x) xG(x)xG(x)例例5.6 5.6 求公式的前束范式求公式的前束范式（1 1） xF(x)xF(x) x xG(G(x x) )法一法一 xF(x)xF(x) x xG(G(x x) ) xF(x)xF(x) yG(y) yG(y) ( (換名規(guī)則換名規(guī)則) ) xF(x)xF(x) yG(y) yG(y) (5.2)(5.2)第二式第二式) ) x(F(x)x(F(x) yG(y) yG(y) (5.3)(5.3)第二式第二式) ) x x y(F(x)G(y) y(F(x)G(y) (5.3)(5.3)第二式第二式

38、) ) 法二法二 xF(x)xF(x) xG(x) xG(x) xF(x)xF(x) xG(x)xG(x) (5.2)(5.2)第二式第二式) ) x(F(x)G(x) x(F(x)G(x) (5.5)(5.5)第一式第一式) ) 例例5.6 5.6 求公式的前束范式求公式的前束范式（2 2） xF(x)xF(x) xG(x)xG(x) xF(x)xF(x) xG(xG(x x) ) (5.2)(5.2)第二式第二式) ) xF(x)xF(x) yG(y) yG(y) ( (換名規(guī)則換名規(guī)則) ) x(F(x)x(F(x) yG(y) yG(y) (5.3)(5.3)第一式第一式) ) x x

39、 y(F(x)G(y) y(F(x)G(y) (5.3)(5.3)第一式第一式) ) 說(shuō)明說(shuō)明q 求前束范式的過(guò)程，就是制造量詞轄域可以擴(kuò)大的求前束范式的過(guò)程，就是制造量詞轄域可以擴(kuò)大的條件，進(jìn)行量詞轄域擴(kuò)大。條件，進(jìn)行量詞轄域擴(kuò)大。q 任何公式的前束范式都是存在的，但一般說(shuō)來(lái)，并任何公式的前束范式都是存在的，但一般說(shuō)來(lái)，并不唯一。不唯一。q 利用一階邏輯等值式以及三條變換規(guī)則（置換規(guī)則利用一階邏輯等值式以及三條變換規(guī)則（置換規(guī)則、換名規(guī)則、代替規(guī)則）就可以求出與公式等值的、換名規(guī)則、代替規(guī)則）就可以求出與公式等值的前束范式，或所謂公式的前束范式。前束范式，或所謂公式的前束范式。例例5.8 5

40、.8 求公式的前束范式求公式的前束范式(1)(1) xF(xF(x,x,y)y) yG(x,yG(x,y y) ) (2)(2)( x x1 1F(F(x x1 1,x,x2 2) ) x x2 2G(G(x x2 2) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) 例例5.8 5.8 求公式的前束范式求公式的前束范式(1)(1) xF(xF(x,x,y)y) yG(x,yG(x,y y) ) tF(t,y)tF(t,y) wG(x,w) (wG(x,w) (換名規(guī)則換名規(guī)則) ) t t w(F(t,y)G(x,w) (5.3),(5.4) w(F(t,y)G(x,w

41、) (5.3),(5.4) 或者或者 xF(x,xF(x,y y) yG(yG(x x,y) ,y) xF(x,t)xF(x,t) yG(w,y) (yG(w,y) (代替規(guī)則代替規(guī)則) ) x x y(F(x,t)G(w,y) (5.3),(5.4)y(F(x,t)G(w,y) (5.3),(5.4)說(shuō)明說(shuō)明q 解本題時(shí)一定注意，哪些個(gè)體變項(xiàng)是約束出現(xiàn)解本題時(shí)一定注意，哪些個(gè)體變項(xiàng)是約束出現(xiàn)，哪些是自由出現(xiàn)，特別要注意那些既是約束，哪些是自由出現(xiàn)，特別要注意那些既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。不能混淆出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。不能混淆。例例5.8 5.8 求公式的前束范式求公式的前束范

42、式(2)(2)( x x1 1F(F(x x1 1,x,x2 2) ) x x2 2G(G(x x2 2) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) ( ( x x4 4F(F(x x4 4,x,x2 2) ) x x5 5G(G(x x5 5) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) x x4 4 x x5 5(F(F(x x4 4,x,x2 2) ) G(G(x x5 5) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) x x4 4 x x5 5 x x1 1( ( (F(F(x x4 4,x,x2 2) )

43、 G(G(x x5 5) ) ) H(xH(x1 1,x,x2 2,x,x3 3) ) ) 5.3 5.3 一階邏輯的推理理論一階邏輯的推理理論q 在一階邏輯中，從前提在一階邏輯中，從前提A A1 1,A,A2 2, ,A Ak k出發(fā)推結(jié)論出發(fā)推結(jié)論B B的推理形式結(jié)的推理形式結(jié)構(gòu)，依然采用如下的蘊(yùn)涵式形式構(gòu)，依然采用如下的蘊(yùn)涵式形式A A1 1 A A2 2 A Ak k B B （5.65.6）若式（若式（5.65.6）為永真式，則稱）為永真式，則稱推理正確推理正確，否則稱推理不正確。，否則稱推理不正確。q 于是，在一階邏輯中判斷推理是否正確也歸結(jié)為判斷（于是，在一階邏輯中判斷推理是否正

44、確也歸結(jié)為判斷（5.65.6）式是否為永真式了。式是否為永真式了。q 在一階邏輯中稱永真式的蘊(yùn)涵式為在一階邏輯中稱永真式的蘊(yùn)涵式為推理定律推理定律，q 在一階邏輯的推理中，在一階邏輯的推理中，某些前提與結(jié)論可能是受量詞限制，某些前提與結(jié)論可能是受量詞限制，為了使用命題邏輯中的為了使用命題邏輯中的等值式和推理定律等值式和推理定律，必須在推理過(guò)程必須在推理過(guò)程中有消去和添加量詞的規(guī)則中有消去和添加量詞的規(guī)則，以便使謂詞公式的推理過(guò)程可，以便使謂詞公式的推理過(guò)程可類似于命題演算中推理理論那樣進(jìn)行。類似于命題演算中推理理論那樣進(jìn)行。定義定義5.3 5.3 自然推理系統(tǒng)自然推理系統(tǒng)N N定義定義1.1.

45、字母表。同一階語(yǔ)言的字母表。字母表。同一階語(yǔ)言的字母表。2.2.合式公式。同合式公式的定義。合式公式。同合式公式的定義。3.3.推理規(guī)則。推理規(guī)則。一階語(yǔ)言中的字母表一階語(yǔ)言中的字母表定義定義4.14.1 一階語(yǔ)言一階語(yǔ)言L L的的字母表字母表定義如下定義如下: :(1)(1)個(gè)體常項(xiàng)：個(gè)體常項(xiàng)：a , b , c , , ai , bi , ci , , i 1(2)(2)個(gè)體變項(xiàng)：個(gè)體變項(xiàng)：x , y , z, , xi , yi , zi , , i 1 (3)(3)函數(shù)符號(hào)：函數(shù)符號(hào)：f , g , h , , fi , gi , hi , , i 1(4)(4)謂詞符號(hào)：謂詞符號(hào)：F

46、 , G , H , , Fi , Gi , Hi , , i 1(5)(5)量詞符號(hào)量詞符號(hào): : ， (6)(6)聯(lián)結(jié)詞符號(hào)聯(lián)結(jié)詞符號(hào):, :, (7)(7)括號(hào)與逗號(hào)括號(hào)與逗號(hào):(,),:(,),，定義定義4.3 設(shè)設(shè)R(x1,x2,xn)是一階語(yǔ)言是一階語(yǔ)言L L中的中的n元謂詞符號(hào)元謂詞符號(hào)。t1,t2,tn 是是L L 的的n個(gè)個(gè)項(xiàng)項(xiàng)，則稱，則稱 R(t1,t2,tn )是是L L 的的原子公式原子公式。例如例如 一元謂詞一元謂詞F(x)，G(y)；二元謂詞二元謂詞H(x,y)，L(x,y)都是原子公式都是原子公式合式公式合式公式定義定義4.4 一階語(yǔ)言一階語(yǔ)言L L 中的中的合式

47、公式合式公式 (也稱為謂詞公式或公式也稱為謂詞公式或公式) 定義如下：定義如下：(1) 原子公式是合式公式；原子公式是合式公式；(2) 若若A是合式公式，則是合式公式，則 (A)也是合式公式；也是合式公式；(3) 若若A, B 是合式公式，則是合式公式，則(AB), (AB), (AB), (AB)也是合也是合式公式；式公式；(4) 若若A是合式公式，則是合式公式，則 xA, xA也是合式公式；也是合式公式；(5) 只有有限次應(yīng)用只有有限次應(yīng)用 (1)(4) 構(gòu)成的符號(hào)串才是合式公式。構(gòu)成的符號(hào)串才是合式公式。例如例如 x(F(x,y)G(x,z)、x(F(x)G(y)y(H(x)L(x,y,

48、z) 推理規(guī)則的來(lái)源推理規(guī)則的來(lái)源q 命題邏輯推理定律的代換實(shí)例命題邏輯推理定律的代換實(shí)例q 由基本等值式生成的推理規(guī)則由基本等值式生成的推理規(guī)則q 量詞分配等值式量詞分配等值式q 推理規(guī)則推理規(guī)則量詞消去和引入規(guī)則量詞消去和引入規(guī)則命題邏輯推理定律的代換實(shí)例命題邏輯推理定律的代換實(shí)例q xF(x)xF(x) yG(y) yG(y) xF(x)xF(x)（化簡(jiǎn)律的代換實(shí)例）（化簡(jiǎn)律的代換實(shí)例）q xF(x) xF(x) xF(x) xF(x) yG(y) yG(y) （附加律的代換實(shí)例）（附加律的代換實(shí)例）q xF(x) xF(x) xF(x) xF(x) （雙重否定律的代換實(shí)例） xF(x)

49、 xF(x) xF(x)xF(x)由基本等值式生成的推理定律由基本等值式生成的推理定律q xF(x) xF(x) xF(x)xF(x)q xF(x) xF(x) xF(x) xF(x) q 其他推理規(guī)則其他推理規(guī)則q xA(x)xA(x) xB(x) xB(x) x(A(x)B(x) x(A(x)B(x) q x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x)xB(x) q x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x) xB(x) q x(A(x)B(x) x(A(x)B(x) xA(x) xA(x) xB(x) xB(x) q 對(duì)對(duì)

50、x(A(x)B(xx(A(x)B(x) ) xA(x)xA(x) xB(xxB(x) )的討論的討論若若 x(A(x)B(xx(A(x)B(x)為真，則有一個(gè)客體為真，則有一個(gè)客體c c，使得，使得A(c)B(cA(c)B(c) )為真，即為真，即A(cA(c) )和和B(cB(c) )都為真，所以都為真，所以 xA(x)xA(x) xB(xxB(x) )也為真。也為真。 量詞消去和引入規(guī)則量詞消去和引入規(guī)則q 為了構(gòu)造推理系統(tǒng)，還要給出為了構(gòu)造推理系統(tǒng)，還要給出4 4條重要的推理規(guī)則條重要的推理規(guī)則, ,即消去量詞和引入量詞的規(guī)則：即消去量詞和引入量詞的規(guī)則：1 1全稱量詞消去規(guī)則全稱量詞消

51、去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UIUI規(guī)則或規(guī)則或-規(guī)則規(guī)則) )2 2全稱量詞引入規(guī)則全稱量詞引入規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UGUG規(guī)則規(guī)則+規(guī)則規(guī)則) )3 3存在量詞消去規(guī)則存在量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為EIEI規(guī)則規(guī)則-規(guī)則規(guī)則) ) 4 4存在量詞引入規(guī)則存在量詞引入規(guī)則( (簡(jiǎn)稱簡(jiǎn)稱EGEG規(guī)則規(guī)則+規(guī)則規(guī)則) )全稱量詞消去規(guī)則全稱量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UIUI規(guī)則或規(guī)則或-) )含義含義：如果個(gè)體域的所有元素都具有性質(zhì)：如果個(gè)體域的所有元素都具有性質(zhì)A A，則個(gè)體域中的任，則個(gè)體域中的任一元素具有性質(zhì)一元素具有性質(zhì)A A。 兩式成立的條件兩式成立的條件： (1)(1)在第一式

52、中，當(dāng)在第一式中，當(dāng)A(x)A(x)不是原子公式時(shí)，不是原子公式時(shí)，y y不在不在A(x)A(x)中約束中約束出現(xiàn)出現(xiàn), ,或或x x應(yīng)為不在應(yīng)為不在A(y)A(y)中自由出現(xiàn)的個(gè)體變項(xiàng)。中自由出現(xiàn)的個(gè)體變項(xiàng)。 (2)(2)在第二式中，在第二式中，c c為任意個(gè)體常項(xiàng)。為任意個(gè)體常項(xiàng)。 (3)(3)用用y y或或c c去取代去取代A(x)A(x)中自由出現(xiàn)的中自由出現(xiàn)的x x時(shí)，一定要在時(shí)，一定要在x x自由出現(xiàn)自由出現(xiàn)的一切地方進(jìn)行取代。的一切地方進(jìn)行取代。 A A( (c c) )x xA A( (x x) )或或A A( (y y) )x xA A( (x x) )1 1 全稱量詞消去規(guī)

53、則全稱量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UIUI規(guī)則或規(guī)則或UI)UI)舉例舉例當(dāng)當(dāng)A(xA(x) )為原子公式時(shí)，比如為原子公式時(shí)，比如A(xA(x)=)=F(xF(x) )，則當(dāng)，則當(dāng) xA(xxA(x) )為為真時(shí)，對(duì)于個(gè)體域中任意的個(gè)體變項(xiàng)真時(shí)，對(duì)于個(gè)體域中任意的個(gè)體變項(xiàng)y y，不會(huì)出現(xiàn)，不會(huì)出現(xiàn)F(yF(y) )為為假的情況。假的情況。當(dāng)當(dāng)A(xA(x) )不是原子公式時(shí)，如不是原子公式時(shí)，如y y已在已在A(xA(x) )中約束出現(xiàn)了，就中約束出現(xiàn)了，就不能用不能用y y取代取代x x，否則會(huì)出現(xiàn)，否則會(huì)出現(xiàn) xA(xxA(x) )為真而為真而A(yA(y) )為假的情為假的情況。況。

54、考慮個(gè)體域?yàn)閷?shí)數(shù)集合，公式考慮個(gè)體域?yàn)閷?shí)數(shù)集合，公式A(xA(x)=)= yF(x,yyF(x,y) )為為xyxy。當(dāng)對(duì)公式當(dāng)對(duì)公式 xA(xxA(x)=)= x x yF(x,yyF(x,y) )使用使用UIUI規(guī)則時(shí)，用規(guī)則時(shí)，用y y取代取代x x，就會(huì)得到，就會(huì)得到A(yA(y)=)= yF(y,yyF(y,y) )，即，即 y(yy(yy)y)，這顯然是假命，這顯然是假命題。原因是違背了條件題。原因是違背了條件(1)(1)。若用若用z z取代取代x x，得，得A(zA(z)=)= yF(z,yyF(z,y)=)= y(zy(zy)y)就不會(huì)產(chǎn)生這就不會(huì)產(chǎn)生這種錯(cuò)誤。種錯(cuò)誤。2 2

55、全稱量詞引入規(guī)則全稱量詞引入規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UGUG規(guī)則或規(guī)則或+) )該式成立的條件是：該式成立的條件是： （1 1）x x不能在前提任何公式中自由出現(xiàn)。不能在前提任何公式中自由出現(xiàn)。x xA A( (x x) )A A( (x x) )含義含義：如果個(gè)體域中的任一元素：如果個(gè)體域中的任一元素具有性質(zhì)具有性質(zhì)A，則個(gè)體域的所有元素，則個(gè)體域的所有元素都具有性質(zhì)都具有性質(zhì)A。 例例 設(shè)個(gè)體域設(shè)個(gè)體域I I為整數(shù)集合，為整數(shù)集合，P P(x)(x)：x x為偶數(shù)，為偶數(shù)，Q Q（x x）x x被被2 2整除整除。指出在推理系統(tǒng)中，以。指出在推理系統(tǒng)中，以P P(x)(x)Q Q（x x）(

56、 (真命題真命題) )，P P(x)(x)為前為前提，推出提，推出 x xQ Q(x)(x)(假命題假命題) )的下述推理證明中的錯(cuò)誤。的下述推理證明中的錯(cuò)誤。 P P(x)(x)Q Q（x x） 前提引入前提引入 P P（x x） 前提引入前提引入 Q Q（x x） 假言推理假言推理 x xQ Q(x) (x) +規(guī)則規(guī)則 解解 在以上推理證明中，第四步錯(cuò)了，由于在以上推理證明中，第四步錯(cuò)了，由于x x在在前提公式前提公式中中自由自由出現(xiàn)出現(xiàn)，用了，用了+規(guī)則，導(dǎo)致了從真命題推出假命題的錯(cuò)誤。規(guī)則，導(dǎo)致了從真命題推出假命題的錯(cuò)誤。3 3 存在量詞消去規(guī)則存在量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為EI

57、EI規(guī)則或規(guī)則或-) ) 該式成立的條件是：該式成立的條件是： (1)c(1)c是使是使A A為真的為真的特定特定的個(gè)體常項(xiàng)。的個(gè)體常項(xiàng)。 (2)x(2)x不在前提中自由出現(xiàn)。不在前提中自由出現(xiàn)。(3) (3) A(x)不含其它自由出現(xiàn)的個(gè)體變項(xiàng)。自由出現(xiàn)的個(gè)體變項(xiàng)。 A A( (c c) )x xA A( (x x) )舉例舉例取個(gè)體域?yàn)樽匀粩?shù)集合，取個(gè)體域?yàn)樽匀粩?shù)集合，F(xiàn)(xF(x) )為為x x是奇數(shù)，是奇數(shù)，G(xG(x) )為為x x是偶數(shù)是偶數(shù)。 xF(xxF(x) )與與 xG(xxG(x) )都是真命題，則對(duì)于某些都是真命題，則對(duì)于某些c c和和d d，可以斷，可以斷定定F(c

58、)G(dF(c)G(d) )必定為真，但不能斷定必定為真，但不能斷定F(c)G(cF(c)G(c) )是真。是真。 對(duì)對(duì) xF(xxF(x) )使用使用 - -規(guī)則時(shí)，取代規(guī)則時(shí)，取代x x的的c c一定是特定的個(gè)體常項(xiàng)一定是特定的個(gè)體常項(xiàng)1,3,51,3,5等奇數(shù)。等奇數(shù)。對(duì)對(duì) xG(xxG(x) )使用使用 - -規(guī)則時(shí)，取代規(guī)則時(shí)，取代x x的的c c一定是特定的個(gè)體常項(xiàng)一定是特定的個(gè)體常項(xiàng)2,4,62,4,6等偶數(shù)。等偶數(shù)。B BA(x)A(x)B BA(x)A(x)x例例例例 設(shè)個(gè)體域?yàn)閷?shí)數(shù)集合，設(shè)個(gè)體域?yàn)閷?shí)數(shù)集合，F(xiàn)(x,y)F(x,y)為為xyxy。指出在推理系統(tǒng)中，。指出在推理

59、系統(tǒng)中，以以 x x yF(xyF(x，y)(y)(真命題真命題) )為前提，推出為前提，推出 xF(x,c)(xF(x,c)(假命題假命題) )的的下述推理證明中的錯(cuò)誤。下述推理證明中的錯(cuò)誤。 x x yF(x,y) yF(x,y) 前提引入前提引入 yF(z,y) yF(z,y) UIUI規(guī)則規(guī)則 F(z,c) F(z,c) EIEI規(guī)則規(guī)則 xF(x,c) xF(x,c) UGUG規(guī)則規(guī)則 解解 由于由于c c為特定的個(gè)體常項(xiàng)，所以為特定的個(gè)體常項(xiàng)，所以 xF(x,c)(xF(x,c)(即為即為 x(xc)x(xc)為為假命題。如果按推理規(guī)則進(jìn)行推理，不會(huì)從真命題推出假命假命題。如果按推

60、理規(guī)則進(jìn)行推理，不會(huì)從真命題推出假命題。題。在以上推理證明中，第三步錯(cuò)了，由于在以上推理證明中，第三步錯(cuò)了，由于F(z,y)F(z,y)中有自由出現(xiàn)中有自由出現(xiàn)的的z z，按，按EIEI規(guī)則應(yīng)該滿足的條件規(guī)則應(yīng)該滿足的條件(3)(3)，此處不能用，此處不能用EIEI規(guī)則。用規(guī)則。用了了EIEI規(guī)則，導(dǎo)致了從真命題推出假命題的錯(cuò)誤。規(guī)則，導(dǎo)致了從真命題推出假命題的錯(cuò)誤。4 4 存在量詞引入規(guī)則存在量詞引入規(guī)則( (簡(jiǎn)稱簡(jiǎn)稱EGEG規(guī)則或規(guī)則或+) ) 該式成立的條件是：該式成立的條件是： (1)c(1)c是特定的個(gè)體常項(xiàng)。是特定的個(gè)體常項(xiàng)。(2)(2)取代取代c c的的x x不能在不能在A(c)