1.8謂詞演算的推理規(guī)則

《1.8謂詞演算的推理規(guī)則》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、離散數(shù)學(xué)DiscreteMathematics數(shù)理邏輯張曉西北工業(yè)大學(xué)計算機(jī)學(xué)院zhangxiao@nwpu.edu.cn2011-1-101.8.1“A(x)對y是自由的”可以這樣吧考察以下謂詞公式:x替換為y嗎？?yP(y)∨Q(x)∨R(x)?yP(y)∨Q(y)∨R(x)?yP(x,y)∨Q(x,y)?yP(y,y)∨Q(y,y)?yP(y)∨Q(x,y)?yP(y)∨Q(y,y)2011-1-10離散數(shù)學(xué)2術(shù)語“A(x)對y是自由的”:如果公式A(x)中,x不出現(xiàn)在量詞?y或?y的轄域之內(nèi),則稱A(x)對y是自由的。上面的例子中，第二個式子

2、中的x是對y不自由的。不自由變量，不能進(jìn)行代入。想替換x為y時，可以替換與y沒有關(guān)系（自由）的x，否則不能替換2011-1-10離散數(shù)學(xué)3(2)式如果有必要代入y,則應(yīng)先將式中的約束變元y改名,例如,把(2)式改名為:?zP(x,z)∨Q(x,y)然后代入得?zP(y,z)∨Q(y,y)2011-1-10離散數(shù)學(xué)41.8.2謂詞演算中的推理規(guī)則-命題演算中所有推理規(guī)則都是謂詞演算中的推理規(guī)則;-謂詞演算中的所有永真蘊(yùn)含式,恒等式和代入規(guī)則也都可作為推理規(guī)則。2011-1-10離散數(shù)學(xué)5(1)全稱指定規(guī)則(全稱特定化規(guī)則/全稱量詞消去規(guī)則)(Unive

3、rsalSpecification)簡記為US?xA(x)∴A(y)應(yīng)用US規(guī)則的條件是:A(x)對于y必須是自由的。設(shè)則A(x)=?y(x>y)?xA(x)=?x?y(x>y),x,y的個體域為R，是一真命題.若應(yīng)用US得?y(y>y)，則是錯誤的。正確的做法是換成?y(z>y)(z∈R)這一規(guī)則也可寫為:?xA(x)推得A(x)或?xA(x)?A(x).它的意義是,全稱量詞可以刪除。2011-1-10離散數(shù)學(xué)7(2)存在指定規(guī)則(存在特定規(guī)則/存在量詞消去規(guī)則)(ExistentialSpecification)簡記為ES。?xA(x)∴A(y)

4、含義:如果已證明?xA(x),那么我們可以假設(shè)某一確定的個體y使A(y)是真,這里y只是一個表面的自由變元。應(yīng)用ES規(guī)則的條件應(yīng)用ES規(guī)則的條件:(1)y(說c更好些)是使A為真的特定的個體常項。(2)y不在A(x)中出現(xiàn)。（3）y不是前提和居先推導(dǎo)步驟中的（表面）自由變元(3)若A(x)中還有其它自由出現(xiàn)的個體變項，此規(guī)則不能使用。2011-1-10離散數(shù)學(xué)9(3)存在推廣規(guī)則（存在一般化規(guī)則/存在量詞引入規(guī)則）(ExistentialGeneralization)簡記為EG。A(y)∴?xA(x)應(yīng)用這一規(guī)則的條件是:A(y)對x是自由的（x最好

5、在A(y)中沒有出現(xiàn)過）。這一規(guī)則可寫成:A(y)??xA(x)(4)全稱推廣規(guī)則（全稱一般化規(guī)則/全稱量詞引入規(guī)則）(UniversalGeneralization)簡記為UG。A(y)∴?xA(x)（1）無論A(y)中自由出現(xiàn)的個體變項y取何值，A(y)應(yīng)該均為真。(1)y在A(y)中自由出現(xiàn)，且y取任何值時A均為真。（2）y不能是居先推導(dǎo)步驟中使用ES引入的。（3(2)x）取代自由出現(xiàn)的不在A(y)中約束出現(xiàn)y的x也不能在A(y)中約束出現(xiàn)。觀察下述推理過程:(1)?x?yP(x,y)P,前提(2)?yP(c,y)T,(1),US(3)P(c,

6、d)T,(2),ES(4)?xP(x,d)T,(3),UG(5)?y?xP(x,y)T,(4),EG第(4)步是錯誤的：-P(c,d)無論c取何值，P(c,d)都為真？不是均為真!-P(c,d)中的d是使用ES引入的新變元，且自由出現(xiàn)!2011-1-10離散數(shù)學(xué)12?x?yP(x,y)??y?xP(x,y)而這一式前面已指明它是不成立的。特別要注意,使用ES而產(chǎn)生的自由變元不能保留在結(jié)論中,因它是暫時的假設(shè),在推導(dǎo)結(jié)束之前必須使用EG使之成為約束變元。2011-1-10離散數(shù)學(xué)13推理規(guī)則的正確使用(1)例設(shè)實數(shù)集中，語句“不存在最大的實數(shù)”可符號化

7、為：(?x)(?y)G(x,y)。其中：G(x,y)：y>x。推導(dǎo)1：（1）(?x)(?y)G(x,y)P（2）(?y)G(y,y)US,(1)分析注意：：推導(dǎo)使用1是錯誤的。正確的推導(dǎo)如下：US規(guī)則來消去量詞時，若選用變元（y取代1）(x?，則要求x)(?y)G(x,y)在原公式中x不能出現(xiàn)P在量詞（2(）?y)(?或y)G(z,y)(?y)的轄域之內(nèi)。US,(1)2011-1-10離散數(shù)學(xué)14推理規(guī)則的正確使用（2）推導(dǎo)2：（1）(?x)(?y)G(x,y)P（2）(?y)G(z,y)US,(1)（3）G(z,c)ES,(2)分析：推導(dǎo)2是錯誤的

8、。正確的推導(dǎo)如下：注意：使用ES規(guī)則來消去量詞時，若還（1）(?x)(?y)G(x,y)P有其它自由變元時，