謂詞演算的推理理論課件

第6講§2—7謂詞演算的推理理論

要求：熟練掌握謂詞的推理理論與推理方法，會用謂詞的推理理論與推理方法進行推理。

重點：應(yīng)用謂詞的推理理論與推理方法進行推理。

難點：正確理解和運用有關(guān)量詞規(guī)則。

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

全稱量詞消去規(guī)則(稱為全稱指定規(guī)則，簡稱US規(guī)則)(x)A(x)A(c)：其中c為論域中任意個體常元（舉例說明）(2)

存在量詞消去規(guī)則(稱為存在指定規(guī)則，簡稱ES規(guī)則)(x)A(x)A(c)：其中c為論域中的某些特定的個體常元，它不是任意的。c不得在前提中或者居先推導(dǎo)公式中出現(xiàn)或自由出現(xiàn)。（舉例說明：存在一些人是男生，存在一些人是女生）量詞產(chǎn)生規(guī)則（證后加量詞）：(3)

存在量詞產(chǎn)生規(guī)則(稱為存在推廣規(guī)則，簡稱EG規(guī)則)A(c)(y)A(y)其中c為論域中特定個體常元

(4)

全稱量詞產(chǎn)生規(guī)則(稱為全稱推廣規(guī)則，簡稱UG規(guī)則)A(c)(y)A(y)若能證明對論域中每一個客體c斷言A(c)都成立，則全稱推廣規(guī)則可得到結(jié)論(y)A(y)成立。二、Lp中推理實例：

Lp的推理方法是Ls推理方法的擴展，因此在Lp中利用的推理規(guī)則：（1）T規(guī)則、P規(guī)則和CP規(guī)則（2）已知的等價式，蘊含式（3）有關(guān)量詞的消去和產(chǎn)生規(guī)則。使用的推理方法是：直接構(gòu)造法和間接證法（不能用真值表）。

所有謂詞的推理，均可先忽略量詞，按命題邏輯中分析基本思路及所用方法，然后再注意證前去量詞，證后加量詞，并注意次序即可例題1

證明蘇格拉底論證：所有的人都是要死的。蘇格拉底是人。所以蘇格拉底是要死的。解設(shè)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例題2

證明證明(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）注意（3）（4）兩條次序不能顛倒。（1）原來的作用變元相同：若先用ES后用US，可用同一常元也可用不同常元（按需決定）； 若先用US后用ES，必用不同常元; 若幾個ES在一起，必用不同常元． 若幾個US在一起，可用相同常元也可用不同常元（按需決定）（2）原來作用變元不同： 無論順序如何，ＥＳ或ＵＳ后，常元必不同例題3

證明(x)(P(x)∨Q(x))(x)P(x)∨(x)Q(x)方法（１）：用反證法（假定┐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方法（２）：用CP規(guī)則原題可轉(zhuǎn)為：(x)(P(x)∨Q(x))┐(x)P(x)(x)Q(x)(要證SRC

，也就是證明(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例題4

構(gòu)造下面推理的證明：每個學(xué)術(shù)會的成員都是專家并且是工人，有些成員是青年人，所以有些成員是青年專家。證明設(shè)P(x)：x是學(xué)術(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)例5

任何人違反了交通規(guī)則都要處以罰款，如果沒有罰款，就沒有人違反交通規(guī)則。解：S(x,y)：x違反了y（x的論域是人）Ｍ(y)：y是交通規(guī)則，

P(z)：z是罰款

R(x,z)：x受到z。則問題符號化為：Ｈ：(

x)((y)(S(x,y)∧M(y))→(z)(P(z)∧R(x,z)))

Ｃ：┐(

z)P(z)→(x)(

y)(S(x,y)→┐

M(y))（可改為存在量詞，并把非提前，與陳述更接近，更好理解）由于結(jié)論為條件式，故用CP規(guī)則推理。(1)(x)((y)(S(x,y)∧M(y))→(z)(P(z)∧R(x,z)))P(2)(y)(S(b,y)∧M(y))→(z)(P(z)∧R(b,z))

US(1) (3)┐(

z)P(z) P（附加前提）(4)(z)┐

P(z)

T(3)E(5)┐

P(a) US(4)(6)

┐

P(a)

∨┐R(b,a)

T(5)I(7) (

z)(

┐

P(z)∨

┐

R(b,z))

UG(6)(8)

┐(z)(

P(z)∧

R(b,z))

T(7)E(9) ┐(y)(S(b,y)∧M(y))

T(2)(8)I(10)(y)(┐

S(b,y)∨

┐

M(y))

T(9)E(11)

(y)(S(b,y)→┐

M(y))

T(10)E(12)

（

x)

(y)(S(x,y)→┐

M(y))

UG(11)┐(

z)P(z)→(x)(y)(S(x,y)→┐M(y)) CP例中（7）（8），（9）（10），（10）（11）都是錯誤步驟。其中（7）（8），（9）（10）還犯了省略步驟的錯誤。在推理過程中，謂詞公式只能用表２－１所列的蘊含式與等價式；除表中所列的帶量詞的公式外，一般的不能在量詞后面的轄域內(nèi)進行蘊含推證或等價變換，因此必須消除量詞后，才能對謂詞公式進行蘊含或等價推證；在作了適當(dāng)?shù)耐蒲莺?，再恢?fù)約束關(guān)系，以完成帶量詞公式的邏輯推證．(1)(x)((y)(S(x,y)∧M(y))→(z)(P(z)∧R(x,z)))P(2)(y)(S(b,y)∧M(y))→(z)(P(z)∧R(b,z))

US(1) (3)┐(

z)P(z) P（附加前提）(4)(z)┐

P(z)

T(3)E(5)┐

P(a) US(4)(6)

┐

P(a)

∨┐R(b,a)

T(5)I(7)┐(

P(a)∧

R(b,a))

T(6)E

(8)(z)┐(

P(z)∧

R(b,z))

UG(7)(9)┐(z)(

P(z)∧

R(b,z))

T(8)E(10)

┐(y)(S(b,y)∧M(y))

T(2)(9)I(11)(y)┐(S(b,y)∧M(y))T(10)I(12)

┐(S(b,

c)∧M(c))

US(11)

(13)

┐S(b,c)∨

┐

M(c)

T(12)E(14)

S(b,c)→┐

M(c)

T(13)E(15)(

y)(S(b,y)→┐

M(y))

UG(14)(16)(

x)

(y)(S(x,y)

→┐

M(y))

UG(15)

(17)┐(z)P(z)→(x)(y)(S(x,y)→┐M(y))CP數(shù)理邏輯在計算機科學(xué)中的用途：(1)作為知識表示的手段，因為日常生活中的或數(shù)學(xué)領(lǐng)域中的命題，大多能用謂詞邏輯的符號表達(dá)式，便于計算機處理；(2)

研究形式推理，為計算機進行自動推理提供方法和理論。

第二個用途過于專門和復(fù)雜，已超過本課程教學(xué)大綱的要求。但是，第