《離散數(shù)學(xué)》第二章 一階邏輯 講稿

1、離散數(shù)學(xué)講稿2.1 一階邏輯基本概念一、本節(jié)主要內(nèi)容基本概念個(gè)體詞、謂詞、量詞 命題符號(hào)化二、教學(xué)內(nèi)容個(gè)體詞（個(gè)體）: 所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體，它可以是一個(gè)具體的事物，也可以是一個(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è)體域: 宇宙間一切事物組成 基本概念 謂詞: 表示個(gè)體詞的性質(zhì)或相互之間關(guān)系的詞 謂詞常項(xiàng)：表

2、示具體性質(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ù)：謂詞中所包含的個(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) 個(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)?,1n元謂詞 L(x1, x2, xn)的真值不確定，不

3、是命題, 如：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是常項(xiàng)， x1, x2, xn是個(gè)體常項(xiàng)0元謂詞: 不含個(gè)體變項(xiàng)的謂詞, 如L(a, b) 如L的意義明確，則0元謂詞都是命題 一階邏輯中命題符號(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)例1(續(xù)) (2)

4、 是無(wú)理數(shù)僅當(dāng) 是有理數(shù) 在命題邏輯中, 設(shè) p： 是無(wú)理數(shù)，q： 是有理數(shù). 符號(hào)化為 p q, 這是假命題 在一階邏輯中, 設(shè)F(x): x是無(wú)理數(shù), G(x): x是有理 數(shù)符號(hào)化為 (3) 如果23，則33，q：3y，G(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) 或 $x$y(F(x)G(y)L(x,y) 兩者等值一階邏輯中命題符號(hào)化(續(xù))幾點(diǎn)注意： 1元謂詞與多元謂詞的區(qū)分 無(wú)特別要求，用全總個(gè)體域

5、量詞順序一般不要隨便顛倒 例：對(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) 否定式的使用例：在一界邏輯中命題符號(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

6、) H(x,y) )例：在一界邏輯中命題符號(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)

7、：x有先驅(qū)數(shù)2.2 一階邏輯公式及解釋一、本節(jié)主要內(nèi)容字母表合式公式(簡(jiǎn)稱公式)個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn)解釋永真式（邏輯有效式）矛盾式（永假式）可滿足式 二、教學(xué)內(nèi)容字母表 定義 字母表包含下述符號(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)：( ,

8、), ， 項(xiàng) 定義 項(xiàng)的定義如下： (1) 個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng). (2) 若j(x1, x2, , xn)是任意的n元函數(shù)，t1,t2,tn是任意的n個(gè)項(xiàng)，則j(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)原子公式 定義 設(shè)R(x1, x2, , xn)是任意的n元謂詞，t1,t2, tn是任意的n個(gè)項(xiàng)，則稱R(t1, t2, , tn)是原子公式. 其實(shí)，原子

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

10、是約束出現(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)的公式.例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(

11、x,y) 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)的.換名規(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)，改成公式

12、中未出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)，處處代替。 代替規(guī)則：xF(x) G(z,y)用處：不存在既是約束出現(xiàn)，又是自由出現(xiàn)的個(gè)體變項(xiàng)公式的解釋與分類 給定公式 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) 有成假解釋嗎？ 解釋 定義 解釋I由下面4部分組成： (a)非空個(gè)體域DI (b)DI中一些特定元素 (c)DI上特定函數(shù)集合 (d)DI上特定謂詞的集合 說(shuō)明：1 將公

13、式的個(gè)體常項(xiàng)用I的特定常項(xiàng)代替，函數(shù)和謂詞用I的特定函數(shù)和 謂詞代替2 被解釋的公式不一定全部包含解釋中的4部分. 3 閉式在任何解釋下都是命題，4 不是閉式的公式在某些解釋下也可能是命題.例 給定解釋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( F(f(x) G(x, f(x)

14、 ) ( 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 真命題例 給定解釋： (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(0+x,y) F(y+0,x) ) x y

15、( (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 不是命題例1 給定解釋I 如下: (a) 個(gè)體域 D=N (b) (c) (d) 謂詞說(shuō)明下列公式在 I 下的涵義,并討論真值 公式的分類 永真式（邏輯有效式）：公式在任何解釋下都是真的，即無(wú)成假賦值矛盾式（永假式）：公式在任何解釋下都是假的，即無(wú)成真賦值可滿足式：至少存在一個(gè)解釋使公式成真說(shuō)明：永真式為可滿足式，但反之不真某些代換實(shí)例可判公式類型 代

16、換實(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í)例，在謂詞公 式中都是矛盾式. 代換實(shí)例(續(xù))例2 判斷下面公式的類型 (1) xF(x) $x F(x) 解：設(shè)任意解釋Ia)如果存在a 使得F(a ) 為假，則xF(x)為假，所以xF(x) $x F(x)

17、為真b)如果對(duì)任意 x使得F(x ) 為真，則xF(x)為真，而且$x F(x) 也為真，所以xF(x) $x F(x) 為真因此，公式為永真式. (2) xF(x) (x $y G (x,y) xF(x) ) (3) xF(x) (xF(x) $y G (y) (4) (F(x,y) R(x,y) R(x,y) (5) x$y F(x,y) $ x y F(x,y) 解：解釋I1,個(gè)體域?yàn)樽匀粩?shù)集合N， F(x,y) : x等于y 此時(shí)，前件為真，后件為假 解釋I2,個(gè)體域?yàn)樽匀粩?shù)集合N， F(x,y) : x小于等于y 此時(shí)，前件為真，后件為真 因此，公式為非永真式的可滿足式 2.3 一階

18、邏輯等值式一、本節(jié)主要內(nèi)容等值式基本等值式量詞否定等值式量詞轄域收縮與擴(kuò)張等值式量詞分配等值式前束范式 二、教學(xué)內(nèi)容等值式與基本等值式基本等值式:命題邏輯中16組基本等值式的代換實(shí)例如， xF(x) xF(x) xF(x) xF(x)$yG(y) xF(x)$yG(y) (xF(x)$yG(y) xF(x)$yG(y) 基本等值式:消去量詞等值式 設(shè)D=a1,a2,an (1) xA(x)A(a1)A(a2)A(an) (2) $xA(x)A(a1)A(a2)A(an)量詞否定等值式 (1) xA(x) $ x A(x) (2) $ xA(x) x A(x) 基本等值式(續(xù))量詞轄域收縮與擴(kuò)張

19、等值式 設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xià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) 基本的等值式(續(xù))量詞分配等值式 x(A(x)B(x)xA(x)xB(x) $x(A(x)B(x)$xA(x)$xB(x)注意：對(duì)無(wú)分配律，$對(duì)無(wú)分配律 量詞等值式 x y A(x,y) y x A(x,y) $ x $ y $ y $ x A(x,y)其中A(x,y) 是x,y自由出現(xiàn)的謂詞公式基本的等值式(續(xù))例 將下面命題用兩種形式符號(hào)化 (1) 沒(méi)有不犯錯(cuò)誤的人 (2) 不是所有的人都愛(ài)看電影解

20、 (1) 令F(x)：x是人，G(x)：x犯錯(cuò)誤. $x(F(x)G(x) x(F(x)G(x) 請(qǐng)給出演算過(guò)程，并說(shuō)明理由. (2) 令F(x)：x是人，G(x)：愛(ài)看電影. x(F(x)G(x) $x(F(x)G(x) 給出演算過(guò)程，并說(shuō)明理由. 前束范式 例如，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)不是前束范式，公式的前束范式 定理（前束范式存在定理）一階邏輯中的任何公式都存在與之等值的前束范式 注意: 公式的前束范式不惟一 求公式的前束范式的方法: 利用重要等值式、 置換規(guī)則、換名規(guī)則

21、、代替規(guī)則進(jìn)行等值演算. 換名規(guī)則與代替規(guī)則 換名規(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)，公式中其余部分不變，則所得公式與原來(lái)的公式等值.代替規(guī)則: 對(duì)某自由出現(xiàn)的個(gè)體變項(xiàng)用與原公式中所有個(gè)體變項(xiàng)符號(hào)不同的符號(hào)去代替，則所得公式與原來(lái)的公式等值. 公式的前束范式(續(xù))例 求下列公式的前束范式 (1) $x(M(x)F(x)解 $x(M(x)F(x) x(M(x)F(x) （量詞否定等值式） x(M(x)F(x) 兩步結(jié)果都是前束范式，說(shuō)明前束范式不惟一.例(續(xù)) (2) xF(x)$xG(x)解 xF(x)$xG(x) xF(

22、x)xG(x) （量詞否定等值式） x(F(x)G(x) （量詞分配等值式）另有一種形式 xF(x)$xG(x) xF(x)xG(x) xF(x)yG(y) ( 代替規(guī)則 ) xy(F(x)G(y) ( 量詞轄域擴(kuò)張 )兩種形式是等值的 例(續(xù)) (3) $xF(x)xG(x) 解 $xF(x)xG(x) $xF(x)$xG(x) $x(F(x)G(x) （為什么？） 或 $x$y(F(x)G(y) （為什么？） (4) xF(x)$y(G(x,y)H(y) 解 xF(x)$y(G(x,y)H(y) zF(z)$y(G(x,y)H(y) （換名規(guī)則） $z$y(F(z)(G(x,y)H(y)

23、（為什么？）例(續(xù))或 xF(x)$y(G(z,y)H(y) （代替規(guī)則） $x$y(F(x)(G(z,y)H(y) (5) x(F(x,y)$y(G(x,y)H(x,z)解 用換名規(guī)則, 也可用代替規(guī)則, 這里用代替規(guī)則 x(F(x,y)$y(G(x,y)H(x,z) x(F(x,u)$y(G(x,y)H(x,z) x$y(F(x,u)G(x,y)H(x,z)注意：x與$y不能顛倒 2.4 一階邏輯推理理論一、本節(jié)主要內(nèi)容推理的形式結(jié)構(gòu)判斷推理是否正確的方法重要的推理定律推理規(guī)則構(gòu)造證明附加前提證明法 推理 二、教學(xué)內(nèi)容推理的形式結(jié)構(gòu)有兩種： 第一種 A1A2AkB (*) 第二種 前提：A

24、1，A2，Ak 結(jié)論： B其中 A1,A2,Ak,B為一階邏輯公式. 若(*)為永真式, 則稱推理正確, 否則稱推理不正確.判斷方法: 真值表法, 等值演算法, 主析取范式法及構(gòu)造證明法. 前3種方法采用第一種形式結(jié)構(gòu), 構(gòu)造證明法采用第二種形式結(jié)構(gòu).重要的推理定律 第一組 命題邏輯推理定律代換實(shí)例 如 xF(x)$yG(y)xF(x)為化簡(jiǎn)律代換實(shí)例. 第二組 由基本等值式生成 如 由 xA(x)$xA(x) 生成 xA(x)$xA(x), $xA(x)xA(x), 第三組 xA(x)xB(x)x(A(x)B(x) $x(A(x)B(x)$xA(x)$xB(x) x（A(x) B(x)） x

25、A(x) x B(x)） x（A(x) B(x)） $ xA(x) $ x B(x)）推理規(guī)則 (1)前提引入規(guī)則 (2)結(jié)論引入規(guī)則(3)置換規(guī)則 (4)假言推理規(guī)則(5)附加規(guī)則 (6)化簡(jiǎn)規(guī)則(7)拒取式規(guī)則 (8)假言三段論規(guī)則(9)析取三段論規(guī)則 (10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則 推理規(guī)則(續(xù))(12) 全稱量詞消去規(guī)則（簡(jiǎn)記為UI規(guī)則或UI）兩式成立的條件是： x是A(x)中的自由出現(xiàn)的個(gè)體變項(xiàng) 在第一式中，取代x的y應(yīng)為任意的不在A(x)中約束出現(xiàn)的個(gè)體變項(xiàng). 在第二式中，c為任意個(gè)體常項(xiàng). 用y或c去取代A(x)中的自由出現(xiàn)的x時(shí)，一定要在x自由出現(xiàn)的一切地方進(jìn)行取代.推理規(guī)則(續(xù))(13) 全稱量詞引入規(guī)則（簡(jiǎn)記為UG規(guī)則或UG） 該式成立的條件是： y是A(y)中自由出現(xiàn)的個(gè)體變項(xiàng)； 無(wú)論y取何值，A(y)應(yīng)該均為真； 取代自由出現(xiàn)的y的x，也不能在A(y)中約束出現(xiàn). 推理規(guī)則(續(xù))(14) 存在量詞引入規(guī)則（簡(jiǎn)記為EG規(guī)則或EG） 該式成立的條件是： c是使A為真的特定個(gè)體常項(xiàng). 取代c的x不能在A(c)中出現(xiàn)過(guò). 推理規(guī)則(續(xù))(15) 存在量詞消去規(guī)則（簡(jiǎn)記為EI規(guī)則或EI） 該式成立的條件是： c是使A為真的特定的個(gè)體常項(xiàng). c不在A(x)中出現(xiàn). 若A(x)中除自由出現(xiàn)的x外，還有其他自由出現(xiàn)的個(gè)體變