1、2-7謂詞演算的推理理論,消去和添加量詞規(guī)則：,US(全稱(chēng)指定規(guī)則)：(x)G(x)G(c) ES(存在指定規(guī)則)：(x)G(x)G(c) UG(全稱(chēng)推廣規(guī)則)：G(y)(x)G(x) EG(存在推廣規(guī)則)：G(c)(x)G(x),US全稱(chēng)指定規(guī)則，書(shū)寫(xiě)形式： (x)G(x)G(c) 成立的條件是： c為任意的個(gè)體常量。,謂詞演算的推理理論,謂詞演算的推理理論,ES(存在指定規(guī)則) ，書(shū)寫(xiě)形式： (x)G(x)G(c) 成立的條件是： c是使G(x)為真的特定的個(gè)體常量。 c不在前提中或者居先推導(dǎo)公式中出現(xiàn)或自由出現(xiàn)，換句話說(shuō)，此c是在該推導(dǎo)之前從未使用過(guò)的。,謂詞演算的推理理論,例：令個(gè)體域

2、為全體自然數(shù)，O(x):x是奇數(shù)，E(x):x為偶數(shù)，試考察從已知前提 (x)O(x)和(x)E(x)出發(fā)的下列推理。 （1） (x)O(x) P （2） O(c) ES(1) （3） (x)E(x) P （4） E(c) ES(3) （5） O(c) E(c) T(2)(4)I,謂詞演算的推理理論,UG全稱(chēng)推廣規(guī)則 ，書(shū)寫(xiě)形式： G(x)(x)G(x) 成立的條件和限制是： x是G(x)中自由出現(xiàn)的個(gè)體變量。且x取遍整個(gè)個(gè)體域時(shí)，都有G(x)為真。,謂詞演算的推理理論,EG存在推廣規(guī)則 ，書(shū)寫(xiě)形式： G(c)(x)G(x) 成立的條件和限制是： c是使G(c)為真的特定的個(gè)體常量。,謂詞演算

3、的推理理論,在推導(dǎo)的過(guò)程中，可以引用命題演算中的規(guī)則P、規(guī)則T、規(guī)則CP 。 為了在推導(dǎo)過(guò)程中消去量詞，可以引用規(guī)則US和規(guī)則ES來(lái)消去量詞。 當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則UG和規(guī)則EG將其量詞加入。 證明時(shí)可采用如命題演算中的直接證明方法和間接證明方法。 在推導(dǎo)過(guò)程中，對(duì)消去量詞的公式或公式中沒(méi)含量詞的子公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。,謂詞演算的推理理論,在推導(dǎo)過(guò)程中，對(duì)含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。 在推導(dǎo)過(guò)程中，如既要使用規(guī)則US又要使用規(guī)則ES消去公式中的量詞(只要有可能，我們總是先使用規(guī)則ES，再使用規(guī)則US)。然

4、后再使用命題演算中的推理規(guī)則，最后使用規(guī)則UG或規(guī)則EG引入量詞，得到所要的結(jié)論。 如一個(gè)變量是用規(guī)則ES消去量詞,對(duì)該變量在添加量詞時(shí),則只能使用規(guī)則EG,而不能使用規(guī)則UG;如使用規(guī)則US消去量詞,對(duì)該變量在添加量詞時(shí),則可使用規(guī)則EG和規(guī)則UG。,謂詞演算的推理理論,如有兩個(gè)含有存在量詞的公式，當(dāng)用規(guī)則ES消去量詞時(shí)，不能選用同樣的一個(gè)常量符號(hào)來(lái)取代兩個(gè)公式中的變?cè)?，而?yīng)用不同的常量符號(hào)來(lái)取代它們。 在用規(guī)則US和規(guī)則ES消去量詞時(shí)，此量詞必須位于整個(gè)公式的最前端。 在添加的量詞(x)、(x)時(shí)，所選用的x不能在公式G(c)中以任何約束出現(xiàn)。,謂詞演算的推理理論,推理一般根據(jù)US或UG規(guī)

5、則，消除量詞后，才能對(duì)謂詞公式進(jìn)行蘊(yùn)含或等價(jià)推證。在做了適當(dāng)?shù)耐蒲莺?，在?yīng)用ES，EG規(guī)則恢復(fù)約束關(guān)系，以完成帶量詞公式的邏輯推證,解：設(shè)H(x)：x是人；M(x)：x是要死的；s：蘇格拉底。 則符號(hào)化為： (x)(H(x)M(x)，H(s)M(s),例：證明 “所有的人都是要死的；蘇格拉底是人。所以蘇格拉底是要死的?！?證明：(1)(x)(H(x)M(x)P (2)H(x)M(x)US(1) (3)H(s)P (4)M(s)T(2),(3),證明：(1)(x)(H(x)M(x)P (2)H(s)M(s)US(1) (3)H(s)P (4)M(s)T(2),(3),(2)錯(cuò)了！ 正確的為：,謂

6、詞演算的推理理論,謂詞演算的推理理論,請(qǐng)看推導(dǎo)： (1)(x)(P(x)Q(x) P (2)(P(x)Q(x) US(1) (3)(x)P(x) P (4)P(x)ES (5)Q(x)T(2),(4),I (6)(x)Q(x) EG(5) 錯(cuò)誤。A:使用了US ES ,該用特定個(gè)體變量沒(méi)有用。,例：證明(x)(P(x)Q(x)，(x)P(x)(x)Q(x),謂詞演算的推理理論,請(qǐng)看推導(dǎo)： (1)(x)(P(x)Q(x) P (2)(P(c)Q(c)US(1) (3)(x)P(x)P (4)P(c)ES (5)Q(c)T(2),(4),I (6)(x)Q(x)EG(5),US和ES的使用順序反了

7、,謂詞演算的推理理論,正確地推導(dǎo)如下： (1)(x)P(x)P (2)P(c)ES(1) (3)(x)(P(x)Q(x) P (4)(P(c)Q(c)US(3) (5)Q(c)T(2),(4),I (6)(x)Q(x)EG(5),謂詞演算的推理理論,證明：1)(x)(P(x)Q(x)P 2)(P(c)Q(c)ES(1) 3)P(c)T(2),I 4)Q(c)T(2),I 5)(x)P(x) EG(3),I 6)(x)Q(x) EG(4),I 7)(x)P(x)(x)Q(x)T(5),(6),I,例：證明(x)(P(x)Q(x)(x)P(x)(x)Q(x),謂詞演算的推理理論,1)(x)P(x)

8、(x)Q(x) P 2)(x)P(x) T(1) 3)P(c)ES(2) 4)(x)Q(x) T(1) 5)Q(c)ES(4) 6)(P(c)Q(c)T(3),(4) 7)(x)(P(x)Q(x)EG(6),請(qǐng)看上述推論的逆推導(dǎo)：,謂詞演算的推理理論,正確地推導(dǎo)如下： 1)(x)P(x)(x)Q(x) P 2)(x)P(x) T(1) 3)P(c) ES(2) 4)(x)Q(x) T(1) 5)Q(b) ES(4) 6)(P(c)Q(b) T(3),(4) 7)(y) (P(c)Q(y) EG(6) 8)(x)(y)(P(x)Q(y) EG(7),謂詞演算的推理理論,例：證明下述論斷的正確性：

9、 所有的哺乳動(dòng)物都是脊椎動(dòng)物； 并非所有的哺乳動(dòng)物都是胎生動(dòng)物； 故有些脊椎動(dòng)物不是胎生的。,謂詞演算的推理理論,解：設(shè)謂詞如下： P(x)：x是哺乳動(dòng)物； Q(x)：x是脊椎動(dòng)物； R(x)：x是胎生動(dòng)物。 則有：(x)(P(x)Q(x),(x)(P(x)R(x) (x)(Q(x)R(x),謂詞演算的推理理論,(x)(P(x)R(x)P (P(x)R(x)US(1) (P(x)R(x)T(2)，E (P(x)R(x)T(3),E P(x)T(4),I R(x)T(4),I,請(qǐng)看下面推導(dǎo)：,謂詞演算的推理理論,續(xù)： (x)(P(x)Q(x)P P(x)Q(x)US(7) Q(x)T(5),(8

10、),I Q(x)R(x)T(6),(9),I (x)(Q(x)R(x)EG(10),謂詞演算的推理理論,(x)(P(x)R(x)P (x) (P(x)R(x) T(1),E (P(c) R(c) ES(2) (P(c)R(c)T(3),E P(c)T(4),I,證明：,謂詞演算的推理理論,續(xù)： R(c)T(4),I (x)(P(x)Q(x)P P(c)Q(c)US(7) Q(c)T(5),8),I Q(c)R(c)T(6),(9),I (x)(Q(x)R(x)EG(10),謂詞演算的推理理論,證明(采用反證法)： (x)P(x)(x)Q(x)P(附加前提) (x)P(x)(x)Q(x)T(1)

11、,E (x)P(x)T(2),I (x)Q(x)T(2),I (x)P(x)T(3),E P(c)ES(5)(7),例：證明(x)(P(x)Q(x)(x)P(x)(x)Q(x),謂詞演算的推理理論,續(xù)： (x)Q(x)T(4),E Q(c)US(7) P(c)Q(c)T(6),(8),I (P(c)Q(c)T(9),E (x)(P(x)Q(x)P (P(c)Q(c)US(11) (P(c)Q(c)(P(c)Q(c)T(10),謂詞演算的推理理論,例：證明下列論斷的正確性： 有些學(xué)生相信所有的教師；任何一個(gè)學(xué)生都不相信騙子；所以，教師都不是騙子。 解：設(shè)謂詞如下： S(x)：x是學(xué)生T(x)：x

12、是教師 P(x)：x是騙子L(x,y)：x相信y 則可符號(hào)化為： 前提：(x)(S(x)(y)(T(y)L(x,y)， (x)(S(x)(y)(P(y)L(x,y)。 結(jié)論：(x)(T(x)P(x) 即證明：(x)(S(x)(y)(T(y)L(x,y)， (x)(S(x)(y)(P(y)L(x,y) (x)(T(x)P(x),謂詞演算的推理理論,證明： (x)(S(x)(y)(T(y)L(x,y)P S(c)(y)(T(y)L(c,y)ES(1) S(c)T(2),I (y)(T(y)L(c,y)T(2),I T(b)L(c,b)US(4) (x)(y)(S(x)P(y)L(x,y)P,謂詞演

13、算的推理理論,續(xù)： (y)(S(c)P(y)L(c,y)US(6) (S(c)P(b)L(c,b) US(7) S(c)(P(b)L(c,b) T(8),E P(b)L(c,b) T(3),(8),E L(c,b)P(b) T(10),E T(b)P(b) T(5),(11),E (x)(T(x)P(x) US(12),謂詞演算的推理理論,1.采用反證法： (x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y) P (x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y) T(1),E (y)(P(y)R(c,y)(y)(Q(y)R(c,y) ES(2) (y)(P(y)R(c,

14、y)(y)(Q(y)R(c,y) T(3),E (y)(P(y)R(c,y)T(4),I,例：證明(x)(P(x)Q(x)(x)(y)(P(y)R(x,y)(y)(Q(y)R(x,y)。,謂詞演算的推理理論,續(xù)： 6) P(b)R(c,b)ES(5) 7) P(b)T(6),I 8) (x)(P(x)Q(x)P 9) P(b)Q(b)US(8) 10)Q(b)T(7),(9),I,謂詞演算的推理理論,續(xù)： R(c,b)T(6),I (Q(b)R(c,b)T(10),(11)I (y)(Q(y)R(c,y)T(4),E (y)(Q(y)R(c,y)T(4),E (Q(b)R(c,b)US(14)

15、 (Q(b)R(c,b)(Q(b)R(c,b),CP,P78例題4,(1)(x)(y)(S(x,y) M(y)(z)(P(z)R(x,z) P (2)(y)(S(b,y) M(y)(z)(P(z)R(b,z) US(1) (3) (z)P(z) P(附加前提） (4) (z) P(z) T(3)E (5) P(a) US(4) (6) P(a) R(b,a) T(5)I (7) (P(a) R(b,a) T(6)E (8) (z) (P(z) R(b,z) UG(7) (9) (z) (P(z) R(b,z) T(8)E (10) (y)(S(b,y) M(y) T(2)(9)I (11) (

16、y) (S(b,y) M(y) T(10)I,P78例題4,(12) (S(b,c) M(c) US(11) (13) S(b,c) M(c) T(12)E (14) S(b,c) - M(c) T(13)E (15) (y) (S(b,y) - M(y) ) UG(14) (16) (x)(y)(S(x,y) - M(y) UG(15) (17) (z)P(z) - (x)(y)(S(x,y) - M(y) CP,P79(3)c,解：設(shè)G(x):x是大學(xué)生。L(x):x是文科學(xué)生。 P(x):x是理工科學(xué)生。S(x):x是優(yōu)秀生。c:小張 本題符號(hào)化為 (x)(G(x)-L(x) P(x),(x)(G(x) S(x), P(c),S(c)=G(c)-L(c) L(x) P(x) (L(x) P(x) (1) G(c) P(附加前提) (2) (x)(G(x)- (L(x) P(x) P (3) (G(c)- (L(c) P(c) U