一階邏輯推理理論

離散數(shù)學(xué)

第10課一階邏輯推理理論內(nèi)容回憶一階邏輯合式公式及解釋一階邏輯等值式及前束范式上節(jié)課練習(xí)：求以下公式的前束范式﹁(xF(x,y)∨yG(x,y))xF(x,y)∧yG(x,y)xF(x,y)∧yG(x,y)xF(x,t)∧yG(s,y)x(F(x,t)∧yG(s,y))xy(F(x,t)∧G(s,y))今日內(nèi)容一階邏輯推理理論推理形式的定義量詞引入和消去規(guī)那么一階邏輯下的推理證明一階邏輯推理理論在一階邏輯中，推理的形式結(jié)構(gòu)仍為A1∧A2∧…∧Ak→B假設(shè)該式是永真式，那么稱推理正確，稱B是A1，A2，…，Ak的邏輯結(jié)論此時(shí)將該式記為A1∧A2∧…∧AkB命題邏輯中的推理規(guī)那么及在一階邏輯中的代換實(shí)例，在一階邏輯中仍然成立一階邏輯中新增加4條推理規(guī)那么消去和引入規(guī)那么:全稱量詞消去規(guī)那么全稱量詞引入規(guī)那么存在量詞引入規(guī)那么存在量詞消去規(guī)那么全稱量詞消去規(guī)那么〔簡稱UI規(guī)那么〕

這條規(guī)那么含以下兩種形式：

xA(x)A(y)①

xA(x)A(c)②

兩式成立的條件是1.x是A(x)中自由出現(xiàn)的個(gè)體變項(xiàng)；2.在①式中，y為任意的不在A(x)中約束出現(xiàn)的個(gè)體變項(xiàng)；3.在②式中，c為個(gè)體域中任意的個(gè)體常項(xiàng)。只有在滿足上述條件時(shí)，推理規(guī)那么才成立！在推理過程中①，②兩種形式可根據(jù)需要選用。例：設(shè)定義域?yàn)閷?shí)數(shù)，取F(x,y)為x＞y，A(x)=yF(x,y)，xA(x)xyF(x,y)公式xA(x)是真命題?？紤]如下推理是否正確:①xyF(x,y) 前提引入②yF(y,y)①UI規(guī)那么yF(y,y)是假命題，推理不正確出錯(cuò)的原因是違背了條件：xA(x)A(y)中，y應(yīng)為任意的不在A(x)中約束出現(xiàn)的個(gè)體變項(xiàng)。全稱量詞引入規(guī)那么〔簡稱UG規(guī)那么〕A(y)xA(x)③公式成立的條件是1.y在A(y)中自由出現(xiàn)，且y取任何值時(shí)A均為真2.取代y的x不在A(y)中約束出現(xiàn)。

例:設(shè)定義域?yàn)閷?shí)數(shù)，取F(x,y)為x>y，A(y)=xF(x,y)=x(x>y)，A對任意給定的y都是真的。如下推理是否正確:①xF(x,y)前提引入②xxF(x,x)①UG

xx(x>x)是假命題，推理出錯(cuò)。出錯(cuò)的原因是違背了條件2：取代y的x不在A(y)中約束出現(xiàn)

②zxF(x,z)①UG

√

存在量詞引入規(guī)那么〔簡稱EG規(guī)那么〕A(c)xA(x)④公式成立的條件是1.c是特定的個(gè)體常項(xiàng)；2.取代c的x不能已在A(c)中出現(xiàn)過。例1:設(shè)定義域?yàn)閷?shí)數(shù)，取F(x,y)為x＜y，A(2)=xF(x,2)=x(x<2)，〔真命題〕如下推理是否正確:①xF(x,2)前提引入②xxF(x,x)①EG假命題，推理出錯(cuò)。出錯(cuò)的原因是違背了條件2,x已在A(2)中出現(xiàn)過。存在量詞引入規(guī)那么〔簡稱EG規(guī)那么〕A(c)xA(x)④公式成立的條件是1.c是特定的個(gè)體常項(xiàng)；2.取代c的x不能已在A(c)中出現(xiàn)過。例1:設(shè)定義域?yàn)閷?shí)數(shù)，取F(x,y)為x＜y，A(2)=xF(x,2)=x(x<2)，〔真命題〕如下推理是否正確:①xF(x,2)P②yxF(x,y)EG,①√

存在量詞消去規(guī)那么〔簡稱EI規(guī)那么〕xA(x)A(c)⑤公式成立的條件是1.c是使A為真的特定的個(gè)體常項(xiàng)；2.c不曾在A(x)中出現(xiàn)過；3.A(x)中除x外沒有其他自由出現(xiàn)的個(gè)體變項(xiàng)。例:在自然數(shù)集中，設(shè)F(x)為x是奇數(shù)，G(x)是x是偶數(shù)，那么xF(x)∧xG(x)是真命題.以下推論是否正確：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化簡規(guī)那么(3)xG(x)(1)化簡規(guī)那么(4)F(a)(2)ES規(guī)那么(5)G(a)(3)ES規(guī)那么(6)F(a)∧G(a)(4)(5)合取規(guī)那么(7)x(F(x)∧G(x))(6)EG規(guī)那么例:在自然數(shù)集中，設(shè)F(x)為x是奇數(shù)，G(x)是x是偶數(shù)，那么xF(x)∧xG(x)是真命題.以下推論是否正確：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化簡規(guī)那么(3)xG(x)(1)化簡規(guī)那么(4)F(a)(2)EI規(guī)那么(5)G(a)(3)EI規(guī)那么×(6)F(a)∧G(a)(4)(5)合取規(guī)那么(7)x(F(x)∧G(x))(6)EG規(guī)那么出錯(cuò)的原因是存在量詞消去規(guī)那么xA(x)A(c)時(shí)違背了條件：c是使A為真的特定的個(gè)體常項(xiàng)例:在自然數(shù)集中，設(shè)F(x)為x是奇數(shù)，G(x)是x是偶數(shù)，那么xF(x)∧xG(x)是真命題.以下推理是否正確：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化簡規(guī)那么(3)xG(x)(1)化簡規(guī)那么(4)F(a)(2)EI(5)G(b)(3)EI(6)F(a)∧G(b)(4)(5)合取規(guī)那么(7)x(F(x)∧G(x))(6)EG 例:在自然數(shù)集中，設(shè)F(x)為x是奇數(shù)，G(x)是x是偶數(shù)，那么xF(x)∧xG(x)是真命題.以下推理是否正確：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化簡規(guī)那么(3)xG(x)(1)化簡規(guī)那么(4)F(a)(2)EI(5)G(b)(3)EI(6)F(a)∧G(b)(4)(5)合取規(guī)那么(7)x(F(x)∧G(x))(6)EG× (7)x(F(x)∧G(b))(6)EG(8)xy(F(x)∧G(y))(7)EG在應(yīng)用以上4條量詞規(guī)那么時(shí)，要特別注意??！一階邏輯推理實(shí)例命題邏輯中的推理規(guī)那么及在一階邏輯中的代換實(shí)例，在一階邏輯推理中仍然使用量詞消去和引入規(guī)那么例1:證明蘇格拉底三段論“凡人都是要死的。蘇格拉底是人.所以蘇格拉底是要死的?！泵}符號化：F〔x〕：x是人〔特性謂詞〕；G〔x〕：x是要死的；a：蘇格拉底前提：x〔F(x)→G(x)〕，F(xiàn)(a)結(jié)論：G(a)證明：〔1〕x〔F(x)→G(x)〕前提引入〔2〕F(a)→G(a)UI(1)〔3〕F(a)前提引入〔4〕G(a)(2)(3)假言推理例2:所有的有理數(shù)都是實(shí)數(shù)，有的有理數(shù)是整數(shù)。所以，有的實(shí)數(shù)是整數(shù)。請?jiān)谝浑A邏輯中證明上述推理的正確性。證明：

命題符號化：F(x)：x為有理數(shù)；G(x)：x為實(shí)數(shù)；H(x)：x為整數(shù)前提:"x(F(x)→

G(x))，$x

(

F(x)∧H(x)

)結(jié)論:$

x(G(x)∧H(x))

前提:"x(F(x)→

G(x))，$x

(

F(x)∧H(x)

)結(jié)論:$

x(G(x)∧H(x))

證明：①$x(F(x)∧H(x))前提引入②F〔c〕∧H(c)EI①③"x(F(x)→G(x))前提引入④F(c)→G(c)UI③⑤F(c)②化簡⑥G(c)④⑤假言推理⑦H(c)②化簡⑧G(c)∧H(c)⑥⑦合?、?x(G(x)∧H(x))EG⑧將證明的步驟改為：證明：①"x(F(x)→G(x))前提引入②F(c)→G(c)UI①③$x(F(x)∧H(x))前提引入④F〔c〕∧H(c)EI③⑤F(c)②化簡⑥G(c)④⑤假言推理⑦H(c)②化簡⑧G(c)∧H(c)⑥⑦合?、?x(G(x)∧H(x))EG⑧哪步存在錯(cuò)誤？例3:請?jiān)谝浑A邏輯中證明下述推理的正確性。不存在能表示出分?jǐn)?shù)的無理數(shù)，有理數(shù)都能表示成分?jǐn)?shù)，因此，有理數(shù)都不是無理數(shù)。

解：命題符號化：設(shè)F(x):x為無理數(shù)；G(x):x為有理數(shù)；H(x)：x能表示成分?jǐn)?shù)。

前提：┐?x(F(x)∧H(x)),?x(G(x)→H(x))

結(jié)論：?x(G(x)→┐F(x))

前提：x〔F(x)∧H(x)〕，x〔G(x)→H(x)〕結(jié)論：x〔G(x)→F(x)〕證明:〔1〕x〔F(x)∧H(x)〕前提引入〔2〕x〔F(x)∨H(x)〕(1)置換規(guī)那么〔3〕x〔H(x)→F(x)〕(2)置換規(guī)那么〔4〕H(y)→F(y)UI〔3〕〔5〕x〔G(x)→H(x)〕前提引入〔6〕G(y)→H(y)UI〔5〕〔7〕G(y)→F(y)(4)(6〕假言三段論〔8〕x〔G(x)→F(x)〕UG〔7〕課堂練習(xí)：前提："x(F(x)→

(

G(y)∧R(x)

))，$x

F(x)

結(jié)論：$

x(F(x)∧R(x))

證明：①$xF(x)前提引入②F〔c〕EI①③"x(F(x)→(G(y)∧R(x)))前提引入④F(c)→(G(y)∧R(c))UI③⑤G(y)∧R(c)②④假言推理