離散數(shù)學(xué)第五章)

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

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

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

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

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

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

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

8、義也完全相同,,§2.3 一階邏輯等值式與置換規(guī)則,（2）量詞否定轉(zhuǎn)換律 ¬?xP(x)? ?x¬P(x) ¬?xP(x)? ?x¬P(x) 下面證明：¬?xP(x)? ?x¬P(x)設(shè)個(gè)體域?yàn)椋?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ī)則,舉例說(shuō)明量化命題和非量化命題的差別:否定形式不同例： 否定下列命題： (a)上海是一個(gè)小城鎮(zhèn) A(s) (b)每一個(gè)自然數(shù)都是偶數(shù) ?x(N(x)?E(x))上述二命題的否定為： (a)上海不是一個(gè)小城鎮(zhèn) ¬A(s)

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

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

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)設(shè)個(gè)體域?yàn)椋?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ī)則,從上述幾個(gè)等價(jià)公式可以推出如下的等價(jià)式：?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)設(shè)個(gè)體域?yàn)椋?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的個(gè)體域?yàn)檎麛?shù)。 A(x)：x是奇數(shù) B(x)：x是偶數(shù) ?x (A(x) ∨ B(x)) ? 所有正整數(shù)是奇數(shù)或者偶

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

18、x A(x) ? ? x B(x) ? 存在為奇數(shù)的正整數(shù)且存在為偶數(shù)的正整數(shù)。,,,§2.3 一階邏輯等值式與置換規(guī)則,量詞與聯(lián)結(jié)詞∧，∨的關(guān)系總結(jié)：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ī)則,對(duì)于二元謂詞有八種情況：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）含有多個(gè)量詞的等價(jià)式 在含有多個(gè)量詞的謂詞公式中, ?x?y, ?x?y的位置是可以改變的,且不影響命題的真值。 即相同量詞間的次序是可以任意調(diào)動(dòng)的，不同量詞間的次序則不能隨意調(diào)動(dòng)。所以有： ?x?yP(x,y) ? ?y?xP(x,y) ?x?yP(x,y)? ?y?xP(x,y),,§2.3 一階邏輯等值式與置換規(guī)則,若謂詞公式中出現(xiàn)多個(gè)不同量詞時(shí)，則按照從左到右的次序讀

21、出，不能顛倒次序。例： ?y?x(x<y-2))表示任何y均存在x，使得x<y-2。,,§2.3 一階邏輯等值式與置換規(guī)則,,例 設(shè) A(x,y)表示x和y同姓,論域x是甲村的人,y是乙村的人(?x)(?y)A(x,y): 甲村和乙村所有的人都同姓(?y)(?x)A(x,y)： 乙村和甲村所有的人都同姓。 顯然上述倆語(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) 表示對(duì)于甲村所有的人，乙村都有人和他同姓。(?y)(?x)A(x,y) 表示存在一個(gè)乙村的人，甲村所有的人和他同姓

23、。 (?y)(?x)A(x,y) 表示對(duì)于乙村所有的人，甲村都有人和他同姓。(?x)(?y)A(x,y) 表示存在一個(gè)甲村的人，乙村所有人和他同姓。上述四種語(yǔ)句，表達(dá)的情況各不相同，故全稱量詞與存在量詞的次序，不能隨意更換。,,§2.3 一階邏輯等值式與置換規(guī)則,例：設(shè)個(gè)體域是整數(shù)集，則下列命題的真值為真的是（　?。〢． ? 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ī)則： 設(shè)P(A)是含公式A的公式，若A ? B,則用公式B取代P(A)中所有的A之后的公式P(B)與P(A)等價(jià)。 例：(?x) (A(x) → B) ? (?x) (? A(x) ∨ B),等價(jià)演算的基本規(guī)則(1),,§2.3 一階邏輯等值式與置換規(guī)則,2．約

25、束元的換名規(guī)則 設(shè)A為一公式，將A中某量詞轄域中某約束變量的指導(dǎo)變?cè)跋鄳?yīng)的約束變?cè)某稍摿吭~轄域中未曾出現(xiàn)過(guò)的某個(gè)體變量符號(hào)，公式的其余部分不變，所得公式與A等價(jià). 例：?(?x) (P(x,y) ? Q(x)) ? ?xR(x) ? ?(?z) (P(z,y) ? Q(z)) ? ?xR(x),等價(jià)演算的基本規(guī)則(2),,§2.3 一階邏輯等值式與置換規(guī)則,3．自由元的代入規(guī)

26、則 設(shè)A為一公式，將A中某個(gè)自由出現(xiàn)的個(gè)體變?cè)乃谐霈F(xiàn)用A中未曾出現(xiàn)過(guò)的個(gè)體變?cè)?hào)代替，A中其余部分不變，所得公式與A等價(jià). 例：?(?x) (P(x,y) ? Q(x)) ? ?xR(x) ? ?(?x) (P(x,w) ? Q(x)) ? ?xR(x),等價(jià)演算的基本規(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) /* ?對(duì)∨的分配率*/? ? (? x) A(x) ∨ (? x) B(x) /*量詞轉(zhuǎn)化率*/ ? (? x) A(x) → (? x) B(x) /* 命題等價(jià)式在謂詞演算中推廣,,§2.3

28、 一階邏輯等值式與置換規(guī)則,,§2.4 一階邏輯前束范式,前束范式(Prenex normal form) 定義1:任何一個(gè)謂詞公式A，如果具有如下形式： (□x1) (□x2)… (□xn)B其中□可能是量詞?或量詞?， xi（i=1，… n）是客體變?cè)珺是不含量詞的謂詞公式，則稱A是前束范式。說(shuō)明:前束范式的量詞均在全式的開(kāi)頭,它們的作用域延伸到整個(gè)公式的末尾。例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:任何一個(gè)謂詞公式,均和一個(gè)前束范式等價(jià)。前束范式的求法：第一步：否定深入。即利用量詞轉(zhuǎn)化公式，把否定聯(lián)結(jié)詞深入到命題變?cè)椭^詞填式的前面。第二步：改名。即利用換名規(guī)則、代入規(guī)則更換一些變?cè)拿Q，以便消除混亂。第三步：量詞前

30、移。即利用量詞轄域的收縮與擴(kuò)張把量詞移到前面。這樣便可求出與公式等價(jià)的前束范式。,,§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) /*量詞轉(zhuǎn)化律*/??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)) /*量詞轄域擴(kuò)張*/,,§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) /*量詞轉(zhuǎn)化律*/? (?x?P(x,t) ? ?y?Q(y)) ? ?zR(z) /*改名及代入規(guī)則*/? (?x ?y(?P(x,t) ? ?Q(y))) ? ?z R(z) /*轄域擴(kuò)張*/? ?x ?y ?z ((?P(x,t) ??Q(y)) ? R(z)

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

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

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

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

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

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

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

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

43、))，M(a）. 結(jié)論： 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). 結(jié)論： ?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) 結(jié)論： ?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). 結(jié)論： ?x F(x) .(歸謬法)證明：① ┐?x F(x) P結(jié)論否定引入

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é)：本節(jié)介紹了謂詞演算的推理規(guī)則,并舉例說(shuō)明了它們的應(yīng)用. 重點(diǎn):深刻理解四個(gè)推理規(guī)則,會(huì)應(yīng)用它們推理證明.作業(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 一階邏輯的推理理論,例 將下列推理符號(hào)化并給出形式證明: 每一個(gè)大學(xué)生不是文科生就是理科生；有的大學(xué)生是優(yōu)等生；小張不是文科生但他是優(yōu)等生。因此，如果小張是大學(xué)生，他就是理科生。解 個(gè)體域取全總個(gè)體域，設(shè)P(x)：x是大學(xué)生，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)結(jié)論：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,,第二章小結(jié),學(xué)習(xí)第二章要注意以下幾點(diǎn)：(1)同一個(gè)命題在不同個(gè)體域內(nèi)可能有不同的符號(hào)化形式，同時(shí)也可能有不同的真值，因而在將一個(gè)命題符號(hào)化之前，必須弄清個(gè)體域。(2)在將命題符號(hào)化時(shí)，要特別注意量詞與聯(lián)結(jié)詞的搭配。經(jīng)常的情況是全稱量詞?與蘊(yùn)含詞?搭配，存在量詞?與合取詞?搭配。因此有下面兩種形式的公式：?x(A(x) ?B(x)) ①?x(A