《離散數(shù)學(xué)課件》謂詞演算的推理理論

1、1,第5講 謂詞演算的推理理論,推理的形式結(jié)構(gòu)重要的推理定律推理規(guī)則構(gòu)造證明附加前提證明法,2,推理,推理的形式結(jié)構(gòu)有兩種： 第一種 A1?A2?…?Ak?B (*) 第二種 前提：A1，A2，…，Ak 結(jié)論： B其中 A1,A2,…,Ak,B為一階邏輯公式. 若(*)為永真式, 則稱推理正確, 否則稱推理不正確.判斷方法: 真值表法,

2、 等值演算法, 主析取范式法及構(gòu)造證明法. 前3種方法采用第一種形式結(jié)構(gòu), 構(gòu)造證明法采用第二種形式結(jié)構(gòu).,3,重要的推理定律,第一組 命題邏輯推理定律代換實(shí)例 如 ?xF(x)??yG(y)??xF(x)為化簡律代換實(shí)例. ?xF(x)??yG(y)的代換實(shí)例為p?q 化簡律: (pÙq) Þ p,重要的推理定律 A Þ (AÚB)

3、 附加律 (AÙB) Þ A 化簡律 (A®B)ÙA Þ B 假言推理 (A®B)ÙØB Þ ØA

4、 拒取式 (AÚB)ÙØB Þ A 析取三段論 (A®B)Ù(B®C) Þ (A®C) 假言三段論 (A«B)Ù(B«C) Þ (A«C)

5、 等價(jià)三段 (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 構(gòu)造性二難,4,推理定律——重言蘊(yùn)涵式,5,第二組 由基本等值式生成 如 由 ??xA(x)??x?A(x) 生成 ??xA(x)??x?A(x), ?x?A(x)???xA(x), …第三組 ?xA(x)??xB(x)??x(A(x)?B

6、(x)) ?x(A(x)?B(x))??xA(x)??xB(x),6,推理規(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ī)則,7,推理規(guī)則(續(xù)),(12) 全稱量詞消去規(guī)則（簡記為UI規(guī)則或U

7、I）兩式成立的條件是： 在第一式中，取代x的y應(yīng)為任意的不在A(x)中約束出現(xiàn)的個(gè)體變項(xiàng). 在第二式中，c為任意個(gè)體常項(xiàng). 用y或c去取代A(x)中的自由出現(xiàn)的x時(shí)，一定要在x自由出現(xiàn)的一切地方進(jìn)行取代.,,8/51,例 下面推理是否正確？,設(shè)前提為?x?yF（x，y）， （1） ?x?yF（x，y） 前提引入 （2） ?y F（y，y）

8、 全稱量詞消去,解 推理并不正確。 如果給定解釋I：個(gè)體域?yàn)閷?shí)數(shù)集，F(xiàn)（x，y）：x＞y。 則 ?x?yF（x，y）意為 “對于每個(gè)實(shí)數(shù)x，均存在著比之更小的實(shí)數(shù)y”， 這是一個(gè)真命題。 而?yF（y，y）意為 “存在著比自己小的實(shí)數(shù)”，是假命題。 之所以出現(xiàn)這樣的錯(cuò)誤,是因?yàn)?yF（x，y） 中有1個(gè)自由變 元x, 而?y F（y，y）中無自由變元。

9、,9,推理規(guī)則(續(xù)),(13) 全稱量詞引入規(guī)則（簡記為UG規(guī)則或UG） 該式成立的條件是： 無論A(y)中自由出現(xiàn)的個(gè)體變項(xiàng)y取何值，A(y)應(yīng)該均為真. 取代自由出現(xiàn)的y的x，也不能在A(y)中約束出現(xiàn).,,10,推理規(guī)則(續(xù)),(14) 存在量詞引入規(guī)則（簡記為EG規(guī)則或EG） 該式成立的條件是： c是使A為真的特定個(gè)體常項(xiàng).

10、 取代c的x不能在A(c)中出現(xiàn)過.,,11,推理規(guī)則(續(xù)),(15) 存在量詞消去規(guī)則（簡記為EI規(guī)則或EI） 該式成立的條件是： c是使A為真的特定的個(gè)體常項(xiàng). c不在A(x)中出現(xiàn). 若A(x)中除自由出現(xiàn)的x外，還有其他自由出現(xiàn)的個(gè)體變項(xiàng)，此規(guī)則不能使用.,,12,例如，設(shè)(?ｘ)Ｐ(ｘ)和(?ｘ)Ｑ(ｘ)都真， 則對于某些ｃ和某些ｄ，可以斷定Ｐ(ｃ)∧Ｑ(ｄ)為真，但卻不

11、能斷定Ｐ(ｃ)∧Ｑ(ｃ)為真或Ｐ(ｄ)∧Ｑ(ｄ)為真。,例 考察?yF（x，y） 存在量詞消去能不能得到下式: F（x，c）,?,F（x，c）表示對常元c與任意變元x成立, 錯(cuò)誤在于: c可能與x有關(guān)的.,13/51,例 下面推理是否正確？,設(shè)前提為?x?yF（x，y），（1） ?x?yF（x，y） 前提引入（2） ?yF（t，y）

12、 全稱量詞消去（3） F（t，c） 存在量詞消去（4） ?xF（x，c） 全稱量詞引入（5） ?y?xF（x，y） 存在量詞引入,解： 推理并不正確。 如果給定解釋I：個(gè)體域?yàn)閷?shí)數(shù)集，F(xiàn)(x,y)：x＞y。 則 ? x?yF（x，y）為真，

13、 而?y ?xF（x，y）意為“存在著最小實(shí)數(shù)”， 是假命題，故知推理不正確。 之所以出現(xiàn)這樣的錯(cuò)誤，是在第（3）步中， ?yF（t，y ）非閉式（含有自由變元t)。,14,構(gòu)造推理證明,例1 證明蘇格拉底三段論: “人都是要死的, 蘇格拉底是人，所以蘇格拉底是要死的.” 令 F(x): x是人, G(x): x是要死的, a: 蘇格拉底 前提：?x(F(x)?G(x))，F(xiàn)(

14、a) 結(jié)論：G(a) 證明：① F(a) 前提引入 ② ?x(F(x)?G(x)) 前提引入 ③ F(a)?G(a) ②UI ④ G(a) ①③假言推理注意：使用UI時(shí)，用a取代x .,1

15、5,構(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)),證明： ①

16、?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)??

17、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

18、(c) ①EI ④ F(c)?G(c) ②UI ⑤ G(c) ③④假言推理 ⑥ ?xG(x) ⑤EG注意：必須先消存在量詞,18,構(gòu)造推理證明(續(xù)),例4 構(gòu)造下述推理證明

19、 前提：?xF(x)??xG(x) 結(jié)論：?x(F(x)?G(x))證明：① ?xF(x)??xG(x) 前提引入 ② ?x?y(F(x)?G(y)) ①置換 ③ ?x(F(x)?G(z)) ②UI ④ F(z)?G(z) ③UI ⑤ ?x(F(x)?G(

20、x)) ④UG,19/51,例 在自然推理系統(tǒng)中構(gòu)造下面推理的證明     前提： ?xP(x)→?xQ(x)        結(jié)論： ?x(P(x)→Q(x)),證明: ? xP(x)→?xQ(x) 前提引入 ?xP(x)

21、 前提引入? P(a)→?xQ(x) 去存在量詞(1) ? P(a) 去全稱量詞(2) ?xQ(x) (3)(4),?,(2)并非是結(jié)論的前件 (3)錯(cuò)誤使用規(guī)則，(1)并非前束范式,20,構(gòu)造推理證明(續(xù)),例5 構(gòu)造下述推理證明 前提：?x(F(x)?G(x

22、)) 結(jié)論：?xF(x)??xG(x)證明：① ?xF(x) 附加前提引入 ② F(y) ①UI ③ ?x(F(x)?G(x)) 前提引入 ④ F(y)?G(y) ③UI ⑤

23、 G(y) ②④假言推理 ⑥ ?xG(x) ⑤UG本題可以使用附加前提證明法,21/51,解：?x(P(x)? Q(x)) ?x P(x) (3) P(e) (4)

24、P(e)? Q(e) (5) Q(e) (3)(4)(6) ?x Q(x),?,例 (p55) ?x(P(x)?Q(x))?(?xP(x)??xQ(x)),解：?x(P(x)? Q(x)) ?x P(x) (3) P(e)? Q(e)