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

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

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

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

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

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

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

7、立；A(x)對(duì)對(duì)y是是自在的；對(duì)于由于運(yùn)用自在的；對(duì)于由于運(yùn)用EI 規(guī)那么所得到的公式中原約束變規(guī)那么所得到的公式中原約束變?cè)芭c其在同一個(gè)原子公式的自在變?cè)?，都不能運(yùn)用本規(guī)那元及與其在同一個(gè)原子公式的自在變?cè)?，都不能運(yùn)用本規(guī)那么而成為指點(diǎn)變?cè)?，否那么將產(chǎn)生錯(cuò)誤推理。么而成為指點(diǎn)變?cè)?，否那么將產(chǎn)生錯(cuò)誤推理。二、二、Lp中推理實(shí)例中推理實(shí)例 Lp的推理方法是的推理方法是Ls推理方法的擴(kuò)展，因此在推理方法的擴(kuò)展，因此在Lp中利用的推理規(guī)那么也是中利用的推理規(guī)那么也是T規(guī)那么、規(guī)那么、P規(guī)那規(guī)那么和么和CP規(guī)那么，還有知的等價(jià)式，蘊(yùn)含式以規(guī)那么，還有知的等價(jià)式，蘊(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是一個(gè)人。是一個(gè)人。 M(x)：x是要死的。是要死的。 s：蘇格拉底。：蘇格拉底。故蘇格拉底論證可符號(hào)化為：故蘇格拉底論證可符號(hào)化為：(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)造下面推理的證明： 每個(gè)學(xué)術(shù)會(huì)的成員都是專家并且是工人，有些成員是青年人，所以有些成員是每個(gè)學(xué)術(shù)會(huì)的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。青年專家。證明證明設(shè)設(shè) P(x)： x是學(xué)術(shù)會(huì)的成員。是學(xué)術(shù)會(huì)的成員。 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ì)算機(jī)科學(xué)中的用途有兩個(gè)：數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的用途有兩個(gè)：一個(gè)是作為知識(shí)表示的手段，由于日常生活一個(gè)是作為知識(shí)表示的手段，由于日常生活中的或數(shù)學(xué)領(lǐng)域中的命題，大多能用謂詞邏中的或數(shù)學(xué)領(lǐng)域中的命題，大多能用