第5章 推理与证明技术

1、第第5 5章章 推理与证明技术推理与证明技术 数学归纳法的使用数学归纳法的使用 3CPCP规则相关证明规则相关证明4命题逻辑的推理理论命题逻辑的推理理论 1谓词逻辑的推理理论谓词逻辑的推理理论 25.2 命题逻辑的推理理论命题逻辑的推理理论 概念概念描述问题描述问题的句子的句子Add Your TexT判断判断对概念的肯对概念的肯定定与否定的与否定的判断判断推理推理从一个或多从一个或多个前提推出个前提推出结论的结论的思维思维过程过程认识世界的渐进过程认识世界的渐进过程在推理中，在推理中，前提前提是已知的命题公式，是已知的命题公式，结论结论是从前提出是从前提出发应用推理规则推出的命题公式，这一过

2、程称为发应用推理规则推出的命题公式，这一过程称为有效有效推理推理或或形式证明形式证明，所得的结论称为，所得的结论称为有效结论有效结论。在推理中，最关心的不是结论的真实性而是在推理中，最关心的不是结论的真实性而是推理的有推理的有效性效性。所谓所谓推理有效推理有效，指的是，指的是它的结论是它前提的合它的结论是它前提的合乎逻辑的结果乎逻辑的结果。推理的有效性和结论的真实性推理的有效性和结论的真实性推理的有效性推理的有效性和和结论的真实性结论的真实性是不同的，是不同的，有效的推理有效的推理不一定产生真实的结论不一定产生真实的结论；而；而产生真实结论的推理过程产生真实结论的推理过程未必是有效的未必是有效

3、的，因为，因为有效的推理有效的推理中可能包含为中可能包含为“假假”的前提的前提，而，而无效的推理无效的推理却可能得到为却可能得到为“真真”的结论的结论。如果前提为真，有效推理所得的结论必然为真如果前提为真，有效推理所得的结论必然为真。5.2.1 5.2.1 推理的基本概念和推理形式推理的基本概念和推理形式 定义定义5.2.0 5.2.0 设设G,HG,H是公式，对任意解释是公式，对任意解释I I，如果，如果I I满满足足G G，那么，那么I I满足满足H H，则称，则称H H是是G G的逻辑结果的逻辑结果( (或称或称G G蕴蕴涵涵H),H),记为记为G G，此时称，此时称G G为前提为前提，

4、H H为为结论结论。 推理也称论证，它是由已知命题得到新的命题的思推理也称论证，它是由已知命题得到新的命题的思维过程，其中已知的命题称为维过程，其中已知的命题称为推理的前提推理的前提或或假设假设，推得的新命题称为推得的新命题称为推理的结论推理的结论。判定定理判定定理定理定理5.2.0 5.2.0 设设G,HG,H是公式，是公式，H H是是G G的逻辑结果当且仅当的逻辑结果当且仅当GG为永真公式。为永真公式。 证明：证明：“”若若G G，但，但GHGH不是永真不是永真公公式。式。于是，必存在一个解释于是，必存在一个解释I I，使得，使得GHGH为假，即在为假，即在解释解释I I下，下，G G为真

5、，而为真，而H H为假，这与为假，这与G G矛盾，故矛盾，故GHGH是永真公式。是永真公式。“”若若GHGH是永真式，但是永真式，但G G不成立，故存不成立，故存在在G,HG,H的一个解释的一个解释I I，使得，使得G G为真，而为真，而H H为假，从而为假，从而在解释在解释I I下，下，GHGH为假，这与为假，这与GHGH是永真是永真公公式矛式矛盾，所以盾，所以G G。推广推广 定义定义5.2.1 5.2.1 设设G G1 1,G,G2 2, , ,G Gn n,H,H是公式，称是公式，称H H是是G G1 1,G,G2 2, , , G Gn n的逻辑结果的逻辑结果(G(G1 1,G,G2

6、 2, , ,G Gn n共同蕴涵共同蕴涵H),H),当且仅当当且仅当H H是是G G1 1GG2 2G Gn n的逻辑结果的逻辑结果(logic conclusion)(logic conclusion)。记。记为为G G1 1,G,G2 2, , ,G Gn n，此时称，此时称G G1 1,G,G2 2, , ,G Gn n为为有效有效的的(efficacious),(efficacious),否则称为否则称为无效的无效的(inefficacious)(inefficacious)。G G1 1,G,G2 2, , ,G Gn n称为一组前提称为一组前提(Premise),(Premise

7、),有时用集合有时用集合来 表 示 ， 记来 表 示 ， 记 = G = G1 1, G, G2 2, , , , G Gn n 。 H H 称 为称 为 结 论结 论(conclusion)(conclusion)。又称。又称H H是是前提集合前提集合的逻辑结果。记的逻辑结果。记为为H H。 判定定理判定定理定理定理5.2.15.2.1 公式公式H H是前提集合是前提集合=G=G1 1,G,G2 2, , ,G Gn n 的逻的逻辑结果当且仅当辑结果当且仅当G G1 1GG2 2G Gn n为永真公式。为永真公式。 “”与与“”的的不同不同1.1.“”“”仅是一般的仅是一般的蕴涵联结词蕴涵联

8、结词，GHGH的结果仍是一的结果仍是一个公式，而个公式，而“”却描述了两个公式却描述了两个公式G G，H H之间的一种之间的一种逻辑蕴涵关系，逻辑蕴涵关系，G G H H的的“结果结果”，并非命题公式；，并非命题公式；2.2. 用计算机来判断用计算机来判断G G H H是办不到的。然而计算机是办不到的。然而计算机却可却可“计算计算”公式公式GHGH是否为永真公式。是否为永真公式。5.2.2 5.2.2 判断有效结论的常用方法判断有效结论的常用方法 =G G1 1, G, G2 2, , , ,G Gn n H HG G1 1GG2 2G Gn n为永真公式为永真公式真值表技术、演绎法和真值表技

9、术、演绎法和间接证明方法间接证明方法1 1、真值表技术、真值表技术设设P P1 1,P,P2 2, , ,P Pn n是出现在前提是出现在前提G G1 1,G,G2 2, ,G,Gn n和结论和结论H H中中的一切命题变元，如果将的一切命题变元，如果将P P1 1,P,P2 2, , ,P Pn n中所有可能中所有可能的解释及的解释及G G1 1,G,G2 2, ,G,Gn n，H H的对应真值结果都列在一的对应真值结果都列在一个表中，个表中，根据根据“”的定义，的定义，则有判断方法如下：则有判断方法如下：1.1. 对所有对所有G G1 1,G,G2 2, ,G,Gn n都具有真值都具有真值T

10、 T的行的行( (表示前提为真的表示前提为真的行行),),如果在每一个这样的行中，如果在每一个这样的行中，H H也具有真值也具有真值T T，则则H H是是G G1 1,G,G2 2, ,G,Gn n的逻辑结果。的逻辑结果。2.2. 对所有对所有H H具有真值为具有真值为F F的行的行( (表示结论为假的行表示结论为假的行),),如果在如果在每一个这样的行中，每一个这样的行中，G G1 1,G,G2 2, ,G,Gn n中至少有一个公式的中至少有一个公式的真值为真值为F(F(前提也为假前提也为假),),则则H H是是G G1 1,G,G2 2, ,G,Gn n的逻辑结果的逻辑结果。例例5.2.1

11、 5.2.1 判断下列判断下列H H是否是前提是否是前提G G1 1,G,G2 2的逻辑结果的逻辑结果(1)(1)H H：Q Q；G G1 1：P P；G G2 2：PQPQ；(2)(2)H H：P P； G G1 1：PQPQ；G G2 2：Q Q；(3)(3)H H：Q Q；G G1 1：P P；G G2 2：PQPQ。解解P P Q Q G G1 1G G2 2H H0 0 0 0 0 01 1 0 00 0 1 1 0 01 1 1 11 1 0 0 1 10 0 0 01 1 1 1 1 11 1 1 1(1)(1)P P Q Q G G1 1G G2 2H H0 0 0 01 11

12、 11 10 0 1 11 10 01 11 1 0 00 01 10 01 1 1 11 10 00 0(2)(2)P P Q Q G G1 1G G2 2H H0 0 0 0 1 11 1 0 00 0 1 1 1 11 1 1 11 1 0 0 0 00 0 0 01 1 1 1 0 01 1 1 1(3)(3)是是是是否否2 2 推理定律推理定律设设G G，H H，I I，J J是任意的命题公式，则有：是任意的命题公式，则有：1)1) I I1 1：GHGHG G( (简化规则简化规则) )I I2 2：GHGHH H2)2) I I3 3：G GGHGH( (添加规则添加规则) )I

13、 I4 4：H HGHGH3)3) I I5 5：G GGHGHI I6 6：H HGHGH4)4) I I7 7：(GH)(GH)G GI I8 8：(GH)(GH)HH5)5) I I9 9：G G，H HGHGH2 2 推理定律推理定律( (续续) )6)6) I I1010：G G，GHGHH H( (选言三段论选言三段论) )I I1111：G G，G HG HH H7)7) I I1212：G G，GHGHH H( (分离规则分离规则) )8)8) I I1313：H H，GHGHGG( (否定后件式否定后件式) )9)9) I I1414：GHGH，HIHIGIGI( (假言三段

14、论假言三段论) )10)10)I I1515：GHGH，GIGI，HHI II I( (二难推论二难推论) )3 3 演绎法演绎法 演绎法演绎法是从前提是从前提( (假设假设) )出发，依据公认的推理规则出发，依据公认的推理规则和推理定律，推导出一个结论来。和推理定律，推导出一个结论来。 Y YN N触发规则触发规则新事实新事实事实事实= =结结论？论？事实库事实库规则匹配规则匹配公理库公理库将事实加入到事实库中将事实加入到事实库中结束结束引入事实引入事实演绎的定义演绎的定义定义定义5.2.25.2.2 从前提集合从前提集合推出结论推出结论H H的一个演绎是的一个演绎是构造命题公式的一个有限序

15、列：构造命题公式的一个有限序列： H H1 1，H H2 2，H Hn n其中，其中，H Hi i或者是或者是中的某个前提，或者是前面的某中的某个前提，或者是前面的某些些H Hj j（jijxyx。 推导推导1 1： （1 1）( ( x)(x)( y)G(x, y)y)G(x, y) P P （2 2）( ( y)G(y, y) y)G(y, y) US,(1) US,(1) 分析分析：推导：推导1 1是错误的。是错误的。正确的推导如下：正确的推导如下： （1 1）( ( x)(x)( y)G(xy)G(x, y) , y) P P （2 2）( ( y)G(zy)G(z, y), y)US

16、,(1)US,(1)注意：注意：使用使用US规则规则来来消去消去量词时，若选用量词时，若选用变元变元y取代取代x，则要求，则要求在在原公式中原公式中x x不能出现不能出现在量词在量词( ( y)y)或或( ( y)y)的辖域之内的辖域之内。推理规则的正确使用推理规则的正确使用(2)(2)推导推导2 2： （1 1）( ( x)(x)( y)G(x, y) P y)G(x, y) P （2 2）( ( y)G(z, y) US,(1)y)G(z, y) US,(1) （3 3）G(z, c) ES,(2)G(z, c) ES,(2) 分析分析：推导：推导2 2是错误的。是错误的。正确的推导如下：

17、正确的推导如下： （1 1）( ( x) (x) ( y)G(x, y) P y)G(x, y) P （2 2）( ( y)G(z, y) US,(1)y)G(z, y) US,(1) （3 3）G(z, f(z) ES,(2) G(z, f(z) ES,(2) 注意：注意：使用使用ESES规则规则来来消去消去量词时，量词时， 若还若还有其它有其它自由变自由变元元时，时，则必须用关于自由则必须用关于自由变元的变元的函数符号函数符号来取代常量符号来取代常量符号. .推理规则的正确使用推理规则的正确使用(3)(3)推导推导3 3： （1 1）( ( y)G(z, y) Py)G(z, y) P （

18、2 2）( ( y)(y)( y)G(y, y) UG,(1)y)G(y, y) UG,(1)分析分析：推导：推导3 3是错误的。是错误的。正确的推导如下：正确的推导如下： （1 1）( ( y)G(zy)G(z, y) P, y) P （2 2）( ( z)(z)( y)G(zy)G(z, y) UG,(1), y) UG,(1)注意：注意：使用使用UG规则规则来来添加添加量词时，若选量词时，若选用变元用变元x取代取代y，则要求，则要求在在原公式中原公式中y不不能出现在量词能出现在量词( x)或或( x)的辖域之内的辖域之内。推理规则的正确使用推理规则的正确使用(4)(4)推导推导4 4：

19、（1 1）G(x, c) PG(x, c) P （2 2）( ( x)G(x, x) EG,(2)x)G(x, x) EG,(2)分析分析：推导：推导4 4是错误的。是错误的。正确的推导如下：正确的推导如下： （1 1）G(xG(x, c) P, c) P （2 2）( ( y)G(x, y) EG,(2)y)G(x, y) EG,(2)注意：注意：使用使用EG规则规则来来添加添加量词时，若选用量词时，若选用变元变元x取代取代c，则要求，则要求在在原公式中原公式中c不能出现不能出现在量词在量词( x)或或( x)的辖域之内的辖域之内且且原公式中原公式中无无自由变量自由变量x x。判断判断（1

20、1）( ( x)(x)( y)G(x, y)y)G(x, y) P P （2 2）( ( y)G(z, y)y)G(z, y)US,(1)US,(1)（3 3）G(z, c)G(z, c) ES,(2) ES,(2)（4 4）( ( x)G(x, c) x)G(x, c) UG,(3) UG,(3)（5 5）( ( y)y) ( ( x)G(x, y) x)G(x, y) EG,(4)EG,(4)5.3.2 5.3.2 谓词演算的综合推理方法谓词演算的综合推理方法1.1. 推导过程中可以引用命题演算中的推导过程中可以引用命题演算中的规则规则P P和规则和规则T T。2.2. 如果如果结论结论是

21、以是以蕴涵形式蕴涵形式( (或或析取形式析取形式) )给出，我们给出，我们还可以使用还可以使用规则规则CPCP。3.3. 若需若需消去量词消去量词，可以引用，可以引用规则规则USUS和和规则规则ESES。4.4. 当所要求的结论可能被当所要求的结论可能被定量定量时，此时可引用时，此时可引用规则规则UGUG和规则和规则EGEG将其量词加入。将其量词加入。谓词演算的综合推理方法谓词演算的综合推理方法( (续续1)1)5.5. 证明时可采用如证明时可采用如命题演算命题演算中的中的直接证明方法直接证明方法和和间接证明方法间接证明方法。6.6. 在推导过程中，在推导过程中，对消去量词的公式或公式中不对消

22、去量词的公式或公式中不含量词的子公式含量词的子公式，完全可以引用，完全可以引用命题演算中的命题演算中的基本等价公式和基本蕴涵公式基本等价公式和基本蕴涵公式。7.7. 在推导过程中，对在推导过程中，对含有量词的公式含有量词的公式可以引用可以引用谓谓词中的基本等价公式和基本蕴涵公式词中的基本等价公式和基本蕴涵公式。例例5.3.2 解：设解：设H(x)H(x)：x x是人；是人；M(xM(x) )：x x是要死的；是要死的；s s：苏格拉底。苏格拉底。则符号化为：则符号化为： ( ( x)(H(x)x)(H(x)M(xM(x)，H(sH(s) ) M(sM(s) )证明证明苏格拉底三段论苏格拉底三段

23、论：“所有的人都是要死的；苏格拉所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。底是人。所以苏格拉底是要死的。”证明：证明： (1) ( x)(H(x)M(x)P (2) H(x)M(x)US,(1) (3) H(s)P (4) M(s)T,(2),(3),I证明：证明：(1)( x)(H(x)M(x)P (2)H(s)M(s)US,(1) (3)H(s)P (4)M(s)T,(2),(3),I(4)错了！错了！例例5.3.3 5.3.3 证明：证明：( ( x)(P(x)x)(P(x)Q(xQ(x)，( ( x)x)P(xP(x) )( ( x)x)Q(x)Q(x)有下面的推导有下面

24、的推导： (1) (1) ( ( x)(P(x)x)(P(x)Q(xQ(x) P P (2) (2) P(x)P(x)Q(xQ(x) ) US,(1) US,(1) (3) (3) ( ( x)x)P(xP(x) ) P P (4) (4) P(cP(c) )ES,(3)ES,(3) (5) (5) Q(cQ(c) )T,(2),(4),IT,(2),(4),I (6) (6) ( ( x)x)Q(x)Q(x) EG,(5) EG,(5)推导错误！推导错误！例例5.3.3(5.3.3(续续) )推导可修改为推导可修改为：(1) (1) ( ( x)(P(x)x)(P(x)Q(xQ(x)P P(

25、2) (2) P(c)P(c)Q(cQ(c) )US,(1)US,(1)(3)(3) ( ( x)x)P(xP(x) )P P(4)(4) P(cP(c) )ES,(3)ES,(3)(5) (5) Q(cQ(c) )T,(2),(4),IT,(2),(4),I(6) (6) ( ( x)x)Q(x)Q(x)EG,(5)EG,(5)推导错误！推导错误！例例5.3.3(5.3.3(续续) )请看推导请看推导：(1)(1) ( ( x)x)P(xP(x) )P P(2)(2) P(cP(c) )ES,(1)ES,(1)(3) (3) ( ( x)(P(x)x)(P(x)Q(xQ(x)P P(4) (

26、4) P(c)P(c)Q(cQ(c) )US,(3)US,(3)(5) (5) Q(cQ(c) )T,(2),(4),IT,(2),(4),I(6) (6) ( ( x)x)Q(x)Q(x)EG,(5)EG,(5)正确！正确！例例5.3.4 5.3.4 证明证明：1) (1) ( x x) )( (P(xP(x) )Q(x)Q(x)P P 2) 2) P(cP(c) )Q(cQ(c) ) ES,1) ES,1) 3) 3) P(cP(c) )T,2),IT,2),I 4) 4) Q(cQ(c) )T,2),IT,2),I 5) 5) ( ( x x) )P(xP(x) )EG,3)EG,3)

27、6) 6) ( ( x x) )Q(x)Q(x)EG,4)EG,4) 7) 7) ( ( x x) )P(xP(x) )( ( x x) )Q(x)Q(x)T,5),6),I T,5),6),I 证明：证明：( ( x x) )( (P(xP(x) )Q(x)Q(x)( ( x)x)P(xP(x) )( ( x)x)Q(x)Q(x)例例5.3.4(5.3.4(续续1)1)1) (1) ( x x) )P(xP(x) )( ( x x) )Q(x)Q(x)P P2) 2) ( ( x x) )P(xP(x) )T,1),IT,1),I3) 3) P(cP(c) )ES,2)ES,2)4) 4)

28、( ( x x) )Q(x)Q(x)T,1),IT,1),I5) 5) Q(cQ(c) )ES,4)ES,4)6) 6) P(cP(c) )Q(cQ(c) )T,3),4),IT,3),4),I7) 7) ( ( x x) )( (P(xP(x) )Q(x)Q(x)EG,6) EG,6) 请看上述推论的逆推导：请看上述推论的逆推导：( ( x)x)P(xP(x) )( ( x)x)Q(xQ(x) )( ( x x) )( (P(xP(x) )Q(xQ(x) 错误！错误！例例5.3.4(5.3.4(续续2)2)正确地推导：正确地推导：1) (1) ( x x) )P(xP(x) )( ( x x

29、) )Q(x)Q(x)P P2) 2) ( ( x x) )P(xP(x) )T,1),IT,1),I3) 3) P(cP(c) )ES,2)ES,2)4) 4) ( ( x x) )Q(x)Q(x)T,1),IT,1),I5) 5) Q(bQ(b) )ES,4)ES,4)6) 6) P(cP(c) )Q(bQ(b) )T,3),5),IT,3),5),I7) 7) ( ( y y) )( (P(cP(c) )Q(yQ(y)EG,6)EG,6)8) 8) ( ( x x) )( ( y y) )( (P(xP(x) )Q(yQ(y)EG,7) EG,7) 例例5.3.5 5.3.5 证明证明(

30、 (采用反证法，采用反证法，CPCP规则的方法由同学完成规则的方法由同学完成) )：1 1) ) ( ( ( x)P(xx)P(x) )( ( x)x)Q(x)Q(x)P(P(附加附加) )2 2) ) ( ( x)P(xx)P(x) ) ( ( x)x)Q(x)Q(x)T,1),ET,1),E3) 3) ( ( x)P(xx)P(x) )T,2),IT,2),I4) 4) ( ( x)x)Q(x)Q(x)T,2),IT,2),I5) 5) ( ( x)x) P(xP(x) )T,3),ET,3),E6) 6) P(cP(c) ) ES,5) ES,5)证明证明( ( x)(P(xx)(P(x

31、) )Q(xQ(x) ) ( ( x)P(xx)P(x) )( ( x)x)Q(x)Q(x)例例5.3.5 5.3.5 7) (7) ( x)x) Q(x)Q(x) T,4),ET,4),E8) 8) Q(c)Q(c) US,7)US,7)9) 9) P(cP(c) ) Q(c)Q(c) T,6),8),IT,6),8),I10) 10) (P(c)(P(c)Q(c)Q(c) T,9),ET,9),E11) (11) ( x)(P(x)x)(P(x)Q(x)Q(x) P P12) (P(c)12) (P(c)Q(cQ(c) US,11)US,11)13) 13) ( (P(cP(c) )Q(c

32、)Q(c)( (P(cP(c) )Q(cQ(c) ) T,10),T,10),12)12)5.3.3 5.3.3 谓词逻辑推理的难点谓词逻辑推理的难点1.1. 在推导过程中，如在推导过程中，如既要使用规则既要使用规则USUS又要使用规则又要使用规则ESES消去公式中的量词，而且选用的个体是同一个消去公式中的量词，而且选用的个体是同一个符号，则必须符号，则必须先先使用规则先先使用规则ESES，再使用规则，再使用规则USUS。然后再使用命题演算中的推理规则，最后使用规然后再使用命题演算中的推理规则，最后使用规则则UGUG或规则或规则EGEG引入量词，得到所要的结论。引入量词，得到所要的结论。2.2

33、. 如一个变量是用如一个变量是用规则规则ESES消去量词消去量词，对该变量在添，对该变量在添加量词时，则加量词时，则只能使用规则只能使用规则EGEG，而不能使用规则，而不能使用规则UGUG；如使用；如使用规则规则USUS消去量词消去量词，对该变量在添加量，对该变量在添加量词时，则词时，则可使用规则可使用规则EGEG和规则和规则UGUG。谓词逻辑推理的难点谓词逻辑推理的难点( (续续) )3.3. 如有如有两个含有存在量词的公式两个含有存在量词的公式，当用，当用规则规则ESES消去消去量词量词时，时，不能选用同样的一个常量符号不能选用同样的一个常量符号来取代两来取代两个公式中的变元，而应用不同的

34、常量符号来取代个公式中的变元，而应用不同的常量符号来取代它们。它们。4.4. 在用在用规则规则USUS和和规则规则ESES消去量词消去量词，此量词必须位于，此量词必须位于整个公式的最前端。整个公式的最前端。谓词逻辑推理的难点谓词逻辑推理的难点( (续续) )5.5. 在在添加量词添加量词( ( x)x)、( ( x)x)时，所选用的时，所选用的x x不能在不能在公式公式G(yG(y) )或或G(cG(c) )中中自由出现自由出现，且，且G(yG(y) )或或G(cG(c) )对对x x应是应是自由自由的。的。6.6. 在使用在使用规则规则EGEG引入存在量词引入存在量词( ( x)x)时，时，

35、此此x x不得不得仅为仅为G(cG(c) )或或G(yG(y) )中的函数变元中的函数变元。在使用。在使用规则规则UGUG引入全称量词引入全称量词( ( x)x)时，时，此此x x不得为不得为G(yG(y) )中的函中的函数变元数变元( (因该函数变元不得作为自由变元因该函数变元不得作为自由变元) )。7.7. 在使用在使用规则规则UGUG引入全称量词引入全称量词( ( x)x)时，时，G(yG(y) )中不中不得出现在使用得出现在使用规则规则USUS引入引入y y之后由之后由规则规则ESES引入的引入的常量或函数。常量或函数。5.3.4 5.3.4 谓词逻辑推理的应用谓词逻辑推理的应用例例5

36、.3.65.3.6 每个喜欢步行的人都不喜欢坐汽车；每每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。喜欢骑自行车。因而有的人不喜欢步行。 设：设：H(xH(x) )：x x是人；是人； P(xP(x) )：x x喜欢坐汽车；喜欢坐汽车； Q(xQ(x) )：x x喜欢骑自行车；喜欢骑自行车；R(xR(x) )：x x喜欢步行喜欢步行。则上述语句可符号化为：则上述语句可符号化为： 前提前提：( ( x)(H(x)R(x)x)(H(x)R(x) P(x)P(x)， ( ( x)(H(x)

37、P(x)Q(x)x)(H(x)P(x)Q(x)， ( ( x)(H(x)x)(H(x) Q(x) Q(x) 结论结论：( ( x)(H(x)x)(H(x) R(x) R(x) 例例5.3.65.3.6证明证明(1)(1)( ( x)(H(x)x)(H(x) Q(x)Q(x) P P(2)(2)H(c)H(c) Q(c)Q(c)ES,(1)ES,(1)(3)(3)H(c)H(c)T,(2 ),IT,(2 ),I(4)(4) Q(c)Q(c)T,(2 ),IT,(2 ),I(5)(5)( ( x)( H(x)P(x)Q(x) Px)( H(x)P(x)Q(x) P(6)(6)H(c)P(c)Q(c

38、)H(c)P(c)Q(c)US,(5)US,(5)(7)(7)P(c)Q(c)P(c)Q(c)T,(3),(6),IT,(3),(6),I(8)(8)P(c)P(c)T,(4),(7),IT,(4),(7),I例例5.3.6(5.3.6(续续) )(9)(9)( ( x)(H(x)R(x)x)(H(x)R(x) P(x) PP(x) P(10)(10)H(c)R(c)H(c)R(c) P(c)P(c) US,(9) US,(9)(11)(11) (H(c)R(c)(H(c)R(c) T,(8),(10),I T,(8),(10),I(12)(12) H(c)H(c) R(c)R(c) T,(11),E T,(11),E(13)(13) R(c)R(c) T,(3),(12),I T,(3)