1、1,第2章 一階邏輯,一階邏輯基本概念、命題符號(hào)化 一階邏輯公式、解釋及分類 一階邏輯等值式、前束范式 一階邏輯推理理論,2,蘇格拉底三段論,凡人都是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,3,2.1 一階邏輯基本概念,個(gè)體詞 謂詞 量詞 一階邏輯中命題符號(hào)化,4,基本概念個(gè)體詞、謂詞、量詞,個(gè)體詞（個(gè)體）: 所研究對(duì)象中可以獨(dú)立存在的具 體或抽象的客體 謂詞: 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞 2是素?cái)?shù)。 張三是程序員。 小李比小王大三歲。,5,基本概念個(gè)體詞、謂詞、量詞,個(gè)體詞（個(gè)體）: 所研究對(duì)象中可以獨(dú)立存在的具 體或抽象的客體 個(gè)體常項(xiàng)：具體的事務(wù)，用a, b, c表示 個(gè)

2、體變項(xiàng)：抽象的事物，用x, y, z表示 個(gè)體域: 個(gè)體變項(xiàng)的取值范圍 有限個(gè)體域，如a, b, c, 1, 2 無(wú)限個(gè)體域，如N, Z, R, 全總個(gè)體域: 宇宙間一切事物組成,6,基本概念 (續(xù)),謂詞: 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞 謂詞常項(xiàng)：F: 是人，F(xiàn)(a)：a是人 謂詞變項(xiàng)：F: 具有性質(zhì)F，F(xiàn)(x)：x具有性質(zhì)F 一元謂詞: 表示事物的性質(zhì) 多元謂詞(n元謂詞, n2): 表示事物之間的關(guān)系 如 L(x,y)：x與y有關(guān)系L，L(x,y)：xy， 0元謂詞: 不含個(gè)體變項(xiàng)的謂詞, 即命題常項(xiàng)或命 題變項(xiàng),7,基本概念 (續(xù)),例 將下列命題用0元謂詞符號(hào)化 （1）2是素?cái)?shù)且

3、是偶數(shù)。 （2）如果2大于3，則2大于4。 （3）如果張明比李民高，李民比趙亮高，則張明比趙亮高。 問(wèn)題：如何表示 （1）所有的人都是要死的。 （2）有的人活百歲以上。,8,基本概念(續(xù)),量詞: 表示數(shù)量的詞 全稱量詞: 表示任意的, 所有的, 一切的等 如 x 表示對(duì)個(gè)體域中所有的x 存在量詞: 表示存在, 有的, 至少有一個(gè)等 如 x 表示在個(gè)體域中存在x 問(wèn)題：如何表示 （1）所有的人都是要死的。 （2）有的人活百歲以上。,9,一階邏輯中命題符號(hào)化(續(xù)),幾點(diǎn)注意： 個(gè)體域的不同。無(wú)特別要求，用全總個(gè)體域。 特性謂詞的兩種形式 全稱量詞與合取式；存在量詞與析取式 量詞順序一般不要隨便顛

4、倒 否定式的使用 思考： 沒(méi)有不呼吸的人 不是所有的人都喜歡吃糖 不是所有的火車都比所有的汽車快 以上命題應(yīng)如何符號(hào)化？,10,一階邏輯中命題符號(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),11,例1(續(xù)),(2) 2是質(zhì)數(shù)僅當(dāng) 4是奇數(shù) 在命題邏輯中, 設(shè) p：2是質(zhì)數(shù)，q：4是奇數(shù). 符號(hào)化為 p q, 這是假命題 在一階邏輯中, 設(shè)F(x): x是質(zhì)數(shù), G(x): x是奇

5、數(shù) 符號(hào)化為F(2)G(4) (3) 如果23，則33，q：3y，G(x,y)：xy, 符號(hào)化為 F(2,3)G(3,4),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,一階邏輯中命

6、題符號(hào)化(續(xù)),例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ù)),思考： 不存在最大的自然數(shù)。,15,2.2 一階邏輯公式及解釋,字母

7、表 合式公式(簡(jiǎn)稱公式) 個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn) 解釋 永真式（邏輯有效式） 矛盾式（永假式） 可滿足式,16,字母表,定義 字母表包含下述符號(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)：(, ), ，,17,項(xiàng),定義 項(xiàng)的定義如下： (1) 個(gè)體常項(xiàng)

8、和個(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) 得到的. 其實(shí), 個(gè)體常項(xiàng)、變項(xiàng)是項(xiàng)，由它們構(gòu)成的n元函數(shù) 和復(fù)合函數(shù)還是項(xiàng) 項(xiàng)在謂詞公式中起的是名詞的作用，不是句子。,18,關(guān)于函數(shù)與謂詞（注意區(qū)分）,D是個(gè)體名稱集，xD，a:張三，b:李四 x,a,b都是項(xiàng) f(x): x的父親 函數(shù)，f(a)仍是項(xiàng) s(x,y): x,y的兒子 函數(shù)，s(a,b)仍是項(xiàng) f(f(x):x的祖父 函數(shù)，f(f(a)仍是項(xiàng) P(x,y): x是y的父親 謂詞,

9、19,原子公式,公式的最小單位，最小的句子單位。 定義 設(shè)R(x1, x2, , xn)是任意的n元謂詞，t1,t2, tn 是任意的n個(gè)項(xiàng)，則稱R(t1, t2, , tn)是原子公式. 其實(shí)，原子公式是由項(xiàng)組成的n元謂詞. 例如，F(xiàn)(x,y), F(f(x1,x2),g(x3,x4)等均為原子公式,20,合式公式,定義 合式公式（簡(jiǎn)稱公式）定義如下： (1) 原子公式是合式公式. (2) 若A是合式公式，則 (A)也是合式公式 (3) 若A, B是合式公式，則(AB), (AB), (AB), (AB)也是合式公式 (4) 若A是合式公式，則xA, xA也是合式公式 (5) 只有有限次地應(yīng)

10、用(1)(4)形成的符號(hào)串 才是合式公式. 請(qǐng)舉出幾個(gè)合式公式的例子.,21,個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn),定義 在公式xA和xA中，稱x為指導(dǎo)變?cè)珹為相 應(yīng)量詞的轄域. 在x和x的轄域中，x的所有出現(xiàn)都 稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)均稱 為是自由出現(xiàn)的. 例如, 在公式 x(F(x,y)G(x,z) 中, A=(F(x,y)G(x,z)為x的轄域， x為指導(dǎo)變?cè)? A中x的兩次出現(xiàn)均為約束出現(xiàn)， y與z均為自由出現(xiàn). 閉式: 不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式.,22,換名規(guī)則與代替規(guī)則,換名規(guī)則 將量詞轄域中某個(gè)約束出現(xiàn)的個(gè)體變項(xiàng)及對(duì)應(yīng)的指導(dǎo)變項(xiàng)，改成公式中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)

11、，公式其余部分不變。 代替規(guī)則 對(duì)某自由出現(xiàn)的個(gè)體變項(xiàng)用與原公式中所有個(gè)體變項(xiàng)符號(hào)不同的變項(xiàng)符號(hào)去代替，且處處代替。,23,解釋,定義 解釋I由下面4部分組成： (a)非空個(gè)體域DI (b)DI中一些特定元素的集合 (c)DI上特定函數(shù)集合 (d)DI上特定謂詞的集合 說(shuō)明： 在解釋的定義中引進(jìn)了元語(yǔ)言符號(hào), 如 等 被解釋的公式A中的個(gè)體變項(xiàng)均取值于DI 若A中含個(gè)體常項(xiàng)ai，就解釋成,24,公式的解釋與分類,給定公式 A=x(F(x)G(x) 成真解釋: 個(gè)體域N, F(x): x2, G(x): x1 代入得A=x(x2x1) 真命題 成假解釋: 個(gè)體域N, F(x): x1, G(x)

12、: x2 代入得A=x(x1x2) 假命題 問(wèn): xF(x)xF(x) 有成真解釋嗎？ xF(x)xF(x) 有成假解釋嗎？,25,解釋 (續(xù)),說(shuō)明： 1、被解釋的公式不一定全部包含解釋中的4部分。 2、一個(gè)謂詞公式若無(wú)自由變?cè)ㄩ]式），則在一個(gè)解釋下，可得確定真值。即閉式在任何解釋下都是命題。 3、公式的解釋并不對(duì)變?cè)M(jìn)行指定。若公式中含有自由變?cè)?，即使?duì)公式進(jìn)行了指派，也僅是一個(gè)命題函數(shù)，一般得不到確定的真值。 4、公式的解釋有無(wú)數(shù)種，因而謂詞邏輯的公式不可能有真值表。 不是閉式的公式在某些情況下也可能成為命題。,26,公式的分類,永真式（邏輯有效式）：無(wú)成假賦值 矛盾式（永假式）：無(wú)成

13、真賦值 可滿足式：至少有一個(gè)成真賦值 幾點(diǎn)說(shuō)明： 永真式可為可滿足式，但反之不真 判斷公式是否為永真式不是易事 某些代換實(shí)例可判公式類型,27,代換實(shí)例,定義 設(shè)A0是含命題變項(xiàng)p1, p2, ,pn的命題公式， A1,A2,An是n個(gè)謂詞公式，用Ai處處代替A0中的pi (1in) ，所得公式A稱為A0的代換實(shí)例. 例如: F(x)G(x), xF(x)yG(y)等都是pq的代換實(shí)例， x(F(x)G(x) 等不是 pq 的代換實(shí)例. 定理 重言式的代換實(shí)例都是永真式，矛盾式的代 換實(shí)例都是矛盾式.,28,本節(jié)例題,例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) 假命題,29,例1(續(xù)),(3) xyzF(f(x,y),z),兩點(diǎn)說(shuō)明: 5個(gè)小題都是閉式,在I下全是命題 (3)與(5)說(shuō)明，量詞順序不能隨意改變,(5) xy