1、1,第5講 謂詞演算的推理理論,推理的形式結(jié)構(gòu) 重要的推理定律 推理規(guī)則 構(gòu)造證明 附加前提證明法,2,推理,推理的形式結(jié)構(gòu)有兩種： 第一種 A1A2AkB (*) 第二種 前提：A1，A2，Ak 結(jié)論： B 其中 A1,A2,Ak,B為一階邏輯公式. 若(*)為永真式, 則稱推理正確, 否則稱推理不正確. 判斷方法: 真值表法, 等值演算法, 主析取范式法及構(gòu)造證明法. 前3種方法采用第一種形式結(jié)構(gòu), 構(gòu)造證明法采用第二種形式結(jié)構(gòu).,3,重要的推理定律,第一組 命題邏輯推理定律代換實例 如 xF(x)yG(y)xF(x)為化簡律代換實例. xF(x)yG(y)的代換實例為pq 化簡律: (p

2、q) p,重要的推理定律 A (AB) 附加律 (AB) A 化簡律 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段論 (AB)(BC) (AC) 假言三段論 (AB)(BC) (AC) 等價三段 (AB)(CD)(AC) (BD) 構(gòu)造性二難,4,推理定律重言蘊涵式,5,第二組 由基本等值式生成 如 由 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),6,推理規(guī)則,(1)前提引入規(guī)則 (2)結(jié)論引入規(guī)則 (3)置換規(guī)則 (4)假言推理規(guī)則 (5)

3、附加規(guī)則 (6)化簡規(guī)則 (7)拒取式規(guī)則 (8)假言三段論規(guī)則 (9)析取三段論規(guī)則 (10)構(gòu)造性二難推理規(guī)則 (11)合取引入規(guī)則,7,推理規(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)的一切地方進行取代.,8/51,例 下面推理是否正確？,設(shè)前提為xyF（x，y）， （1） xyF（x，y） 前提引入 （2） y F（y，y） 全稱量詞消去,解 推理并不正確。 如果給定解釋I：個體域為實

4、數(shù)集， F（x，y）：xy。 則 xyF（x，y）意為 “對于每個實數(shù)x，均存在著比之更小的實數(shù)y”， 這是一個真命題。 而yF（y，y）意為 “存在著比自己小的實數(shù)”，是假命題。 之所以出現(xiàn)這樣的錯誤,是因為yF（x，y） 中有1個自由變 元x, 而y F（y，y）中無自由變元。,9,推理規(guī)則(續(xù)),(13) 全稱量詞引入規(guī)則（簡記為UG規(guī)則或UG） 該式成立的條件是： 無論A(y)中自由出現(xiàn)的個體變項y取何值，A(y) 應(yīng)該均為真. 取代自由出現(xiàn)的y的x，也不能在A(y)中約束出 現(xiàn).,10,推理規(guī)則(續(xù)),(14) 存在量詞引入規(guī)則（簡記為EG規(guī)則或EG） 該式成立的條件是： c是使A為

5、真的特定個體常項. 取代c的x不能在A(c)中出現(xiàn)過.,11,推理規(guī)則(續(xù)),(15) 存在量詞消去規(guī)則（簡記為EI規(guī)則或EI） 該式成立的條件是： c是使A為真的特定的個體常項. c不在A(x)中出現(xiàn). 若A(x)中除自由出現(xiàn)的x外，還有其他自由出現(xiàn) 的個體變項，此規(guī)則不能使用.,12,例如，設(shè)()()和()()都真， 則對于某些和某些，可以斷定()()為真，但卻不能斷定()()為真或()()為真。,例 考察yF（x，y） 存在量詞消去能不能得到下式: F（x，c）,F（x，c）表示對常元c與任意變元x成立, 錯誤在于: c可能與x有關(guān)的.,13/51,例 下面推理是否正確？,設(shè)前提為xyF

6、（x，y）， （1） xyF（x，y） 前提引入 （2） yF（t，y） 全稱量詞消去 （3） F（t，c） 存在量詞消去 （4） xF（x，c） 全稱量詞引入 （5） yxF（x，y） 存在量詞引入,解： 推理并不正確。 如果給定解釋I：個體域為實數(shù)集，F(xiàn)(x,y)：xy。 則 xyF（x，y）為真， 而y xF（x，y）意為“存在著最小實數(shù)”， 是假命題，故知推理不正確。 之所以出現(xiàn)這樣的錯誤，是在第（3）步中， yF（t，y ）非閉式（含有自由變元t)。,14,構(gòu)造推理證明,例1 證明蘇格拉底三段論: “人都是要死的, 蘇格拉 底是人，所以蘇格拉底是要死的.” 令 F(x): x是人,

7、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 .,15,構(gòu)造推理證明(續(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),16,前提：x(F(x)H(x)，x(G(x)H(x)結(jié) 論：x(G(x)F(x),證明： x(F(x)H(x)

8、前提引入 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,17,構(gòu)造推理證明(續(xù)),例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 注意：必須先消存在量詞,18,構(gòu)造推理證明(續(xù)),例4 構(gòu)造下述推理證明 前提：xF(x)xG(x) 結(jié)論：x(F(x)G(x) 證明： xF(x)xG(x

9、) 前提引入 xy(F(x)G(y) 置換 x(F(x)G(z) UI F(z)G(z) UI x(F(x)G(x) UG,19/51,例 在自然推理系統(tǒng)中構(gòu)造下面推理的證明 前提： xP(x)xQ(x) 結(jié)論： x(P(x)Q(x),證明: xP(x)xQ(x) 前提引入 xP(x) 前提引入? P(a)xQ(x) 去存在量詞(1) ? P(a) 去全稱量詞(2) xQ(x) (3)(4),(2)并非是結(jié)論的前件 (3)錯誤使用規(guī)則，(1)并非前束范式,20,構(gòu)造推理證明(續(xù)),例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 本題可以使用附加前提證明法,21/51,解： x(P(x) Q(x) x P(x) (3) P(e) (4) P(e) Q(e) (5) Q(e) (3)(4) (6) x Q(x),例 (