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

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

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

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

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

5、例 用0元謂詞將命題符號化 要求：先將它們在命題邏輯中符號化，再在一階 邏輯中符號化 (1) 墨西哥位于南美洲,在命題邏輯中, 設 p: 墨西哥位于南美洲 符號化為 p,在一階邏輯中, 設a：墨西哥，F(xiàn)(x)：x位于南美洲, 符號化為F(a),8,例(續(xù)),(2)   是無理數(shù)僅當 是有理數(shù),在命題邏輯中, 設 p： 是無理數(shù)，q： 是有理數(shù). 符號化為 p ?

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

7、人都是要死的; (2) 有人活百歲以上 分別取(a) D為人類集合, (b) D為全總個體域 .解：,(a) (1) 設G(x): x是要死的, 符號化為 ?x G(x) (2) 設G(x): x活百歲以上, 符號化為 ?x G(x),(b) 設F(x): x為人，G(x): 同(a)中 (1) ?x (F(x)?G(x)) (2) ? x (F(x)?G(x)),說明：

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

9、 (1) 正數(shù)都大于負數(shù) (2) 有的無理數(shù)大于有的有理數(shù)解,注意: 題目中沒給個體域, 使用全總個體域,(1) 令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)) 兩者等值,(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,一階邏輯中命題符號化(續(xù)),例 在一階邏輯中將下面命題符號化 對任意的x，存在y，使得x+y=5 (個體域為實數(shù)域),解 令H(x,y): x+y=5，則有 ?x?yH(x

11、,y),上式不能寫成 ?y?x H(x,y)，此式含義“存在y，使得對任意的x，都有x+y=5”,說明：一般不能隨意顛倒多個量詞的順序,13,一階邏輯中命題符號化(續(xù)),例 在一階邏輯中將下面命題符號化 (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 一階邏輯公式及解釋,合式公式(簡稱公式)個體變項的自由出現(xiàn)和約束出現(xiàn)解釋與賦值公式分類

13、邏輯有效式，矛盾式, 可滿足式,15,字母表,定義 字母表包含下述符號： (1) 個體常項：a, b, c, …, ai, bi, ci, …, i ?1 (2) 個體變項：x, y, z, …, xi, yi, zi, …, i ?1 (3) 函數(shù)符號：f, g, h, …, fi, gi, hi, …, i ?1 (4) 謂詞符號：F, G, H, …, Fi, Gi, Hi, …, i ?1 (5) 量詞符

14、號：?, ? (6) 聯(lián)結詞符號：?, ?, ?, ?, ? (7) 括號與逗號：(, ), ，,16,項,定義 項的定義如下： (1) 個體常項和個體變項是項. (2) 若?(x1, x2, …, xn)是任意的n元函數(shù)，t1,t2,…,tn是任意的n個項，則?(t1, t2, …, tn) 是項. (3) 所有的項都是有限次使用 (1), (2) 得到的.個體常項、個體變項是項，由它們構成的n元函數(shù)和復

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

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

17、元，A為相應量詞的轄域. 在?x和?x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項均稱為是自由出現(xiàn).例如, 在公式 ?x(F(x,y)?G(x,z)) 中, A=(F(x,y)?G(x,z))為?的轄域， x為指導變元, A中x的兩次出現(xiàn)均為約束出現(xiàn)， y與z均為自由出現(xiàn).,20,例 公式 ?x(F(x) ?G(x))x為指導變元, ?的轄域為(F(

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

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

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

21、符號F指定一個DI上的謂詞賦值?：給定解釋I，對公式中每個自由出現(xiàn)的個體變項x指定一個值?(x)?DI,24,實例,例 給定解釋I 如下: (a) 個體域 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) 對于閉式，只需給定解釋即為命題.,對(3)中的公式，取解釋I下的賦值?：?(x)=1, ?(y)=2, ?(z)=3，則(3)在解釋I和賦值?下為：1+2=2+3，假命題,26,公式的分類,邏輯有效式(永真式):在任何

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

24、G(y)是p?q的代換實例定理 重言式的代換實例都是永真式，矛盾式的代換實例都是矛盾式.,實例,例 判斷下列公式的類型(1) ?xF(x)→?xF(x)；,28,設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) 的代換實例，是邏輯有效式.,例(續(xù)),(3) ?xF(x)→(?xF(x)∨?yG(y))；,29,重言式p→(p∨q)的代換實例, 是邏輯有效式.,(4) ?(F(x,y)→R(x,y))∧R(x,y)；,矛盾式?(p→q)∧q的代換實例, 是矛盾式.,例(續(xù)),(5) ?x?yF(x,y)→?x?yF(x,y).,30,取解釋I：個體域N, F(x,y)為x=y.公式被解釋為?x?y(x=y)??x?y(x=y)，其值

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

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

28、?yG(y) 等 消去量詞等值式 設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ù)),量詞否定等值式設A(x)是含x自由出現(xiàn)的公式 ??xA(x)? ?x ?A(x) ? ?xA

29、(x)??x ?A(x),說明：考慮個體域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ù)),量詞轄域收縮與擴張等值式 設A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xià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),關于存在量詞的: ?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,說明：考慮個體域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,舉例說明?對?無分配律，?對?無分配律,例 令解釋I如下：個體域D為自然數(shù)集，A(x): x是奇數(shù)，B(x): x是偶數(shù). 則有 (1) ?x(A(x)?B(x))表示任意自然數(shù)不是奇數(shù)就是偶數(shù)，此為真命題；而?xA(x)??xB(x)表

34、示兩個假命題的析取，仍為假 (2) ?x(A(x)?B(x)表示存在自然數(shù)既然奇數(shù)又是偶數(shù)，顯然是假命題；而?xA(x)??xB(x)表示兩個真命題的合取，仍為真,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))不是前束范式.,定義 設A為一個一階邏輯公式, 若A具有如下形式Q1x1Q2x2…QkxkB, 則稱A為前束范式, 其中Qi (1?i?k)為?或?，B為不含量詞的公式.,42,公式的前束范式,例 求下列公式的前

36、束范式 (1) ??x(M(x)?F(x))解,定理（前束范式存在定理）一階邏輯中的任何公式都存在與之等值的前束范式求前束范式: 使用重要等值式、置換規(guī)則、換名規(guī)則進行等值演算.,? ?x(?M(x)??F(x)) 量詞否定等值式 ? ?x(M(x)??F(x)) 兩步結果都是前束范式，說明前束范式不惟一.,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)) ( 量詞轄域擴張 ),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)))注意：?與?不能顛倒,蘇格拉底三段論的正確性,“凡是人都要死的. 蘇格拉底是人. 所以蘇格拉底是要死的.”設F(x)：x是人，G(x)：x是要死的，a：蘇格拉底. ?x(F(x)→G(x))∧F(a)→G(a)設前件為真，即?x(F(x)→