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

離散數(shù)學謂詞演算的推理理論第1頁，共14頁，2023年，2月20日，星期一第6講§2—7謂詞演算的推理理論要求：熟練掌握謂詞的推理理論與推理方法，會用謂詞的推理理論與推理方法進行推理。重點：應用謂詞的推理理論與推理方法進行推理。難點：正確理解和運用有關量詞規(guī)則。

第2頁，共14頁，2023年，2月20日，星期一

謂詞邏輯是命題邏輯的進一步深化和發(fā)展，謂詞演算的推理方法，可以看作是命題演算推理方法的擴張。因此命題邏輯的推理理論在謂詞邏輯中幾乎可以完全照搬，只不過這時涉及的公式是謂詞邏輯的公式罷了。在謂詞邏輯中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要消去量詞和添加量詞，因此正確理解和運用有關量詞規(guī)則是謂詞邏輯推理理論中十分重要的關鍵所在。第3頁，共14頁，2023年，2月20日，星期一

下面在介紹有關量詞規(guī)則之前做些必要準備。下面給出A(x)對y是自由的這個概念。其目的是，允許用y代入x后得到A(y)，它不改變原來公式A(x)的約束關系。定義2.7.1在謂詞公式A(x)中，若x自由出現(xiàn)在量詞(y)或(y)的轄域，則稱A(x)對于y是自由的。由定義可知，若y在A(x)中不是約束出現(xiàn)，則A(x)對于y一定是自由的。第4頁，共14頁，2023年，2月20日，星期一一、有關量詞消去和添加規(guī)則量詞消去規(guī)則：(1)全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱UI或US規(guī)則)有兩種形式：(x)A(x)A(c)

其中c為任意個體常元

(x)A(x)A(y) A(x)對y是自由的(2)存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡稱EI或ES規(guī)則)有兩種形式：(x)A(x)A(c)其中c為特定個體常元

(x)A(x)A(y)成立充分條件是：①c或y不得在前提中或者居先推導公式中出現(xiàn)或自由出現(xiàn)；②若A(x)中有其它自由變元時，不能應用本規(guī)則。值得注意的是，A(y)只是新引入的暫時假設，它不是對y的一切值都是成立的。y是一個暫時的、表面上的自由變元。第5頁，共14頁，2023年，2月20日，星期一量詞產(chǎn)生規(guī)則：(3)存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱EG規(guī)則)有兩種形式：A(c)(y)A(y)

其中c為特定個體常元

A(x)(y)A(y)成立充分條件：①取代c的個體變元y不在A(c)中出現(xiàn)；②A(x)對y是自由的；③若A(x)是推導行中的公式，且x是由使用EI引入的，那么不能用A(x)中除x外的個體變元作約束變元，或者說，y不得為A(x)中的個體變元。(4)全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡稱UG規(guī)則)A(x)(y)A(y)成立條件：①前提A(x)對于x的任意取值都成立；②A(x)對y是自由的；③對于由于使用EI規(guī)則所得到的公式中原約束變元及與其在同一個原子公式的自由變元，都不能使用本規(guī)則而成為指導變元，否則將產(chǎn)生錯誤推理。第6頁，共14頁，2023年，2月20日，星期一二、Lp中推理實例

Lp的推理方法是Ls推理方法的擴展，因此在Lp中利用的推理規(guī)則也是T規(guī)則、P規(guī)則和CP規(guī)則，還有已知的等價式，蘊含式以及有關量詞的消去和產(chǎn)生規(guī)則。使用的推理方法是直接構(gòu)造法和間接證法。第7頁，共14頁，2023年，2月20日，星期一例題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(2)(3)I第8頁，共14頁，2023年，2月20日，星期一例題2證明證明注意（3）（4）兩條次序不能顛倒。練習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第9頁，共14頁，2023年，2月20日，星期一例題3證明(x)(P(x)∨Q(x))(x)P(x)∨(x)Q(x)用間接證法。要證SC，即要證SCT，而SC┐S∨C，所以SCT即┐S∨CT，亦就是┐(┐S∨C)F，S∧┐CF。假定┐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第10頁，共14頁，2023年，2月20日，星期一證法2本題可用CP規(guī)則原題為(x)(P(x)∨Q(x))┐(x)P(x)(x)Q(x)復習CP規(guī)則要證SRC

，即要證S(RC)T,即┐S∨(┐R∨C)T,(┐S∨┐R)∨CT,┐(S∧R)∨CT,(S∧R)CT也就是證明(S∧R)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)(x)Q(x)CP第11頁，共14頁，2023年，2月20日，星期一例題4構(gòu)造下面推理的證明：每個學術(shù)會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。證明設P(x)：x是學術(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(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)第12頁，共14頁，2023年，2月20日，星期一