1、廣東工業大學計算機學院1主要內容主要內容l 4.1 一階邏輯命題符號化一階邏輯命題符號化 個體詞、謂詞、量詞個體詞、謂詞、量詞 一階邏輯命題符號化一階邏輯命題符號化l 4.2 一階邏輯公式及其解釋一階邏輯公式及其解釋 一階語言一階語言 合式公式合式公式 合式公式的解釋合式公式的解釋 永真式、矛盾式、可滿足式永真式、矛盾式、可滿足式第四章第四章 一階邏輯基本概念一階邏輯基本概念廣東工業大學計算機學院2一階邏輯的引入一階邏輯的引入為什么要研究謂詞邏輯？為什么要研究謂詞邏輯？1. 為了刻畫命題內部的邏輯結構。為了刻畫命題內部的邏輯結構。 命題邏輯中主要命題邏輯中主要研究命題研究命題和和命題演算命題演

2、算，原子命題原子命題是命題演算的基是命題演算的基本單位。即：本單位。即：命題邏輯不再對原子命題進行分解命題邏輯不再對原子命題進行分解. 但實際上，某些原子命題之間具有但實際上，某些原子命題之間具有共同特征共同特征。例如：例如：張三張三是個大是個大學生學生。李四。李四是個大學生是個大學生。So: 命題邏輯無法研究命題邏輯無法研究命題內部的邏輯結構命題內部的邏輯結構及及命題之間的內在聯系命題之間的內在聯系。2. 命題邏輯在推理方面存在局限性，命題邏輯在推理方面存在局限性，有些簡單的論斷也不能用命有些簡單的論斷也不能用命題邏輯進行推證。題邏輯進行推證。 例如例如無法判斷著名的無法判斷著名的“蘇格拉底

3、三段論蘇格拉底三段論”的正確性。的正確性。廣東工業大學計算機學院3蘇格拉底三段論蘇格拉底三段論蘇格拉底三段論蘇格拉底三段論 所有的人都是要死的，所有的人都是要死的， 蘇格拉底是人，蘇格拉底是人， 所以蘇格拉底是要死的。所以蘇格拉底是要死的。眾所周知，這是眾所周知，這是真真命題。命題。命題邏輯中的求解：命題邏輯中的求解：令令 P: 所有的人都是要死的，所有的人都是要死的， Q: 蘇格拉底是人，蘇格拉底是人， R: 所以蘇格拉底是要死的。所以蘇格拉底是要死的。在命題邏輯中，只能用在命題邏輯中，只能用 (P Q) R 表示上述命題，但它表示上述命題，但它僅是僅是可滿足式可滿足式，不是不是重言式重言式

4、。這個簡單而著名的論斷就這個簡單而著名的論斷就無法無法用用命題邏輯命題邏輯予以推證。予以推證。廣東工業大學計算機學院44.1 一階邏輯命題符號化一階邏輯命題符號化 個體詞個體詞所研究對象中可以獨立存在的具體或抽象的客體所研究對象中可以獨立存在的具體或抽象的客體個體常項個體常項：具體的事物，用：具體的事物，用a, b, c表示表示個體變項個體變項：抽象的事物，用：抽象的事物，用x, y, z表示表示個體域個體域(論域論域)個體變項的取值范圍個體變項的取值范圍 有限個體域有限個體域，如，如 a, b, c, 1, 2 無限個體域無限個體域，如，如 N, Z, R, 全總個體域全總個體域由宇宙間一切

5、事物組成由宇宙間一切事物組成廣東工業大學計算機學院5謂詞謂詞謂詞謂詞表示個體詞性質或相互之間關系的詞表示個體詞性質或相互之間關系的詞 謂詞常項謂詞常項 如如, F(a)：a是人是人 謂詞變項謂詞變項 如如, F(x)：x具有性質具有性質Fn（n 1）元謂詞）元謂詞 1. 一元謂詞一元謂詞(n=1)表示性質表示性質 2. 多元謂詞多元謂詞(n 2)表示事物之間的關系表示事物之間的關系 例如例如, L(x, y)：x與與 y 存在關系存在關系 L，L(x, y)：x y， 3. 0元謂詞元謂詞不含個體變項的謂詞，代入確定個體詞之后有不含個體變項的謂詞，代入確定個體詞之后有確定真值的命題。確定真值的

6、命題。廣東工業大學計算機學院6實例實例1例例1 用用0元謂詞將命題符號化元謂詞將命題符號化 (1) 墨西哥位于南美洲墨西哥位于南美洲 (2) 是無理數僅當是無理數僅當 是有理數是有理數 (3) 如果如果2 3，則，則3 3，q：3 y，G(x, y)：x 3，則，則3 y x(F(x) y(G(y) L(x, y)或者或者 x y(F(x) G(y) L(x, y) (2) 令令F(x)：x是無理數，是無理數，G(y)：y是有理數，是有理數，L(x, y)：xy x(F(x) y(G(y) L(x, y)或者或者 x y(F(x) G(y) L(x, y)廣東工業大學計算機學院12實例實例4例

7、例4 在一階邏輯中將下面命題符號化在一階邏輯中將下面命題符號化 (1) 沒有不呼吸的人沒有不呼吸的人 (2) 不是所有的人都喜歡吃糖不是所有的人都喜歡吃糖解解 (1) F(x): x是人是人, G(x): x呼吸呼吸x(F(x)G(x) x(F(x)G(x)(2) F(x): x是人是人, G(x): x喜歡吃糖喜歡吃糖 x(F(x)G(x)x(F(x)G(x)廣東工業大學計算機學院13實例實例5例例5 設個體域為實數域設個體域為實數域, 將下面命題符號化將下面命題符號化 (1) 對每一個數對每一個數x都存在一個數都存在一個數y使得使得x y (2) 存在一個數存在一個數x使得對每一個數使得對

8、每一個數y都有都有x y解解 L(x, y): x = 2)元謂詞。元謂詞。2. 多個量詞出現時，它們的順序一般不能互換。多個量詞出現時，它們的順序一般不能互換。例如：例如：設個體域為實數集，設個體域為實數集，H(x, y)：x + y = 10，則命題，則命題“對對于任意于任意x，都存在，都存在y，使得，使得x + y = 10”，可以符號化為？，可以符號化為？ x yH(x, y) 如果改變量詞的順序：如果改變量詞的順序： y xH(x, y)，所表示的意義是？，所表示的意義是？存在存在y，使得對于任意，使得對于任意x，都有，都有x + y = 10廣東工業大學計算機學院15n元謂詞的命題

9、符號化需要注意元謂詞的命題符號化需要注意對于含對于含n元謂詞的命題，在符號化時需注意元謂詞的命題，在符號化時需注意(續續)：3. 命題符號化的形式不唯一。命題符號化的形式不唯一。例如：例如：并不是所有的兔子都比烏龜跑得快。并不是所有的兔子都比烏龜跑得快。解：解：F(x): x是兔子是兔子 G(y): y是烏龜是烏龜 H(x, y)：x比比y跑得還快跑得還快使用存在量詞使用存在量詞 作符號化：作符號化： x y(F(x) G(y) H(x, y)還可以使用全稱量詞還可以使用全稱量詞 符號化為：符號化為： x y(F(x) G(y) H(x, y)廣東工業大學計算機學院164.2 一階邏輯公式及解

10、釋一階邏輯公式及解釋一階語言：一階語言：謂詞演算系統的形式語言。它本身是由抽象符號謂詞演算系統的形式語言。它本身是由抽象符號構成的。構成的。一階語言包含以下兩大部分：一階語言包含以下兩大部分：廣東工業大學計算機學院17一階語言的字母表一階語言的字母表定義定義4.1 設設L是一個非邏輯符集合是一個非邏輯符集合, 由由L生成的生成的一階語言一階語言L L 的的字母表字母表包括下述符號：包括下述符號：1. 非邏輯符號非邏輯符號 (1) 個體常項符號個體常項符號：a, b, c, , ai, bi, ci, , i 1 (2) 函數符號函數符號：f, g, h, , fi, gi, hi, , i 1

11、 (3) 謂詞符號謂詞符號：F, G, H, , Fi, Gi, Hi, , i 12. 邏輯符號邏輯符號 (4) 個體變項符號個體變項符號：x, y, z, , xi, yi, zi, , i 1 (5) 量詞符號量詞符號： , (6) 聯結詞符號聯結詞符號： , , , , (7) 括號與逗號括號與逗號：(, ), ，廣東工業大學計算機學院18一階語言一階語言L L的項與原子公式的項與原子公式定義定義4.2 L L 的的項項的定義如下：的定義如下：(1) 個體常項和個體變項是項個體常項和個體變項是項.(2) 若若 (x1, x2, , xn)是任意的是任意的n元函數，元函數，t1, t2,

12、 , tn是任意的是任意的 n個項，則個項，則 (t1, t2, , tn) 是項是項.(3) 所有的項都是有限次使用所有的項都是有限次使用(1)，(2)得到的得到的 例如例如, a, x, x + y, f(x), g(x, y)等都是項等都是項 定義定義4.3 設設R(x1, x2, , xn)是是L L 的任意的任意n元謂詞，元謂詞，t1, t2, , tn 是是L L 的任意的任意n個項，則稱個項，則稱R(t1, t2, , tn)是是L L 的的原子公式原子公式. 例如例如, F(x, y), F(f(x1, x2), g(x3, x4)等均為原子公式等均為原子公式廣東工業大學計算機

13、學院19定義定義4.4 L L 的的合式公式合式公式定義如下：定義如下： (1) 原子公式是合式公式原子公式是合式公式. (2) 若若A是合式公式，則是合式公式，則 ( A)也是合式公式也是合式公式 (3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是也是 合式公式合式公式 (4) 若若A是合式公式，則是合式公式，則 xA, xA也是合式公式也是合式公式 (5) 只有有限次地應用只有有限次地應用(1)(4)形成的符號串才是合式公式形成的符號串才是合式公式.合式公式簡稱合式公式簡稱公式公式例如例如, F(x), F(x)G(x,y), x(F(x)

14、G(x) x y(F(x) G(y) L(x,y)等都是合式公式等都是合式公式一階語言一階語言L L 的公式的公式廣東工業大學計算機學院20關于一階語言的幾點說明關于一階語言的幾點說明1. L不一定要包含全部不一定要包含全部3類非邏輯符號。可以只包含類非邏輯符號。可以只包含其中其中1種或種或2種，甚至等于空集種，甚至等于空集2. 當當L = 時，時，L中無任何公式，也就沒有任何意義中無任何公式，也就沒有任何意義3. 當當L不包含邏輯符號時，不包含邏輯符號時，L退化成退化成命題邏輯中的語命題邏輯中的語言言。因此，通常假設。因此，通常假設L中至少包含一個邏輯符號。中至少包含一個邏輯符號。廣東工業大

15、學計算機學院21封閉的公式封閉的公式定義定義4.5 在公式在公式 xA 和和 xA 中，稱中，稱x為為指導變元指導變元，A為相應為相應量詞的量詞的轄域轄域. 在在 x和和 x的轄域中，的轄域中，x的所有出現都稱為的所有出現都稱為約束約束出現出現，A中不是約束出現的其他變項均稱為是中不是約束出現的其他變項均稱為是自由出現自由出現的的. 例如：例如： x(F(x, y)G(x, z)，x為指導變元，為指導變元，(F(x, y)G(x, z)為為 x 的轄域，的轄域，x的兩次出現均為約束出現，的兩次出現均為約束出現，y與與 z 均為自均為自由出現由出現又如又如, x(F(x, y, z) y(G(x

16、, y) H(x, y, z) ： x中中x是指導變元是指導變元, 轄域為轄域為(F(x, y, z) y(G(x, y) H(x, y, z). y中的中的y是指導變元是指導變元, 轄域為轄域為(G(x, y) H(x, y, z). x的的3次出現都是約束出現次出現都是約束出現, y的第一次出現是自由出現的第一次出現是自由出現, 后后2次次是約束出現是約束出現, z的的2次出現都是自由出現次出現都是自由出現廣東工業大學計算機學院22封閉的公式封閉的公式定義定義4.6 若公式若公式A中不含自由出現的個體變項，則稱中不含自由出現的個體變項，則稱A為為封閉封閉的公式的公式，簡稱，簡稱閉式閉式.例

17、如，例如， x y(F(x) G(y)H(x,y) 為閉式，為閉式，而而 x(F(x) G(x,y) 不是閉式不是閉式 廣東工業大學計算機學院23公式的解釋公式的解釋FafF定義定義4.7 設設L L 是是L生成的一階語言生成的一階語言, L L 的的解釋解釋I由由4部分組成：部分組成： (a) 非空個體域非空個體域 DI . (b) 對每一個對每一個個體常項符號個體常項符號a L, 有一個有一個 DI, 稱稱 為為a在在I 中的解釋中的解釋. (c) 對每一個對每一個n元函數符號元函數符號f L, 有一個有一個DI上的上的n元函數元函數 , 稱稱 為為f在在I中的解釋中的解釋. (d) 對每

18、一個對每一個n元謂詞符號元謂詞符號F L, 有一個有一個DI上的上的n元謂詞常項元謂詞常項 , 稱稱 為為F在在I中的解釋中的解釋.aInIDDf:afF 設對公式設對公式A, 取個體域取個體域DI , 把把A中的個體常項符號中的個體常項符號a、函數符、函數符號號f、謂詞符號、謂詞符號F分別替換成它們在分別替換成它們在I中的解釋中的解釋 、 、 , 稱稱所得到的公式所得到的公式A 為為A在在I下的下的解釋解釋, 或或A在在I下下被解釋成被解釋成A .廣東工業大學計算機學院24yxyxF :),(0 ayxyxgyxyxf ),(,),(例例6 給定解釋給定解釋 I 如下：如下： (a) 個體域

19、個體域 D = R (b) (c) (d) 寫出下列公式在寫出下列公式在I下的解釋下的解釋, 并指出它的真值并指出它的真值. (1) xF(f(x, a), g(x, a)實例實例 x(x + 0 = x 0) 真真(2) x y(F(f(x, y), g(x, y) F(x, y) x y(x + y = x y x = y) 假假(3) xF(g(x, y), a) x(x y = 0) 真值不定真值不定, 不是命題不是命題y是自由出現是自由出現廣東工業大學計算機學院25公式的類型公式的類型定理定理4.1 閉式在任何解釋下都是命題閉式在任何解釋下都是命題注意注意: 不是閉式的公式在解釋下可

20、能是命題不是閉式的公式在解釋下可能是命題, 也可能也可能不是命題不是命題. 定義定義4.8 若公式若公式A在任何解釋下均為真在任何解釋下均為真, 則稱則稱A為為永真式永真式(邏輯邏輯有效式有效式). 若若A在任何解釋下均為假在任何解釋下均為假, 則稱則稱A為為矛盾式矛盾式(永假式永假式). 若至少有一個解釋使若至少有一個解釋使A為真為真, 則稱則稱A為為可滿足式可滿足式.幾點說明：幾點說明： 1. 永真式為可滿足式，但反之不真永真式為可滿足式，但反之不真 2. 判斷公式是否是可滿足的判斷公式是否是可滿足的(永真式永真式, 矛盾式矛盾式)是不可判定的是不可判定的廣東工業大學計算機學院26代換實例代換實例定義定義4.9 設設A0是含命題變項是含命題變項 p1, p2, , pn的命題公式，的命題公式，A1, A2, , An是是n個謂詞公式，用個謂詞公式，用Ai (1 i n) 處處代替處處代替A0中的中的pi，所得公式所得公式A稱為稱為A0的的代換實例代換實例.例如，例如， F(x)G(x),