第二章-高級(jí)數(shù)理邏輯

1、1,第2章 一階邏輯,2.1 一階邏輯基本概念2.2 一階邏輯合式公式及解釋2.3 一階邏輯等值式與前束范式,命題邏輯的局限性,蘇格拉底三段論： 凡是人都要死的. 蘇格拉底是人. 所以蘇格拉底是要死的.在命題邏輯中，只能用p、q、r表示以上3個(gè)命題，上述推理可表成 (p∧q)→r這不是重言式,2,3,2.1 一階邏輯基本概念,,個(gè)體詞 謂詞 量詞 一階邏輯中命題符號(hào)化,4,基本概

2、念——個(gè)體詞、謂詞、量詞,個(gè)體詞（個(gè)體）: 所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體 個(gè)體常項(xiàng)：具體的或特定的事物，用a, b, c表示 個(gè)體變項(xiàng)：抽象的或泛指的事物，用x, y, z表示 個(gè)體域: 個(gè)體變項(xiàng)的取值范圍 有限個(gè)體域，如{a, b, c}, {1, 2} 無限個(gè)體域，如N, Z, R, … 全總個(gè)體域: 宇宙間一切事物組成,5,基本概念 (續(xù))

3、,謂詞: 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞     謂詞常項(xiàng)：F(a)：a是人     謂詞變項(xiàng)：F(x)：x具有性質(zhì)F n元謂詞：含n (n?1)個(gè)個(gè)體詞的謂詞      一元謂詞: 表示個(gè)體詞的性質(zhì) 多元謂詞(n元謂詞, n?2): 表示個(gè)體詞之間的關(guān)系 如 L(x,y)

4、：x與y有關(guān)系L，L(x,y)：x?y，… 0元謂詞: 不含個(gè)體變項(xiàng)的謂詞, 即命題常項(xiàng)或命題變項(xiàng),6,基本概念(續(xù)),量詞: 表示數(shù)量的詞     全稱量詞?: 表示任意的, 所有的, 一切的等 如 ?x 表示對(duì)個(gè)體域中所有的x 存在量詞?: 表示存在, 有的, 至少有一個(gè)等 如 ?x 表示在個(gè)體域中存在x,7,一階邏輯中命題符號(hào)化,

5、例 用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),8,例(續(xù)),(2)   是無理數(shù)僅當(dāng) 是有理數(shù),在命題邏輯中, 設(shè) p： 是無理數(shù)，q： 是有理數(shù). 符號(hào)化為 p ?

6、q,在一階邏輯中, 設(shè)F(x): x是無理數(shù), G(x): x是有理數(shù) 符號(hào)化為,在命題邏輯中, 設(shè) p：2>3，q：3<4. 符號(hào)化為 p?q,在一階邏輯中, 設(shè) F(x,y)：x>y，G(x,y)：x<y, 符號(hào)化為 F(2,3)?G(3,4),(3) 如果2>3，則3<4,9,一階邏輯中命題符號(hào)化(續(xù)),例 在一階邏輯中將下面命題符號(hào)化 (1) 所有

7、人都是要死的; (2) 有人活百歲以上 分別取(a) D為人類集合, (b) D為全總個(gè)體域 .解：,(a) (1) 設(shè)G(x): x是要死的, 符號(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)),說明：

8、符號(hào)化前必須先明確個(gè)體域,?x (F(x)?G(x))對(duì)于任意的個(gè)體x，如果x具有性質(zhì)F，那么x有性質(zhì)G? x (F(x)?G(x))存在個(gè)體x，具有性質(zhì)F和性質(zhì)G；存在具有性質(zhì)F的個(gè)體x，同時(shí)也具有性質(zhì)G?x (F(x)?G(x))所有的個(gè)體x，都具有性質(zhì)F和性質(zhì)G? x (F(x)?G(x))存在個(gè)體x，如果x具有性質(zhì)F，那么x有性質(zhì)G,10,11,一階邏輯中命題符號(hào)化(續(xù)),例 在一階邏輯中將下面命題符號(hào)化

9、 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無理數(shù)大于有的有理數(shù)解,注意: 題目中沒給個(gè)體域, 使用全總個(gè)體域,(1) 令F(x): x為正數(shù), G(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是無理數(shù), G(y): y是有理數(shù),

10、 L(x,y)：x>y ?x(F(x)??y(G(y)?L(x,y))) 或 ?x?y(F(x)?G(y)?L(x,y)) 兩者等值,12,一階邏輯中命題符號(hào)化(續(xù)),例 在一階邏輯中將下面命題符號(hào)化 對(duì)任意的x，存在y，使得x+y=5 (個(gè)體域?yàn)閷?shí)數(shù)域),解 令H(x,y): x+y=5，則有 ?x?yH(x

11、,y),上式不能寫成 ?y?x H(x,y)，此式含義“存在y，使得對(duì)任意的x，都有x+y=5”,說明：一般不能隨意顛倒多個(gè)量詞的順序,13,一階邏輯中命題符號(hào)化(續(xù)),例 在一階邏輯中將下面命題符號(hào)化 (1) 沒有不呼吸的人 (2) 不是所有的人都喜歡吃糖解,(1) 令M(x): x是人, F(x): x呼吸, 則 ??x(M(x)??F(x)) 或

12、 ?x(M(x)?F(x)) (所有的人都呼吸),(2) 令M(x): x是人, F(x): x吃糖, 則 ??x(M(x)?F(x)) 或 ?x(M(x)??F(x)) (存在不喜歡吃糖的人),說明：(1)、(2)中的兩式分別是等值的,14,2.2 一階邏輯公式及解釋,合式公式(簡(jiǎn)稱公式)個(gè)體變項(xiàng)的自由出現(xiàn)和約束出現(xiàn)解釋與賦值公式分類

13、邏輯有效式，矛盾式, 可滿足式,15,字母表,定義 字母表包含下述符號(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) 量詞符

14、號(hào)：?, ? (6) 聯(lián)結(jié)詞符號(hào)：?, ?, ?, ?, ? (7) 括號(hào)與逗號(hào)：(, ), ，,16,項(xiàng),定義 項(xiàng)的定義如下： (1) 個(gè)體常項(xiàng)和個(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) 得到的.個(gè)體常項(xiàng)、個(gè)體變項(xiàng)是項(xiàng)，由它們構(gòu)成的n元函數(shù)和復(fù)

15、合函數(shù)還是項(xiàng),17,原子公式,定義 設(shè)R(x1, x2, …, xn)是任意的n元謂詞，t1,t2,…, tn是任意的n個(gè)項(xiàng)，則稱R(t1, t2, …, tn)是原子公式. 原子公式是由項(xiàng)組成的n元謂詞. 例如，F(xiàn)(x,y), F(f(x1,x2),g(x3,x4))等均為原子公式,18,合式公式,定義 合式公式（謂詞公式，簡(jiǎn)稱公式）定義如下： (1) 原子公式是合式公式. (2) 若A是合式公式，則 (?A)也

16、是合式公式 (3) 若A, B是合式公式，則(A?B), (A?B), (A?B), (A?B)也是合式公式 (4) 若A是合式公式，則?xA, ?xA也是合式公式 (5) 只有有限次地應(yīng)用(1)~(4)形成的符號(hào)串是合 式公式.如 x?0, ?x (F(x)?G(x)), ?x?y(x+y=1),19,個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn),定義 在公式?xA和?xA中，稱x為指導(dǎo)變

17、元，A為相應(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為指導(dǎo)變?cè)? A中x的兩次出現(xiàn)均為約束出現(xiàn)， y與z均為自由出現(xiàn).,20,例 公式 ?x(F(x) ?G(x))x為指導(dǎo)變?cè)? ?的轄域?yàn)?F(

18、x) ?G(x))，x是約束出現(xiàn). 若公式中無自由出現(xiàn)的個(gè)體變項(xiàng)，則被稱為封閉的合式公式，簡(jiǎn)稱閉式.例 公式 ?xF(x)?G(x,y) 在?xF(x)中，x為指導(dǎo)變?cè)? ?的轄域?yàn)镕(x)，x是約束出現(xiàn)， G(x,y)中x和y的都是自由出現(xiàn). 在整個(gè)公式中，x的第一次出現(xiàn)是約束出現(xiàn)，第二次出現(xiàn)是自由出現(xiàn)，y是自由出現(xiàn).,21,換名規(guī)則,換名規(guī)則: 將一個(gè)指導(dǎo)變項(xiàng)及其在轄域中所有約束出現(xiàn)替換成公式中沒有出現(xiàn)的個(gè)體變項(xiàng)符號(hào)，公式

19、中其余部分不變，則所得公式與原來的公式等值.,例 利用換名規(guī)則，公式 ?xF(x)?G(x,y) 則變成 ?zF(z)?G(x,y),22,公式的解釋與分類,給定閉式 A=?x(F(x)?G(x))取個(gè)體域N, F(x): x>2, G(x): x>1 代入得A=?x(x>2?x>1) 真命題給定非閉式 B=?xF(x,y

20、)取個(gè)體域N, F(x,y): x?y 代入得B=?x(x?y) 不是命題令y=1, B=?x(x?1) 假命題,23,解釋和賦值,定義 解釋I由下面4部分組成： (a) 非空個(gè)體域DI (b) 對(duì)每一個(gè)命題常項(xiàng)a 指定一個(gè) ?DI (c) 對(duì)每一個(gè)函數(shù)變項(xiàng)符號(hào)f指定一個(gè)DI上的函數(shù) (d) 對(duì)每一個(gè)謂詞變項(xiàng)

21、符號(hào)F指定一個(gè)DI上的謂詞賦值?：給定解釋I，對(duì)公式中每個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)x指定一個(gè)值?(x)?DI,24,實(shí)例,例 給定解釋I 如下: (a) 個(gè)體域 D=N (b) (c) (d) 謂詞說明下列公式在 I 與?下的涵義,并討論真值 (1) ?xF(g(x,a),x),?x(2x=x) 假命題,25,例(續(xù)),?x?y?z (x+y=z) 真命題,

22、(3) F(f(x,y), f(y,z)),x+y=y+z 真值不確定，因而不是命題,(2) ?x?y?zF(f(x,y),z),說明：1) 給定解釋和賦值，任何公式都是命題. 2) 對(duì)于閉式，只需給定解釋即為命題.,對(duì)(3)中的公式，取解釋I下的賦值?：?(x)=1, ?(y)=2, ?(z)=3，則(3)在解釋I和賦值?下為：1+2=2+3，假命題,26,公式的分類,邏輯有效式(永真式):在任何

23、解釋和賦值下為真命題矛盾式(永假式):在任何解釋和賦值下為假命題可滿足式：存在成真的解釋和賦值說明：永真式為可滿足式，但反之不真謂詞公式的可滿足性（永真性,永假性)是不可判定的,27,代換實(shí)例,定義 設(shè)A0是含命題變項(xiàng)p1, p2, …,pn的命題公式， A1,A2,…,An是n個(gè)謂詞公式，用Ai處處代替A0中的pi (1?i?n) ，所得公式A稱為A0的代換實(shí)例.如 F(x)?G(x), ?xF(x)??y

24、G(y)是p?q的代換實(shí)例定理 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式.,實(shí)例,例 判斷下列公式的類型(1) ?xF(x)→?xF(x)；,28,設(shè)I為任意的解釋，若?xF(x)為假，則?xF(x)→?xF(x)為真. 若?xF(x)為真，則?xF(x)也為真，所以?xF(x)→?xF(x)也為真. 是邏輯有效式.,(2) ?xF(x)→(?x?yG(x,y)→?xF(x))；,重言式p→(q→

25、p) 的代換實(shí)例，是邏輯有效式.,例(續(xù)),(3) ?xF(x)→(?xF(x)∨?yG(y))；,29,重言式p→(p∨q)的代換實(shí)例, 是邏輯有效式.,(4) ?(F(x,y)→R(x,y))∧R(x,y)；,矛盾式?(p→q)∧q的代換實(shí)例, 是矛盾式.,例(續(xù)),(5) ?x?yF(x,y)→?x?yF(x,y).,30,取解釋I：個(gè)體域N, F(x,y)為x=y.公式被解釋為?x?y(x=y)??x?y(x=y)，其值

26、為假.,解釋I′: 個(gè)體域N, F(x,y)為x?y, 得到一個(gè)新的 在I′下,公式被解釋為?x?y(x?y)??x?y(x?y)，其值為真.是非邏輯有效式的可滿足式.,例(續(xù)),(6) ?xF(x,y),31,取解釋I：個(gè)體域N, F(x,y)為x<y. 賦值?1：?1(y)=1. 在I和?1下, ?x(x<1)，真命題.,取解釋I: 個(gè)體域N, F(x,y)為x<y. 賦值?2：?2(y)=0.

27、 在I和?2下, ?x(x<0)， 假命題是非邏輯有效式的可滿足式.,32,2.3 一階邏輯等值式與前束范式,等值式基本等值式 量詞否定等值式 量詞轄域收縮與擴(kuò)張等值式 量詞分配等值式前束范式,33,等值式與基本等值式,基本等值式:命題邏輯中24個(gè)基本等值式的代換實(shí)例如，?xF(x)??yG(y) ? ??xF(x)??yG(y) ?(?xF(x)??yG(y)) ? ??xF(x)??

28、?yG(y) 等 消去量詞等值式 設(shè)D={a1,a2,…,an} ?xA(x)?A(a1)?A(a2)?…?A(an) ?xA(x)?A(a1)?A(a2)?…?A(an),定義 若A?B為邏輯有效式，則稱A與B是等值的，記作 A?B，并稱A?B為等值式.,34,基本的等值式(續(xù)),量詞否定等值式設(shè)A(x)是含x自由出現(xiàn)的公式 ??xA(x)? ?x ?A(x) ? ?xA

29、(x)??x ?A(x),說明：考慮個(gè)體域D={a1,a2,…,an} ??xA(x)? ?(A(a1)?A(a2)?…?A(an)) ? ?A(a1)? ?A(a2)?…? ?A(an) ? ?x ?A(x),35,例 (1) 沒有不呼吸的人 ??x(M(x)??F(x)) ??x? (M(x

30、)??F(x)) ??x(?M(x)?F(x)) ??x(M(x)?F(x)) (所有的人都呼吸) (2) 不是所有的人都喜歡吃糖 ??x(M(x)?F(x)) ??x?(M(x)?F(x)) ??x?(?M(x)?F(x)) ??x(M(x)??F(x)) (存在不喜歡吃糖的人

31、),36,基本等值式(續(xù)),量詞轄域收縮與擴(kuò)張等值式 設(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(B?A(x))?B??xA(x),關(guān)于存在量詞的: ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?

32、x(A(x)?B)??xA(x)?B ?x(B?A(x))?B??xA(x),37,說明：考慮個(gè)體域D={a1,a2,…,an} (1) ?x(A(x)?B) ? (A(a1) ?B) ?(A(a2) ?B) ?…?(A(an)?B) ? (A(a1) ?A(a2) ?…?A(an) ) ?B ??xA(x)?B (2) ?x(A(x)?B)

33、 ? ?x(?A(x)?B) ? ?x?A(x)?B ? ??xA(x)?B ??xA(x)?B,38,基本的等值式(續(xù)),39,舉例說明?對(duì)?無分配律，?對(duì)?無分配律,例 令解釋I如下：個(gè)體域D為自然數(shù)集，A(x): x是奇數(shù)，B(x): x是偶數(shù). 則有 (1) ?x(A(x)?B(x))表示任意自然數(shù)不是奇數(shù)就是偶數(shù)，此為真命題；而?xA(x)??xB(x)表

34、示兩個(gè)假命題的析取，仍為假 (2) ?x(A(x)?B(x)表示存在自然數(shù)既然奇數(shù)又是偶數(shù)，顯然是假命題；而?xA(x)??xB(x)表示兩個(gè)真命題的合取，仍為真,40,基本的等值式(續(xù)),同類量詞交換等值式A(x,y)是任意的含x、y自由出現(xiàn)的公式 ?x?y A(x,y) ? ?y?x A(x,y) ?x ? y A(x,y) ? ?y?x A(x,y),41,前束范式,例如，?x?y(F(x)?(G(y)?

35、H(x,y))) ?x?(F(x)?G(x))是前束范式, 而 ?x(F(x)??y(G(y)?H(x,y))) ??x(F(x)?G(x))不是前束范式.,定義 設(shè)A為一個(gè)一階邏輯公式, 若A具有如下形式Q1x1Q2x2…QkxkB, 則稱A為前束范式, 其中Qi (1?i?k)為?或?，B為不含量詞的公式.,42,公式的前束范式,例 求下列公式的前

36、束范式 (1) ??x(M(x)?F(x))解,定理（前束范式存在定理）一階邏輯中的任何公式都存在與之等值的前束范式求前束范式: 使用重要等值式、置換規(guī)則、換名規(guī)則進(jìn)行等值演算.,? ?x(?M(x)??F(x)) 量詞否定等值式 ? ?x(M(x)??F(x)) 兩步結(jié)果都是前束范式，說明前束范式不惟一.,43,例(續(xù)),(2) ?xF(x)???xG(x)解,??xF

37、(x)??x?G(x) （量詞否定等值式）??x(F(x)??G(x)) （量詞分配等值式）,或者 ??xF(x)??x?G(x) ??xF(x)??y?G(y) ( 換名規(guī)則 ) ??x?y(F(x)??G(y)) ( 量詞轄域擴(kuò)張 ),44,例(續(xù)),(3) ?xF(x)???xG(x) 解,??xF(x)??x?

38、G(x) ??x(F(x)??G(x)),(4) ?xF(x)??y(G(x,y)??H(y)),解 ??zF(z)??y(G(x,y)??H(y)) ??z?y(F(z)?(G(x,y)??H(y))),或 ??xF(x)? ??yG(y) ??x(F(x)??y?G(y)) ??x?y(F(x)??G(y)),45,例(續(xù)),(5) ?x(F(x,

39、y)??y(G(x,y)?H(x,z))),解 ??x(F(x,y)??u(G(x,u)?H(x,z))) ??x?u(F(x,y)?G(x,u)?H(x,z)))注意：?與?不能顛倒,蘇格拉底三段論的正確性,“凡是人都要死的. 蘇格拉底是人. 所以蘇格拉底是要死的.”設(shè)F(x)：x是人，G(x)：x是要死的，a：蘇格拉底. ?x(F(x)→G(x))∧F(a)→G(a)設(shè)前件為真，即?x(F(x)→