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

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

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

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

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

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

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

8、運用的推及有關量詞的消去和產生規那么。運用的推理方法是直接構造法和間接證法。理方法是直接構造法和間接證法。例題例題1 證明蘇格拉底論證：證明蘇格拉底論證： 一切的人都是要死的。一切的人都是要死的。 蘇格拉底是人。蘇格拉底是人。 所以蘇格拉底是要死的。所以蘇格拉底是要死的。解解 設設 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兩條次序不能顛倒。練習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規那么規那么原題為原題為(x)(P(x)Q(x)(x)P(x)(x)Q(x)復習復習CPCP規那么規那么要證要證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 構造下面推理的證明：構造下面推理的證明： 每個學術會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是每個學術會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。青年專家。證明證明設設 P(x)： x是學術會的成員。是學術會的成員。 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) 數理邏輯在計算機科學中的用途有兩個：數理邏輯在計算機科學中的用途有兩個：一個是作為知識表示的手段，由于日常生活一個是作為知識表示的手段，由于日常生活中的或數學領域中的命題，大多能用謂詞邏中的或數學領域中的命題，大多能用