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

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

第2頁(yè)，共14頁(yè)，2023年，2月20日，星期一

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

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

其中c為任意個(gè)體常元

(x)A(x)A(y) A(x)對(duì)y是自由的(2)存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡(jiǎn)稱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)中有其它自由變?cè)獣r(shí)，不能應(yīng)用本規(guī)則。值得注意的是，A(y)只是新引入的暫時(shí)假設(shè)，它不是對(duì)y的一切值都是成立的。y是一個(gè)暫時(shí)的、表面上的自由變?cè)５?頁(yè)，共14頁(yè)，2023年，2月20日，星期一量詞產(chǎn)生規(guī)則：(3)存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡(jiǎn)稱EG規(guī)則)有兩種形式：A(c)(y)A(y)

其中c為特定個(gè)體常元

A(x)(y)A(y)成立充分條件：①取代c的個(gè)體變?cè)獃不在A(c)中出現(xiàn)；②A(x)對(duì)y是自由的；③若A(x)是推導(dǎo)行中的公式，且x是由使用EI引入的，那么不能用A(x)中除x外的個(gè)體變?cè)骷s束變?cè)蛘哒f(shuō)，y不得為A(x)中的個(gè)體變?cè)?4)全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡(jiǎn)稱UG規(guī)則)A(x)(y)A(y)成立條件：①前提A(x)對(duì)于x的任意取值都成立；②A(x)對(duì)y是自由的；③對(duì)于由于使用EI規(guī)則所得到的公式中原約束變?cè)芭c其在同一個(gè)原子公式的自由變?cè)?，都不能使用本?guī)則而成為指導(dǎo)變?cè)?，否則將產(chǎn)生錯(cuò)誤推理。第6頁(yè)，共14頁(yè)，2023年，2月20日，星期一二、Lp中推理實(shí)例

Lp的推理方法是Ls推理方法的擴(kuò)展，因此在Lp中利用的推理規(guī)則也是T規(guī)則、P規(guī)則和CP規(guī)則，還有已知的等價(jià)式，蘊(yùn)含式以及有關(guān)量詞的消去和產(chǎn)生規(guī)則。使用的推理方法是直接構(gòu)造法和間接證法。第7頁(yè)，共14頁(yè)，2023年，2月20日，星期一例題1證明蘇格拉底論證：所有的人都是要死的。蘇格拉底是人。所以蘇格拉底是要死的。解設(shè)H(x)：x是一個(gè)人。

M(x)：x是要死的。

s：蘇格拉底。故蘇格拉底論證可符號(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(2)(3)I第8頁(yè)，共14頁(yè)，2023年，2月20日，星期一例題2證明證明注意（3）（4）兩條次序不能顛倒。練習(xí)79頁(yè)（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頁(yè)，共14頁(yè)，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頁(yè)，共14頁(yè)，2023年，2月20日，星期一證法2本題可用CP規(guī)則原題為(x)(P(x)∨Q(x))┐(x)P(x)(x)Q(x)復(fù)習(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頁(yè)，共14頁(yè)，2023年，2月20日，星期一例題4構(gòu)造下面推理的證明：每個(gè)學(xué)術(shù)會(huì)的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。證明設(shè)P(x)：x是學(xué)術(shù)會(huì)的成員。Q(x)：x是專家。

R(x)：x是工人。S(x)：x是青年人。證明過(guò)程如下：則本題要證明：(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頁(yè)，共14頁(yè)，2023年，2月20日，星期一