謂詞演算的推理理論.ppt

《謂詞演算的推理理論.ppt》由會員分享，可在線閱讀，更多相關(guān)《謂詞演算的推理理論.ppt（24頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第6講 27 謂詞演算的推理理論,要求：熟練掌握謂詞的推理理論與推理方法，會用謂詞的推理理論與推理方法進(jìn)行推理。 重點(diǎn)：應(yīng)用謂詞的推理理論與推理方法進(jìn)行推理。 難點(diǎn)：正確理解和運(yùn)用有關(guān)量詞規(guī)則。,,謂詞邏輯是命題邏輯的進(jìn)一步深化和發(fā)展，謂詞演算的推理方法，可以看作是命題演算推理方法的擴(kuò)張。因此命題邏輯的推理理論在謂詞邏輯中幾乎可以完全照搬，只不過這時(shí)涉及的公式是謂詞邏輯的公式罷了。 在謂詞邏輯中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消去量詞和添加量詞，因此正確理解和運(yùn)用有關(guān)量詞規(guī)則是謂詞邏輯推理理論中十分重要的關(guān)鍵所在。,一、有關(guān)量詞消去和添加規(guī)則 量詞

2、消去規(guī)則（證前去量詞）： (1) 全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱US規(guī)則) (x)A(x)A(c)： 其中c為論域中任意個(gè)體常元 （舉例說明）,(2) 存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡稱ES規(guī)則) (x)A(x)A(c) ： 其中c為論域中的某些特定的個(gè)體常元，它不是任意的。 c不得在前提中或者居先推導(dǎo)公式中出現(xiàn)或自由出現(xiàn)。 （舉例說明：存在一些人是男生，存在一些人是女生）,量詞產(chǎn)生規(guī)則（證后加量詞）： (3) 存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱EG規(guī)則) A(c)(y)A(y) 其中c為論域中特定個(gè)體常元,(4) 全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡稱UG

3、規(guī)則) A(c)(y)A(y) 若能證明對論域中每一個(gè)客體c斷言A(c)都成立，則全稱推廣規(guī)則可得到結(jié)論(y)A(y)成立。,二、Lp中推理實(shí)例： Lp的推理方法是Ls推理方法的擴(kuò)展，因此在Lp中利用的推理規(guī)則： （1）T規(guī)則、P規(guī)則和CP規(guī)則 （2）已知的等價(jià)式，蘊(yùn)含式 （3）有關(guān)量詞的消去和產(chǎn)生規(guī)則。 使用的推理方法是：直接構(gòu)造法和間接證法（不能用真值表）。 所有謂詞的推理，均可先忽略量詞，按命題邏輯中分析基本思路及所用方法，然后再注意證前去量詞，證后加量詞，并注意次序即可,例題1 證明蘇格拉底論證： 所有的人都是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,解 設(shè) H(x)：

4、x是一個(gè)人。 M(x)：x是要死的。 s：蘇格拉底。 故蘇格拉底論證可符號化為： (x)(H(x) M(x)) H(s)M(s),證明,(1) (x)(H(x) M(x)) P,(2) H(s)M(s) US(1),(3) H(s) P,(4) M(s) T(2)(3)I,例題2 證明,證明,,(x)(C(x)W(x)R(x))(x)(C(x)Q(x))(x)(Q(x)R(x)),(1) (x)(C(x)W(x)R(x)) P,(2) (x)(C(x)Q(x)) P,(4) C(a)W(a)R(a) US(1),(3) C(a)Q(a)

5、 ES(2),(5) C(a) T(3)I,(6) W(a)R(a) T(4)(5)I,(7) Q(a) T(3)I,(8) R(a) T(6)I,(9) Q(a)R(a) T(7)(8)I,(10) (x)(Q(x)R(x)) EG（9）,注意（3）（4）兩條次序不能顛倒。,（1）原來的作用變元相同：,若先用ES后用US，可用同一常元也可用不同常元（按需決定） ； 若先用US后用ES，必用不同常元; 若幾個(gè)ES在一起，必用不同常元 若幾個(gè)US在一起，可用相同常元也可用不同常元（按需決定）,（2）原來作用變元不同：

6、,,無論順序如何，或后，常元必不同,例題3 證明,(x)(P(x)Q(x))(x)P(x)(x)Q(x),,方法（）：用反證法（假定C為T，推出矛盾）,(1) ((x)P(x)(x)Q(x)) P(附加前提),(2) (x)P(x)(x)Q(x) T(1)E,(3) (x)P(x) T(2)I,(4) (x)Q(x) T(2)I,(5) P(c) ES(3),(6) Q(c) US(4),(7) P(c)Q(c) T(5)(6)I,(8) (P(c)Q(c)) T(7)E,(9) (x)(P(x)Q(x)) P,(10) P(c)Q(c) US(9)

7、,(11) (P(c)Q(c)) (P(c)Q(c)) (矛盾)T(8)(10)I,方法（）：用CP規(guī)則,原題可轉(zhuǎn)為：,(x)(P(x)Q(x))(x)P(x)(x)Q(x),(要證SRC ，也就是證明(SR)C。),(1) (x)P(x) P（附加前提）,(2) (x)P(x) T（1）E,(3) P(c) ES(2),(4) (x)(P(x)Q(x)) P,(5) P(c)Q(c) US(3),(6) Q(c) T(3)(5)I,(7) (x)Q(x) EG(6),(8) (x)P(x)

8、(x)Q(x) CP,例題4 構(gòu)造下面推理的證明： 每個(gè)學(xué)術(shù)會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。,證明,設(shè) P(x)： x是學(xué)術(shù)會的成員。 Q(x)： x是專家。 R(x) ：x是工人。 S(x) ：x是青年人。,證明過程如下：,則本題要證明： (x)(P(x)Q(x)R(x))，(x)(P(x)S(x))(x)(P(x)Q(x)S(x)),(1) (x)(P(x)S(x)) P,(2) P(a)S(a) ES(1),(3) P(a) T(2)I,(4) S(a) T(2)I,(5) (x)(P(x)Q

9、(x)R(x)) P,(6) P(a)Q(a)R(a) US(5),(7) Q(a)R(a) T(3)(6)I,(8) Q(a) T(7)I,(9) P(a)Q(a)S(a) T(3)(4)(8)I,(10) (x)(P(x)Q(x)S(x)) EG(9),例5 任何人違反了交通規(guī)則都要處以罰款，如果沒有罰款，就沒有人違反交通規(guī)則。,,解：S(x, y)：x違反了y（x的論域是人） (y)：y是交通規(guī)則， P(z)：z是罰款 R(x, z)：x受到z 。,則問題符號化為： ：( x)((y)(S(x,y)M(y))( z) (P(z) R(x,z))) ： ( z)P

10、(z) ( x)( y)(S(x,y) M(y)) （可改為存在量詞，并把非提前，與陳述更接近，更好理解）,由于結(jié)論為條件式，故用CP規(guī)則推理。,(1) (x)((y)(S(x,y)M(y))(z) (P(z)R(x,z))) P (2) (y)(S(b,y)M(y))(z) (P(z)R(b,z)) US(1) (3) ( z)P(z) P（附加前提） (4) ( z) P(z) T(3)E (5) P(a) US(4) (6) P(a) R(b,a) T(5)I,(7) ( z) ( P(z) R(b,z)) UG(6) (8) ( z) ( P(z) R(b

11、,z)) T(7)E (9) ( y) (S(b,y) M(y)) T(2)(8)I (10) ( y) ( S(b,y) M(y)) T(9)E (11) ( y) (S(b,y) M(y)) T(10)E (12) （ x) ( y) (S(x,y) M(y)) UG(11) ( z)P(z)(x)(y)(S(x,y) M(y))CP,,,,,例中（7） （8），（9） （10），（10） （11）都是錯(cuò)誤步驟。 其中（7） （8），（9） （10）還犯了省略步驟的錯(cuò)誤。,在推理過程中，謂詞公式只能用表所列的蘊(yùn)含式與等價(jià)式； 除表中所列的帶量詞的公式外，一般的不能在量詞后面

12、的轄域內(nèi)進(jìn)行蘊(yùn)含推證或等價(jià)變換，因此必須消除量詞后，才能對謂詞公式進(jìn)行蘊(yùn)含或等價(jià)推證； 在作了適當(dāng)?shù)耐蒲莺?，再恢?fù)約束關(guān)系，以完成帶量詞公式的邏輯推證,(1) (x)((y)(S(x,y)M(y))(z) (P(z)R(x,z))) P (2) (y)(S(b,y)M(y))(z) (P(z)R(b,z)) US(1) (3) ( z)P(z) P（附加前提） (4) ( z) P(z) T(3)E (5) P(a) US(4) (6) P(a) R(b,a) T(5)I,(7)( P(a) R(b,a)) T(6)E (8)( z) ( P(z) R(b,z)) UG(

13、7) (9)( z) ( P(z) R(b,z)) T(8)E (10) ( y) (S(b,y) M(y)) T(2)(9)I (11) ( y) (S(b,y) M(y)) T(10)I (12) (S (b, c) M(c)) US(11),(13) S(b,c) M(c) T(12)E (14) S(b,c) M(c) T(13)E (15) ( y) (S(b,y) M(y)) UG(14) (16)( x) ( y) (S(x,y) M(y)) UG(15) (17)(z)P(z)(x)(y)(S(x,y) M(y)) CP,數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的用途

14、： (1) 作為知識表示的手段，因?yàn)槿粘Ｉ钪械幕驍?shù)學(xué)領(lǐng)域中的命題，大多能用謂詞邏輯的符號表達(dá)式，便于計(jì)算機(jī)處理； (2) 研究形式推理，為計(jì)算機(jī)進(jìn)行自動推理提供方法和理論。 第二個(gè)用途過于專門和復(fù)雜，已超過本課程教學(xué)大綱的要求。但是，第一個(gè)用途確是非常重要，所以應(yīng)該掌握。,小結(jié),一、有關(guān)量詞消去和添加規(guī)則 量詞消去規(guī)則（證前去量詞）： (1) 全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱US規(guī)則) (x)A(x)A(c)： 其中c為論域中任意個(gè)體常元 (2) 存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡稱ES規(guī)則) (x)A(x)A(c) ： 其中c為論域中的某些特定的個(gè)體常元，它不是任意的

15、。 c不得在前提中或者居先推導(dǎo)公式中出現(xiàn)或自由出現(xiàn)。,量詞產(chǎn)生規(guī)則（證后加量詞）： (3) 存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱EG規(guī)則) A(c)(y)A(y) 其中c為論域中特定個(gè)體常元 (4) 全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡稱UG規(guī)則) A(c)(y)A(y) 若能證明對論域中每一個(gè)客體c斷言A(c)都成立，則全稱推廣規(guī)則可得到結(jié)論(y)A(y)成立。,二、Lp中推理實(shí)例 Lp的推理方法是Ls推理方法的擴(kuò)展，因此在Lp中利用的推理規(guī)則： （1）T規(guī)則、P規(guī)則和CP規(guī)則 （2）已知的等價(jià)式，蘊(yùn)含式 （3）有關(guān)量詞的消去和產(chǎn)生規(guī)則 使用的推理方法是：直接構(gòu)造法和間接證法（不能用真值表）。,,作業(yè)： P79 (1)c) (2)b) (3)c),