高等數(shù)學(xué)-離散數(shù)學(xué)及其應(yīng)用-課件-第四章一階邏輯基本概念

1、1,主要內(nèi)容一階邏輯命題符號(hào)化 個(gè)體詞、謂詞、量詞 一階邏輯命題符號(hào)化一階邏輯公式及其解釋 一階語(yǔ)言 合式公式 合式公式的解釋 永真式、矛盾式、可滿足式,第四章 一階邏輯基本概念,2,4.1 一階邏輯命題符號(hào)化,個(gè)體詞——所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體 個(gè)體常項(xiàng)：具體的事務(wù)，用a, b, c等表示 個(gè)體變項(xiàng)：抽象的事物，用x, y, z等表示

2、 個(gè)體域(論域)——個(gè)體變項(xiàng)的取值范圍 有限個(gè)體域，如 {a, b, c}, {1, 2} 無(wú)限個(gè)體域，如 N, Z, R, … 全總個(gè)體域——由宇宙間一切事物組成,3,謂詞,謂詞——表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞 謂詞常項(xiàng) 如, F(a)：a是人 謂詞變項(xiàng) 如, F(x)：x具有性質(zhì)F n(n?1)元謂詞 一元謂詞(n

3、=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),4,量詞,量詞——表示數(shù)量的詞 全稱量詞?: 表示所有的 ?x : 對(duì)個(gè)體域中所有的x

4、 如, ?xF(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

5、都存在一個(gè)y使得 x和y有關(guān)系G ?x?yG(x,y)表示個(gè)體域中存在一個(gè)x使得對(duì)每一個(gè)y, x和y有關(guān)系G,5,實(shí)例1,,例1 用0元謂詞將命題符號(hào)化 (1) 墨西哥位于南美洲 (2) 是無(wú)理數(shù)僅當(dāng) 是有理數(shù) (3) 如果2>3，

6、則3<4,解：在命題邏輯中： (1) p, p為墨西哥位于南美洲（真命題） (2) p→q, 其中, p： 是無(wú)理數(shù), q： 是有理數(shù). 是假命題 (3) p?q, 其中, p：2>3, q：3<4. 是真命題,6,實(shí)例1解答,在一階邏輯中： (1) F(a)，其中，a：墨西哥，F(xiàn)(x)：x位于南美洲. (2) F( )?G( ),

7、 其中，F(xiàn)(x)：x是無(wú)理數(shù)，G(x)：x是有理數(shù) (3) F(2, 3)?G(3, 4)，其中，F(xiàn)(x, y)：x>y，G(x, y)：x<y,實(shí)例2,例 2 在一階邏輯中將下面命題符號(hào)化 (1) 人都愛(ài)美 (2) 有人用左手寫(xiě)字個(gè)體域分別為 (a) D為人類集合 (b) D為全總個(gè)體域,解 (a) (1) ?xG(x), G(x)：x愛(ài)美,(2) ?xH(x), H(

8、x)：x用左手寫(xiě)字,(b) F(x)：x為人,(1) ?x(F(x)?G(x)),(2) ?x(F(x)?H(x)),說(shuō)明: 1. 引入特性謂詞F(x) 2. (1),(2)是一階邏輯中的兩個(gè)“基本”公式,8,實(shí)例3,例3 在一階邏輯中將下面命題符號(hào)化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無(wú)理數(shù)大于有的有理數(shù),解 注意：題目中沒(méi)給個(gè)體域，一律用全總個(gè)體域 (1) 令F(x)：x為正數(shù)，G

9、(y)：y為負(fù)數(shù), L(x,y)：x>y,?x(F(x)??y(G(y)?L(x,y)))或者 ?x?y(F(x)?G(y)?L(x,y)),(2) 令F(x)：x是無(wú)理數(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)),9,實(shí)例4,例4 在一階邏輯中將下面命題符號(hào)化 (1) 沒(méi)有不呼吸的人 (2) 不

10、是所有的人都喜歡吃糖,解 (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)),10,實(shí)例5,例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

11、,解 L(x,y): x<y,(1) ?x?yL(x,y),注意: ?與?不能隨意交換顯然(1)是真命題, (2)是假命題,(2) ?x?yL(x,y),11,4.2 一階邏輯公式及解釋,定義4.1 設(shè)L是一個(gè)非邏輯符集合, 由L生成的一階語(yǔ)言L 的字母表包括下述符號(hào)：非邏輯符號(hào) (1) 個(gè)體常項(xiàng)符號(hào)：a, b, c, …, ai, bi, ci, …, i ?1 (2) 函數(shù)符號(hào)：f,

12、 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)：(, ), ，,12,一階語(yǔ)言L 的項(xiàng)與原子公式,定義4.2

13、 L 的項(xiàng)的定義如下：(1) 個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng).(2) 若?(x1, x2, …, xn)是n元函數(shù)符號(hào)，t1, t2, …, tn是 n個(gè)項(xiàng)， 則?(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元謂詞符號(hào)，t1, t2, …, t

14、n 是L 的n個(gè)項(xiàng)，則稱R(t1, t2, …, tn)是L 的原子公式. 如，F(xiàn)(x, y), F(f(x1, x2), g(x3, x4))等均為原子公式,13,定義4.4 L 的合式公式定義如下： (1) 原子公式是合式公式. (2) 若A是合式公式，則 (?A)也是合式公式 (3) 若A, B是合式公式，則(A?B), (A?B), (A?B), (A?B)也是 合式公式 (4) 若A

15、是合式公式，則?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))等都是合式公式,一階語(yǔ)言L 的公式,14,量詞的轄域,定義4.5 在公式 ?xA 和 ?xA 中，稱x為指導(dǎo)變?cè)?，A為相應(yīng)量詞的轄域. 在?x和 ?x的轄域中

16、，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))). ?y中的y

17、是指導(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).,15,封閉的公式,定義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)) 不是閉式,16,公式的解釋,,,,定義4.7 設(shè)L 是L生

18、成的一階語(yǔ)言, L 的解釋I由4部分組成： (a) 非空個(gè)體域 DI . (b) 對(duì)每一個(gè)個(gè)體常項(xiàng)符號(hào)a?L, 有一個(gè) ?DI, 稱 為a在I 中的解釋. (c) 對(duì)每一個(gè)n元函數(shù)符號(hào)f?L, 有一個(gè)DI上的n元函數(shù) , 稱 為f在I中的解釋. (d) 對(duì)每一個(gè)n元謂詞符

19、號(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?.,17,實(shí)例,,,,例6 給定解釋 I 如下： (a) 個(gè)體域 D=R (b) (c) (d)

20、寫(xiě)出下列公式在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) 真值不定, 不是命題,18,公式的類型,定理4.1 閉式在任何解釋下都是命

21、題注意: 不是閉式的公式在解釋下可能是命題, 也可能不是命題. 定義4.8 若公式A在任何解釋下均為真, 則稱A為永真式(邏輯有效式). 若A在任何解釋下均為假, 則稱A為矛盾式(永假式). 若至少有一個(gè)解釋使A為真, 則稱A為可滿足式.幾點(diǎn)說(shuō)明： 永真式為可滿足式，但反之不真 判斷公式是否是可滿足的(永真式, 矛盾式)是不可判定的,19,代換實(shí)例,定義4.9 設(shè)A0是含命題變項(xiàng) p1, p2, …

22、, 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í)例都是矛盾式.,20,實(shí)例,例7 判斷下列公式的類型: (1) ?xF(x)?(?x?yG(x,y)??xF(x)),重言式 p?(q?p) 的代換實(shí)例，故為

23、永真式.,(2) ?(?xF(x)??yG(y))??yG(y),矛盾式 ?(p?q)?q 的代換實(shí)例，故為永假式.,(3) ?x(F(x)?G(x)),解釋I1: 個(gè)體域N, F(x):x>5, G(x): x>4, 公式為真 解釋I2: 個(gè)體域N, F(x):x<5, G(x):x<4, 公式為假結(jié)論: 非永真式的可滿足式,21,第四章 習(xí)題課,主要內(nèi)容個(gè)體詞、謂詞、量詞一階邏輯

24、命題符號(hào)化一階語(yǔ)言L 項(xiàng)、原子公式、合式公式公式的解釋 量詞的轄域、指導(dǎo)變?cè)?、個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋公式的類型 永真式(邏輯有效式)、矛盾式(永假式)、可滿足式,22,基本要求,準(zhǔn)確地將給定命題符號(hào)化 理解一階語(yǔ)言的概念 深刻理解一階語(yǔ)言的解釋, 熟練地給出公式的解釋 記住閉式的性質(zhì)并能應(yīng)用它 深刻理解永真式、矛盾式、可滿足式的概念, 會(huì)判斷簡(jiǎn) 單公式的類型,23,練習(xí)1

25、,1. 在分別取個(gè)體域?yàn)?(a) D1=N (b) D2=R (c) D3為全總個(gè)體域的條件下, 將下面命題符號(hào)化，并討論真值 (1) 對(duì)于任意的數(shù)x，均有,解 設(shè)G(x): (a) ?xG(x),(b) ?xG(x),(c) 又設(shè)F(x):x是實(shí)數(shù) ?x(F(x)?G(x)),真,真,假,24,練習(xí)1(續(xù)),解 設(shè)H(x)：x+7=5

26、 (a) ?xH(x),,(2) 存在數(shù)x，使得 x+7=5,(b) ?xH(x),(c) 又設(shè)F(x)：x為實(shí)數(shù) ?x(F(x)?H(x)),本例說(shuō)明：在不同個(gè)體域內(nèi), 命題符號(hào)化形式可能不同、也可能相同, 真值可能不同、也可能相同.,真,真,假,25,練習(xí)2,2. 在一階邏輯中將下列命題符號(hào)化 (1) 大熊貓都可愛(ài),(2) 有人愛(ài)發(fā)脾氣,(3) 說(shuō)所有人都愛(ài)吃面包是不對(duì)的,設(shè)F(x): x為大熊貓，

27、G(x): x可愛(ài) ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛(ài)發(fā)脾氣 ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛(ài)吃面包 ??x(F(x)?G(x)) 或 ?x(F(x)??G(x)),練習(xí)2,(4) 沒(méi)有不愛(ài)吃糖的人,(5) 任何兩個(gè)不同的人都不一樣高,(6) 不是所有的汽車都比所有的火車快,設(shè)F(x): x是人，G(x): x愛(ài)吃糖??x(F(x)??G

28、(x)) 或 ?x(F(x)?G(x)),設(shè)F(x):x是人, H(x,y), x與y相同, L(x,y): x與y一樣高 ?x(F(x)??y(F(y)??H(x,y)??L(x,y))) 或 ?x?y(F(x)?F(y)??H(x,y)??L(x,y)),設(shè)F(x):x是汽車, G(y):y是火車, H(x,y):x比y快 ??x?y(F(x)?G(y)?H(x,y)) 或 ?x?y(F(x)?

29、G(y)??H(x,y)),27,練習(xí)3,?x(2x=x) 假,,3. 給定解釋 I 如下: (a) 個(gè)體域D=N (b) =2 (c) (d) 給出下列公式在 I 下的解釋,并討論真值 (1) ?xF(g(x,a),x),(2) ?x?y(F(f(x,a),y)?F(f(y,a),x)),?x?y(x+2=y?y+2=x) 假,

30、28,練習(xí)3,(3) ?x?y?zF(f(x,y),z),,(5) ?xF(f(x,x),g(x,x)),(4) ?x?y?zF(f(y,z),x),?x?y?z(y+z=x) 假,?x?y?z(x+y=z) 真,?x(x+x=x?x) 真,(3),(4)說(shuō)明?與?不能隨意交換,29,練習(xí)4,4. 證明下面公式既不是永真式，也不是矛盾式:,(1) ?x(F(x)?G(x)),(2)

31、?x?y(F(x)?G(y)?H(x,y)),解釋1: D1=N, F(x):x是偶數(shù), G(x): x是素?cái)?shù), 真,解釋2: D2=N, F(x):x是偶數(shù), G(x): x是奇數(shù), 假,解釋1: D1=Z, F(x):x是正數(shù), G(x): x是負(fù)數(shù), H(x,y):x>y 真,解釋2: D2=Z, F(x):x是偶數(shù)