離散數(shù)學(xué)一階邏輯

1、1第第3 3章章 一階邏輯一階邏輯2第第3 3章章 一階邏輯一階邏輯 3.1 一階邏輯基本概念一階邏輯基本概念 3.2 一階邏輯等值演算一階邏輯等值演算33.1 一階邏輯基本概念一階邏輯基本概念 3.1.1 命題邏輯的局限性命題邏輯的局限性 3.1.2 個(gè)體詞、謂詞與量詞個(gè)體詞、謂詞與量詞 個(gè)體常項(xiàng)、個(gè)體變項(xiàng)、個(gè)體域、全總個(gè)體域個(gè)體常項(xiàng)、個(gè)體變項(xiàng)、個(gè)體域、全總個(gè)體域 謂詞常項(xiàng)、謂詞變項(xiàng)謂詞常項(xiàng)、謂詞變項(xiàng) 全稱量詞、存在量詞全稱量詞、存在量詞 3.1.3 一階邏輯命題符號(hào)化一階邏輯命題符號(hào)化43.1 一階邏輯基本概念一階邏輯基本概念( (續(xù)續(xù)) ) 3.1.4 一階邏輯公式與分類一階邏輯公式與分

2、類 一階語(yǔ)言一階語(yǔ)言L （字母表、項(xiàng)、原子公式、合式（字母表、項(xiàng)、原子公式、合式公式）公式） 轄域和指導(dǎo)變?cè)?、約束出現(xiàn)和自由出現(xiàn)轄域和指導(dǎo)變?cè)?、約束出現(xiàn)和自由出現(xiàn) 閉式閉式 一階語(yǔ)言一階語(yǔ)言L 的解釋的解釋 永真式、矛盾式、可滿足式永真式、矛盾式、可滿足式 代換實(shí)例代換實(shí)例5命題邏輯的局限性命題邏輯的局限性考慮下述推理考慮下述推理:凡偶數(shù)都能被凡偶數(shù)都能被2整除整除, 6是偶數(shù)是偶數(shù), 所以所以6能被能被2整除整除.在命題邏輯中在命題邏輯中令令 p: 凡偶數(shù)都能被凡偶數(shù)都能被2整除整除, q: 6是偶數(shù)是偶數(shù), r: 6能被能被2整除整除符號(hào)化為符號(hào)化為 (p q) r不能證明其正確性不能證明

3、其正確性6個(gè)體詞與個(gè)體域個(gè)體詞與個(gè)體域個(gè)體詞個(gè)體詞: 所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體 個(gè)體常項(xiàng)個(gè)體常項(xiàng): 表示具體事物的個(gè)體詞表示具體事物的個(gè)體詞, 用用a, b, c等表示等表示 個(gè)體變項(xiàng)個(gè)體變項(xiàng): 表示抽象事物的個(gè)體詞表示抽象事物的個(gè)體詞, 用用x, y, z等表示等表示 個(gè)體域個(gè)體域: 個(gè)體變項(xiàng)的取值范圍個(gè)體變項(xiàng)的取值范圍 全總個(gè)體域全總個(gè)體域: 宇宙間一切事物宇宙間一切事物例如例如 “若若x是偶數(shù)是偶數(shù), 則則x能被能被2整除整除.” x、 偶數(shù)和偶數(shù)和2是個(gè)體詞是個(gè)體詞, 偶數(shù)和偶數(shù)和2是個(gè)體常項(xiàng)是個(gè)體常項(xiàng), x是個(gè)體變項(xiàng)是個(gè)體變

4、項(xiàng) 個(gè)體域可以是自然數(shù)集個(gè)體域可以是自然數(shù)集N, 整數(shù)集整數(shù)集Z, 也可以是全總個(gè)也可以是全總個(gè) 體域體域7謂詞謂詞謂詞謂詞: 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞 謂詞常項(xiàng)謂詞常項(xiàng): 表示具體性質(zhì)或相互之間關(guān)系的謂詞表示具體性質(zhì)或相互之間關(guān)系的謂詞 謂詞變項(xiàng)謂詞變項(xiàng): 表示抽象性質(zhì)或相互之間關(guān)系的謂詞表示抽象性質(zhì)或相互之間關(guān)系的謂詞 謂詞用謂詞用F,G,H,P等表示等表示 n元謂詞元謂詞P(x1, x2, xn): 含含n個(gè)命題變項(xiàng)的謂詞個(gè)命題變項(xiàng)的謂詞, 是定義在是定義在個(gè)體域上個(gè)體域上, 值域?yàn)橹涤驗(yàn)?,1的的n元函數(shù)元函數(shù) 一元謂詞一元謂詞: 表示事物的性質(zhì)

5、表示事物的性質(zhì) 多元謂詞多元謂詞(n 2): 表示事物之間的關(guān)系表示事物之間的關(guān)系 0元謂詞元謂詞: 不含個(gè)體變項(xiàng)的謂詞不含個(gè)體變項(xiàng)的謂詞,即命題常項(xiàng)或命題變項(xiàng)即命題常項(xiàng)或命題變項(xiàng)8實(shí)例實(shí)例例例1 (1) 4是偶數(shù)是偶數(shù) 4是個(gè)體常項(xiàng)是個(gè)體常項(xiàng), “是偶數(shù)是偶數(shù)”是謂詞常項(xiàng)是謂詞常項(xiàng), 符號(hào)化為符號(hào)化為: F(4) (2) 小王和小李同歲小王和小李同歲 小王小王, 小李是個(gè)體常項(xiàng)小李是個(gè)體常項(xiàng), 同歲是謂詞常項(xiàng)同歲是謂詞常項(xiàng). 記記a:小王小王, b: 小李小李, G(x,y): x與與y同歲同歲, 符號(hào)化為符號(hào)化為: G(a,b)(3) x y x,y是命題變項(xiàng)是命題變項(xiàng), 3，則，則3y,

6、 G(x,y): x10, G(x): x0 真命題真命題21解釋解釋定義定義3.7 設(shè)一階語(yǔ)言設(shè)一階語(yǔ)言L 的個(gè)體常項(xiàng)集的個(gè)體常項(xiàng)集ai| i 1, 函數(shù)符號(hào)集函數(shù)符號(hào)集fi| i 1, 謂詞符號(hào)集謂詞符號(hào)集Fi| i 1, L 的的解釋解釋I由下面由下面4部分組成部分組成:(1) 非空個(gè)體域非空個(gè)體域DI(2) 對(duì)每一個(gè)個(gè)體常項(xiàng)對(duì)每一個(gè)個(gè)體常項(xiàng)ai, DI, 稱作稱作ai在在I中的解釋中的解釋(3) 對(duì)每一個(gè)函數(shù)符號(hào)對(duì)每一個(gè)函數(shù)符號(hào)fi, 設(shè)其為設(shè)其為m元的元的, 是是DI上的上的m元函元函數(shù)數(shù), 稱作稱作fi在在I中的解釋中的解釋(4) 對(duì)每一個(gè)謂詞符號(hào)對(duì)每一個(gè)謂詞符號(hào)Fi, 設(shè)其為設(shè)其

7、為n元的元的, 是一個(gè)是一個(gè)n元謂詞元謂詞, 稱作稱作Fi在在I中的解釋中的解釋iaifiF22實(shí)例實(shí)例例例8 給定解釋給定解釋I I 如下如下: : (a) 個(gè)體域個(gè)體域 D=N (b) (c) (d) 謂詞謂詞說(shuō)明下列公式在說(shuō)明下列公式在 I 下的含義下的含義, 并討論其真值并討論其真值 (1) xF(g(x,a),x)2 axyyxgyxyxf ),(,),(yxyxF :),( x(2x=x) 假命題假命題(2) x y(F(f(x,a),y)F(f(y,a),x) x y(x+2=yy+2=x) 假命題假命題23實(shí)例實(shí)例(續(xù)續(xù))(3) x y zF(f(x,y),z)(5) F(f(

8、x,a), g(x,a)(4) xF(f(x,x),g(x,x) x(2x=x2) 真命題真命題 x y z (x+y=z) 真命題真命題(6) x (F(x,y)F(f(x,a), f(y,a) x (x=yx+2=y+2) 真命題真命題x+2=2x 不是命題不是命題24閉式的性質(zhì)閉式的性質(zhì)定理定理3.1 閉式在任何解釋下都變成命題閉式在任何解釋下都變成命題.例例8 (1)(4)都是閉式都是閉式, 在在I下全是命題下全是命題.(5)和和(6)不是閉式不是閉式, 在在I下下(5)不是命題不是命題, (6)是命題是命題25一階邏輯公式的分類一階邏輯公式的分類永真式永真式( (邏輯有效式邏輯有效式

9、) ): : 無(wú)成假解釋無(wú)成假解釋矛盾式矛盾式( (永假式永假式) ): : 無(wú)成真解釋無(wú)成真解釋可滿足式可滿足式: : 至少有一個(gè)成真解釋至少有一個(gè)成真解釋在一階邏輯中在一階邏輯中, , 公式的可滿足性公式的可滿足性( (永真性永真性, ,永假性永假性) )是不可是不可判定的判定的, ,即不存在算法能在有限步內(nèi)判斷任給的公式是否即不存在算法能在有限步內(nèi)判斷任給的公式是否是可滿足式是可滿足式( (永真式永真式, ,矛盾式矛盾式) )26代換實(shí)例代換實(shí)例定義定義3.9 設(shè)設(shè)A0是含命題變項(xiàng)是含命題變項(xiàng)p1, p2, ,pn的命題公式的命題公式, A1,A2, An是是n個(gè)謂詞公式個(gè)謂詞公式, 用

10、用Ai處處代替處處代替A0中的中的pi(1 i n), 所得公式所得公式A稱為稱為A0的的代換實(shí)例代換實(shí)例.例如例如 F(x)G(x), xF(x)yG(y) 等都是等都是pq的代換實(shí)例的代換實(shí)例 定理定理3.2 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式例都是矛盾式. 27實(shí)例實(shí)例例例9 判斷下列公式的類型判斷下列公式的類型:(1) x(F(x)G(x)非永真式的可滿足式非永真式的可滿足式(2) ( xF(x) ( xF(x) 這是這是 p p 的代換實(shí)例的代換實(shí)例, p p是重言式是重言式, 取解釋取解釋I1, D1=R, :x是整數(shù)是

11、整數(shù), :x是有理數(shù)是有理數(shù), 真命題真命題)(xF)(xG永真式永真式(3) ( xF(x)yG(y) yG(y)這是這是 (pq) q的代換實(shí)例的代換實(shí)例, (pq) q是矛盾式是矛盾式矛盾式矛盾式取解釋取解釋I2, D2=R, :x是整數(shù)是整數(shù), :x是自然數(shù)是自然數(shù), 假命題假命題)(xF)(xG283.2 一階邏輯等值演算一階邏輯等值演算 3.2.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則 基本等值式基本等值式 置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則、換名規(guī)則、代替規(guī)則 3.2.2 一階邏輯前束范式一階邏輯前束范式29等值式等值式定義定義3.10 若若AB是永真式是永真式,

12、則稱則稱A與與B是是等值等值的的, 記作記作 AB, 并稱并稱AB為為等值式等值式基本等值式基本等值式命題邏輯中基本等值式的代換實(shí)例命題邏輯中基本等值式的代換實(shí)例如，如， xF(x)yG(y) xF(x)yG(y) ( xF(x)yG(y) xF(x)yG(y) 等等 消去量詞等值式消去量詞等值式 設(shè)設(shè)D=a1,a2,an xA(x)A(a1) A(a2) A(an) xA(x)A(a1) A(a2) A(an)30基本等值式基本等值式(續(xù)續(xù))量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式 設(shè)設(shè)A(x)是含是含x自由出現(xiàn)的公式，自由出現(xiàn)的公式，B中不含中不含x的出現(xiàn)的出現(xiàn)關(guān)于全稱量詞的：關(guān)于

13、全稱量詞的： 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) 關(guā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)31基本等值式基本等值式(續(xù)續(xù))量詞否定等值式量詞否定等值式設(shè)設(shè)A(x)是含是含x自由出現(xiàn)的公式自由出現(xiàn)的公式 xA(x) x A(x) xA(x) x A(x)量詞分配等值式量詞分配等值式 x(A(x) B(x)xA(x)xB(x) x(A(x) B(x)xA(x)xB(x)注意：注意： 對(duì)對(duì) 無(wú)分配

14、律，無(wú)分配律， 對(duì)對(duì) 無(wú)分配律無(wú)分配律 32置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則置換規(guī)則 設(shè)設(shè) (A)是含公式是含公式A的公式的公式, (B)是用公式是用公式B取取代代 (A)中的所有中的所有A得到的公式得到的公式, 則則 (A) (B)換名規(guī)則換名規(guī)則 將公式將公式A中某量詞的指導(dǎo)變?cè)捌湓谳犛騼?nèi)的中某量詞的指導(dǎo)變?cè)捌湓谳犛騼?nèi)的所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個(gè)個(gè)體變所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng)項(xiàng), 其余部分不變其余部分不變, 記所得公式為記所得公式為A , 則則AA 代替規(guī)則代替規(guī)則 將公式將公式A中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)的所有自

15、中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)的所有自由出現(xiàn)改成由出現(xiàn)改成A中未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng)中未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng), 其余部分不變其余部分不變, 記所得公式為記所得公式為A , 則則AA33實(shí)例實(shí)例例例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)(1) xF(x,y,z) yG(x,y,z) uF(u,y,z) yG(x,y,z) 換名規(guī)則換名規(guī)則 uF(u,y,z) vG(x,v,z) 換名規(guī)則換名規(guī)則或者或者 xF(x,u,z) yG(x,y,z) 代替規(guī)則代替規(guī)則 xF(x,u,z) yG(v,y,z) 代替規(guī)則代替規(guī)則(2) x(F(x,y) yG(x,

16、y,z) x(F(x,y) tG(x,t,z) 換名規(guī)則換名規(guī)則或者或者 x(F(x,t) yG(x,y,z) 代替規(guī)則代替規(guī)則34實(shí)例實(shí)例例例2 設(shè)個(gè)體域設(shè)個(gè)體域D=a,b,c, 消去下面公式中的量詞消去下面公式中的量詞:(1) x(F(x)G(x) (F(a)G(a) (F(b)G(b) (F(c)G(c)(2) x(F(x)yG(y) xF(x)yG(y) 量詞轄域收縮量詞轄域收縮(F(a) F(b) F(c) (G(a) G(b) G(c) x(F(x,a) F(x,b) F(x,c)(3) x yF(x,y) (F(a,a) F(a,b) F(a,c) (F(b,a) F(b,b)

17、F(b,c) (F(c,a) F(c,b) F(c,c)35實(shí)例實(shí)例解解 (F(f(2) G(2, f(2) (F(f(3) G(3, f(3)例例3 給定解釋給定解釋I: (a) D=2,3, (b) (c) :x是奇數(shù)是奇數(shù), : x=2 y=2, : x=y.在在I下求下列各式的真值下求下列各式的真值:(1) x(F(f(x) G(x, f(x) , 2)3(, 3)2(:fff),(yxG),(yxL)(xF(2) x yL(x,y) (1 1) (0 1) 1解解 yL(2,y) yL(3,y) (L(2,2) L(2,3) (L(3,2) L(3,3) (1 0) (0 1) 03

18、6實(shí)例實(shí)例例例4 證明下列等值式證明下列等值式: x(M(x) F(x) x(M(x) F(x)證證 左邊左邊 x (M(x) F(x) 量詞否定等值式量詞否定等值式 x( M(x) F(x) x(M(x) F(x)37前束范式前束范式定義定義3.11 設(shè)設(shè)A為一個(gè)一階邏輯公式為一個(gè)一階邏輯公式, 若若A具有如下形式具有如下形式 Q1x1Q2x2Qkxk B則稱則稱A為為前束范式前束范式, 其中其中Qi 為為 或或 , 1 i k, B為不含量詞的為不含量詞的公式公式.例如例如 x y(F(x)(G(y) H(x,y) x (F(x) G(x)是前束范式是前束范式 x(F(x)y(G(y) H(x,y) x(F(x) G(x)不是前束范式不是前