離散完整ppt課件2.12

1、1第第2章章 一階邏輯一階邏輯 2.1 一階邏輯基本概念一階邏輯基本概念2.2 一階邏輯合式公式及解釋一階邏輯合式公式及解釋2.3 一階邏輯等值式一階邏輯等值式 22.1 一階邏輯基本概念一階邏輯基本概念 個體詞個體詞 謂詞謂詞 量詞量詞 一階邏輯中命題符號化一階邏輯中命題符號化 3基本概念基本概念個體詞、謂詞、量詞個體詞、謂詞、量詞 個體詞（個體）個體詞（個體）: 所研究對象中可以獨立存在的具所研究對象中可以獨立存在的具體或抽象的客體體或抽象的客體 個體常項個體常項：具體的事物，用：具體的事物，用a, b, c表示表示 個體變項個體變項：抽象的事物，用：抽象的事物，用x, y, z表示表示

2、個體域個體域: 個體變項的取值范圍個體變項的取值范圍 有限個體域有限個體域，如，如a, b, c, 1, 2 無限個體域無限個體域，如，如n, z, r, 全總個體域全總個體域: 宇宙間一切事物組成宇宙間一切事物組成 4基本概念基本概念 (續(xù)續(xù))謂詞謂詞: 表示個體詞性質(zhì)或相互之間關(guān)系的詞表示個體詞性質(zhì)或相互之間關(guān)系的詞 謂詞常項謂詞常項：f(a)：a是人是人 謂詞變項謂詞變項：f(x)：x具有性質(zhì)具有性質(zhì)f 一元謂詞一元謂詞: 表示事物的性質(zhì)表示事物的性質(zhì) 多元謂詞多元謂詞(n元謂詞元謂詞, n 2): 表示事物之間的關(guān)系表示事物之間的關(guān)系 如如 l(x,y)：x與與y有關(guān)系有關(guān)系l，l(x

3、,y)：x y， 0元謂詞元謂詞: 不含個體變項的謂詞不含個體變項的謂詞, 即命題常項或命即命題常項或命題變項題變項 5基本概念基本概念( (續(xù)續(xù)) )量詞量詞: 表示數(shù)量的詞表示數(shù)量的詞 全稱量詞全稱量詞 : 表示任意的表示任意的, 所有的所有的, 一切的等一切的等 如如 x 表示對個體域中所有的表示對個體域中所有的x 存在量詞存在量詞 : 表示存在表示存在, 有的有的, 至少有一個等至少有一個等 如如 x 表示在個體域中存在表示在個體域中存在x6一階邏輯中命題符號化一階邏輯中命題符號化 例例1 用用0元謂詞將命題符號化元謂詞將命題符號化 要求：先將它們在命題邏輯中符號化，再在一階要求：先將

4、它們在命題邏輯中符號化，再在一階 邏輯中符號化邏輯中符號化 (1) 墨西哥位于南美洲墨西哥位于南美洲 在命題邏輯中在命題邏輯中, 設(shè)設(shè) p: 墨西哥位于南美洲墨西哥位于南美洲 符號化為符號化為 p, 這是真命題這是真命題 在一階邏輯中在一階邏輯中, 設(shè)設(shè)a：墨西哥，：墨西哥，f(x)：x位于南美洲位于南美洲 符號化為符號化為f(a)7例例1(續(xù)續(xù))2233)3()2(gf (2) 是無理數(shù)僅當(dāng)是無理數(shù)僅當(dāng) 是有理數(shù)是有理數(shù) 在命題邏輯中在命題邏輯中, 設(shè)設(shè) p： 是無理數(shù)，是無理數(shù)，q： 是有理數(shù)是有理數(shù). 符號化為符號化為 p q, 這是假命題這是假命題 在一階邏輯中在一階邏輯中, 設(shè)設(shè)f(

5、x): x是無理數(shù)是無理數(shù), g(x): x是有理數(shù)是有理數(shù) 符號化為符號化為 (3) 如果如果23，則，則33，q：3y，g(x,y)：xy x(f(x)y(g(y)l(x,y) 或或 x y(f(x) g(y)l(x,y) 兩者等值兩者等值 (2) 令令f(x): x是無理數(shù)是無理數(shù), g(y): y是有理數(shù)是有理數(shù), l(x,y)：xy x(f(x)y(g(y) l(x,y) 或或 x y(f(x) g(y) l(x,y) 兩者等值兩者等值10一階邏輯中命題符號化一階邏輯中命題符號化( (續(xù)續(xù)) )幾點注意：幾點注意： 1 1元謂詞與多元謂詞的區(qū)分元謂詞與多元謂詞的區(qū)分 無特別要求，用全

6、總個體域無特別要求，用全總個體域 量詞順序一般不能隨便顛倒量詞順序一般不能隨便顛倒 否定式的使用否定式的使用思考：思考： 沒有不呼吸的人沒有不呼吸的人 不是所有的人都喜歡吃糖不是所有的人都喜歡吃糖 不是所有的火車都比所有的汽車快不是所有的火車都比所有的汽車快以上命題應(yīng)如何符號化？以上命題應(yīng)如何符號化？ 112.2 一階邏輯公式及解釋一階邏輯公式及解釋字母表字母表合式公式合式公式( (簡稱公式簡稱公式) )個體變項的自由出現(xiàn)和約束出現(xiàn)個體變項的自由出現(xiàn)和約束出現(xiàn)解釋解釋永真式（邏輯有效式）永真式（邏輯有效式）矛盾式（永假式）矛盾式（永假式）可滿足式可滿足式 12字母表字母表 定義定義 字母表字母

7、表包含下述符號：包含下述符號： (1) 個體常項：個體常項：a, b, c, , ai, bi, ci, , i 1 (2) 個體變項：個體變項：x, y, z, , xi, yi, zi, , i 1 (3) 函數(shù)符號：函數(shù)符號：f, g, h, , fi, gi, hi, , i 1 (4) 謂詞符號：謂詞符號：f, g, h, , fi, gi, hi, , i 1 (5) 量詞符號：量詞符號： , (6) 聯(lián)結(jié)詞符號：聯(lián)結(jié)詞符號： , , , , (7) 括號與逗號：括號與逗號：(, ), ， 13項項 定義定義 項項的定義如下：的定義如下： (1) 個體常項和個體變項是項個體常項和個

8、體變項是項. (2) 若若 (x1, x2, , xn)是任意的是任意的n元函數(shù)，元函數(shù)，t1,t2,tn是任意的是任意的n個項，則個項，則 (t1, t2, , tn) 是項是項. (3) 所有的項都是有限次使用所有的項都是有限次使用 (1), (2) 得到的得到的.個體常項、變項是項，由它們構(gòu)成的個體常項、變項是項，由它們構(gòu)成的n元函數(shù)和復(fù)元函數(shù)和復(fù)合函數(shù)還是項合函數(shù)還是項14原子公式原子公式 定義定義 設(shè)設(shè)r(x1, x2, , xn)是任意的是任意的n元謂詞，元謂詞，t1,t2, tn是任意的是任意的n個項，則稱個項，則稱r(t1, t2, , tn)是是原子公式原子公式. 原子公式是

9、由項組成的原子公式是由項組成的n元謂詞元謂詞. 例如，例如，f(x,y), f(f(x1,x2),g(x3,x4)等均為原子公式等均為原子公式 15合式公式合式公式 定義定義 合式公式合式公式（簡稱（簡稱公式公式）定義如下：）定義如下： (1) 原子公式是合式公式原子公式是合式公式. (2) 若若a是合式公式，則是合式公式，則 ( a)也是合式公式也是合式公式 (3) 若若a, b是合式公式，則是合式公式，則(a b), (a b), (ab), (ab)也是合式公式也是合式公式 (4) 若若a是合式公式，則是合式公式，則 xa, xa也是合式公式也是合式公式 (5) 只有有限次地應(yīng)用只有有限

10、次地應(yīng)用(1)(4)形成的符號串是合形成的符號串是合 式公式式公式.請舉出幾個合式公式的例子請舉出幾個合式公式的例子. 16個體變項的自由出現(xiàn)與約束出現(xiàn)個體變項的自由出現(xiàn)與約束出現(xiàn) 定義定義 在公式在公式 xa和和 xa中，稱中，稱x為為指導(dǎo)變元指導(dǎo)變元，a為相為相應(yīng)量詞的應(yīng)量詞的轄域轄域. 在在 x和和 x的的轄域轄域中，中，x的所有出現(xiàn)都的所有出現(xiàn)都稱為稱為約束出現(xiàn)約束出現(xiàn)，a中不是約束出現(xiàn)的其他變項均稱中不是約束出現(xiàn)的其他變項均稱為是為是自由出現(xiàn)的自由出現(xiàn)的.例如例如, 在公式在公式 x(f(x,y)g(x,z) 中中, a=(f(x,y)g(x,z)為為 x的轄域，的轄域， x為指導(dǎo)變

11、元為指導(dǎo)變元, a中中x的兩次出現(xiàn)均為約束出現(xiàn)，的兩次出現(xiàn)均為約束出現(xiàn)， y與與z均為自由出現(xiàn)均為自由出現(xiàn). 閉式閉式: 不含自由出現(xiàn)的個體變項的公式不含自由出現(xiàn)的個體變項的公式.17公式的解釋與分類公式的解釋與分類 給定公式給定公式 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)x f(x) 有成真解釋嗎？有成真解釋嗎？ xf(x)x f(x) 有成假解

12、釋嗎？有成假解釋嗎？ 18解釋解釋 faffa定義定義 解釋解釋i由下面由下面4部分組成：部分組成： (a) 非空個體域非空個體域di (b) di中一些特定元素中一些特定元素 等等 (c) di上一些特定函數(shù)上一些特定函數(shù) 等等 (d) di上一些特定謂詞上一些特定謂詞 等等說明：說明： 被解釋的公式被解釋的公式a中的個體變項均取值于中的個體變項均取值于di 若若a中含個體常項中含個體常項a、 函數(shù)函數(shù)f、 謂詞謂詞f, 就分別解釋就分別解釋成成 、 、f19解釋解釋 (續(xù)續(xù))被解釋的公式不一定全部包含解釋中的被解釋的公式不一定全部包含解釋中的4部分部分. 閉式在任何解釋下都是命題，閉式在任

13、何解釋下都是命題，注意不是閉式的公式在某些解釋下也可能是命注意不是閉式的公式在某些解釋下也可能是命題題. .20公式的分類公式的分類 永真式（邏輯有效式）永真式（邏輯有效式）：無成假賦值：無成假賦值矛盾式（永假式）矛盾式（永假式）：無成真賦值：無成真賦值可滿足式可滿足式：至少有一個成真賦值：至少有一個成真賦值幾點說明：幾點說明：永真式為可滿足式，但反之不真永真式為可滿足式，但反之不真謂詞公式的可滿足性（永真性謂詞公式的可滿足性（永真性, ,永假性永假性) )是不可判是不可判定的定的利用代換實例可判某些公式的類型利用代換實例可判某些公式的類型 21代換實例代換實例 定義定義 設(shè)設(shè)a0是含命題變項

14、是含命題變項p1, p2, ,pn的命題公式，的命題公式， a1,a2,an是是n個謂詞公式，用個謂詞公式，用ai處處代替處處代替a0中的中的pi (1 i n) ，所得公式，所得公式a稱為稱為a0的的代換實例代換實例. 例如例如: f(x)g(x), xf(x)yg(y) 等都是等都是pq的換實例，的換實例， x(f(x)g(x) 等不是等不是 pq 的代換實例的代換實例. 定理定理 重言式的代換實例都是永真式，矛盾式的代重言式的代換實例都是永真式，矛盾式的代換實例都是矛盾式換實例都是矛盾式. 22代換實例代換實例( (續(xù)續(xù)) )例例1 1 給定解釋給定解釋i i 如下如下: : (a) 個

15、體域個體域 d=n (b) (c) (d) 謂詞謂詞說明下列公式在說明下列公式在 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例例1( (續(xù)續(xù)) )(3) x y zf(f(x,y),z)兩點說明兩點說明:5個小題都是閉式個小題都是閉式,在在i下全是命題下全是命題(3)與與(5)說明，量詞順序不能隨意改變說明，量詞順序不能隨意改變 (5) x y zf(f(y,z),x) x y z (y+z=x) 假命題假命題(4) xf(f(x,x),g(x,x)