離散數(shù)學(xué)第2章一階邏輯.ppt

1、1,第2章 一階邏輯,一階邏輯基本概念、命題符號化 一階邏輯公式、解釋及分類 一階邏輯等值式、前束范式 一階邏輯推理理論,2,例 “蘇格拉底三段論” 人都是要死的.(p) 蘇格拉底是人.(q) 所以蘇格拉底是要死的.(r) 在命題邏輯中，推理的形式結(jié)構(gòu)： （p q） r (不是重言式) 原因：命題邏輯中，p、q、r之間的內(nèi)在聯(lián)系沒有反映出來. 方法：反映p、q、r內(nèi)在聯(lián)系，對簡單命題進一步分析.,3,2.1 一階邏輯基本概念,個體詞 謂詞 量詞 一階邏輯中命題符號化,4,基本概念個體詞、謂詞、量詞,個體詞（個體）: 所研究對象中可以獨立存在的具體或抽象的客體，它可以是一個具體的事物，也可以是一

2、個抽象的概念. 表示主語的詞（名詞或代詞）：蘇格拉底，2，黑板，自然數(shù)，思想，定理. 個體常項：具體的或特定的個體詞， 用a, b, c表示 個體變項：抽象的或泛指的個體詞， 用x, y, z表示 個體域: 個體變項的取值范圍 有限個體域，如a, b, c, 1, 2 無限個體域，如N, Z, R, 全總個體域: 宇宙間一切事物組成,5,基本概念 (續(xù)),謂詞: 表示個體詞的性質(zhì)或相互之間關(guān)系的詞 謂詞常項：表示具體性質(zhì)或關(guān)系的謂詞 F: 是人，F(xiàn)(a)：a是人 G： 是自然數(shù)， F(2)：2是自然數(shù) 謂詞變項：表示抽象的或泛指的謂詞 F: 具有性質(zhì)F，F(xiàn)(x)：x具有性質(zhì)F 元數(shù)：謂詞中所包

3、含的個體詞數(shù) 一元謂詞: 表示事物的性質(zhì) 多元謂詞(n元謂詞, n2): 表示個體詞之間的關(guān)系 如 L(x,y)： x與y有關(guān)系L， L(x,y)： x比y高2厘米 注意：多元謂詞中，個體變項的順序不能隨意改動,6,個體變項和謂詞的聯(lián)合體，F(xiàn)(x),L(x,y)，也稱為謂詞 n元謂詞 L(x1, x2, xn)可看作一個函數(shù)，定義域為個體變項的個體域，值域為0,1 n元謂詞 L(x1, x2, xn)的真值不確定，不是命題, 如：L(x,y) 如果L(x,y)表示 “x小于y”，謂詞部分已經(jīng)是常項，但 還不是命題. 考慮L(2,3)和L(3,2) L(x1, x2, xn)是命題：只有當L是常

4、項， x1, x2, xn是個體常項 0元謂詞: 不含個體變項的謂詞, 如L(a, b) 如L的意義明確，則0元謂詞都是命題,7,一階邏輯中命題符號化,例1 用0元謂詞將命題符號化 要求：先將它們在命題邏輯中符號化，再在一階 邏輯中符號化 (1) 墨西哥位于南美洲 在命題邏輯中, 設(shè) p: 墨西哥位于南美洲 符號化為 p, 這是真命題 在一階邏輯中, 設(shè)a：墨西哥，F(xiàn)(x)：x位于南美洲 符號化為F(a),8,例1(續(xù)),(2) 是無理數(shù)僅當 是有理數(shù) 在命題邏輯中, 設(shè) p： 是無理數(shù)，q： 是有理數(shù). 符號化為 p q, 這是假命題 在一階邏輯中, 設(shè)F(x): x是無理數(shù), G(x):

5、x是有理 數(shù)符號化為 (3) 如果23，則33，q：3y，G(x,y)：xy, 符號化為 F(2,3)G(3,4),9,例1(續(xù)) （4）如果張明比李民高，李民比趙亮高，則張明比趙亮高. 在命題邏輯中, 設(shè) p：張明比李民高，q：李民比趙亮高, r:張明比趙亮高. 符號化為： p q r 在一階邏輯中, 設(shè) F(x,y)：x比y高 a:張明，b:李民，c:趙亮 符號化為： F(a, b) F(b, c) F(a, c),10,基本概念(續(xù)) 量詞: 表示數(shù)量的詞 例如 （1）所有的人都要死的； （2）有的人活一百歲以上； 全稱量詞: 表示任意的, 所有的, 一切的等 x 表示對個體域中所有的個

6、體， x F(x)表示個體域中所有的個體都有性質(zhì)F. x F(x)，其中F(x)： x是要死的，個體域為人類集合 存在量詞: 表示存在著, 有的, 有一個，至少有一個等 x 表示存在個體域中的個體， x F(x)表示存在著個體域中的個體具有有性質(zhì)F x G(x)，其中G (x)： x活一百歲以上，個體域為人類集合,11,如果個體域D為全總個體域，則 x F(x)，其中F(x)： x是要死的，表示宇宙間的一切事物都要死的. x G(x)，其中G (x)： x活一百歲以上，表示宇宙間的一切事物中存在活一百歲以上的. 特性謂詞： M(x): x是人 符號化為： （1）x （M(x) F(x)） （2

7、） x （M(x) G(x)） 考慮： （1）x （M(x) F(x)） （2） x （M(x) G(x)）,12,一階邏輯中命題符號化(續(xù)),例2 在一階邏輯中將下面命題符號化 (1)人都愛美; (2) 有人用左手寫字 分別取(a) D為人類集合, (b) D為全總個體域 . 解：(a) (1) 設(shè)G(x)：x愛美, 符號化為 x G(x) (2) 設(shè)G(x)：x用左手寫字, 符號化為 x G(x) (b) 設(shè)F(x)：x為人，G(x)：同(a)中 (1) x (F(x)G(x) (2) x (F(x)G(x) 這是兩個基本公式, 注意這兩個基本公式的使用.,13,一階邏輯中命題符號化(續(xù))

8、,例3 在一階邏輯中將下面命題符號化 (1) 正數(shù)都大于負數(shù) (2) 有的無理數(shù)大于有的有理數(shù) 解 注意: 題目中沒給個體域, 一律用全總個體域 (1) 令F(x): x為正數(shù), G(y): y為負數(shù), L(x,y): xy x(F(x)y(G(y)L(x,y) 或 xy(F(x)G(y)L(x,y) 兩者等值 (2) 令F(x): x是無理數(shù), G(y): y是有理數(shù), L(x,y)：xy x(F(x)y(G(y)L(x,y) 或 xy(F(x)G(y)L(x,y) 兩者等值,14,一階邏輯中命題符號化(續(xù)),幾點注意： 1元謂詞與多元謂詞的區(qū)分 無特別要求，用全總個體域 量詞順序一般不要隨

9、便顛倒 例：對任意x，存在著y，使得x+y=5. 個體域為實數(shù)集. 符號化為： x y H（x,y), 其中H（x,y):x+y=5 考慮 y x H（x,y) 否定式的使用,15,例：在一界邏輯中命題符號化 沒有不呼吸的人 不是所有的人都喜歡吃糖 不是所有的火車都比所有的汽車快 x( F(x) G(x) 其中F(x)：x是人， G(x)：x呼吸 或者： x( F(x) G(x) x( F(x) G(x) 其中F(x)：x是人， G(x)：x喜歡吃糖 或者： x( F(x) G(x) x( F(x) y (G(y) H(x,y) ) 或者： x( F(x) y (G(y) H(x,y) ),1

10、6,例：在一界邏輯中命題符號化 一切人都不一樣高 每個自然數(shù)都有后繼數(shù) 有的自然數(shù)無先驅(qū)數(shù) x y( F(x) F(y) G(x,y) H(x,y) 其中F(x)：x是人， G(x,y) :x和y不是同一個人， H(x,y)： x和y一樣高 或者： x y( F(x) F(y) G(x,y) H(x,y) x( F(x) y(G(y) H(x,y) 其中F(x)：x是自然數(shù)， H(x,y) ：y是x的后繼數(shù) 或者： x( F(x) L(x) ， L(x) ：x有后繼數(shù) x( F(x) y(G(y) H(x,y) 或者： x( F(x) L(x) ) ，L(x) ：x有先驅(qū)數(shù),17,2.2 一階

11、邏輯公式及解釋,字母表 合式公式(簡稱公式) 個體變項的自由出現(xiàn)和約束出現(xiàn) 解釋 永真式（邏輯有效式） 矛盾式（永假式） 可滿足式,18,字母表,定義 字母表包含下述符號： (1) 個體常項：a, b, c, , ai, bi, ci, , i 1 (2) 個體變項：x, y, z, , xi, yi, zi, , i 1 (3) 函數(shù)符號：f, g, h, , fi, gi, hi, , i 1 (4) 謂詞符號：F, G, H, , Fi, Gi, Hi, , i 1 (5) 量詞符號：, (6) 聯(lián)結(jié)詞符號：, , , , (7) 括號與逗號：( , ), ，,19,項,定義 項的定義如

12、下： (1) 個體常項和個體變項是項. (2) 若(x1, x2, , xn)是任意的n元函數(shù)，t1,t2,tn 是任意的n個項，則(t1, t2, , tn) 是項. (3) 所有的項都是有限次使用 (1), (2) 得到的. 例：a，b，x，y，f(x,y)=x+y， g(x,y)=x-y都是項 f(a, g(x,y)=a+ (x-y)是項 其實, 個體常項、變項是項，由它們構(gòu)成的n元函數(shù) 和復(fù)合函數(shù)還是項,20,原子公式,定義 設(shè)R(x1, x2, , xn)是任意的n元謂詞，t1,t2, tn 是任意的n個項，則稱R(t1, t2, , tn)是原子公式. 其實，原子公式是由項組成的n

13、元謂詞. 例如，F(xiàn)(x,y), F(f(x1,x2),g(x3,x4)等均為原子公式,21,合式公式,定義 合式公式（簡稱公式）定義如下： (1) 原子公式是合式公式. (2) 若A是合式公式，則 (A)也是合式公式 (3) 若A, B是合式公式，則(AB), (AB), (AB), (AB)也是合式公式 (4) 若A是合式公式，則xA, xA也是合式公式 (5) 只有有限次地應(yīng)用(1)(4)形成的符號串 才是合式公式(謂詞公式).,22,個體變項的自由出現(xiàn)與約束出現(xiàn),定義 在公式xA和xA中，稱x為指導(dǎo)變元，A為相 應(yīng)量詞的轄域. 在x和x的轄域中，x的所有出現(xiàn)都 稱為約束出現(xiàn)，A中不是約束

14、出現(xiàn)的其他變項均稱 為是自由出現(xiàn)的. 例如, 在公式 x(F(x,y)G(x,z) 中, A=(F(x,y)G(x,z)為x的轄域， x為指導(dǎo)變項, A中x的兩次出現(xiàn)均為約束出現(xiàn)， y與z均為自由出現(xiàn). 閉式: 不含自由出現(xiàn)的個體變項的公式.,23,例1：x(F(x) y H(x,y) ) y H(x,y)中， y 為指導(dǎo)變項， 的轄域為H(x,y)，其中y 為約束出現(xiàn)的， x為自由出現(xiàn)的. 在整個合式公式中， x為指導(dǎo)變項， 的轄域為(F(x) y H(x,y) )，其中x與y 都是約束出現(xiàn)的， x約束出現(xiàn)2次， y約束出現(xiàn)1次. 例2：x y(R(x,y) L(y,z) ) x H(x,y

15、) x y(R(x,y) L(y,z) )中， x,y都是指導(dǎo)變項，轄域為(R(x,y) L(y,z) )， x與y 都是約束出現(xiàn)的， z為自由出現(xiàn)的. x H(x,y)中， x 為指導(dǎo)變項， 的轄域為H(x,y)，其中x 為約束出現(xiàn)的， y為自由出現(xiàn)的 在此公式中， x 為約束出現(xiàn)的，y為約束出現(xiàn)的，又為自由出現(xiàn)的. z為自由出現(xiàn)的.,24,換名規(guī)則 將量詞轄域中出現(xiàn)的某個約束出現(xiàn)的個體變項及對應(yīng)的指導(dǎo)變項，改成另一個轄域中未出現(xiàn)過的個體變項符號，公式中的其余部分不變。 例：xF(x) G(x,y) 換名規(guī)則：zF(z) G(x,y) 代替規(guī)則 將某個自由出現(xiàn)的個體變項及對應(yīng)的指導(dǎo)變項，改成

16、公式中未出現(xiàn)過的個體變項符號，處處代替。 代替規(guī)則：xF(x) G(z,y) 用處：不存在既是約束出現(xiàn)，又是自由出現(xiàn)的個體變項,25,公式的解釋與分類,給定公式 A=x(F(x)G(x) 成真解釋: 個體域N, F(x): x2, G(x): x1 代入得A=x(x2x1) 真命題 成假解釋: 個體域N, F(x): x1, G(x): x2 代入得A=x(x1x2) 假命題 問: xF(x)xF(x) 有成真解釋嗎？ xF(x)xF(x) 有成假解釋嗎？,26,解釋,定義 解釋I由下面4部分組成： (a)非空個體域DI (b)DI中一些特定元素 (c)DI上特定函數(shù)集合 (d)DI上特定謂詞

17、的集合 說明： 1 將公式的個體常項用I的特定常項代替，函數(shù)和謂詞用I的特定函數(shù)和 謂詞代替 2 被解釋的公式不一定全部包含解釋中的4部分. 3 閉式在任何解釋下都是命題， 4 不是閉式的公式在某些解釋下也可能是命題.,27,例 給定解釋I： (a)DI2,3 (b)DI中特定元素a=2 (c)DI上特定函數(shù)f(x) :f(2)=3, f(3)=2 (d) DI上特定謂詞F(x) :F(2)=0, F(3)=1， G(x,y)為G(i,j)=1, 其中i,j=2,3 1） x（F(x) G(x,a) （F(2) G(2,2) （F(3) G(3,2) (01) (1 1) 0 假命題 2) x

18、( F(f(x) G(x, f(x) ) ( F(f(2) G(2, f(2) ) ( F(f(3) G(3, f(3) ) ( F(3) G(2, 3) ) ( F(2) G(3, 2) ) ( 1 1 ) ( 0 1 ) 1 真命題,28,例 給定解釋： (a)個體域為自然數(shù)集合DN (b)DN中特定元素a=0 (c)DN上特定函數(shù)f(x,y)= x+y , g(x,y)= x.y (d) DN上特定謂詞F(x,y) 為xy 1） xF(g(x,a), x) xF(x.0 , x) x(x.0= x) 假命題 2) x y( F(f(x,a),y) F(f(y,a),x) ) x y( F

19、(0+x,y) F(y+0,x) ) x y ( (0+x=y) (y+0=x) ) 真命題 3) x y F(f(x,y), g(x,y) x y F(x+y, x.y) x y (x+y= x.y)假命題 4) F(f(x,y), f(y,z) F(x+y, y+z) x+y= y+z 不是命題,29,例1 給定解釋I 如下: (a) 個體域 D=N (b) (c) (d) 謂詞 說明下列公式在 I 下的涵義,并討論真值 (1) xF(g(x,a),x),x(2x=x) 假命題,(2) xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x) 假命題,30,例1(續(xù)),(3) xyzF(f(x,y),z),兩點說明: 5個小題都是閉式,在I下全是命題 (3)與(5)說明，量詞順序不能隨意改變,(5) xyzF(f(y,z),x),xyz (y+z=x) 假命題,(4) xF(f(x,x),g(x,x),x(2x=x2) 真命題,xyz (x+y=z) 真命題,31,公式的分類,永真式（邏輯有效式）：公式在任何解釋下都是真的，即無成假賦值 矛盾式（永假式）：公式在任何解釋下都是假的，