離散數(shù)學(xué)第三章

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

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

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

4、項(xiàng) 個體域可以是自然數(shù)集個體域可以是自然數(shù)集N, 整數(shù)集整數(shù)集Z, 也可以是全總個也可以是全總個 體域體域7謂詞謂詞謂詞謂詞: 表示個體詞性質(zhì)或相互之間關(guān)系的詞表示個體詞性質(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個命題變項(xiàng)的謂詞個命題變項(xiàng)的謂詞, 是定義在是定義在個體域上個體域上, 值域?yàn)橹涤驗(yàn)?,1的的n元函數(shù)元函數(shù) 一元謂詞一元謂詞: 表示事物的性質(zhì)

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

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

7、函元函數(shù)數(shù), 稱作稱作fi在在I中的解釋中的解釋(4) 對每一個謂詞符號對每一個謂詞符號Fi, 設(shè)其為設(shè)其為n元的元的, 是一個是一個n元謂詞元謂詞, 稱作稱作Fi在在I中的解釋中的解釋iaifiF22解釋與賦值解釋與賦值(續(xù)續(xù))(5) 對每一個自由出現(xiàn)的個體變項(xiàng)對每一個自由出現(xiàn)的個體變項(xiàng)x指定個體域中的一個值指定個體域中的一個值 (x), 稱作稱作賦值賦值 .任何公式在給定的解釋和賦值下都是命題任何公式在給定的解釋和賦值下都是命題. 23實(shí)例實(shí)例例例8 給定解釋給定解釋I I 如下如下: : (a) 個體域個體域 D=N (b) (c) (d) 謂詞謂詞及賦值及賦值 : (x)=0, (y)

8、=1, (z)=2.說明下列公式在說明下列公式在 I 及及 下的含義下的含義, 并討論其真值并討論其真值 (1) xF(g(x,a),y)2 axyyxgyxyxf ),(,),(yxyxF :),( x(2x=1) 假命題假命題24實(shí)例實(shí)例(續(xù)續(xù))(3) x y zF(f(x,y),z)(5) F(f(x,a), g(y,a)(4) xF(f(x,y),g(x,z) x(x+1=2x) 真命題真命題 x y z (x+y=z) 真命題真命題(6) x(F(x,y)yF(f(x,a), g(y,a) x (x=1y(x+2=2y) 假命題假命題0+2=1 2 真命題真命題(2) x y(F(f

9、(x,a),y)F(f(y,a),x) x y(x+2=yy+2=x) 假命題假命題25閉式的性質(zhì)閉式的性質(zhì)定理定理3.1 閉式在任何解釋下都變成命題閉式在任何解釋下都變成命題.閉式只需給定解釋閉式只需給定解釋,如例如例8 (2),(3). 只給定解釋只給定解釋,非閉式可能成為命題非閉式可能成為命題, 但通常不能成為命題但通常不能成為命題.只有給定解釋和賦值只有給定解釋和賦值, 非閉式才能一定成為命題非閉式才能一定成為命題.26一階邏輯公式的分類一階邏輯公式的分類永真式永真式( (邏輯有效式邏輯有效式) ): : 無成假解釋和賦值無成假解釋和賦值矛盾式矛盾式( (永假式永假式) ): : 無成

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

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

12、F)(xG永真式永真式(3) ( xF(x)yG(y) yG(y)這是這是 (pq) q的代換實(shí)例的代換實(shí)例, (pq) q是矛盾式是矛盾式矛盾式矛盾式取解釋取解釋I2, D2=R, :x是整數(shù)是整數(shù), :x是自然數(shù)是自然數(shù), 假命題假命題)(xF)(xG29實(shí)例實(shí)例(續(xù)續(xù))(4) xF(x,y)非永真式的可滿足式非永真式的可滿足式解釋解釋I1, D1=N, :x y; 賦值賦值 (y)=0, 真命題真命題),(yxF解釋解釋I2, D2=N, :x y; 賦值賦值 (y)=1, 假命題假命題),(yxF303.2 一階邏輯等值演算一階邏輯等值演算 3.2.1 一階邏輯等值式與置換規(guī)則一階邏輯

13、等值式與置換規(guī)則 基本等值式基本等值式 置換規(guī)則、換名規(guī)則置換規(guī)則、換名規(guī)則 3.2.2 一階邏輯前束范式一階邏輯前束范式31等值式等值式定義定義3.10 若若AB是永真式是永真式, 則稱則稱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)

14、32基本等值式基本等值式(續(xù)續(xù))量詞轄域收縮與擴(kuò)張等值式量詞轄域收縮與擴(kuò)張等值式 設(shè)設(shè)A(x)是含是含x自由出現(xiàn)的公式，自由出現(xiàn)的公式，B中不含中不含x的出現(xiàn)的出現(xiàn)關(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) 關(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)33基本等值式基本等值式(續(xù)續(xù))量詞否定等值式量詞否定等值式設(shè)設(shè)A(x)是含是含x自由出現(xiàn)的公式自由出現(xiàn)的公式 xA(x

15、) 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)注意：注意： 對對 ， 對對 無分配律無分配律 34置換規(guī)則、換名規(guī)則置換規(guī)則、換名規(guī)則置換規(guī)則置換規(guī)則 設(shè)設(shè) (A)是含公式是含公式A的公式的公式, (B)是用公式是用公式B取取代代 (A)中的所有中的所有A得到的公式得到的公式, 則則 (A) (B)換名規(guī)則換名規(guī)則 將公式將公式A中某量詞的指導(dǎo)變元及其在轄域內(nèi)的中某量詞的指導(dǎo)變元及其在轄域內(nèi)的所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個個體變所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個個

16、體變項(xiàng)項(xiàng), 其余部分不變其余部分不變, 記所得公式為記所得公式為A , 則則AA 35實(shí)例實(shí)例例例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個體變項(xiàng)消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個體變項(xiàng)(1) xF(x,y,z) yG(x,y,z) uF(u,y,z) yG(x,y,z) 換名規(guī)則換名規(guī)則(2) x(F(x,y) yG(x,y,z) x(F(x,y) tG(x,t,z) 換名規(guī)則換名規(guī)則 uF(u,y,z) vG(x,v,z) 換名規(guī)則換名規(guī)則36實(shí)例實(shí)例例例2 設(shè)個體域設(shè)個體域D=a,b,c, 消去下面公式中的量詞消去下面公式中的量詞:(1) x(F(x)G(x) (F(a)G(a) (F(

17、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) F(b,c) (F(c,a) F(c,b) F(c,c)37實(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下求下列

18、各式的真值下求下列各式的真值:(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) 038實(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)39前束范式前束范式定義定義3.11 設(shè)設(shè)A為一個一階邏輯公式為一個一階邏輯公式, 若若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)不是