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

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

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

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

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

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

6、體， x F(x)表示個(gè)體域中所有的個(gè)體都有性質(zhì)F. x F(x)，其中F(x)： x是要死的，個(gè)體域?yàn)槿祟惣?存在量詞: 表示存在著, 有的, 有一個(gè)，至少有一個(gè)等 x 表示存在個(gè)體域中的個(gè)體， x F(x)表示存在著個(gè)體域中的個(gè)體具有有性質(zhì)F x G(x)，其中G (x)： x活一百歲以上，個(gè)體域?yàn)槿祟惣?11,如果個(gè)體域D為全總個(gè)體域，則 x F(x)，其中F(x)： x是要死的，表示宇宙間的一切事物都要死的. x G(x)，其中G (x)： x活一百歲以上，表示宇宙間的一切事物中存在活一百歲以上的. 特性謂詞： M(x): x是人 符號(hào)化為： （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,一階邏輯中命題符號(hào)化(續(xù)),例2 在一階邏輯中將下面命題符號(hào)化 (1)人都愛(ài)美; (2) 有人用左手寫字 分別取(a) D為人類集合, (b) D為全總個(gè)體域 . 解：(a) (1) 設(shè)G(x)：x愛(ài)美, 符號(hào)化為 x G(x) (2) 設(shè)G(x)：x用左手寫字, 符號(hào)化為 x G(x) (b) 設(shè)F(x)：x為人，G(x)：同(a)中 (1) x (F(x)G(x) (2) x (F(x)G(x) 這是兩個(gè)基本公式, 注意這兩個(gè)基本公式的使用.,13,一階邏輯中命題符號(hào)化(續(xù))

8、,例3 在一階邏輯中將下面命題符號(hào)化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無(wú)理數(shù)大于有的有理數(shù) 解 注意: 題目中沒(méi)給個(gè)體域, 一律用全總個(gè)體域 (1) 令F(x): x為正數(shù), G(y): y為負(fù)數(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是無(wú)理數(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,一階邏輯中命題符號(hào)化(續(xù)),幾點(diǎn)注意： 1元謂詞與多元謂詞的區(qū)分 無(wú)特別要求，用全總個(gè)體域 量詞順序一般不要隨

9、便顛倒 例：對(duì)任意x，存在著y，使得x+y=5. 個(gè)體域?yàn)閷?shí)數(shù)集. 符號(hào)化為： x y H（x,y), 其中H（x,y):x+y=5 考慮 y x H（x,y) 否定式的使用,15,例：在一界邏輯中命題符號(hào)化 沒(méi)有不呼吸的人 不是所有的人都喜歡吃糖 不是所有的火車都比所有的汽車快 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,例：在一界邏輯中命題符號(hào)化 一切人都不一樣高 每個(gè)自然數(shù)都有后繼數(shù) 有的自然數(shù)無(wú)先驅(qū)數(shù) x y( F(x) F(y) G(x,y) H(x,y) 其中F(x)：x是人， G(x,y) :x和y不是同一個(gè)人， 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、邏輯公式及解釋,字母表 合式公式(簡(jiǎn)稱公式) 個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn) 解釋 永真式（邏輯有效式） 矛盾式（永假式） 可滿足式,18,字母表,定義 字母表包含下述符號(hào)： (1) 個(gè)體常項(xiàng)：a, b, c, , ai, bi, ci, , i 1 (2) 個(gè)體變項(xiàng)：x, y, z, , xi, yi, zi, , i 1 (3) 函數(shù)符號(hào)：f, g, h, , fi, gi, hi, , i 1 (4) 謂詞符號(hào)：F, G, H, , Fi, Gi, Hi, , i 1 (5) 量詞符號(hào)：, (6) 聯(lián)結(jié)詞符號(hào)：, , , , (7) 括號(hào)與逗號(hào)：( , ), ，,19,項(xiàng),定義 項(xiàng)的定義如

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

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

14、出現(xiàn)的其他變項(xiàng)均稱 為是自由出現(xiàn)的. 例如, 在公式 x(F(x,y)G(x,z) 中, A=(F(x,y)G(x,z)為x的轄域， x為指導(dǎo)變項(xiàng), A中x的兩次出現(xiàn)均為約束出現(xiàn)， y與z均為自由出現(xiàn). 閉式: 不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式.,23,例1：x(F(x) y H(x,y) ) y H(x,y)中， y 為指導(dǎo)變項(xiàng)， 的轄域?yàn)镠(x,y)，其中y 為約束出現(xiàn)的， x為自由出現(xiàn)的. 在整個(gè)合式公式中， x為指導(dǎo)變項(xiàng)， 的轄域?yàn)?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)變項(xiàng)，轄域?yàn)?R(x,y) L(y,z) )， x與y 都是約束出現(xiàn)的， z為自由出現(xiàn)的. x H(x,y)中， x 為指導(dǎo)變項(xiàng)， 的轄域?yàn)镠(x,y)，其中x 為約束出現(xiàn)的， y為自由出現(xiàn)的 在此公式中， x 為約束出現(xiàn)的，y為約束出現(xiàn)的，又為自由出現(xiàn)的. z為自由出現(xiàn)的.,24,換名規(guī)則 將量詞轄域中出現(xiàn)的某個(gè)約束出現(xiàn)的個(gè)體變項(xiàng)及對(duì)應(yīng)的指導(dǎo)變項(xiàng)，改成另一個(gè)轄域中未出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)，公式中的其余部分不變。 例：xF(x) G(x,y) 換名規(guī)則：zF(z) G(x,y) 代替規(guī)則 將某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)及對(duì)應(yīng)的指導(dǎo)變項(xiàng)，改成

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

17、的集合 說(shuō)明： 1 將公式的個(gè)體常項(xiàng)用I的特定常項(xiàng)代替，函數(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)個(gè)體域?yàn)樽匀粩?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) 個(gè)體域 D=N (b) (c) (d) 謂詞 說(shuō)明下列公式在 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),兩點(diǎn)說(shuō)明: 5個(gè)小題都是閉式,在I下全是命題 (3)與(5)說(shuō)明，量詞順序不能隨意改變,(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,公式的分類,永真式（邏輯有效式）：公式在任何解釋下都是真的，即無(wú)成假賦值 矛盾式（永假式）：公式在任何解釋下都是假的，