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

《謂詞演算的推理規(guī)則.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、1.8謂詞演算的推理規(guī)則1.8.1謂詞邏輯中推理的形式結(jié)構(gòu)重要推理定律1.8.2量詞消去與引入規(guī)則UI規(guī)則、UG規(guī)則、EG規(guī)則、EI規(guī)則1A(x)對y是自由的如果在公式A(x)中，x不出現(xiàn)在量詞?y或?y的轄域之內(nèi)，則稱A(x)對y是自由的。例如：B(x)=?yP(y)?Ｑ(x)?R(z),B(x)對y是自由的C(x)=?yP(x,y)?Q(x,y),C(x)對y不是自由的2注：在將A(x)中的x代以y時，需要先觀察A(x)對y是否自由，如果不自由，不能代入。如：?yP(x,y)?Q(x,y)，

2、將x代以y得?yP(y,y)?Q(y,y)，此時原來自由的x變成約束的，故需要先將y改名。3謂詞邏輯中推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)形式1A1?A2?…?Ak?B(*)形式2前提：A1,A2,…,Ak結(jié)論：B其中A1,A2,…,Ak,B為謂詞邏輯公式.若(*)為永真式,則稱推理正確,記作A1?A2?…?Ak?B4推理定律重要推理定律第一組命題邏輯推理定律的代換實例例如?xF(x)??yG(y)??xF(x)化簡律的代換實例第二組每個謂詞邏輯基本等值式生成2個推理定律例如??xF(x)??x(?F(

3、x)),?x(?F(x))???xF(x)第三組?xA(x)??xB(x)??x(A(x)?B(x))?x(A(x)?B(x))??xA(x)??xB(x)推理定律:謂詞邏輯中永真的蘊涵式5量詞消去與引入規(guī)則UI全稱量詞消去規(guī)則(UI)成立的條件是:(1)A(x)對y必須是自由的。(2)在第二式中,c為任意個體常元.(3)用y或c去取代A(x)中的自由出現(xiàn)的x時,一定要在x自由出現(xiàn)的一切地方進行取代.6注意違反第一條：F(x,y):x>y，個體域為實數(shù)域?xA(x)=?x?yF(x,y)—真命題

4、使用UI規(guī)則，若用y取代x,得?yF(y,y)—假命題若用z取代x,得?yF(z,y)7量詞消去與引入規(guī)則EG該式成立的條件是：(1)c是使A為真的特定個體常元.(2)取代c的x不能在A(c)中出現(xiàn)過.存在量詞引入規(guī)則(EG)8注意違反第二條：F(x,y):x>y，個體域為實數(shù)域取A(5)=?xF(x,5)—真命題使用EG規(guī)則，若用x取代5,得?xA(x)=?x?xF(x,x)=?x?x(x>x)假若用y取代5,得?yA(y)=?y?xF(x,y)=?y?x(x>y)真9量詞消去與引入規(guī)則EI該

5、式成立的條件是：(1)c是使A為真的特定的個體常元.(2)c不在A(x)中出現(xiàn).(3)x在A(x)中自由出現(xiàn),除x之外沒有其他自由出現(xiàn)的個體變元存在量詞消去規(guī)則(EI)10注意違反第二條：F(x,y):x>y，個體域為實數(shù)域?xA(x)=?xF(x,5)對?xA(x)使用EI規(guī)則，若用5取代x,得A(5)=(5>5)假若用6取代x,得A(6)=(6>5)真11注意(1)個體域為自然數(shù)集合NF(x):x為奇數(shù).G(x):x為偶數(shù).?xF(x)—真命題?xG(x)—真命題對?xF(x)使用EI規(guī)則時

6、，取代x的只能是1，3，5等特定的個體常元，而不能取4，6等.對?xG(x)使用EI規(guī)則時，取代x的只能是0，2，16等特定的個體常元，而不能取3，7等.12量詞消去與引入規(guī)則UG該式成立的條件是Γ是公理和前提的合取，其中沒有x的自由出現(xiàn)。其意義：若從?？赏瞥鯝(x)，那么從Γ中也可推出?xA(x).(2)在推出A(x)前提中，x必須不是自由的；且A(x)中x不是由使用ES而引入的。(3)在居先的步驟中，如果使用US而求得之x是自由的，那么在后繼步驟中，使用ES而引入的任何新變元都沒有在A(x)

7、中自由出現(xiàn)。全稱量詞引入規(guī)則(UG)13觀察下面的推理(1)?x?yP(x,y)P,前提(2)?yP(t,y)T,(1),US(3)P(t,d)T,(2),ES(4)?xP(x,d)T,(3),UG(5)?y?xP(x,y)T,(4),EG14自然推理系統(tǒng)F自然推理系統(tǒng)F包括下述組成部分:1.字母表,同謂詞語言?的字母表2.合式公式,同?的合式公式3.推理規(guī)則(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則15自然推理系統(tǒng)F(續(xù))(6)化簡規(guī)則(7)拒取式規(guī)則(

8、8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則(12)UI規(guī)則(13)UG規(guī)則(14)EG規(guī)則(15)EI規(guī)則16例1解令F(x):x是人,G(x):x是要死的,a:蘇格拉底前提：?x(F(x)?G(x))，F(xiàn)(a)結(jié)論：G(a)證明：①F(a)前提引入②?x(F(x)?G(x))前提引入③F(a)?G(a)②UI④G(a)①③假言推理例1證明蘇格拉底三段論:“人都是要死的,蘇格拉底是人，所以蘇格拉底是要死的.”17例2例2構(gòu)造下述推理證明前提：?x(F(x