離散數(shù)學(xué)26謂詞演算的推理理論ppt課件

1、離散數(shù)學(xué)Discrete Mathematics第第6講講 27 謂詞演算的推理實際謂詞演算的推理實際 要求：熟練掌握謂詞的推理實際與推理方法，要求：熟練掌握謂詞的推理實際與推理方法，會用謂詞的推理實際與推理方法進(jìn)展推理。會用謂詞的推理實際與推理方法進(jìn)展推理。 重點(diǎn)：運(yùn)用謂詞的推理實際與推理方法進(jìn)展重點(diǎn)：運(yùn)用謂詞的推理實際與推理方法進(jìn)展推理。推理。 難點(diǎn)：正確了解和運(yùn)用有關(guān)量詞規(guī)那么。難點(diǎn)：正確了解和運(yùn)用有關(guān)量詞規(guī)那么。 謂詞邏輯是命題邏輯的進(jìn)一步深化和開展，謂詞邏輯是命題邏輯的進(jìn)一步深化和開展，謂詞演算的推理方法，可以看作是命題演算謂詞演算的推理方法，可以看作是命題演算推理方法的擴(kuò)張。因此命

2、題邏輯的推理實際推理方法的擴(kuò)張。因此命題邏輯的推理實際在謂詞邏輯中幾乎可以完全照搬，只不過這在謂詞邏輯中幾乎可以完全照搬，只不過這時涉及的公式是謂詞邏輯的公式罷了。在謂時涉及的公式是謂詞邏輯的公式罷了。在謂詞邏輯中，某些前提和結(jié)論能夠遭到量詞的詞邏輯中，某些前提和結(jié)論能夠遭到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)絡(luò)，約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)絡(luò)，有必要消去量詞和添加量詞，因此正確了解有必要消去量詞和添加量詞，因此正確了解和運(yùn)用有關(guān)量詞規(guī)那么是謂詞邏輯推理實際和運(yùn)用有關(guān)量詞規(guī)那么是謂詞邏輯推理實際中非常重要的關(guān)鍵所在。中非常重要的關(guān)鍵所在。 下面在引見有關(guān)量詞規(guī)那么之前做些必下面在引見

3、有關(guān)量詞規(guī)那么之前做些必要預(yù)備。下面給出要預(yù)備。下面給出A(x)對對y是自在的這個概念。是自在的這個概念。其目的是，允許用其目的是，允許用y代入代入x后得到后得到A(y)，它不，它不改動原來公式改動原來公式A(x)的約束關(guān)系。的約束關(guān)系。 定義定義2.7.1 在謂詞公式在謂詞公式A(x)中，假設(shè)中，假設(shè)x自在出自在出如今量詞如今量詞(y)或或(y)的轄域，的轄域， 那么稱那么稱A(x)對于對于y是自在的。是自在的。 由定義可知，假設(shè)由定義可知，假設(shè)y在在A(x)中不是約束出中不是約束出現(xiàn)，那么現(xiàn)，那么A(x)對于對于y一定是自在的。一定是自在的。一、有關(guān)量詞消去和添加規(guī)那么一、有關(guān)量詞消去和添

4、加規(guī)那么量詞消去規(guī)那么：量詞消去規(guī)那么：(1) 全稱量詞消去規(guī)那么全稱量詞消去規(guī)那么(稱為全稱指定規(guī)那么，簡稱稱為全稱指定規(guī)那么，簡稱UI或或US規(guī)規(guī)那么那么)有兩種方式：有兩種方式：(x)A(x)A(c) 其中其中c為恣意個體常元為恣意個體常元 (x)A(x)A(y) A(x)對對y是自在的是自在的(2) 存在量詞消去規(guī)那么存在量詞消去規(guī)那么(稱為存在指定規(guī)那么，簡稱稱為存在指定規(guī)那么，簡稱EI或或ES規(guī)規(guī)那么那么)有兩種方式：有兩種方式：(x)A(x)A(c) 其中其中c為特定個體常元為特定個體常元 (x)A(x)A(y)成立充分條件是：成立充分條件是：c或或y不得在前提中或者居先推導(dǎo)公式

5、中出現(xiàn)或自在出現(xiàn)；不得在前提中或者居先推導(dǎo)公式中出現(xiàn)或自在出現(xiàn)；假設(shè)假設(shè)A(x)中有其它自在變元時，不能運(yùn)用本規(guī)那么。中有其它自在變元時，不能運(yùn)用本規(guī)那么。值得留意的是，值得留意的是，A(y)只是新引入的暫時假設(shè)，它不是對只是新引入的暫時假設(shè)，它不是對y的的一切值都是成立的。一切值都是成立的。y是一個暫時的、外表上的自在變元。是一個暫時的、外表上的自在變元。量詞產(chǎn)生規(guī)那么：量詞產(chǎn)生規(guī)那么：(3) 存在量詞產(chǎn)生規(guī)那么存在量詞產(chǎn)生規(guī)那么(稱為存在推行規(guī)那么，簡稱稱為存在推行規(guī)那么，簡稱EG規(guī)那么規(guī)那么)有兩種方式：有兩種方式：A(c)(y)A(y) 其中其中c為特定個體常元為特定個體常元 A(x)

6、(y)A(y)成立充分條件：取代成立充分條件：取代c的個體變元的個體變元y不在不在A(c)中出現(xiàn)；中出現(xiàn)；A(x)對對y 是自在的；假設(shè)是自在的；假設(shè)A(x)是推導(dǎo)行中的公式，且是推導(dǎo)行中的公式，且x是由運(yùn)是由運(yùn)用用EI引入的，那么不能用引入的，那么不能用A(x)中除中除x外的個體變元作約束變外的個體變元作約束變元，或者說，元，或者說，y不得為不得為A(x)中的個體變元。中的個體變元。(4) 全稱量詞產(chǎn)生規(guī)那么全稱量詞產(chǎn)生規(guī)那么(稱為全稱推行規(guī)那么，簡稱稱為全稱推行規(guī)那么，簡稱UG規(guī)那么規(guī)那么)A(x)(y)A(y)成立條件：前提成立條件：前提A(x)對于對于x的恣意取值都成立；的恣意取值都成

7、立；A(x)對對y是是自在的；對于由于運(yùn)用自在的；對于由于運(yùn)用EI 規(guī)那么所得到的公式中原約束變規(guī)那么所得到的公式中原約束變元及與其在同一個原子公式的自在變元，都不能運(yùn)用本規(guī)那元及與其在同一個原子公式的自在變元，都不能運(yùn)用本規(guī)那么而成為指點(diǎn)變元，否那么將產(chǎn)生錯誤推理。么而成為指點(diǎn)變元，否那么將產(chǎn)生錯誤推理。二、二、Lp中推理實例中推理實例 Lp的推理方法是的推理方法是Ls推理方法的擴(kuò)展，因此在推理方法的擴(kuò)展，因此在Lp中利用的推理規(guī)那么也是中利用的推理規(guī)那么也是T規(guī)那么、規(guī)那么、P規(guī)那規(guī)那么和么和CP規(guī)那么，還有知的等價式，蘊(yùn)含式以規(guī)那么，還有知的等價式，蘊(yùn)含式以及有關(guān)量詞的消去和產(chǎn)生規(guī)那么。

8、運(yùn)用的推及有關(guān)量詞的消去和產(chǎn)生規(guī)那么。運(yùn)用的推理方法是直接構(gòu)造法和間接證法。理方法是直接構(gòu)造法和間接證法。例題例題1 證明蘇格拉底論證：證明蘇格拉底論證： 一切的人都是要死的。一切的人都是要死的。 蘇格拉底是人。蘇格拉底是人。 所以蘇格拉底是要死的。所以蘇格拉底是要死的。解解 設(shè)設(shè) H(x)：x是一個人。是一個人。 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(

9、2)(3)I例題例題2 證明證明證明證明留意34兩條次序不能顛倒。練習(xí)79頁1題(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) 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例題例題3 證明證明 (x)(P(x)Q(x)(x)P(x)(x)Q(x

10、)用間接證法。要證用間接證法。要證S SC C，即要證，即要證S SC CT T，而，而S SC CSCSC，所以所以S SC CT T即即SCSCT T，亦就是，亦就是(SC)(SC)F F，SCSCF F。假定。假定CC為為T 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

11、) P(10) P(c)Q(c) US(9)(11) (P(c)Q(c) (P(c)Q(c) (矛盾矛盾)T(8)(10)I證法證法2 此題可用此題可用CP規(guī)那么規(guī)那么原題為原題為(x)(P(x)Q(x)(x)P(x)(x)Q(x)復(fù)習(xí)復(fù)習(xí)CPCP規(guī)那么規(guī)那么要證要證S SR RC C ，即要證，即要證S S(R(RC)C)T,T,即即S(RC)S(RC)T,T,(SR)C(SR)CT, (SR)CT, (SR)CT,(SR)T,(SR)C CT T也就是證明也就是證明(SR)(SR)C C。(1) (x)P(x) P附加前提附加前提(2) (x)P(x) T1E(3) P(c) ES(2)(

12、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)(x)Q(x) CP例題例題4 構(gòu)造下面推理的證明：構(gòu)造下面推理的證明： 每個學(xué)術(shù)會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是每個學(xué)術(shù)會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。青年專家。證明證明設(shè)設(shè) P(x)： x是學(xué)術(shù)會的成員。是學(xué)術(shù)會的成員。 Q(x)： x是專家。是專家。 R(x) ：x是工人。是工人。 S(x) ：x是青年人。是青年人。證明過程如下：證明過程如下：那么此題要證明：那么此

13、題要證明：(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(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) 數(shù)理邏輯在計算機(jī)科學(xué)中的用途有兩個：數(shù)理邏輯在計算機(jī)科學(xué)中的用途有兩個：一個是作為知識表示的手段，由于日常生活一個是作為知識表示的手段，由于日常生活中的或數(shù)學(xué)領(lǐng)域中的命題，大多能用謂詞邏中的或數(shù)學(xué)領(lǐng)域中的命題，大多能用