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

《離散數(shù)學(xué)26 謂詞演算的推理理論》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、離散數(shù)學(xué)DiscreteMathematics第6講§2—7謂詞演算的推理理論要求：熟練掌握謂詞的推理理論與推理方法，會(huì)用謂詞的推理理論與推理方法進(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ī)則是謂詞邏輯推理

2、理論中十分重要的關(guān)鍵所在。下面在介紹有關(guān)量詞規(guī)則之前做些必要準(zhǔn)備。下面給出A(x)對y是自由的這個(gè)概念。其目的是，允許用y代入x后得到A(y)，它不改變原來公式A(x)的約束關(guān)系。定義2.7.1在謂詞公式A(x)中，若x自由出現(xiàn)在量詞(?y)或(?y)的轄域，則稱A(x)對于y是自由的。由定義可知，若y在A(x)中不是約束出現(xiàn)，則A(x)對于y一定是自由的。一、有關(guān)量詞消去和添加規(guī)則量詞消去規(guī)則：(1)全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱UI或US規(guī)則)有兩種形式：(?x)A(x)?A(c)其中c為任意個(gè)體常元(?x)A(x)?A(y)A(x)對y是自由的(2

3、)存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡稱EI或ES規(guī)則)有兩種形式：(?x)A(x)?A(c)其中c為特定個(gè)體常元(?x)A(x)?A(y)成立充分條件是：①c或y不得在前提中或者居先推導(dǎo)公式中出現(xiàn)或自由出現(xiàn)；②若A(x)中有其它自由變元時(shí)，不能應(yīng)用本規(guī)則。值得注意的是，A(y)只是新引入的暫時(shí)假設(shè)，它不是對y的一切值都是成立的。y是一個(gè)暫時(shí)的、表面上的自由變元。量詞產(chǎn)生規(guī)則：(3)存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱EG規(guī)則)有兩種形式：A(c)?(?y)A(y)其中c為特定個(gè)體常元A(x)?(?y)A(y)成立充分條件：①取代c的個(gè)體變元y不在A(c)中

4、出現(xiàn)；②A(x)對y是自由的；③若A(x)是推導(dǎo)行中的公式，且x是由使用EI引入的，那么不能用A(x)中除x外的個(gè)體變元作約束變元，或者說，y不得為A(x)中的個(gè)體變元。(4)全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡稱UG規(guī)則)A(x)?(?y)A(y)成立條件：①前提A(x)對于x的任意取值都成立；②A(x)對y是自由的；③對于由于使用EI規(guī)則所得到的公式中原約束變元及與其在同一個(gè)原子公式的自由變元，都不能使用本規(guī)則而成為指導(dǎo)變元，否則將產(chǎn)生錯(cuò)誤推理。二、Lp中推理實(shí)例Lp的推理方法是Ls推理方法的擴(kuò)展，因此在Lp中利用的推理規(guī)則也是T規(guī)則、P規(guī)則和CP規(guī)則，

5、還有已知的等價(jià)式，蘊(yùn)含式以及有關(guān)量詞的消去和產(chǎn)生規(guī)則。使用的推理方法是直接構(gòu)造法和間接證法。例題1證明蘇格拉底論證：所有的人都是要死的。蘇格拉底是人。所以蘇格拉底是要死的。解設(shè)H(x)：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證明證明注意（3）（4）兩條次序不能顛倒。練習(xí)79頁（1）題(?x)(C(x)→W(x)∧R(x))∧(?x)(C(x)∧Q(x))

6、?(?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)用間接證法。要證S?C，即要證S?C?T，而S?C?┐S∨C，所以S?C?T即┐S∨C?T，亦就是┐(┐

7、S∨C)?F，S∧┐C?F。假定┐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)(11)┐(P(c)∨Q(c))∧(P(c)∨Q(c))(矛盾)T(8)(10)I證法2本題可用CP規(guī)則原題為(?x)(P(x

8、)∨Q(x