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

《離散數(shù)學(xué)-2-7 謂詞演算的推理理論》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章謂詞邏輯2-7謂詞演算的推理理論授課人：李朔Email:chn.nj.ls@gmail.com1一、謂詞演算推理規(guī)則謂詞演算的推理方法,可以看作是命題演算推理方法的擴(kuò)張。在一階邏輯中，推理的形式結(jié)構(gòu)仍為H1?H2?…?Hn?B。若該式為邏輯有效式，則稱推理正確，稱B是H1，H2，…，Hn，的邏輯結(jié)論，記H1?H2?…?Hn?B。一般的，將邏輯有效蘊(yùn)含式稱為推理定律。命題邏輯中的重言蘊(yùn)含式，在一階邏輯中的代入實(shí)例，都是一階邏輯中的推理定律。另外，每個(gè)等值式都可產(chǎn)生兩條推理定律。2一、謂詞演算推理規(guī)則謂詞演算推理規(guī)則

2、P規(guī)則：前提在推導(dǎo)過程中的任何時(shí)候都可以引入使用。T規(guī)則：在推導(dǎo)過程中，如果有一個(gè)或多個(gè)公式重言蘊(yùn)涵這公式S，則公式S可以引入推導(dǎo)之中。命題演算推理中的P規(guī)則、T規(guī)則（置換規(guī)則、合取引入規(guī)則）在謂詞推理中都是對(duì)的，都可以使用；3一、謂詞演算推理規(guī)則在謂詞推理中，某些前提與結(jié)論可受量詞限制，為了使用等價(jià)式和蘊(yùn)含式，必須在推理過程中有消去和添加的規(guī)則，使推理類似于命題演算中的推理理論。在推理過程中，除了用到命題邏輯中的推理規(guī)則外，還須用到下面4條規(guī)則。其中A?B不一定表示A→B是邏輯有效式(非永真)，而僅表示在一定條件下，

3、當(dāng)A為真時(shí)，B也為真的推理關(guān)系。全稱指定規(guī)則（簡稱US規(guī)則）全稱推廣規(guī)則（簡稱UG規(guī)則）存在量詞指定規(guī)則（簡稱ES規(guī)則）存在推廣規(guī)則（簡稱EG規(guī)則）4二、全稱指定規(guī)則1．全稱指定規(guī)則（簡稱US規(guī)則）(?x)P(x)∴P(c)這條規(guī)則可以有二種形式：?xP(x)?P(y)①?xP(x)?P(c)②在推理過程中①，②兩種形式可根據(jù)需要選用。兩式成立的條件是：（1）x為P（x）中自由出現(xiàn)的個(gè)體變?cè)?不在P(x)中受約束）（2）在①中，y為不在P（x）中約束出現(xiàn)的個(gè)體變?cè)?；?）在②中，C為任意的論域中某個(gè)客體。5二、全稱指定

4、規(guī)則*全稱指定規(guī)則在使用中，若不注意條件會(huì)犯錯(cuò)誤。例如在實(shí)數(shù)集中的二元謂詞F（x，y）：x>y，則公式?x?yF(x,y)為真命題。設(shè)P（x）=?yF(x,y),此時(shí)x在P（x）中自由出現(xiàn)，若用y取代x，則得?x(?yF(x,y))??yF(y,y),結(jié)論為“存在y，y>y”，這是假命題*出錯(cuò)原因?yàn)閥在P（x）中是約束出現(xiàn)。6三、全稱推廣規(guī)則2．全稱推廣規(guī)則（簡稱UG規(guī)則）P(x)∴(?x)P(x)P（y）??xP(x)上式成立，要求以下條件：（1）y在P（y）中自由出現(xiàn)，且y取任何值時(shí)P（y）均為真；（2）取代y的x

5、不能在P（y）中約束出現(xiàn)，否則產(chǎn)生錯(cuò)誤。7三、全稱推廣規(guī)則例在實(shí)數(shù)集中F（x，y）：x>y，取P（y）=?xF(x,y)對(duì)給定y都成立。若應(yīng)用上式時(shí)，以x取代y得?x(?x(x>x))，這是假命題*出錯(cuò)原因是違背了（2）。8四、存在量詞指定規(guī)則3．存在量詞指定規(guī)則（簡稱ES規(guī)則）(?x)P(x)∴P(c)?xP(x)?P(c)上式的成立，要求滿足以下條件：(1)c是使P（x）為真的特定個(gè)體常項(xiàng)；(2)c不曾在P（x）中出現(xiàn)；(3)P（x）中除x還有其它自由的客體變?cè)獣r(shí)，不能用此規(guī)則。9四、存在量詞指定規(guī)則例：在自然數(shù)集

6、中，設(shè)F（x）：x為奇數(shù)，G（x）：x為偶數(shù)。則?xF(x)??xG(x)為真命題。如果不注意以上條件的使用，從?xF(x)，?xG(x)會(huì)推出假命題來：1．?xF(x)P2．F（c）ES(1)3．?xG(x)P4．G（c）ES(3)5．F（c）?G(c)T(2),(4)I6．?x(F(x)?G(x))EG(5)*以上結(jié)論顯然錯(cuò)的，其原因是違背條件（1），2步與4步中的c不應(yīng)相同。10四、存在量詞指定規(guī)則又如，在實(shí)數(shù)集中，?x?y(x>y)是真命題，請(qǐng)看下面推導(dǎo)：1．?x?y(x>y)P2．?y（z>y）US(1)3．

7、z>cES(2)4．?x(x>c)UG(3)而?x(x>c)是假命題。*結(jié)論是錯(cuò)的，其原因是違背了（3），對(duì)2使用ES規(guī)則時(shí)，z為自由出現(xiàn)的個(gè)體變項(xiàng)。11五、存在推廣規(guī)則4．存在推廣規(guī)則（簡稱EG規(guī)則）P(c)∴(?x)P(x)P（c）??xP(x)上式成立，要求以下條件：（1）c為特定的個(gè)體常項(xiàng)；（2）取代c的x不能已在P（c）中出現(xiàn)過。12五、存在推廣規(guī)則例在實(shí)數(shù)集中，取F（x，y）：x>y，并取P(3)=?xF(x,3),P(3)為真命題。在使用上式，若用x取代3，則得到?xF(x,x)這是假命題*其原因是違背了

8、（2）13六、例題例：找出下述推導(dǎo)的錯(cuò)誤原因(a)(1)(?x)A(x)?S(x)P(2)A(x)?S(x)US(1)錯(cuò)：(?x)P(x)使用US規(guī)則時(shí)，P(x)是整個(gè)公式，上述公式中A(x)?S(x)才是整個(gè)公式。正確：（1）(?x)A(x)?S(x)P（2）(?x)A(x)?S(y)T(1)E(換名規(guī)則)(3)A(x)?S(y