一階邏輯推理理論

1、離散數(shù)學(xué)離散數(shù)學(xué)第第1010課課一階邏輯推理理論一階邏輯推理理論內(nèi)容回顧一階邏輯合式公式及解釋一階邏輯合式公式及解釋一階邏輯等值式及前束范式一階邏輯等值式及前束范式上節(jié)課練習(xí)：求下列公式的前束范式上節(jié)課練習(xí)：求下列公式的前束范式( ( xF(x,y)xF(x,y) yG(x,y)yG(x,y) xF(x,y) y G(x,y) x F(x,y) y G(x,y) x F(x,t) y G(s,y) x( F(x,t) y G(s,y) x y( F(x,t) G(s,y)今日內(nèi)容一階邏輯推理理論一階邏輯推理理論推理形式的定義推理形式的定義量詞引入和消去規(guī)則量詞引入和消去規(guī)則一階邏輯下的推理證明

2、一階邏輯下的推理證明 一階邏輯推理理論一階邏輯推理理論在一階邏輯中，推理的形式結(jié)構(gòu)仍為在一階邏輯中，推理的形式結(jié)構(gòu)仍為 A1A2AkB 若該式是永真式，則稱推理正確，稱若該式是永真式，則稱推理正確，稱B是是A1，A2，Ak的邏輯結(jié)論的邏輯結(jié)論 此時(shí)將該式記為此時(shí)將該式記為 A1A2Ak B命題邏輯中的推理規(guī)則及在一階邏輯中的命題邏輯中的推理規(guī)則及在一階邏輯中的代換實(shí)例，在一階邏輯中仍然成立代換實(shí)例，在一階邏輯中仍然成立一階邏輯中新增加一階邏輯中新增加4條推理規(guī)則條推理規(guī)則 消去和引入規(guī)則消去和引入規(guī)則:全稱量詞消去規(guī)則全稱量詞消去規(guī)則全稱量詞引入規(guī)則全稱量詞引入規(guī)則存在量詞引入規(guī)則存在量詞引入

3、規(guī)則存在量詞消去規(guī)則存在量詞消去規(guī)則全稱量詞消去規(guī)則全稱量詞消去規(guī)則（簡稱（簡稱UI規(guī)則規(guī)則）這條規(guī)則含以下兩種形式：這條規(guī)則含以下兩種形式： xA(x) A(y) xA(x) A(c) 兩式成立的條件兩式成立的條件是是1.x是是A(x)中自由出現(xiàn)的個(gè)體變項(xiàng)；中自由出現(xiàn)的個(gè)體變項(xiàng)；2.在在式中，式中，y為任意的不在為任意的不在A(x)中約束出現(xiàn)中約束出現(xiàn)的個(gè)體變項(xiàng)；的個(gè)體變項(xiàng)；3.在在式中，式中，c為個(gè)體域中任意的個(gè)體常項(xiàng)。為個(gè)體域中任意的個(gè)體常項(xiàng)。 只有在滿足上述條件時(shí)，推理規(guī)則才成立！只有在滿足上述條件時(shí)，推理規(guī)則才成立！在推理過程中在推理過程中 ，兩種形式可根據(jù)需要選兩種形式可根據(jù)需要選

4、用。用。例：例：設(shè)定義域?yàn)閷?shí)數(shù)，取設(shè)定義域?yàn)閷?shí)數(shù)，取F(x,y)F(x,y)為為x xy y， A(x)=A(x)= yF(x,y)yF(x,y)， xA(x) xA(x) x x yF(x,y) yF(x,y) 公式公式 xA(x)xA(x)是真命題。是真命題。考慮如下推理是否正確考慮如下推理是否正確 : : x x yF(yF(x x,y) ,y) 前提引入前提引入 yF(yF(y y,y) ,y) UIUI規(guī)則規(guī)則 yF(y,y)yF(y,y)是假命題，是假命題，推理不正確推理不正確 出錯(cuò)的原因是違背了條件：出錯(cuò)的原因是違背了條件： xA(x) xA(x) A(y)A(y)中，中， y

5、y應(yīng)為任意的不在應(yīng)為任意的不在A(x)A(x)中約束中約束出現(xiàn)的個(gè)體變項(xiàng)。出現(xiàn)的個(gè)體變項(xiàng)。 全稱量詞引入規(guī)則全稱量詞引入規(guī)則（簡稱（簡稱UGUG規(guī)則規(guī)則） A(y) A(y) xA(x) xA(x) 公式成立的條件公式成立的條件是是 1.y1.y在在A(y)A(y)中自由出現(xiàn)，且中自由出現(xiàn)，且y y取取任何值任何值時(shí)時(shí)A A均為均為真真 2.2.取代取代y y的的x x不在不在A(y)A(y)中約束出現(xiàn)。中約束出現(xiàn)。 例例: :設(shè)定義域?yàn)閷?shí)數(shù)，設(shè)定義域?yàn)閷?shí)數(shù)， 取取F(x,y)F(x,y)為為xyxy，A(y)=A(y)= xF(x,y)=xF(x,y)= x(xy)x(xy)， A A對任意

6、給定的對任意給定的y y都是真的。都是真的。如下推理是否正確如下推理是否正確 : : xF(x,y) xF(x,y) 前提引入前提引入 x x xF(x,x) xF(x,x) UG UG x x x(xx)x(xx)是假命題，推理出錯(cuò)。是假命題，推理出錯(cuò)。 出錯(cuò)的原因是違背了條件出錯(cuò)的原因是違背了條件2 2：取代：取代y y的的x x不在不在A(y)A(y)中約束出現(xiàn)中約束出現(xiàn) z xF(x,z) UGUG 存在量詞引入規(guī)則存在量詞引入規(guī)則（簡稱（簡稱EGEG規(guī)則規(guī)則） A(c) A(c) xA(x) xA(x) 公式成立的條件公式成立的條件是是 1.c1.c是特定的個(gè)體常項(xiàng)是特定的個(gè)體常項(xiàng)

7、； 2.2.取代取代c c的的x x不能已在不能已在A(c)A(c)中出現(xiàn)過中出現(xiàn)過 。 例例1:1:設(shè)定義域?yàn)閷?shí)數(shù)，設(shè)定義域?yàn)閷?shí)數(shù)，取取F(x,y)F(x,y)為為x xy y， A(2)=A(2)= xF(x,2)= xF(x,2)= x(x2)x(x2)，（，（真命題）真命題）如下推理是否正確如下推理是否正確 : : xF(x,2) xF(x,2) 前提引入前提引入 x x xF(x,x) xF(x,x) EG EG 假命題，推理出錯(cuò)。出錯(cuò)的原因是違背了假命題，推理出錯(cuò)。出錯(cuò)的原因是違背了條件條件2,x2,x已在已在A(2)A(2)中出現(xiàn)過。中出現(xiàn)過。 存在量詞引入規(guī)則存在量詞引入規(guī)則（

8、簡稱（簡稱EGEG規(guī)則規(guī)則） A(c) A(c) xA(x) xA(x) 公式成立的條件公式成立的條件是是 1.c1.c是特定的個(gè)體常項(xiàng)是特定的個(gè)體常項(xiàng) ； 2.2.取代取代c c的的x x不能已在不能已在A(c)A(c)中出現(xiàn)過中出現(xiàn)過 。 例例1:1:設(shè)定義域?yàn)閷?shí)數(shù)，設(shè)定義域?yàn)閷?shí)數(shù)，取取F(x,y)F(x,y)為為x xy y， A(2)=A(2)= xF(x,2)= xF(x,2)= x(x2)x(x2)，（，（真命題）真命題）如下推理是否正確如下推理是否正確 : : xF(x,2) PxF(x,2) P y y xF(x,y) EG, xF(x,y) EG, 存在量詞消去規(guī)則存在量詞消

9、去規(guī)則（簡稱（簡稱EIEI規(guī)則規(guī)則） xA(x) xA(x) A(c) A(c) 公式成立的條件公式成立的條件是是 1.c1.c是使是使A A為真的特定的個(gè)體常項(xiàng)；為真的特定的個(gè)體常項(xiàng)； 2.c2.c不曾在不曾在A(x)A(x)中出現(xiàn)過；中出現(xiàn)過； 3.A(x)3.A(x)中除中除x x外沒有其他自由出現(xiàn)的個(gè)體變項(xiàng)。外沒有其他自由出現(xiàn)的個(gè)體變項(xiàng)。 例例: : 在自然數(shù)集中，設(shè)在自然數(shù)集中，設(shè)F(x)F(x)為為x x是奇數(shù)，是奇數(shù)，G(x)G(x)是是x x是偶數(shù)，則是偶數(shù)，則 xF(x)xF(x) xG(x)xG(x)是真命題是真命題. .以下推論以下推論是否正確：是否正確：(1) (1)

10、xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)xF(x) (1)化簡規(guī)則化簡規(guī)則(3) (3) xG(x) (1)xG(x) (1)化簡規(guī)則化簡規(guī)則(4) F(a) (2)ES(4) F(a) (2)ES規(guī)則規(guī)則(5) G(a) (3)ES(5) G(a) (3)ES規(guī)則規(guī)則(6) F(a)G(a) (4)(5)(6) F(a)G(a) (4)(5)合取規(guī)則合取規(guī)則(7) (7) x(F(x)G(x) (6)EGx(F(x)G(x) (6)EG規(guī)則規(guī)則例例: : 在自然數(shù)集中，設(shè)在自然數(shù)集中，設(shè)F(x)F(x)為為x x是奇數(shù)，是奇數(shù)，G(x)

11、G(x)是是x x是偶數(shù)，則是偶數(shù)，則 xF(x)xF(x) xG(x)xG(x)是真命題是真命題. .以下推論以下推論是否正確：是否正確：(1) (1) xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)xF(x) (1)化簡規(guī)則化簡規(guī)則(3) (3) xG(x) (1)xG(x) (1)化簡規(guī)則化簡規(guī)則(4) F(a) (2)EI(4) F(a) (2)EI規(guī)則規(guī)則(5) G(a) (3)EI(5) G(a) (3)EI規(guī)則規(guī)則 (6) F(a)G(a) (4)(5)(6) F(a)G(a) (4)(5)合取規(guī)則合取規(guī)則(7) (7) x(F(

12、x)G(x) (6)EGx(F(x)G(x) (6)EG規(guī)則規(guī)則出錯(cuò)的原因是存在量詞消去規(guī)則出錯(cuò)的原因是存在量詞消去規(guī)則 xA(x) xA(x) A(c) A(c)時(shí)違背了條件：時(shí)違背了條件：c c是使是使A A為真的特定的個(gè)體常項(xiàng)為真的特定的個(gè)體常項(xiàng)例例: : 在自然數(shù)集中，設(shè)在自然數(shù)集中，設(shè)F(x)F(x)為為x x是奇數(shù)，是奇數(shù)，G(x)G(x)是是x x是偶數(shù)，則是偶數(shù)，則 xF(x)xF(x) xG(x)xG(x)是真命題是真命題. . 以下推理以下推理是否正確：是否正確：(1) (1) xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)

13、xF(x) (1)化簡規(guī)則化簡規(guī)則(3) (3) xG(x) (1)xG(x) (1)化簡規(guī)則化簡規(guī)則(4) F(a) (2)EI(4) F(a) (2)EI(5) G(b) (3)EI(5) G(b) (3)EI(6) F(a)G(b) (4)(5)(6) F(a)G(b) (4)(5)合取規(guī)則合取規(guī)則(7) (7) x(F(x)G(x) (6)EG x(F(x)G(x) (6)EG 例例: : 在自然數(shù)集中，設(shè)在自然數(shù)集中，設(shè)F(x)F(x)為為x x是奇數(shù)，是奇數(shù)，G(x)G(x)是是x x是偶數(shù)，則是偶數(shù)，則 xF(x)xF(x) xG(x)xG(x)是真命題是真命題. . 以下推理以

14、下推理是否正確：是否正確：(1) (1) xF(x)xF(x) xG(x) xG(x) 前提引入前提引入(2) (2) xF(x) (1)xF(x) (1)化簡規(guī)則化簡規(guī)則(3) (3) xG(x) (1)xG(x) (1)化簡規(guī)則化簡規(guī)則(4) F(a) (2)EI(4) F(a) (2)EI(5) G(b) (3)EI(5) G(b) (3)EI(6) F(a)G(b) (4)(5)(6) F(a)G(b) (4)(5)合取規(guī)則合取規(guī)則(7) (7) x(F(x)G(x) (6)EG x(F(x)G(x) (6)EG (7)(7) x(F(x)G(b) (6)EGx(F(x)G(b) (6

15、)EG(8)(8) x x y(F(x)G(y) (7)EGy(F(x)G(y) (7)EGv在應(yīng)用以上在應(yīng)用以上4 4條量詞規(guī)則時(shí)，要特別注意！條量詞規(guī)則時(shí)，要特別注意！ 一階邏輯推理實(shí)例命題邏輯中的推理規(guī)則及在一階邏輯中命題邏輯中的推理規(guī)則及在一階邏輯中的代換實(shí)例，在一階邏輯推理中仍然使的代換實(shí)例，在一階邏輯推理中仍然使用用量詞消去和引入規(guī)則量詞消去和引入規(guī)則例例1:1: 證明蘇格拉底三段論證明蘇格拉底三段論“凡人都是要死的。凡人都是要死的。蘇格拉底是人蘇格拉底是人. .所以蘇格拉底是要死的。所以蘇格拉底是要死的?！泵}符號化命題符號化：F F（x x）：）：x x是人（是人（特性謂詞特性

16、謂詞）；）； G G（x x）：）：x x是要死的；是要死的； a a：蘇格拉底：蘇格拉底前提前提： x x（F(x)G(x)F(x)G(x)），），F(xiàn)(a)F(a)結(jié)論結(jié)論：G(a)G(a)證明證明：（1 1） x x（F(x)G(x)F(x)G(x)） 前提引入前提引入（2 2）F(a)G(a) UI(1)F(a)G(a) UI(1)（3 3）F(a) F(a) 前提引入前提引入（4 4）G(a) (2)(3)G(a) (2)(3)假言推理假言推理例例2:所有的有理數(shù)都是實(shí)數(shù)，有的有理數(shù)是整數(shù)。所有的有理數(shù)都是實(shí)數(shù)，有的有理數(shù)是整數(shù)。 所以，有的實(shí)數(shù)是整數(shù)。所以，有的實(shí)數(shù)是整數(shù)。 請?jiān)谝浑A

17、邏輯中證明上述推理的正確性。請?jiān)谝浑A邏輯中證明上述推理的正確性。 證明：證明： 命題符號化：命題符號化： F(x) ：x為有理數(shù)；為有理數(shù)； G(x) ：x為實(shí)數(shù)；為實(shí)數(shù)； H(x) ：x為整數(shù)為整數(shù) 前提前提: x ( F(x) G(x) ， x ( F(x) H(x) ) 結(jié)論結(jié)論: x ( G(x) H(x) ) 前提前提: x ( F(x) G(x) ， x ( F(x) H(x) ) 結(jié)論結(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

18、) 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ò)誤？哪步存在錯(cuò)誤？例例3 :請?jiān)谝浑A邏輯中證明下述推理的正確請?jiān)谝浑A邏輯中證明下述推理的正確性。性。不存在能

19、表示出分?jǐn)?shù)的無理數(shù)，有理數(shù)都能表不存在能表示出分?jǐn)?shù)的無理數(shù)，有理數(shù)都能表示成分?jǐn)?shù)，因此，有理數(shù)都不是無理數(shù)。示成分?jǐn)?shù)，因此，有理數(shù)都不是無理數(shù)。 解：解：命題符號化：命題符號化： 設(shè)設(shè) F(x):x為無理數(shù)；為無理數(shù)；G(x):x為有理數(shù)；為有理數(shù)；H(x)：x能表示成分?jǐn)?shù)。能表示成分?jǐn)?shù)。 前提：前提： x(F(x)H(x), x(G(x)H(x) 結(jié)論：結(jié)論： x(G(x)F(x) 前提前提：x x（F(x)H(x)F(x)H(x)），）， x x（G(x)H(x)G(x)H(x)）結(jié)論結(jié)論： x x（G(x)G(x) F(x)F(x)）證明證明: :（1 1）x x（F(x)H(x)F(x

20、)H(x)） 前提引入前提引入（2 2） x x（ F(x)F(x) H(x)H(x)） (1)(1)置換規(guī)則置換規(guī)則（3 3） x x（H(x) H(x) F(x)F(x)） (2)(2)置換規(guī)則置換規(guī)則（4 4）H(y)H(y) F(y) UIF(y) UI（3 3）（5 5） x x（G(x)H(x)G(x)H(x)） 前提引入前提引入（6 6）G(y)H(y) UIG(y)H(y) UI（5 5）（7 7）G(y)G(y) F(y) (4)(6F(y) (4)(6）假言三段論）假言三段論（8 8） x x（G(x)G(x) F(x)F(x)） UGUG（7 7）課堂練習(xí)：課堂練習(xí)：前提：前提： x ( F(x) ( G(y) R(x) ) ) ， x F(x) 結(jié)論：結(jié)論： x ( F(x) R(x) ) 證明：證明： x F(x) 前提引入前提引入 F（c） EI x ( F(x) ( G(y) R(x) ) ) 前提引入前提引入 F(c) ( G(y) R(c) ) UI G(y) R(c) 假言推理假言推理 R(c) 化簡化簡 F(c