第五章一階邏輯等值演算與推理

1、復(fù)習(xí)復(fù)習(xí) q 變?cè)募s束(Bound of variable在x和x的轄域中，x的所有出現(xiàn)都稱(chēng)為約束出現(xiàn)，相應(yīng)的x稱(chēng)為約束變?cè)? P(x)中除約束變?cè)酝獬霈F(xiàn)的變?cè)Q(chēng)為是自由變?cè)?。?： 1、x( H(x,y)y(W(y) L(x,y,z) 2、 x( H(x)W(y) y( F(x) L(x,y,z)q 注意：(1)n元謂詞公式A(x1，x2.xn) 中有n個(gè)自由變?cè)?若對(duì)其中的k(kn)個(gè)進(jìn)行約束,則構(gòu)成了n-k元謂詞;如果一個(gè)公式中沒(méi)有自由變?cè)霈F(xiàn),則該公式就變成了一個(gè)命題(2)一個(gè)公式的約束變?cè)褂玫拿Q(chēng)符號(hào)是無(wú)關(guān)緊要的,如(x)M(x)與(y)M(y)意義相同.約束變?cè)膿Q名與自由

2、變?cè)拇胍?guī)則換名規(guī)則: (對(duì)約束變?cè)裕?duì)約束變?cè)M(jìn)行換名,使得一個(gè)變?cè)谝粋€(gè)公式中只呈一種形式出現(xiàn).(1)約束變?cè)梢該Q名,其更改的變?cè)Q(chēng)范圍是量詞中的指導(dǎo)變?cè)约霸摿吭~作用域中所出現(xiàn)的該變?cè)?公式的其余部分不變.(2)換名時(shí)一定要更改為作用域中沒(méi)有出現(xiàn)的變?cè)Q(chēng).q 例1: x( P(x)R(x,y) L(x,y)換名為t( P(t)R(t,y) L(x,y)q x( H(x,y)y(W(y) L(x,y,z)換名為x( H(x,y)s(W(s) L(x,s,z)q 代入規(guī)則（對(duì)自由變?cè)裕?duì)公式中自由變?cè)母姆Q(chēng)為代入(1)對(duì)于謂詞公式中的自由變?cè)梢宰鞔?代入時(shí)需要對(duì)公式中出

3、現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行;(2)用以代入的變?cè)c原公式中所有變?cè)拿Q(chēng)不能相同.例如對(duì)例1中的公式x( P(x)R(x,y) L(x,y) 自由變?cè)獃用z來(lái)代入,得 x( P(x)R(x,z) L(x,z)習(xí)題習(xí)題1、 在一階邏輯中將下列命題符號(hào)化。在一階邏輯中將下列命題符號(hào)化。（1） 大熊貓都可愛(ài)。大熊貓都可愛(ài)。（2） 有人愛(ài)發(fā)脾氣。有人愛(ài)發(fā)脾氣。（3） 說(shuō)所有人都愛(ài)吃面包是不對(duì)的。說(shuō)所有人都愛(ài)吃面包是不對(duì)的。（4） 沒(méi)有不愛(ài)吃糖的人。沒(méi)有不愛(ài)吃糖的人。（5） 一切人都不一樣高。一切人都不一樣高。（6） 并不是所有的汽車(chē)都比火車(chē)快。并不是所有的汽車(chē)都比火車(chē)快。解：由于沒(méi)指出個(gè)體域，故用全總個(gè)

4、體域解：由于沒(méi)指出個(gè)體域，故用全總個(gè)體域（1）大熊貓都可愛(ài)。）大熊貓都可愛(ài)。 設(shè)設(shè)F(x): x為大熊貓，為大熊貓，G(x): x可愛(ài)，命題符號(hào)化為可愛(ài)，命題符號(hào)化為 x(F(x)G(x)（2）有人愛(ài)發(fā)脾氣。）有人愛(ài)發(fā)脾氣。 設(shè)設(shè)F(x): x是人，是人，G(x): x愛(ài)發(fā)脾氣，命題符號(hào)化為愛(ài)發(fā)脾氣，命題符號(hào)化為 x(F(x) G(x)（3）說(shuō)所有人都愛(ài)吃面包是不對(duì)的。）說(shuō)所有人都愛(ài)吃面包是不對(duì)的。 設(shè)設(shè)F(x): x是人，是人，G(x):x愛(ài)吃面包，命題符號(hào)化為愛(ài)吃面包，命題符號(hào)化為 x(F(x)G(x) 或或 x(F(x)G(x)（4）沒(méi)有不愛(ài)吃糖的人。）沒(méi)有不愛(ài)吃糖的人。 設(shè)設(shè)F(x):

5、 x是人，是人，G(x): x愛(ài)吃糖，命題符號(hào)化為愛(ài)吃糖，命題符號(hào)化為 x(F(x)G(x) 或或 x(F(x)G(x)（5）一切人都不一樣高。）一切人都不一樣高。 設(shè)設(shè) F(x):x是人是人, H(x,y)：x與與y相同相同, L(x,y): x與與y一樣高，命題一樣高，命題符號(hào)化為符號(hào)化為 x y(F(x) F(y)H(x,y)L(x,y) 或或 x(F(x)y(F(y)H(x,y)L(x,y)（6）并不是所有的汽車(chē)都比火車(chē)快。）并不是所有的汽車(chē)都比火車(chē)快。 設(shè)設(shè)F(x):x是汽車(chē)是汽車(chē), G(y):y是火車(chē)是火車(chē), H(x,y):x比比y快，命題符號(hào)化為快，命題符號(hào)化為 x y(F(x)

6、 G(y)H(x,y) 或或 x y(F(x) G(y)H(x,y)2、在一階邏輯中將下列命題符號(hào)化。、在一階邏輯中將下列命題符號(hào)化。（1） 沒(méi)有一個(gè)自然數(shù)大于等于任何自然數(shù)。沒(méi)有一個(gè)自然數(shù)大于等于任何自然數(shù)。（2） 有唯一的偶素?cái)?shù)。有唯一的偶素?cái)?shù)。解：解：（1）N(x):x是自然數(shù)，是自然數(shù)，G(x,y):x y x(N(x)y(N(y) G(x,y)（2）Q(x):x是偶數(shù)，是偶數(shù)，P(x):x是素?cái)?shù)，是素?cái)?shù)， E(x,y):xy x(Q(x) P(x)y(Q(y) P(y) E(x,y)3、判斷公式是否為永真公式。判斷公式是否為永真公式。 ( x A(x) x B(x) x (A(x)

7、B(x) 解：解： 不是永真公式。不是永真公式。 設(shè)個(gè)體域?yàn)樵O(shè)個(gè)體域?yàn)閍,b，令令A(yù)(a)=1,B(a)=0, A(b)=0,B(b)=1。小節(jié)結(jié)束小節(jié)結(jié)束第5章 一階邏輯等值演算與推理離離 散散 數(shù)數(shù) 學(xué)學(xué)山東師范大學(xué)本科生課程山東師范大學(xué)本科生課程信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院2008專(zhuān)升本專(zhuān)升本本章說(shuō)明本章說(shuō)明q 本章的主要內(nèi)容本章的主要內(nèi)容一階邏輯等值式與基本等值式一階邏輯等值式與基本等值式置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式前束范式一階邏輯推理理論一階邏輯推理理論q 本章與其他各章的關(guān)系本章與其他各章的關(guān)系本章先行基礎(chǔ)是前四章本章先行基礎(chǔ)是前四章本章

8、是集合論各章的先行基礎(chǔ)本章是集合論各章的先行基礎(chǔ)本章主要內(nèi)容本章主要內(nèi)容 5.1 5.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則5.2 5.2 一階邏輯前束范式一階邏輯前束范式5.3 5.3 一階邏輯的推理理論一階邏輯的推理理論 主要內(nèi)容主要內(nèi)容 作作 業(yè)業(yè)5.1 5.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則在一階邏輯中，有些命題可以有不同的符號(hào)化形式。在一階邏輯中，有些命題可以有不同的符號(hào)化形式。例如：例如：沒(méi)有不犯錯(cuò)誤的人沒(méi)有不犯錯(cuò)誤的人令令 M(x):xM(x):x是人。是人。 F(x):xF(x):x犯錯(cuò)誤。犯錯(cuò)誤。則將上述命題的符號(hào)化有以下兩種正確形式：則將上述

9、命題的符號(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我們稱(chēng)我們稱(chēng)(1)(1)和和(2)(2)是等值的。是等值的。說(shuō)說(shuō)明明等值式的定義等值式的定義定義定義5.15.1 設(shè)設(shè)A A，B B是一階邏輯中任意兩個(gè)公式，若是一階邏輯中任意兩個(gè)公式，若 A AB B是永真是永真式，則稱(chēng)式，則稱(chēng)A A與與B B是是等值等值的。的。記做記做A AB B，稱(chēng)稱(chēng) A AB B 是是等值式等值式。G(x)G(x)x(F(x)x(F(x)G G( (x x) ) )x x( (F F( (x x) ) 例如：例如：q 判斷公式

10、判斷公式A A與與B B是否等值，等價(jià)于判斷公式是否等值，等價(jià)于判斷公式A AB B是否是否為永真式。為永真式。q 謂詞邏輯中關(guān)于聯(lián)結(jié)詞的等值式與命題邏輯中相關(guān)謂詞邏輯中關(guān)于聯(lián)結(jié)詞的等值式與命題邏輯中相關(guān)等值式類(lèi)似。等值式類(lèi)似。 說(shuō)說(shuō)明明一階邏輯中的一些基本而重要等值式一階邏輯中的一些基本而重要等值式q 代換實(shí)例代換實(shí)例q 消去量詞等值式消去量詞等值式 q 量詞否定等值式量詞否定等值式 q 量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式 q 量詞分配等值式量詞分配等值式 代換實(shí)例代換實(shí)例-命題公式的推廣命題公式的推廣 由于命題邏輯中的重言式的代換實(shí)例都是一階邏輯中的永由于命題邏輯中的重言式的

11、代換實(shí)例都是一階邏輯中的永真式，因而真式，因而第二章的第二章的1616組等值式組等值式模式給出的代換實(shí)例都是模式給出的代換實(shí)例都是一階邏輯的等值式的模式。一階邏輯的等值式的模式。例如：例如：(1)(1) xF(xxF(x) ) xF(xxF(x) )（雙重否定律）雙重否定律）(2)(2)F(x)G(y) F(x)G(y) F(x)G(y) F(x)G(y) （蘊(yùn)涵等值式）蘊(yùn)涵等值式）(3)(3) x(F(x)G(y) x(F(x)G(y) zH(zzH(z) ) x(F(x)G(y)x(F(x)G(y) zH(zzH(z) ) （蘊(yùn)涵等值式）蘊(yùn)涵等值式）消去量詞等值式消去量詞等值式設(shè)個(gè)體域?yàn)橛?/p>

12、限集設(shè)個(gè)體域?yàn)橛邢藜疍=aD=a1 1,a,a2 2, ,a,an n,則有則有（1 1） xA(xxA(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(xxA(x) ) xA(x)xA(x)（2 2） xA(x) xA(x) xA(x)xA(x)說(shuō)明說(shuō)明q “并不是所有的并不是所有的x x都

13、有性質(zhì)都有性質(zhì)A”A”與與“存在存在x x沒(méi)有性質(zhì)沒(méi)有性質(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(x)B) xA(x)BxA(x)

14、B x(BA(x) x(BA(x) BB xA(xxA(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) BB xA(xxA(x) )（5.35.3）（5.45.4）量詞轄域中如果有合取或量詞轄域中如果有合取或析析取項(xiàng)，且其中有一個(gè)是命取項(xiàng)，且其中有一個(gè)是命題題，則可將該命題移至量詞，則可將該命題移至量詞轄轄域之外域之外證明證明: : xA(x)BxA(x)B x(A(x)B)x(A(x)B) xA(x)B

15、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)量詞分配等值式量詞分配等值式設(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)xA(x) xB(xxB(x) )（2 2） x(A(x)B(x) x(A(x)B(x) xA(xxA(x) ) xB(xxB(x) )（5.55.5） 例如例如，“聯(lián)歡會(huì)上所有人既唱歌又跳舞聯(lián)歡會(huì)上所有人既唱歌又跳舞”和和“聯(lián)歡會(huì)上所聯(lián)歡會(huì)上所有人唱歌且

16、所有人跳舞有人唱歌且所有人跳舞” ” ，這兩個(gè)語(yǔ)句意義相同。故有，這兩個(gè)語(yǔ)句意義相同。故有(1)(1)式。以下兩式式。以下兩式注意注意 x(A(x)B(x) x A(x) x B(x) x(A(x)B(x)x A(x) x B(x)謂詞演算蘊(yùn)含式謂詞演算蘊(yùn)含式 xA(x)xA(x) xB(x) xB(x) x(A(x)B(x)x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) x A(x) x A(x) x B(x)x B(x)多個(gè)量詞間的次序排列等值式。多個(gè)量詞間的次序排列等值式。q 多個(gè)量詞同時(shí)出現(xiàn)時(shí),其順序是至關(guān)重要的.(1) ( , )( , )x yA x yy xA

17、x y (2) ( , )( , )x yA x yy xA x y x y P(x,y) y x P(x,y) y x P(x,y) x y P(x,y) x y P(x,y) y x P(x,y) y x P(x,y) x y P(x,y) 多個(gè)量詞間的次序排列等值式。多個(gè)量詞間的次序排列等值式。一階邏輯等值演算的三條原則一階邏輯等值演算的三條原則q 置換規(guī)則置換規(guī)則：設(shè)設(shè)(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公式是用公式B B取代取代(A)(A)中所有的中所有的A A之后的公式，若之后的公式，若A AB B，則則(A)(A)(B)(B)。 一階邏輯中的置換規(guī)則

18、與命題邏輯中的置換規(guī)則形式一階邏輯中的置換規(guī)則與命題邏輯中的置換規(guī)則形式上完全相同，只是在這里上完全相同，只是在這里A A，B B是一階邏輯公式。是一階邏輯公式。q 換名規(guī)則換名規(guī)則：設(shè)設(shè)A A為一公式，將為一公式，將A A中某量詞轄域中某中某量詞轄域中某約束變項(xiàng)約束變項(xiàng)的的所有出現(xiàn)及所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)鄳?yīng)的指導(dǎo)變?cè)某稍摿吭~轄域中改成該量詞轄域中未曾出現(xiàn)過(guò)的未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)符號(hào)，某個(gè)體變項(xiàng)符號(hào)，公式的其余部分不變，設(shè)所得公式為公式的其余部分不變，設(shè)所得公式為AA，則則AAA A。q 代替規(guī)則代替規(guī)則：設(shè)設(shè)A A為一公式，將為一公式，將A A中某個(gè)中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)自由出現(xiàn)的

19、個(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.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,zyG(x,y,z) )(2)(2) x(F(x,y)x(F(x,y) yG(x,y,zyG(x,y,z)(1)(1) x xF(F(x x,y,z,y,z) ) y

20、G(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.15.1的解答的解答(2

21、)(2) x x（F(x,F(x,y y) ) yG(x,y,zyG(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(xxB(x) ) （2 2） x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x

22、) )其中其中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(x)F(x)：x x是奇數(shù)，代替是奇數(shù)，代替A(x)A(x)；取取G(x)G(x)：x x是偶數(shù)，代替是偶數(shù)，代替B(x)B(x)。則則 x(F(x)G(x)x(F(x)G(x)為真命題，為真命題，而而 xF(x)xF(x) xG(xxG(x) )為假命題。為假命題。兩邊不等值。兩邊不等值。證明證明例例5.25.2(2)(2) x(A(x)B(

23、x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(F(x)G(x)x(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 全稱(chēng)量詞全稱(chēng)量詞“ ”對(duì)對(duì)“”“”無(wú)分配律。無(wú)分配律。q 存在量詞存在量詞“ ”對(duì)對(duì)“”“”無(wú)分配律。無(wú)分配律。例例5.35.3消去量詞消去量詞例例5.35.3 設(shè)個(gè)體域?yàn)樵O(shè)個(gè)體域?yàn)镈 Da,b,ca,b,c，將下面各公式的量詞消去：將下面

24、各公式的量詞消去： (1) (1) x(F(x)G(x)x(F(x)G(x)(2) (2) x(F(x) x(F(x) yG(yyG(y)(3) (3) x x yF(x,yyF(x,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。解答解答(1)(1) 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)(2)(2) x(F(x) x

25、(F(x) yG(yyG(y) ) xF(x)xF(x) yG(yyG(y) ) ( (公式公式5.3) 5.3) ( (F(a)F(b)F(c)(G(a)G(b)G(c) F(a)F(b)F(c)(G(a)G(b)G(c) 例例5.35.3消去量詞消去量詞(3) (3) x x yF(x,yyF(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 ,

26、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,yyF(x,y) ) yF(a,y)yF(a,y) yF(b,yyF(b,y) ) yF(c,yyF(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,

27、b)F(c,c) (F(c,a)F(c,b)F(c,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) )( (2 2, ,2 2) )y y) )( (x x, ,G GG GG GG GG G。，為：01( (3 3, ,2 2) )( (2

28、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,a) x(F(x)G(x,a) （2 2） x(F(f(x)G(x,f(x)x(F(f(x)G(x,f(x)（3 3） x x yL(x,y) yL(x,y) （4 4） y y xL(x,y)xL(x,y)例例5.45.4的解答的解答（1 1） x(F(x)G(x,a)x(F(x)G(x

29、,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(x)x(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(11)1)(0(01)1) 1 1例例5.4的解答的解答（3 3） x x yL(x,yyL(x,y) ) (L(2,2)(L(2,2)L(2,3)L(2,3

30、)(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)一步可以說(shuō)明量詞的次序不能的結(jié)果進(jìn)一步可以說(shuō)明量詞的次序不能隨意顛倒。隨意顛倒。 例例5.55.5例例5.55.5 證明下列等值式。證明下列等值式。 （1 1） x(M(x)x(M(x)F(

31、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 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(

32、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(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(

33、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 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(

34、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) 小節(jié)結(jié)束小節(jié)結(jié)束小 結(jié)q 本節(jié)介紹了謂詞公式的概念及謂詞演算的等值式與蘊(yùn)涵式，重點(diǎn)掌握謂詞演算的等值式與蘊(yùn)涵式5.2 5.2 一階邏輯前束范式一階邏輯前束范式定義定義5.25.2 設(shè)設(shè)A A為一個(gè)一階邏輯公式，若為一個(gè)一階邏輯公式，若A A具有如下形式具有如下形式Q Q1 1x

35、 x1 1Q Q2 2x x2 2 Q Qk kx xk kB B則稱(chēng)則稱(chēng)A A為為前束范式前束范式，其中，其中Q Qi i(1ik)(1ik)為為 或或 ，B B為不含量詞為不含量詞的公式。的公式。是前束范式的是前束范式的例子例子： x x y(F(x)G(y)H(x,y) y(F(x)G(y)H(x,y) x x y y z(F(x)G(y)H(z)L(x,y,z) z(F(x)G(y)H(z)L(x,y,z) 不是前束范式的例子：不是前束范式的例子： x x( (F(x)F(x) y y(G(y)H(x,y)(G(y)H(x,y) ) x x( (F(x)F(x) y y(G(y)H(x

36、,y)(G(y)H(x,y) )前束范式存在定理前束范式存在定理定理定理5.15.1 一階邏輯中的任何公式都存在與之等值的前束范式。一階邏輯中的任何公式都存在與之等值的前束范式。任何公式的前束范式都是存在的，但一般說(shuō)來(lái)，并不唯一。任何公式的前束范式都是存在的，但一般說(shuō)來(lái)，并不唯一。利用一階邏輯等值式以及三條變換規(guī)則（置換規(guī)則、換名規(guī)則、代替利用一階邏輯等值式以及三條變換規(guī)則（置換規(guī)則、換名規(guī)則、代替規(guī)則）就可以求出與公式等值的前束范式。規(guī)則）就可以求出與公式等值的前束范式。第一步：第一步：否定深入。否定深入。利用量詞轉(zhuǎn)化公式，把利用量詞轉(zhuǎn)化公式，把否定深入否定深入到指導(dǎo)變?cè)暮蟮街笇?dǎo)變?cè)暮竺?/p>

37、。面。 xA(xxA(x) ) xxA(x) A(x) xA(xxA(x) ) xxA(x)A(x)第二步：第二步：改名。改名。即利用換名規(guī)則、代入規(guī)則更換一些變?cè)拿Q(chēng)，以即利用換名規(guī)則、代入規(guī)則更換一些變?cè)拿Q(chēng)，以便消除混亂。便消除混亂。第三步：第三步：量詞前移量詞前移 利用利用 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把量詞移到全式的最前面，這樣得到前把量詞移到全式的最前面，這樣得到前束范式。束范式。 ),(),()(),()(),()()6(),()()()(),()()5()()()()()4()(

38、)()()() 3()()()()()2()()()()() 1 (yxBxyAyyxByxyxAyxyxHxyGyyxFxxGxxFxxGxxFxxGxxFxxGxxFx例求下列公式的前束范式。q 解:)()()()()()()()()()()() 1 (量詞分配量詞轉(zhuǎn)換律xGxFxxGxxFxxGxxFx)()()()()()()()()()()()()()()()()()()()()2(轄域擴(kuò)張轄域擴(kuò)張換名量詞轉(zhuǎn)換律yGxFyxyGyxFxyGyxFxxGxxFxxGxxFx )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()()

39、,()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()5(轄域擴(kuò)張轄域擴(kuò)張轄域擴(kuò)張換名代入ztHyGzxFtyxztHtyGzxFyxztHtyGzxFyxztHtyGyzxFxzxHxyGyzxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxq (6)()() ( , )()() ( , )()( ( , )( , )() () ( , )()() ( , )()( , )( , )()() ( , )()()( , )()( ( , )( , )xy

40、 A x yxy B x yy A y xB x yxy A x yxy B x yyA y xB x yxy A x yxyB x yy A y xB x y ),(),(),(),()()()()()(,(),()(),()(),()(),(),()(),()(),()()6(zuBuzAvuByxAzvuyxzuBuzAzvuBvuyxAyxyxBxyAyyxByxyxAyx換名續(xù)例例5.6 5.6 求公式的前束范式求公式的前束范式（1 1） xF(x)xF(x) x xG(G(x x) ) xF(x)xF(x) yG(yyG(y) ) ( (換名規(guī)則換名規(guī)則) ) xF(x)xF(x)

41、 yG(yyG(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)第二式第二式) ) 或者或者 xF(x)xF(x) xG(xxG(x) ) xF(x)xF(x) xG(xxG(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(xxG(x) ) xF(x)xF(

42、x) xG(xG(x x) ) (5.2)(5.2)第二式第二式) ) xF(x)xF(x) yG(yyG(y) ) ( (換名規(guī)則換名規(guī)則) ) 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)第一式第一式) ) 說(shuō)明說(shuō)明q 公式的前束范式是不唯一的。公式的前束范式是不唯一的。例例5.7 5.7 求前束范式求前束范式(1)(1) xF(xF(x x) ) xG(xxG(x) ) yF(yyF(y) ) xG(xxG(x) ) y y x(F(y)G(x)x(F(y)G(x)(2)

43、 (2) xF(xF(x x) ) xG(xxG(x) ) y yF(yF(y) ) xG(xxG(x) ) y y x(x(F(y)G(x)F(y)G(x)(3) (3) xF(xF(x x) ) xG(xxG(x) ) y yF(yF(y) ) xG(xxG(x) ) y y x(x(F(y)G(x)F(y)G(x)(4) (4) xF(xxF(x) ) y yG(yG(y) ) x x y(y(F(x)G(x)F(x)G(x)例例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

44、(x,wwG(x,w) () (換名規(guī)則換名規(guī)則) ) t t w(F(t,y)G(x,w) (5.3),(5.4) w(F(t,y)G(x,w) (5.3),(5.4) 或者或者 xF(x,xF(x,y y) yG(yG(x x,y,y) ) xF(x,t)xF(x,t) yG(w,yyG(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)又是自由出自

45、由出現(xiàn)，特別要注意那些既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)。不能混淆現(xiàn)的個(gè)體變項(xiàng)。不能混淆。例例5.8 5.8 求公式的前束范式求公式的前束范式(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(

46、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) ) G(G(x x5 5) ) ) H(xH(x1 1,x,x2 2,x,x3 3) ) ) 小節(jié)結(jié)束小節(jié)結(jié)束5.3 5.3 一階邏輯的推理理論一階邏輯的推理理論 在一階邏輯中，從前提在一階邏輯中，從前提A A1 1,A,A2 2, ,A Ak k出發(fā)推結(jié)論出發(fā)推結(jié)論B B的推理形式的推理形式結(jié)構(gòu)，依然采用如下的蘊(yùn)涵式形式結(jié)構(gòu)，依然采用如下的蘊(yùn)涵式形式A A1 1 ,A,A2 2 , , , ,A Ak k B B （5.65.6）若式（若式（5.65.6）

47、為永真式，則稱(chēng)）為永真式，則稱(chēng)推理正確推理正確，否則稱(chēng)推理不正確。，否則稱(chēng)推理不正確。q 在一階邏輯中稱(chēng)永真式的蘊(yùn)涵式為在一階邏輯中稱(chēng)永真式的蘊(yùn)涵式為推理定律推理定律，若一個(gè)推理的，若一個(gè)推理的形式結(jié)構(gòu)正是某條推理定律，則這個(gè)推理顯然是正確的。形式結(jié)構(gòu)正是某條推理定律，則這個(gè)推理顯然是正確的。q 在一階邏輯的推理中，在一階邏輯的推理中，某些前提與結(jié)論可能是受量詞限制，某些前提與結(jié)論可能是受量詞限制，為了使用命題邏輯中的為了使用命題邏輯中的等值式和推理定律等值式和推理定律，必須在推理過(guò)程必須在推理過(guò)程中有消去和添加量詞的規(guī)則中有消去和添加量詞的規(guī)則，以便使謂詞演算公式的推理過(guò)，以便使謂詞演算公式

48、的推理過(guò)程可類(lèi)似于命題演算中推理理論那樣進(jìn)行。程可類(lèi)似于命題演算中推理理論那樣進(jìn)行。推理定律的來(lái)源推理定律的來(lái)源q 命題邏輯推理定律的代換實(shí)例命題邏輯推理定律的代換實(shí)例q 由基本等值式生成的推理定律由基本等值式生成的推理定律q 推理規(guī)則推理規(guī)則量詞消去和引入規(guī)則量詞消去和引入規(guī)則命題邏輯推理定律的代換實(shí)例命題邏輯推理定律的代換實(shí)例q A (AB) 附加律附加律q (AB) A 化簡(jiǎn)律化簡(jiǎn)律q (AB)A B 假言推理假言推理q (AB)B A 拒取式拒取式q (AB)B A 析取三段論析取三段論 q (AB)(BC) (AC) 假言三段論假言三段論q (A B)(B C) (A C) 等價(jià)三段

49、論等價(jià)三段論q (AB)(CD)(AC) (BD) 構(gòu)造性二難構(gòu)造性二難 (AB)(AB)(AA) B 構(gòu)造性二難構(gòu)造性二難 (特殊形式特殊形式)q (AB)(CD)(BD) (AC) 破壞性二難破壞性二難 xF(x)xF(x) yG(yyG(y) ) xF(xxF(x) )（化簡(jiǎn)律的代換實(shí)例）化簡(jiǎn)律的代換實(shí)例） xF(xxF(x) ) xF(xxF(x) ) yG(yyG(y) ) （附加律的代換實(shí)例）附加律的代換實(shí)例）由基本等值式生成的推理定律由基本等值式生成的推理定律 xF(xxF(x) ) xF(xxF(x) ) xF(xxF(x) ) xF(xxF(x) ) xF(xxF(x) )

50、xF(x)xF(x) xF(x) xF(x) xF(xxF(x) ) 量詞推理定律量詞推理定律 xA(x)xA(x) xB(xxB(x) ) x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(A(x)B(x) x(A(x)B(x) xA(xxA(x) ) xB(xxB(x) ) q 對(duì)對(duì) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) )的討論：的討論： 若若 x(A(x)B(x)

51、x(A(x)B(x)為真，則有一個(gè)客體為真，則有一個(gè)客體c c，使得使得A(c)B(c)A(c)B(c)為真，即為真，即A(c)A(c)和和B(c)B(c)都為真，所以都為真，所以 xA(x)xA(x) xB(xxB(x) )也為真。也為真。 說(shuō)明說(shuō)明推理規(guī)則推理規(guī)則 為了構(gòu)造推理系統(tǒng)，還要給出為了構(gòu)造推理系統(tǒng)，還要給出4 4條重要的推理規(guī)則條重要的推理規(guī)則, ,即消去量詞和引入量詞的規(guī)則：即消去量詞和引入量詞的規(guī)則：1 1全稱(chēng)量詞消去規(guī)則全稱(chēng)量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UIUI規(guī)則或規(guī)則或UI)UI)2 2全稱(chēng)量詞引入規(guī)則全稱(chēng)量詞引入規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UGUG規(guī)則或規(guī)則或UG)UG)3

52、 3存在量詞引入規(guī)則存在量詞引入規(guī)則( (簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)EGEG規(guī)則或規(guī)則或EG)EG)4 4存在量詞消去規(guī)則存在量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為EIEI規(guī)則或規(guī)則或EI)EI)說(shuō)明說(shuō)明q 這四條規(guī)則只能使用在前束范式中。這四條規(guī)則只能使用在前束范式中。全稱(chēng)量詞消去規(guī)則全稱(chēng)量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UIUI規(guī)則或規(guī)則或UI)UI)含義含義：如果個(gè)體域的所有元素都具有性質(zhì)：如果個(gè)體域的所有元素都具有性質(zhì)A A，則個(gè)體域中的任一則個(gè)體域中的任一元素具有性質(zhì)元素具有性質(zhì)A A。 兩式成立的條件兩式成立的條件： (1)(1)在第一式中，取代在第一式中，取代x x的的y y應(yīng)為任意的不在應(yīng)為任意的不在A(x

53、)A(x)中約束出現(xiàn)的個(gè)中約束出現(xiàn)的個(gè)體變項(xiàng)。體變項(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) )全稱(chēng)量詞消去規(guī)則全稱(chēng)量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UIUI規(guī)則或規(guī)則或UI)UI)例如例如：個(gè)體域?yàn)閷?shí)數(shù)集合，公式：個(gè)體域?yàn)閷?shí)數(shù)集合，公式A(x)=A(x)= yF(x,yyF(

54、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(y)=A(y)= yF(y,yyF(y,y) )，即即 y(yy)y(yy)，這顯然是假命題。這顯然是假命題。原因是違背了條件原因是違背了條件(1)(1)。 若用若用z z取代取代x x，得得A(z)=A(z)= yF(z,yyF(z,y)=)= y(zy)y(zy)就不會(huì)產(chǎn)生這種就不會(huì)產(chǎn)生這種錯(cuò)誤。錯(cuò)誤。全稱(chēng)量詞引入規(guī)則全稱(chēng)量詞引入規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為UGUG規(guī)則或規(guī)則或UG)UG)該式成立的條件該式成立

55、的條件是：是： (1)(1)無(wú)論無(wú)論A(y)A(y)中自由出現(xiàn)的個(gè)體變項(xiàng)中自由出現(xiàn)的個(gè)體變項(xiàng)y y取何值，取何值，A(y)A(y)應(yīng)該均為真。應(yīng)該均為真。 (2)(2)取代自由出現(xiàn)的取代自由出現(xiàn)的y y的的x x也不能在也不能在A(y)A(y)中約束出現(xiàn)。中約束出現(xiàn)。例如例如：取個(gè)體域?yàn)閷?shí)數(shù)集，：取個(gè)體域?yàn)閷?shí)數(shù)集，F(xiàn)(x,y)F(x,y)為為xyxy，A(y)=A(y)= xF(x,yxF(x,y) )。 顯然顯然A(y)A(y)滿足條件滿足條件(1)(1)。 對(duì)對(duì)A(y)A(y)應(yīng)用應(yīng)用UGUG規(guī)則時(shí)，若取已約束出現(xiàn)的規(guī)則時(shí)，若取已約束出現(xiàn)的x x取代取代y y，會(huì)得到會(huì)得到 xA(xxA(

56、x)=)= x x x(xx)x(xx)，這是假命題。這是假命題。 產(chǎn)生這種錯(cuò)誤的原因是違背了條件產(chǎn)生這種錯(cuò)誤的原因是違背了條件(2)(2)。 若取若取z z取代取代y y，得得 zA(zzA(z)=)= z z x(xz)x(xz)為真命題。為真命題。 x xA A( (x x) )A A( (y y) )存在量詞引入規(guī)則存在量詞引入規(guī)則( (簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)EGEG規(guī)則或規(guī)則或EG) EG) 該式成立的條件該式成立的條件是：是： (1)(1)c c是特定的個(gè)體常項(xiàng)。是特定的個(gè)體常項(xiàng)。(2)(2)取代取代c c的的x x不能在不能在A(c)A(c)中出現(xiàn)過(guò)。中出現(xiàn)過(guò)。 x xA A( (x x) )

57、A A( (c c) )例如例如：個(gè)體域?yàn)閷?shí)數(shù)集，：個(gè)體域?yàn)閷?shí)數(shù)集，F(xiàn)(x,y)F(x,y)為為xyxy，取取A(5)=A(5)= xF(x,5)xF(x,5)。 顯然顯然A(5)A(5)是真命題。是真命題。 在應(yīng)用在應(yīng)用EGEG規(guī)則時(shí)，若用規(guī)則時(shí)，若用A(5)A(5)中已出現(xiàn)的中已出現(xiàn)的x x取代取代5 5，得，得 xF(x,xxF(x,x)=)= x(xx)x(xx)，這是假命題。這是假命題。 產(chǎn)生這種錯(cuò)誤的原因是違背了條件產(chǎn)生這種錯(cuò)誤的原因是違背了條件(2)(2)。 若用若用A(5)A(5)中未出現(xiàn)過(guò)的個(gè)體變項(xiàng)中未出現(xiàn)過(guò)的個(gè)體變項(xiàng)y y取代取代5 5，得，得 yA(yyA(y)=)= y

58、 y xF(xxF(xy)y)，這為真命題。這為真命題。 存在量詞消去規(guī)則存在量詞消去規(guī)則( (簡(jiǎn)記為簡(jiǎn)記為EIEI規(guī)則或規(guī)則或EI) EI) 該式成立的條件該式成立的條件是：是： (1)(1)c c是使是使A A為真的特定的個(gè)體常項(xiàng)。為真的特定的個(gè)體常項(xiàng)。 (2)(2)c c不在不在A(x)A(x)中出現(xiàn)。中出現(xiàn)。 (3)(3)若若A(x)A(x)中除自由出現(xiàn)的中除自由出現(xiàn)的x x外，還有其它自外，還有其它自由出現(xiàn)的個(gè)體變項(xiàng)，此規(guī)則不能使用。由出現(xiàn)的個(gè)體變項(xiàng)，此規(guī)則不能使用。 A A( (c c) )x xA A( (x x) )例如例如：取個(gè)體域?yàn)樽匀粩?shù)集合，：取個(gè)體域?yàn)樽匀粩?shù)集合，F(xiàn)(x

59、)F(x)為為x x是奇數(shù)，是奇數(shù)，G(x)G(x)為為x x是偶是偶數(shù)數(shù)。 xF(xxF(x) )與與 xG(xxG(x) )都是真命題，則對(duì)于某些都是真命題，則對(duì)于某些c c和和d d，可以斷定可以斷定P(c)Q(d)P(c)Q(d)必定為真，但不能斷定必定為真，但不能斷定P(c)Q(c)P(c)Q(c)是真。是真。 對(duì)對(duì) xF(xxF(x) )使用使用EIEI規(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) )使用使用EIEI規(guī)則時(shí)，取代規(guī)則時(shí)，取代x x的的c c一定是特定的個(gè)體常項(xiàng)一定是特定的

60、個(gè)體常項(xiàng)2,4,62,4,6等偶數(shù)。等偶數(shù)。定義定義5.3 5.3 自然推理系統(tǒng)定義自然推理系統(tǒng)定義1.1.字母表。同一階語(yǔ)言的字母表。字母表。同一階語(yǔ)言的字母表。2.2.合式公式。同合式公式的定義。合式公式。同合式公式的定義。3.3.推理規(guī)則：推理規(guī)則：(1)(1)前提引入規(guī)則。前提引入規(guī)則。(2)(2)結(jié)論引入規(guī)則。結(jié)論引入規(guī)則。(3)(3)置換規(guī)則。置換規(guī)則。(4)(4)假言推理規(guī)則。假言推理規(guī)則。(5)(5)附加規(guī)則。附加規(guī)則。(6)(6)化簡(jiǎn)規(guī)則?；?jiǎn)規(guī)則。(7)(7)拒取式規(guī)則。拒取式規(guī)則。(8)(8)假言三段論規(guī)則。假言三段論規(guī)則。(9)(9)析取三段論規(guī)則。析取三段論規(guī)則。(1