第四章謂詞邏輯的推理理論

第四章謂詞邏輯的推理理論第一節(jié)謂詞邏輯的推理演算第二節(jié)謂詞邏輯的歸結(jié)推理方法第一節(jié)謂詞邏輯的推理演算推理的形式結(jié)構(gòu)判斷推理是否正確的方法重要的推理定律推理規(guī)則構(gòu)造證明附加前提證明法推理的形式結(jié)構(gòu)有兩種：

第一種

A1A2…AkB(*)

第二種

前提：A1，A2，…，Ak

結(jié)論：B其中A1,A2,…,Ak,B為一階邏輯公式.若(*)為永真式,則稱推理正確,否則稱推理不正確.判斷方法:真值表法,等值演算法,主析取范式法及構(gòu)造證明法.前3種方法采用第一種形式結(jié)構(gòu),構(gòu)造證明法采用第二種形式結(jié)構(gòu).第一節(jié)謂詞邏輯的推理演算第一節(jié)謂詞邏輯的推理演算重要的推理定律第一組命題邏輯推理定律代換實例

如xF(x)yG(y)xF(x)為化簡律代換實例.第二組由基本等值式生成

如由xA(x)xA(x)生成

xA(x)xA(x),xA(x)xA(x),…第三組

xA(x)xB(x)x(A(x)B(x))x(A(x)B(x))xA(x)xB(x)推理規(guī)則(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則(6)化簡規(guī)則(7)拒取式規(guī)則(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則第一節(jié)謂詞邏輯的推理演算第一節(jié)謂詞邏輯的推理演算推理規(guī)則(續(xù))(12)

全稱量詞消去規(guī)則（簡記為UI規(guī)則或UI）兩式成立的條件是：在第一式中，取代x的y應(yīng)為任意的不在A(x)中約束出現(xiàn)的個體變項.在第二式中，c為任意個體常項.用y或c去取代A(x)中的自由出現(xiàn)的x時，一定要在x自由出現(xiàn)的一切地方進行取代.第一節(jié)謂詞邏輯的推理演算推理規(guī)則(續(xù))(13)

全稱量詞引入規(guī)則（簡記為UG規(guī)則或UG）

該式成立的條件是：無論A(y)中自由出現(xiàn)的個體變項y取何值，A(y)應(yīng)該均為真.取代自由出現(xiàn)的y的x，也不能在A(y)中約束出現(xiàn).第一節(jié)謂詞邏輯的推理演算推理規(guī)則(續(xù))(14)

存在量詞引入規(guī)則（簡記為EG規(guī)則或EG）

該式成立的條件是：

c是使A為真的特定個體常項.取代c的x不能在A(c)中出現(xiàn)過.第一節(jié)謂詞邏輯的推理演算推理規(guī)則(續(xù))(15)

存在量詞消去規(guī)則（簡記為EI規(guī)則或EI）

該式成立的條件是：

c是使A為真的特定的個體常項.

c不在A(x)中出現(xiàn).若A(x)中除自由出現(xiàn)的x外，還有其他自由出現(xiàn)的個體變項，此規(guī)則不能使用.第一節(jié)謂詞邏輯的推理演算例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)①③假言推理注意：使用UI時，用a取代x.例2烏鴉都不是白色的.北京鴨是白色的.因此，北京鴨不是烏鴉.令F(x):x是烏鴉,G(x):x是北京鴨,

H(x):x是白色的前提：x(F(x)H(x))，x(G(x)H(x))結(jié)論：x(G(x)F(x))第一節(jié)謂詞邏輯的推理演算第一節(jié)謂詞邏輯的推理演算證明：①x(F(x)H(x))前提引入②F(y)H(y)①UI③x(G(x)H(x))前提引入④G(y)H(y)③UI⑤H(y)G(y)④置換⑥F(y)G(y)②⑤假言三段論⑦G(y)F(y)⑥置換⑧x(G(x)F(x))⑦UG第一節(jié)謂詞邏輯的推理演算例3構(gòu)造下述推理證明前提：x(F(x)G(x))，xF(x)

結(jié)論：xG(x)證明：①xF(x)前提引入②x(F(x)G(x))前提引入③F(c)①EI④F(c)G(c)②UI⑤G(c)③④假言推理⑥xG(x)⑤EG注意：必須先消存在量詞第一節(jié)謂詞邏輯的推理演算例4構(gòu)造下述推理證明前提：xF(x)xG(x)

結(jié)論：x(F(x)G(x))證明：①xF(x)xG(x)前提引入②xy(F(x)G(y))①置換③x(F(x)G(z))②UI④F(z)G(z)③UI⑤x(F(x)G(x))④UG說明:不能對xF(x)xG(x)消量詞,因為它不是前束范式.對此題不能用附加前提證明法.第一節(jié)謂詞邏輯的推理演算例5構(gòu)造下述推理證明前提：x(F(x)G(x))

結(jié)論：xF(x)xG(x)證明：①xF(x)附加前提引入②F(y)①UI③x(F(x)G(x))前提引入④F(y)G(y)③UI⑤G(y)②④假言推理⑥xG(x)⑤UG本題可以使用附加前提證明法習題P6925(2)(4)、26“數(shù)理邏輯”篇復(fù)習要點命題邏輯部分要弄清命題與陳述句之間的關(guān)系與差別。掌握并能熟練應(yīng)用6種基本的聯(lián)結(jié)詞來對復(fù)合命題

進行翻譯及判斷真值。記住16個基本的等價公式，并能熟練運用到公式

的轉(zhuǎn)換中；會利用真值表和公式的演算方法求一公式的主析

取范式和主合取范式，并能利用范式判斷兩公式

是否相等，是否為永真式、永假式、可滿足式；掌握并能熟練地應(yīng)用推理的四種證明方法?！皵?shù)理邏輯