1、1,主要內(nèi)容 一階邏輯等值式與基本的等值式 置換規(guī)則、換名規(guī)則、代替規(guī)則 前束范式 自然推理系統(tǒng)NL 及其推理規(guī)則,第五章 一階邏輯等值演算與推理,2,5.1 一階邏輯等值式與置換規(guī)則,定義5.1 設(shè)A, B是兩個謂詞公式, 如果AB是永真式, 則稱A 與B等值, 記作AB, 并稱AB是等值式 基本等值式 第一組 命題邏輯中16組基本等值式的代換實例 例如，xF(x)xF(x), xF(x)yG(y) xF(x)yG(y) 等 第二組 (1) 消去量詞等值式 設(shè)D =a1, a2, , an xA(x) A(a1)A(a2)A(an) xA(x) A(a1)A(a2)A(an),3,基本等值式

2、,(2) 量詞否定等值式 xA(x) xA(x) xA(x) xA(x) (3) 量詞轄域收縮與擴張等值式. A(x) 是含 x 自由出現(xiàn)的公式，B 中不含 x 的自由出現(xiàn) 關(guān)于全稱量詞的： x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x),4,基本等值式,關(guān)于存在量詞的： x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x) (4) 量詞分配等值式 x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) 注意：對，

3、對無分配律,5,置換規(guī)則、換名規(guī)則、代替規(guī)則,1. 置換規(guī)則 設(shè)(A)是含A的公式, 那么, 若AB, 則(A)(B). 2. 換名規(guī)則 設(shè)A為一公式，將A中某量詞轄域中個體變項的所有約束 出現(xiàn)及相應的指導變元換成該量詞轄域中未曾出現(xiàn)過的個 體變項符號，其余部分不變，設(shè)所得公式為A，則AA. 3. 代替規(guī)則 設(shè)A為一公式，將A中某個個體變項的所有自由出現(xiàn)用A中 未曾出現(xiàn)過的個體變項符號代替，其余部分不變，設(shè)所得 公式為A，則AA.,6,實例,例1 將下面命題用兩種形式符號化, 并證明兩者等值: (1) 沒有不犯錯誤的人,解 令F(x)：x是人，G(x)：x犯錯誤. x(F(x)G(x) 或 x

4、(F(x)G(x),x(F(x)G(x) x(F(x)G(x) 量詞否定等值式 x(F(x)G(x) 置換 x(F(x)G(x) 置換,7,實例,(2) 不是所有的人都愛看電影,解 令F(x)：x是人，G(x)：愛看電影. x(F(x)G(x) 或 x(F(x)G(x),x(F(x)G(x) x(F(x)G(x) 量詞否定等值式 x(F(x)G(x) 置換 x(F(x)G(x) 置換,8,實例,例2 將公式化成等值的不含既有約束出現(xiàn)、又有自由出現(xiàn) 的個體變項: x(F(x,y,z)yG(x,y,z),解 x(F(x,y,z)yG(x,y,z) x(F(x,y,z)tG(x,t,z) 換名規(guī)則

5、xt(F(x,y,z)G(x,t,z) 轄域擴張等值式,或者 x(F(x,y,z)yG(x,y,z) x(F(x,u,z)yG(x,y,z) 代替規(guī)則 xy(F(x,u,z)G(x,y,z) 轄域擴張等值式,9,實例,例3 設(shè)個體域D=a,b,c, 消去下述公式中的量詞: (1) xy(F(x)G(y),解 xy(F(x)G(y) (y(F(a)G(y)(y(F(b)G(y)(y(F(c)G(y) (F(a)G(a)(F(a)G(b)(F(a)G(c) (F(b)G(a)(F(b)G(b)(F(b)G(c) (F(c)G(a)(F(c)G(b)(F(c)G(c),10,實例,解法二 xy(F(

6、x)G(y) x(F(x)yG(y) 轄域縮小等值式 x(F(x)G(a)G(b)G(c) (F(a)G(a)G(b)G(c) (F(b)G(a)G(b)G(c) (F(c)G(a)G(b)G(c),例3 設(shè)個體域D=a,b,c, 消去下述公式中的量詞: (1) xy(F(x)G(y),11,實例,(2) xyF(x,y),xyF(x,y) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c) (F(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c),例3 設(shè)個體域D=a,b,c, 消去下述公式中的量詞:,12,5.2 一階邏輯前束范式,定義5

7、.2 設(shè)A為一個一階邏輯公式，若A具有如下形式 Q1x1Q2x2QkxkB 則稱A為前束范式，其中Qi (1 i k)為或，B為不含量詞 的公式. 例如， x(F(x)G(x) xy(F(x)(G(y)H(x,y) 是前束范式 而 x(F(x)G(x) x(F(x)y(G(y)H(x,y) 不是前束范式，,13,前束范式存在定理,定理5.1（前束范式存在定理） 一階邏輯中的任何公式都存在與之等值的前束范式,例4 求下列公式的前束范式 (1) x(M(x)F(x),解 x(M(x)F(x) x(M(x)F(x) （量詞否定等值式） x(M(x)F(x) 后兩步結(jié)果都是前束范式，說明公式的前束范式

8、不惟一.,14,求前束范式的實例,(2) xF(x)xG(x),解 xF(x)xG(x) xF(x)xG(x) （量詞否定等值式） x(F(x)G(x) （量詞分配等值式）,或 xF(x)xG(x) xF(x)xG(x) 量詞否定等值式 xF(x)yG(y) 換名規(guī)則 xy(F(x)G(y) 轄域收縮擴張規(guī)則,15,求前束范式的實例,(3) xF(x)y(G(x,y)H(y),或 xF(x)y(G(z,y)H(y) 代替規(guī)則 xy(F(x)(G(z,y)H(y),解 xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) 換名規(guī)則 zy(F(z)(G(x,y)H(y) 轄域收縮

9、擴張規(guī)則,16,5.3 一階邏輯的推論理論,推理的形式結(jié)構(gòu) 1. A1A2Ak B 若次式是永真式, 則稱推理正確, 記作A1A2Ak B 2. 前提: A1, A2, Ak 結(jié)論: B 推理定理: 永真式的蘊涵式,17,推理定律,第一組 命題邏輯推理定律的代換實例 如, xF(x)yG(y) xF(x) 第二組 基本等值式生成的推理定律 如, xF(x) xF(x), xF(x) xF(x) xF(x)xF(x), xF(x) xF(x) 第三組 其他常用推理定律 (1) xA(x)xB(x) x(A(x)B(x) (2) x(A(x)B(x)xA(x)xB(x) (3) x(A(x)B(x

10、) xA(x)xB(x) (4) x(A(x)B(x) xA(x)xB(x),18,量詞消去引入規(guī)則,1. 全稱量詞消去規(guī)則(-) 或 其中x,y是個體變項符號, c是個體常項符號, 且在A中x不在y 和y的轄域內(nèi)自由出現(xiàn). 2. 全稱量詞引入規(guī)則(+) 其中x是個體變項符號, 且不在前提的任何公式中自由出現(xiàn),19,量詞消去引入規(guī)則,3. 存在量詞消去規(guī)則(-) 其中x是個體變項符號, 且不在前提的任何公式和B中自由 出現(xiàn),20,量詞消去引入規(guī)則,4. 存在量詞引入消去規(guī)則(+) 或 或 其中x,y是個體變項符號, c是個體常項符號, 且在A中y和c不在 x和x的轄域內(nèi)自由出現(xiàn).,21,自然推

11、理系統(tǒng)NL,定義5.3 自然推理系統(tǒng)NL 定義如下: 1. 字母表. 同一階語言L 的字母表 2. 合式公式. 同L 的合式公式 3. 推理規(guī)則: (1) 前提引入規(guī)則 (2) 結(jié)論引入規(guī)則 (3) 置換規(guī)則 (4) 假言推理規(guī)則 (5) 附加規(guī)則 (6) 化簡規(guī)則 (7) 拒取式規(guī)則,22,自然推理系統(tǒng)NL,(8) 假言三段論規(guī)則 (9) 析取三段論規(guī)則 (10) 構(gòu)造性二難推理規(guī)則 (11) 合取引入規(guī)則 (12) -規(guī)則 (13) +規(guī)則 (14) -規(guī)則 (15) +規(guī)則 推理的證明,23,構(gòu)造推理證明的實例,例5 在自然推理系統(tǒng)NL 中構(gòu)造下面推理的證明, 取個體域R: 任何自然數(shù)都

12、是整數(shù). 存在自然數(shù). 所以, 存在整數(shù).,解 設(shè)F(x):x是自然數(shù), G(x):x是整數(shù). 前提: x(F(x)G(x), xF(x) 結(jié)論: xG(x) 證明: x(F(x)G(x) 前提引入 F(x)G(x) - F(x)xG(x) + xF(x)xG(x) - xF(x) 前提引入 xG(x) 假言推理,24,構(gòu)造推理證明的實例,例6 在自然推理系統(tǒng)NL 中構(gòu)造下面推理的證明, 取個體域R: 不存在能表示成分數(shù)的無理數(shù). 有理數(shù)都能表示成分數(shù). 所以, 有理數(shù)都不是無理數(shù).,解 設(shè)F(x):x是無理數(shù), G(x):x是有理數(shù), H(x):x能表示成分數(shù). 前提: x(F(x)H(x)

13、, x(G(x)H(x) 結(jié)論: x(G(x)F(x) 證明: x(F(x)H(x) 前提引入 x(F(x)H(x) 置換 x(F(x)H(x) 置換 F(x)H(x) -,25,構(gòu)造推理證明的實例, x(G(x)H(x) 前提引入 G(x)H(x) - H(x)F(x) 置換 G(x)F(x) 假言三段論 x(G(x)F(x) +,26,重要提示,要特別注意使用-、+、-、+規(guī)則的條件. 反例1. 對A=xyF(x,y)使用-規(guī)則, 推得B=yF(y,y). 取解釋I: 個體域為R, 在I下A被解釋為xy(xy), 真; 而B被解釋為y(yy), 假 原因: 在A中x自由出現(xiàn)在y的轄域F(x

14、,y)內(nèi),反例2. 前提: P(x)Q(x), P(x) 結(jié)論: xQ(x) 取解釋I: 個體域為Z, 在I下前提為真, 結(jié)論為假, 從而推理不正確,27,反例2(續(xù)),“證明”: P(x)Q(x) 前提引入 P(x) 前提引入 Q(x) 假言推理 xQ(x) + 錯誤原因: 在使用+規(guī)則, 而x在前提的公式中自由出現(xiàn).,28,第五章 習題課,主要內(nèi)容 一階邏輯等值式 基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則 前束范式 推理的形式結(jié)構(gòu) 自然推理系統(tǒng)NL 推理定律、推理規(guī)則,29,基本要求,深刻理解并牢記一階邏輯中的重要等值式, 并能準確而熟練地應用它們 熟練正確地使用置換規(guī)則、換名規(guī)則、代替規(guī)

15、則 熟練地求出給定公式的前束范式 深刻理解自然推理系統(tǒng)NL 的定義，牢記NL 中的各條推理規(guī)則，特別是注意使用、+、+、 4條推理規(guī)則的條件 能正確地給出有效推理的證明,30,練習1,1. 給定解釋I如下: (1) 個體域D=2,3 (2) (3) (4) 求下述在I下的解釋及其真值: xy(F(f(x)G(y,f(a),解 xF(f(x)yG(y,f(a) F(f(2)F(f(3)(G(2,f(2)G(3,f(2) 10(10)0,31,練習2,2.求下述公式的前束范式: xF(x)y(G(x,y)H(x,y),解 使用換名規(guī)則, xF(x)y(G(x,y)H(x,y) zF(z)y(G(x

16、,y)H(x,y) z(F(z)y(G(x,y)H(x,y) zy(F(z)(G(x,y)H(x,y),使用代替規(guī)則 xF(x)y(G(x,y)H(x,y) xF(x)y(G(z,y)H(z,y) x(F(x)y(G(z,y)H(z,y) xy(F(x)(G(z,y)H(z,y),32,練習3,3.構(gòu)造下面推理的證明: (1) 前提：x(F(x)G(x), xF(x) 結(jié)論：xG(x),證明： x(F(x)G(x) 前提引入 F(y)G(y) xF(x) 前提引入 F(y) G(y) 假言推理 yG(y) + xG(x) 置換,33,練習3(續(xù)),(2) 前提：x(F(x)G(x), xG(x

17、) 結(jié)論：xF(x),證明：用歸謬法 xF(x) 結(jié)論否定引入 xF(x) 置換 xG(x) 前提引入 xG(x) 置換 x(F(x)G(x), 前提引入 F(c) G(c) F(c)G(c) G(c) 析取三段論 G(c)G(c) 合取引入,34,練習3(續(xù)),(3)前提：x(F(x)G(x), x(G(x)H(x) 結(jié)論：xF(x)xH(x),證明: 用附加前提法 xF(x) 附加前提引入 F(x) x(F(x)G(x) 前提引入 F(x)G(x) x(G(x)H(x) 前提引入 G(x)H(x) F(x)H(x) 假言三段論 H(x) 假言推理 xH(x) +,35,練習4,4. 在自然推理系統(tǒng)NL 中，構(gòu)造推理的證明 人都喜歡吃蔬菜但不是所有的人都喜歡吃魚所以, 存在喜歡吃蔬菜而不喜歡吃魚的人,解 令F(x): x為人，G(x): x喜歡吃蔬菜，H(x): x喜歡吃魚 前提：x(F(x)G(x), x(F(x)H(x) 結(jié)論：x(F(x)G(x)H(x),證明：用歸謬法 (1