第四章-一階邏輯基本概念

1、第四章 一階邏輯基本概念【教學(xué)目的與要求】  1掌握一階邏輯的命題符號(hào)化；  2理解謂詞公式與解釋。 【教學(xué)重點(diǎn)、難點(diǎn)】  個(gè)體詞、謂詞、量詞；謂詞公式及其解釋?！窘虒W(xué)方法】：講授法【主要內(nèi)容】l 一階邏輯命題符號(hào)化 個(gè)體詞、謂詞、量詞 一階邏輯命題符號(hào)化l 一階邏輯公式及其解釋 一階語言 合式公式 合式公式的解釋 永真式、矛盾式、可滿足式【教學(xué)過程】4.1 一階邏輯命題符號(hào)化1.個(gè)體詞所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體。 個(gè)體常項(xiàng)：具體的事務(wù)，用a, b, c表示。 個(gè)體變項(xiàng)：抽象的事物，用x, y, z表示。 個(gè)體域(論域)個(gè)體變項(xiàng)的取值范圍

2、。 有限個(gè)體域，如 a, b, c, 1, 2； 無限個(gè)體域，如 N, Z, R, ； 全總個(gè)體域由宇宙間一切事物組成。2.謂詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞。 謂詞常項(xiàng) 如, F(a)：a是人 謂詞變項(xiàng) 如, F(x)：x具有性質(zhì)F n（n³1）元謂詞 一元謂詞(n=1)表示性質(zhì)； 多元謂詞(n³2)表示事物之間的關(guān)系。 如, L(x,y)：x與 y 有關(guān)系 L，L(x,y)：x³y， 0元謂詞不含個(gè)體變項(xiàng)的謂詞, 即命題常項(xiàng)或命題變項(xiàng)。3.量詞表示數(shù)量的詞 全稱量詞": 表示所有的. "x : 對(duì)個(gè)體域中所有的x. 如, "xF

3、(x)表示個(gè)體域中所有的x具有性質(zhì)F； "x"yG(x,y)表示個(gè)體域中所有的x和y有關(guān)系G。 存在量詞$: 表示存在, 有一個(gè). $x : 個(gè)體域中有一個(gè)x . 如, $xF(x)表示個(gè)體域中有一個(gè)x具有性質(zhì)F; $x$yG(x,y)表示個(gè)體域中存在x和y有關(guān)系G. "x$yG(x,y)表示對(duì)個(gè)體域中每一個(gè)x都存在一個(gè)y使得x和y有關(guān)系G; $x"yG(x,y)表示個(gè)體域中存在一個(gè)x使得對(duì)每一個(gè)y, x和y有關(guān)系G.例1 用0元謂詞將命題符號(hào)化 (1) 墨西哥位于南美洲; (2) 是無理數(shù)僅當(dāng)是有理數(shù); (3) 如果2>3，則3<4.解：在

4、命題邏輯中： (1) p, p為墨西哥位于南美洲（真命題）. (2) pq, 其中, p:是無理數(shù)，q：是有理數(shù). 是假命題. (3) p®q, 其中，p：2>3，q：3<4. 是真命題. 在一階邏輯中： (1) F(a)，其中，a：墨西哥，F(xiàn)(x)：x位于南美洲. (2) F()®G(), 其中，F(xiàn)(x)：x是無理數(shù)，G(x)：x是有理數(shù).(3) F(2, 3)®G(3, 4)，其中，F(xiàn)(x, y)：x>y，G(x, y)：x<y.例 2 在一階邏輯中將下面命題符號(hào)化 (1) 人都愛美; (2) 有人用左手寫字.個(gè)體域分別為 (a) D為

5、人類集合; (b) D為全總個(gè)體域.解: (a) (1) "xG(x), G(x)：x愛美(2) $xG(x), G(x)：x用左手寫字 (b) F(x)：x為人，G(x)：x愛美 (1) "x(F(x)®G(x) (2) $x(F(x)ÙG(x)注：1. 引入特性謂詞F(x)； 2. (1),(2)是一階邏輯中兩個(gè)“基本”公式。例3 在一階邏輯中將下面命題符號(hào)化 (1) 正數(shù)都大于負(fù)數(shù)； (2) 有的無理數(shù)大于有的有理數(shù)。解 注意：題目中沒給個(gè)體域，一律用全總個(gè)體域 (1) 令F(x)：x為正數(shù)，G(y)：y為負(fù)數(shù), L(x,y)：x>y &qu

6、ot;x(F(x)®"y(G(y)®L(x,y)或者 "x"y(F(x)ÙG(y)®L(x,y) (2) 令F(x)：x是無理數(shù)，G(y)：y是有理數(shù)，L(x,y)：x>y $x(F(x)Ù$y(G(y)ÙL(x,y)或者 $x$y(F(x)ÙG(y)ÙL(x,y)例4 在一階邏輯中將下面命題符號(hào)化 (1) 沒有不呼吸的人； (2) 不是所有的人都喜歡吃糖。解： (1) F(x): x是人, G(x): x呼吸Ø$x(F(x)ÙØG(x)"

7、x(F(x)®G(x)(2) F(x): x是人, G(x): x喜歡吃糖Ø"x(F(x)®G(x)$x(F(x)ÙØG(x)例5 設(shè)個(gè)體域?yàn)閷?shí)數(shù)域, 將下面命題符號(hào)化 (1) 對(duì)每一個(gè)數(shù)x都存在一個(gè)數(shù)y使得x<y (2) 存在一個(gè)數(shù)x使得對(duì)每一個(gè)數(shù)y都有x<y解： L(x,y):x<y (1) "x$yL(x,y) (2) $x"yL(x,y) 注意: "與$不能隨意交換.顯然(1)是真命題, (2)是假命題.4.2 一階邏輯公式及解釋 1.定義4.1 設(shè)L是一個(gè)非邏輯符集合, 由L生

8、成的一階語言L 的字母表包括下述符號(hào)： 非邏輯符號(hào) (1) 個(gè)體常項(xiàng)符號(hào)：a, b, c, , ai, bi, ci, , i ³1 (2) 函數(shù)符號(hào)：f, g, h, , fi, gi, hi, , i ³1 (3) 謂詞符號(hào)：F, G, H, , Fi, Gi, Hi, , i ³1 邏輯符號(hào) (4) 個(gè)體變項(xiàng)符號(hào)：x, y, z, , xi, yi, zi, , i ³1 (5) 量詞符號(hào)：", $ (6) 聯(lián)結(jié)詞符號(hào)：Ø, Ù, Ú, ®, « (7) 括號(hào)與逗號(hào)：(, ), ， 定義4

9、.2 L 的項(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, x, x+y, f(x), g(x,y)等都是項(xiàng) 定義4.3 設(shè)R(x1, x2, , xn)是L 的任意n元謂詞，t1, t2, , tn 是L 的任意n個(gè)項(xiàng)，則稱R(t1, t2, , tn)是L 的原子公式. 如，F(xiàn)(x, y), F(f(x1, x2), g(x3, x4)等均為原子公式定義4.4 L 的合式公式定義如下：

10、 (1) 原子公式是合式公式. (2) 若A是合式公式，則 (ØA)也是合式公式 (3) 若A, B是合式公式，則(AÙB), (AÚB), (A®B), (A«B)也是合式公式 (4) 若A是合式公式，則"xA, $xA也是合式公式 (5) 只有有限次地應(yīng)用(1)(4)形成的符號(hào)串才是合式公式.合式公式簡(jiǎn)稱公式. 如, F(x), F(x)ÚØG(x,y), "x(F(x)®G(x), $x"y(F(x)®G(y)ÙL(x,y)等都是合式公式. 定義4.5 在公式

11、 "xA 和 $xA 中，稱x為指導(dǎo)變?cè)?，A為相應(yīng)量詞的轄域. 在"x和 $x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的. 例如，"x(F(x,y)®G(x,z)， x為指導(dǎo)變?cè)?F(x,y)®G(x,z)為"x 的轄域，x的兩次出現(xiàn)均為約束出現(xiàn)，y與 z 均為自由出現(xiàn)； 又如, $x(F(x,y,z)®"y(G(x,y)ÙH(x,y,z), $x中的x是指導(dǎo)變?cè)?轄域?yàn)?F(x,y,z)®"y(G(x,y)ÙH(x,y,z). &q

12、uot;y中的y是指導(dǎo)變?cè)? 轄域?yàn)?G(x,y)ÙH(x,y,z). x的3次出現(xiàn)都是約束出現(xiàn), y的第一次出現(xiàn)是自由出現(xiàn), 后2次是約束出現(xiàn), z的2次出現(xiàn)都是自由出現(xiàn)。 定義4.6 若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡(jiǎn)稱閉式. 例如，"x"y(F(x)ÙG(y)®H(x,y) 為閉式，而$x(F(x)ÙG(x,y) 不是閉式。 定義4.7 設(shè)L 是L生成的一階語言, L 的解釋I由4部分組成： (a) 非空個(gè)體域 DI . (b) 對(duì)每一個(gè)個(gè)體常項(xiàng)符號(hào)aÎL, 有一個(gè)ÎDI, 稱為a在I中

13、的解釋. (c) 對(duì)每一個(gè)n元函數(shù)符號(hào)fÎL, 有一個(gè)DI上的n元函數(shù), 稱為f在I中的解釋. (d) 對(duì)每一個(gè)n元謂詞符號(hào)FÎL, 有一個(gè)DI上的n元謂詞常項(xiàng),稱為F在I中的解釋.設(shè)公式A, 取個(gè)體域DI , 把A中的個(gè)體常項(xiàng)符號(hào)a、函數(shù)符號(hào)f、謂詞符號(hào)F分別替換成它們?cè)贗中的解釋、, 稱所得到的公式A¢為A在I下的解釋, 或A在I下被解釋成A¢.例6 給定解釋 I 如下： (a) 個(gè)體域 D=R； (b) ； (c)； (d) 寫出下列公式在I下的解釋, 并指出它的真值.(1) $xF(f(x,a),g(x,a)$x(x+0=x×0) 真(

14、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) 真值不定, 不是命題2.公式的類型定理4.1 閉式在任何解釋下都是命題.注意: 不是閉式的公式在解釋下可能是命題, 也可能不是命題. 定義4.8 若公式A在任何解釋下均為真, 則稱A為永真式(邏輯有效式).若A在任何解釋下均為假, 則稱A為矛盾式(永假式). 若至少有一個(gè)解釋使A為真, 則稱A為可滿足式.幾點(diǎn)說明： 永真式為可滿足式，但反之不真；

15、 判斷公式是否是可滿足的(永真式, 矛盾式)是不可判定的。定義4.9 設(shè)A0是含命題變項(xiàng) p1, p2, , pn的命題公式，A1, A2, , An是n個(gè)謂詞公式，用Ai (1£i£n) 處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例.例如， F(x)®G(x), "xF(x)®$yG(y)等都是p®q的代換實(shí)例.定理4.2 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式. 例7 判斷下列公式中，哪些是永真式，哪些是矛盾式？ (1) "xF(x)®($x$yG(x,y)®"xF(x)重言式 p®(q®p) 的代換實(shí)例，故為永真式.