離散數學第五章)

1、,第二章 謂詞邏輯,2.1謂詞的概念與表示(Predicate and its expression)2.2謂詞公式與翻譯(Predicate formulae)2.3謂詞演算的等價式與蘊含式(Equivalences & implications of predicate calculus)2.4前束范式(Prenex normal form)2.5謂詞演算的推理理論(Inference theory

2、 of predicate calculus),,一、謂詞的等價和永真的概念定義1:給定任意的謂詞公式A,其個體域為E,對于A的所有賦值,公式A都為真,則稱A在E上是永真的(或有效的);若對于A的所有賦值,公式A都為假,則稱A在E上是永假的(或不可滿足的);若至少存在著一種賦值使得公式A為真,則稱A在E上是可滿足的.定義2:給定任何兩個謂詞公式A、B，設它們有共同的個體域E，若對A和B的任一組變元進行賦值，所得命題的真值

3、相同，則稱謂詞公式A和B在E上等價，并記為A ? B,§2.3 一階邏輯等值式與置換規(guī)則,,§2.3 一階邏輯等值式與置換規(guī)則,在命題邏輯中給出了一些常見等價公式和蘊含式,只要用原子謂詞公式去代替第一章中永真蘊含式和等價公式中的原子命題變元，則在第一章中永真蘊含式和等價公式均可變成謂詞演算中的永真蘊含式和等價公式：,,§2.3 一階邏輯等值式與置換規(guī)則,命題邏輯

4、 謂詞邏輯 ¬¬Ｐ?Ｐ ¬¬Ｐ(x)?Ｐ(x)Ｐ∨Ｐ?Ｐ Ｐ(x)∨Ｐ(x)?Ｐ(x) . . . .Ｐ→Ｑ

5、?¬Ｑ→ ¬Ｐ Ｐ(x)→Ｑ(x) ?¬Ｑ(x)→ ¬Ｐ(x) Ｐ?Ｐ∨Ｑ　 Ｐ(x)?Ｐ(x)∨Ｑ(x)　 ＰΛＱ? Ｐ Ｐ(x)ΛＱ(x)? Ｐ(x) . . .

6、 . . .,,§2.3 一階邏輯等值式與置換規(guī)則,下面給出涉及量詞的一些等價式。(1) 消去量詞的等價式設個體域為：S={a1,a2,…an}，我們有： ?xA(x)?A(a1)? A(a2) ?… ? A(an) ?xA(x) ?A(a1)?A(

7、a2) ? … ? A(an),,§2.3 一階邏輯等值式與置換規(guī)則,例1 設 P(x)表示x喜歡夢八隊，則? P(x)表示x不喜歡夢八隊。(個體域限定為人)（1）不是所有人都喜歡夢八隊：?(?x)P(x) （2）存在一些人不喜歡夢八隊： (?x)?P(x) （3）不會有人喜歡夢八隊： ?(?x)P(x) （4）所有人都不喜歡夢八隊： (?x)?P(x) 可以看出命題(1)(2)意義完全相同，(3)(4)意

8、義也完全相同,,§2.3 一階邏輯等值式與置換規(guī)則,（2）量詞否定轉換律 ¬?xP(x)? ?x¬P(x) ¬?xP(x)? ?x¬P(x) 下面證明：¬?xP(x)? ?x¬P(x)設個體域為： S={a1,a2,…an} ¬?xP(x)? ¬(P(a1)? P(a2) ? … ? P(an))

9、?¬P(a1)? ¬P(a2) ?… ?¬P(an) ??x¬P(x),,§2.3 一階邏輯等值式與置換規(guī)則,舉例說明量化命題和非量化命題的差別:否定形式不同例： 否定下列命題： (a)上海是一個小城鎮(zhèn) A(s) (b)每一個自然數都是偶數 ?x(N(x)?E(x))上述二命題的否定為： (a)上海不是一個小城鎮(zhèn) ¬A(s)

10、 (b)有一些自然數不是偶數 ¬?x(N(x)?E(x))??x¬(N(x)?E(x)) ??x¬(¬N(x)?E(x)) ? ?x (N(x) ? ¬E(x))結論：對于非量化命題的否定只需將動詞否定，而對于量化命題的否定不但對動詞進行否定而且對量詞同時進行否定，其方法是： ?x的否定變?yōu)?x ， ?x的否定變?yōu)?x 。,,§2.

11、3 一階邏輯等值式與置換規(guī)則,量詞轉換律的推廣應用:把¬深入到謂詞公式前面去的方法。 ¬?x?yP(x,y,z) ? ?x¬ ?yP(x,y,z) ? ?x?y¬P(x,y,z),,§2.3 一階邏輯等值式與置換規(guī)則,（3）量詞轄域的擴張與收縮量詞轄域中如果有合取或析取項，且其中有一個是命題，則可將該命題移至量詞轄域之外：

12、（?x）（A(x)∨B）?（?x）A(x)∨B（?x）（A(x)∧B）?（?x）A(x)∧ B（?x）（A(x)∨B）?（?x）A(x)∨B（?x）（A(x)∧B）?（?x）A(x)∧B,,§2.3 一階邏輯等值式與置換規(guī)則,證明： ?xA(x) ? B? ?x(A(x) ? B)設個體域為： S={a1,a2,…an} ?xA(x) ? B ?(A(a1)? A(a2) ?… ? A(an)) ? B

13、 ? (A(a1)?B)?(A(a2)?B)?… ?(A(an) ?B) ? ?x(A(x) ?B),,§2.3 一階邏輯等值式與置換規(guī)則,從上述幾個等價公式可以推出如下的等價式：?xA(x)?B? ?x(A(x)?B)? xA(x)?B? ?x(A(x)?B)A??xB(x)? ?x(A?B (x))A? ?x B(x)? ?x(A?B (x))證明：?xA(x)?B? ?x(A(x)?B) ?xA(x

14、)?B? ¬ ?xA(x) ? B ? ? x ¬ A(x) ? B? ? x （¬ A(x) ? B） ? ?x(A(x)?B),,§2.3 一階邏輯等值式與置換規(guī)則,（4）量詞分配律?x(A(x)?B(x)) ? ?xA(x)? ?xB(x)?x (A(x) ?B(x)) ? ?xA(x) ? ?xB(x) ?x (A(x) ? B(x)) ? ?xA(x) ? ?xB(x) ?x

15、(A(x) ? B(x)) ? ?xA(x) ? ?xB(x)?xA(x) ? ?xB(x) ? ?x(A(x) ? B(x)) ?xA(x) ? ?xB(x) ? ?x(A(x) ? B(x)),,§2.3 一階邏輯等值式與置換規(guī)則,證明：?x(A(x)?B(x)) ? ?xA(x)? ?xB(x)設個體域為： S={a1,a2,…an}?x(A(x)?B(x)) ?(A(a1)?B(a1)) ?…. ?

16、(A(an)?B(an)) ?(A(a1)?… ? A(an)) ? (B(a1)?… ? B(an)) ? ?xA(x)? ?x B(x),,§2.3 一階邏輯等值式與置換規(guī)則,?x(A(x)∨B(x)) ? ?x A(x) ∨?x B(x)？,舉例：令 x的個體域為正整數。 A(x)：x是奇數 B(x)：x是偶數 ?x (A(x) ∨ B(x)) ? 所有正整數是奇數或者偶

17、數。 ?x A(x) ∨ ?x B(x) ? 所有正整數都是奇數或者所有正整數都是偶數。,,,§2.3 一階邏輯等值式與置換規(guī)則,(?x)(A(x)?B(x)) ? (?x)A(x) ? (?x)B(x)？,舉例：令 x的個體域為正整數。 A(x)：x是奇數 B(x)：x是偶數 ?x (A(x) ? B(x)) ? 存在既是奇數又是偶數的正整數。 ?

18、x A(x) ? ? x B(x) ? 存在為奇數的正整數且存在為偶數的正整數。,,,§2.3 一階邏輯等值式與置換規(guī)則,量詞與聯(lián)結詞∧，∨的關系總結：1) ?x(A(x) ∧ B(x)) ? ?x A(x) ∧ ?xB(x) ?x(A(x)∨B(x)) ? ?x A(x) ∨?x B(x)2) ?x (A(x) ∨ B(x)) ? ?x A(x)∨ ?x B(x) ?x (A(x) ∧

19、B(x)) ? ?x A(x) ∧ ?x B(x),,,,§2.3 一階邏輯等值式與置換規(guī)則,對于二元謂詞有八種情況：1.(?x)(?y)A(x,y)2.(?x)(?y)A(x,y)3.(?x)(?y)A(x,y)4.(?x)(?y)A(x,y)5.(?y)(?x)A(x,y)6.(?y)(?x)A(x,y)7.(?y)(?x)A(x,y)8.(?y)(?x)A(x,y),,§2.3 一階邏輯等值式與

20、置換規(guī)則,（5）含有多個量詞的等價式 在含有多個量詞的謂詞公式中, ?x?y, ?x?y的位置是可以改變的,且不影響命題的真值。 即相同量詞間的次序是可以任意調動的，不同量詞間的次序則不能隨意調動。所以有： ?x?yP(x,y) ? ?y?xP(x,y) ?x?yP(x,y)? ?y?xP(x,y),,§2.3 一階邏輯等值式與置換規(guī)則,若謂詞公式中出現(xiàn)多個不同量詞時，則按照從左到右的次序讀

21、出，不能顛倒次序。例： ?y?x(x<y-2))表示任何y均存在x，使得x<y-2。,,§2.3 一階邏輯等值式與置換規(guī)則,,例 設 A(x,y)表示x和y同姓,論域x是甲村的人,y是乙村的人(?x)(?y)A(x,y): 甲村和乙村所有的人都同姓(?y)(?x)A(x,y)： 乙村和甲村所有的人都同姓。 顯然上述倆語句的含義相同。故 (?x)(?y)A(x,y) ?(?y)(?

22、x)A(x,y） 同理有： (?x)(?y)A(x,y)： 甲村與乙村有人同姓。 (?y)(?x)A(x,y)： 乙村與甲村有人都同姓。 故 (?x)(?y)A(x,y) ? (?y)(?x)A(x,y),,§2.3 一階邏輯等值式與置換規(guī)則,但是 (?x)(?y)A(x,y) 表示對于甲村所有的人，乙村都有人和他同姓。(?y)(?x)A(x,y) 表示存在一個乙村的人，甲村所有的人和他同姓

23、。 (?y)(?x)A(x,y) 表示對于乙村所有的人，甲村都有人和他同姓。(?x)(?y)A(x,y) 表示存在一個甲村的人，乙村所有人和他同姓。上述四種語句，表達的情況各不相同，故全稱量詞與存在量詞的次序，不能隨意更換。,,§2.3 一階邏輯等值式與置換規(guī)則,例：設個體域是整數集，則下列命題的真值為真的是（　　）A． ? y ? x(x·y=1)B． ? x ? y (x·y≠0)C．

24、? x ? y (x·y=y2)D． ? y ? x(x·y=x2),,§2.3 一階邏輯等值式與置換規(guī)則,1.置換規(guī)則： 設P(A)是含公式A的公式，若A ? B,則用公式B取代P(A)中所有的A之后的公式P(B)與P(A)等價。 例：(?x) (A(x) → B) ? (?x) (? A(x) ∨ B),等價演算的基本規(guī)則(1),,§2.3 一階邏輯等值式與置換規(guī)則,2．約

25、束元的換名規(guī)則 設A為一公式，將A中某量詞轄域中某約束變量的指導變元及相應的約束變元改成該量詞轄域中未曾出現(xiàn)過的某個體變量符號，公式的其余部分不變，所得公式與A等價. 例：?(?x) (P(x,y) ? Q(x)) ? ?xR(x) ? ?(?z) (P(z,y) ? Q(z)) ? ?xR(x),等價演算的基本規(guī)則(2),,§2.3 一階邏輯等值式與置換規(guī)則,3．自由元的代入規(guī)

26、則 設A為一公式，將A中某個自由出現(xiàn)的個體變元的所有出現(xiàn)用A中未曾出現(xiàn)過的個體變元符號代替，A中其余部分不變，所得公式與A等價. 例：?(?x) (P(x,y) ? Q(x)) ? ?xR(x) ? ?(?x) (P(x,w) ? Q(x)) ? ?xR(x),等價演算的基本規(guī)則(3),,§2.3 一階邏輯等值式與置換規(guī)則,例4試證明： (?x) (A(x) → B(x)) ? (?x)A(x)

27、→ (?x)B(x) 證明： (?x) (A(x) → B(x)) ? (? x) (? A(x) ∨ B(x))? (? x) ? A(x) ∨ (? x) B(x) /* ?對∨的分配率*/? ? (? x) A(x) ∨ (? x) B(x) /*量詞轉化率*/ ? (? x) A(x) → (? x) B(x) /* 命題等價式在謂詞演算中推廣,,§2.3

28、 一階邏輯等值式與置換規(guī)則,,§2.4 一階邏輯前束范式,前束范式(Prenex normal form) 定義1:任何一個謂詞公式A，如果具有如下形式： (□x1) (□x2)… (□xn)B其中□可能是量詞?或量詞?， xi（i=1，… n）是客體變元，B是不含量詞的謂詞公式，則稱A是前束范式。說明:前束范式的量詞均在全式的開頭,它們的作用域延伸到整個公式的末尾。例1:

29、 ?x?y（（F(x)∧G(y)）∧┐H(x,y)） √ ?x?y(F(x,y)∧G(y,z))∨ ?x H(x,y,z) ×,,§2.4 一階邏輯前束范式,定理1:任何一個謂詞公式,均和一個前束范式等價。前束范式的求法：第一步：否定深入。即利用量詞轉化公式，把否定聯(lián)結詞深入到命題變元和謂詞填式的前面。第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變元的名稱，以便消除混亂。第三步：量詞前

30、移。即利用量詞轄域的收縮與擴張把量詞移到前面。這樣便可求出與公式等價的前束范式。,,§2.4 一階邏輯前束范式,例1： ?xP(x) ? R(x) ? ?yP(y) ? R(x) ? ?y(P(y) ? R(x)) 例2：把?xP(x)? ?xQ(x) 變成前束范式。?xP(x)? ?xQ(x) ? ¬?xP(x)??xQ(x)

31、 ? ?x¬P(x) ??xQ(x) ? ?x(¬P(x) ?Q(x)),,§2.4 一階邏輯前束范式,例3： ?x ?y(?z P(x,z) ∧ P(y,z)) → ?u Q(x, y, u)解: ?x ?y(?z P(x,z) ∧ P(y,z)) → ?u Q(x, y, u)???

32、x ?y(?z P(x, z) ∧ P(y,z)) ∨?u Q(x, y, u) /*置換規(guī)則*/??x?y(?z ?P(x, z) ∨?P(y, z)) ∨ ?u Q(x,y,u) /*量詞轉化律*/??x?y(?w ?P(x,w) ∨?P(y,z)) ∨ ?u Q(s, t, u) /*改名

33、及代入規(guī)則*/??x ?y ?w ?u(?P(x,w) ∨?P(y,z) ∨ Q(s,t,u)) /*量詞轄域擴張*/,,§2.4 一階邏輯前束范式,練1：(?x P(x,y) ? ?y Q(y)) ? ?xR(x)解：原式 ? ?(?x P(x,y) ? ?y Q(y)) ? ?xR(x) ? (?x?P(x,y) ? ?y?Q(y)) ? ?

34、xR(x) /*量詞轉化律*/? (?x?P(x,t) ? ?y?Q(y)) ? ?zR(z) /*改名及代入規(guī)則*/? (?x ?y(?P(x,t) ? ?Q(y))) ? ?z R(z) /*轄域擴張*/? ?x ?y ?z ((?P(x,t) ??Q(y)) ? R(z)

35、) /*轄域擴張*/,,§2.5 一階邏輯的推理理論,推理規(guī)則(Rules of inference)在謂詞演算中，推理的形式結構仍為 H1?H2?H3?....?Hn?C若 H1?H2?H3?....?Hn?C是永真式，則稱由前提H1,H2,H3,.…,Hn邏輯的推出結論C，但在謂詞邏輯中, H1,H2,H3,.…,Hn , C均為謂詞公式。命題演算中的推理規(guī)則，可在謂詞推理理論中應

36、用。,,§2.5 一階邏輯的推理理論,與量詞有關的四條重要推理規(guī)則：1、全稱量詞消去規(guī)則（US規(guī)則）2、全稱量詞引入規(guī)則（UG規(guī)則）3、存在量詞消去規(guī)則（ES規(guī)則）4、存在量詞引入規(guī)則（EG規(guī)則）注意：只能對前束范式適用上述規(guī)則。,,§2.5 一階邏輯的推理理論,1. 全稱指定規(guī)則（ US ）： ?x P(x) ∴P(c)使用此規(guī)則時要注意：

37、 （1）x是P(x)中的自由變元； （2）c是論域中的某個任意的客體.,,§2.5 一階邏輯的推理理論,2.全稱推廣規(guī)則（UG）： P(y) ∴ ?x P(x)使用此規(guī)則時注意:

38、(1) y在P(y)中自由出現(xiàn)，且y取任何值時P均為真。 (2) x不在P(y)中約束出現(xiàn).,,§2.5 一階邏輯的推理理論,3.存在指定規(guī)則(ES): ?x P(x) ∴ P(c) 注:c是論域中的某些客體,c并不是任意的使用此規(guī)則時應注意： c是使P為真的特定客體；,,§2.5 一階邏輯的推理理論,(4)存在推廣規(guī)則(EG):

39、 P(c) ∴ ?x P(x)使用此規(guī)則時注意: (1) C是個體域中某個確定的個體。 (2) 代替C的x不能已在P(c)中出現(xiàn)。,,§2.5 一階邏輯的推理理論,2 推論規(guī)則及使用說明 命題邏輯中的P,T,CP規(guī)則和直接、間接證明法，都可以引用到謂詞邏輯的推理中來，不過要注意對量詞做適當處理. 其處理方法是：用US,ES在推導

40、中去掉量詞，用UG,EG使結論量化（加上量詞）。,,§2.5 一階邏輯的推理理論,規(guī)則使用說明：（1）在使用ES,US時,謂詞公式必須是前束范式（2）推導中連續(xù)使用US規(guī)則可用相同變元 ?xP(x) ?P(y), ?xQ(x) ?Q(y) （3）推導中既用ES，又用US， 則必須先用ES ，后用US方可取相同變元，反之不行。 ?xP(x) ?P(y) ?xQ(

41、x) ?Q(y) （4）推導中連續(xù)使用ES規(guī)則時，使用一次更改一個變元。,,§2.5 一階邏輯的推理理論,例 指出下列推導中的錯誤，并加以改正。 (1) ?xP(x) P (2) P(c) ES(1) (3) ?xQ(x) P (4) Q(c) ES(2) 解 第二次使用存在量詞消去規(guī)則時，所指定的特定個體應該是證明序列以前公式中沒有出現(xiàn)過的，正確

42、的推理是： (1) ?xP(x) P (2) P(c) ES(1) (3) ?xQ(x) P (4) Q(d) ES(2),,§2.5 一階邏輯的推理理論,例1證明蘇格拉底三段論:凡是人都是要死的。蘇格拉底是人。蘇格拉底是要死的。設：M(x):x是人。D(x):x 是要死的。a:蘇格拉底。則 前提：?x(M(x)?D(x

43、))，M(a）. 結論： D(a) .證明：① ?x (M(x)?D(x)) P ② M(a)?D(a) US ① ③ M(a) P ④ D(a) T② ③ I11 (直接證法),,§2.5 一階邏輯

44、的推理理論,例2:前提：?x(F(x)∨G(x))， ┐?x G(x). 結論： ?x F(x) .證明：① ┐?x G(x) P ② ?x ┐G(x) T① 置換規(guī)則 ③ ┐G(a) US ② ④ ?x(F(x)∨G(x)) P

45、⑤ F(a)∨G(a) US ④ ⑥ F(a) T③ ⑤ ⑦ ?x F(x) EG ⑥,,§2.5 一階邏輯的推理理論,練3:前提： ?x (A(x)?B(x))， ?x A(x) 結論： ?x B(x)證明：① ?x A(x)

46、 P前提引入 ② A(c) ES ① ③ ?x (A(x)?B(x)) P前提引入 ④ A(c)?B(c) US ③ ⑤ B(c) T② ④

47、 ⑥ ?x B(x) EG ⑤注意： ① ③引入的順序不可更改！,,§2.5 一階邏輯的推理理論,例4:前提：?x(F(x)∨G(x)), ?x(┐R(x)∨┐G(x)), ?x R(x). 結論： ?x F(x) .(歸謬法)證明：① ┐?x F(x) P結論否定引入

48、 ② ?x ┐F(x) T① ③ ┐F(a) ES ② ④ ?x(F(x)∨G(x)) P ⑤ F(a)∨G(a) US ④ ⑥ G(a) T③⑤,,§2.5 一階邏輯的推理理論,⑦ ?x(┐R(x)∨┐

49、G(x)) P ⑧ ┐R(a)∨┐G(a)) US ⑦ ⑨ ┐R(a) T⑥ ⑧ ⑩?x R(x) P (11) R(a) US ⑩

50、 (12) ┐R(a)∧R(a) 矛盾式,,§2.5 一階邏輯的推理理論,例5:證明: ?x(P(x)∨Q(x))=>┐(?x)P(x)?(?x)Q(x) (附加前提法)證明：(1) ┐(?x)P(x) P(附加前提) (2) (?x)┐P(x) T(1) (3) ┐P(

51、c) ES(2) (4) ?x(P(x)∨Q(x)) P (5) P(c)∨Q(c) US(4),,§2.5 一階邏輯的推理理論,(6) Q(c) T(3)(5)(7)(?x)Q(x)

52、 EG(6)(8) ?(?x)P(x) ?(?x)Q(x) CP小結：本節(jié)介紹了謂詞演算的推理規(guī)則,并舉例說明了它們的應用. 重點:深刻理解四個推理規(guī)則,會應用它們推理證明.作業(yè): P85 12、15、 24,,§2.5 一階邏輯的推理理論,Cp 規(guī)則證明例：證: ?x (P(x)?Q(x)) ? ?x P(x)? ?xQ(x) 證明：(1) ?x P(x)附加前提 (2) ?x (

53、P(x)?Q(x)) P (3)P(c) ?Q(c) ES (2)　 (4) P(c) US(1) (5) Q(c) T(3)(4)I (6) ?xQ(x) EG(5) (7) ?x P(x)??xQ(x) CP,,§2.5 一階邏輯的推理理論,反證法例：證明： ¬

54、;?x(P(x)?Q(x)), ?xP(x) ? ¬ ?xQ(x) (1) ¬¬ ?xQ(x) 附加前提 (2) ?xQ(x) T(1)E (3) Q(c) US(2) (4) ?xP(x) P (5) P(c)

55、 US(4) (6) P(c)?Q(c) T(3)(5)I (7) ?x(P(x)?Q(x)) UG(6) (8) ¬?x(P(x)?Q(x)) P (9) ?x(P(x)?Q(x)) ? ¬?x(P(x)?Q(x)) T(7)(8)I

56、(10) F,,§2.5 一階邏輯的推理理論,例 將下列推理符號化并給出形式證明: 每一個大學生不是文科生就是理科生；有的大學生是優(yōu)等生；小張不是文科生但他是優(yōu)等生。因此，如果小張是大學生，他就是理科生。解 個體域取全總個體域，設P(x)：x是大學生，Q(x)：x是文科生，S(x)：x是理科生，T(x)：x是優(yōu)等生，c：小張，則前提：?x(P(x)?(Q(x)?S(x)))，?x(P(x)?T(x))，?Q

57、(c)?T(c)結論：P(c)?S(c),,§2.5 一階邏輯的推理理論,推理形式：?x(P(x)?(Q(x)?S(x))),?x(P(x)?T(x))，?Q(c)?T(c)?P(c)?S(c) 證明： (1) P(c) 附加前提 (2) ?x(P(x)?(Q(x)?S(x))) P (3) P(c)?(Q(c)?S(c))

58、 US(2) (4) Q(c)?S(c) T(1)(3) I (5) ?Q(c)?T(c) P (6) ?Q(c) T (5) I (7) ?Q(c) ? S(c) T (4) I (8) S(c) T (6)(7) I (9) P(c)?S(c)

59、 CP,,第二章小結,學習第二章要注意以下幾點：(1)同一個命題在不同個體域內可能有不同的符號化形式，同時也可能有不同的真值，因而在將一個命題符號化之前，必須弄清個體域。(2)在將命題符號化時，要特別注意量詞與聯(lián)結詞的搭配。經常的情況是全稱量詞?與蘊含詞?搭配，存在量詞?與合取詞?搭配。因此有下面兩種形式的公式：?x(A(x) ?B(x)) ①?x(A