离散数学PPT电子教案-第05章_推理与证明技术.ppt

离散数学,2019/12/6,第5章推理与证明技术,2019/12/6,5.1本章学习要求,2019/12/6,5.2命题逻辑的推理理论,2019/12/6,推理的有效性和结论的真实性,有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论。,2019/12/6,推理的有效性和结论的真实性,所谓推理有效，指的是它的结论是它前提合乎逻辑的结果。此时,如果它的前提都为真，那么所得的结论也必然为真;如果它的前提为假,那么所得的结论可以为假.如果推理是有效的，那么不可能它的前提都为真时，而它的结论为假。,2019/12/6,5.2.1推理的基本概念和推理形式,定义5.2.1设G1,G2,Gn,是公式，称H是G1,G2,Gn的逻辑结果(G1,G2,Gn共同蕴涵H),当且仅当H是G1G2Gn的逻辑结果。记为G1,G2,Gn,此时,称G1,G2,Gn为有效的。G1,G2,Gn称为一组前提，有时用集合来表示,记=G1,G2,Gn;H称为结论,它是前提集合的逻辑结果。记为H。,2019/12/6,判定定理,定理5.2.1G1,G2,Gn当且仅当G1G2Gn为永真公式。,注意:“”是蕴涵联结词，GH仍是一个公式;“”描述了两个公式G,H之间的一种逻辑蕴涵关系,GH不是公式；,2019/12/6,练习:P1461(1),1.用基本等价公式的转换方法验证下述论断是否有效.(1)PQ,RS,QPS证明(PQ)(RS)Q(PS)=(PQ)RSQ(PS)=PRSQ(PS)=PRSQ(PS)=PRSQ这说明(PQ)(RS)Q(PS)不是永真式,因此PQ,RS,QPS,2019/12/6,5.2.2判断有效结论的常用方法,2019/12/6,1、真值表技术,设P1,P2,Pn是出现在前提G1,G2,Gn和结论H中的一切命题变元，如果将P1,P2,Pn中所有可能的解释及G1,G2,Gn,H对应的真值结果都列在一个表中，根据“”的定义，则有判断方法如下：,(1)如果在所有G1,G2,Gn都具有真值1的行中,H的真值为1,则H是G1,G2,Gn的逻辑结果。(2)如果在所有H具有真值0的行中,G1,G2,Gn中至少有一个公式的真值为0，则H是G1,G2,Gn的逻辑结果。,2019/12/6,例5.2.1,判断下列H是否是前提G1,G2的逻辑结果(1)H：Q；G1：P；G2：PQ；(2)H：P；G1：PQ；G2：Q；(3)H：Q；G1：P；G2：PQ。,解,2019/12/6,2推理定律I1-I15,设G，H，I，J是任意的命题公式，则有：,I1：GHG;I2：GHH;(简化规则)I3：GGH;I4：HGH;(添加规则)I5：GGH;I6：HGH;I7：(GH)G;I8：(GH)H;I9：G,HGH;,2019/12/6,2推理定律(续),6)I10：G,GHH(选言三段论)I11：G,GHH7)I12：G,GHH(分离规则)8)I13：H,GHG(否定后件式)9)I14：GH,HIGI(假言三段论)10)I15：GH,GI,HII(二难推论),2019/12/6,例子,1)、前提：1.如果明天天晴，我们准备外出旅游。PQ2明天的确天晴。P结论：我们外出旅游。Q可描述为：PQ,PQ(分离规则)2)、前提：1.如果一个人是单身汉，则他不幸福。PQ2.如果一个人不幸福，则他死得早。QR结论：单身汉死得早。PR可描述为：PQ,QRPR(假言三段论),2019/12/6,例子(续),3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提:1.凶手为王某或陈某;。PQ2.如果王某是凶手,则他在作案当晚必外出;PR3.王某案发之晚并未外出。R结论：陈某是凶手。Q则可描述为：PR,RP(否定后件式)PQ,PQ(选言三段论),2019/12/6,3演绎法,演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。,引入事实,2019/12/6,推理规则,在数理逻辑中，主要的推理规则有：P规则(称为前提引用规则)：在推导的过程中，可随时引入前提集合中的任意一个前提；规则T(逻辑结果引用规则)：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。规则CP(附加前提规则)：如果能从给定的前提集合与公式P推导出S，则能从此前提集合推导出PS。,2019/12/6,演绎的定义,定义5.2.2从前提集合推出结论H的一个演绎是构造命题公式的一个有限序列：H1，H2，Hn其中，Hi或者是中的某个前提，或者是前面的某些Hj（jx。,推导1：（1）(x)(y)G(x,y)P（2）(y)G(y,y)US，（1）,分析：推导1是错误的。正确的推导如下：（1）(x)(y)G(x,y)P（2）(y)G(z,y)US，（1）,注意：使用US规则来消去量词时，所选用取代x的变元y在公式中必须是自由的。,2019/12/6,推理规则的正确使用（2）,推导2：（1）(x)(y)G(x,y)P（2）(y)G(z,y)US，（1）（3）G(z,c)ES，（2）,分析：推导2是错误的。正确的推导如下：（1）(x)(y)G(x,y)P（2）(y)G(z,y)US，（1）（3）G(z,f(z)ES，（2）,注意：使用ES规则来消去量词时，若还有其它自由变元时，则必须用关于自由变元的函数符号来取代常量符号.,2019/12/6,推理规则的正确使用（3）,推导3：（1）(y)G(z,y)P（2）(y)(y)G(y,y)UG，（1）,分析：推导3是错误的。正确的推导如下：（1）(y)G(z,y)P（2）(z)(y)G(z,y)UG，（1）,注意：使用UG规则来添加量词时，所使用的变元符号不能与辖域内的变元符号相同.,2019/12/6,推理规则的正确使用（4）,推导4：（1）G(x,c)P（2）(x)G(x,x)EG，（2）,分析：推导4是错误的。正确的推导如下：（1）G(x,c)P（2）(y)G(x,y)EG，（2）,注意：使用EG规则来添加量词时，所使用的变元符号不能与辖域内的变元符号相同.,2019/12/6,5.3.2谓词演算的综合推理方法,（1）推导过程中可以引用命题演算中的规则P和规则T。（2）如果结论是蕴涵式或析取式，我们还可以使用规则CP。（3）若需消去量词，可以引用规则US和规则ES。（4）当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入。,2019/12/6,谓词演算的综合推理方法（续）,（5）证明时可采用如命题演算中的直接证明方法和间接证明方法。（6）在推导过程中，对消去量词的公式或公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。（7）在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。,2019/12/6,例5.3.2,解设H(x)：x是人；M(x)：x是要死的；s：苏格拉底。则符号化为：(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)，I,(4)错了！正确的为,证明：(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,2019/12/6,练习:P1475(1),5.构造下列推理的证明.(1)(x)(P(x)Q(x),(x)Q(x)(x)P(x),2019/12/6,例5.3.3,证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x),有下面的推导：(1)(x)(P(x)Q(x)P(2)(P(x)Q(x)US,(1)(3)(x)P(x)P(4)P(c)ES,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),(5)错了！,2019/12/6,例5.3.3(),证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x)修改后的推导：(1)(x)(P(x)Q(x)P(2)(P(c)Q(c)US,(1)(3)(x)P(x)P(4)P(c)ES,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),(4)错了！,2019/12/6,例5.3.3(),证明：(x)(P(x)Q(x)，(x)P(x)(x)Q(x)正确地推导如下：(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),2019/12/6,例5.3.4,证明：1)(x)(P(x)Q(x)P2)(P(c)Q(c)ES,1)3)P(c)T,2),I4)Q(c)T,2),I5)(x)P(x)EG,3)6)(x)Q(x)EG,4)7)(x)P(x)(x)Q(x)T,5),6),I,证明：(x)(P(x)Q(x)(x)P(x)(x)Q(x),2019/12/6,例5.3.4(续1),1)(x)P(x)(x)Q(x)P2)(x)P(x)T,1),I3)P(c)ES,2)4)(x)Q(x)T,1),I5)Q(c)ES,4)6)(P(c)Q(c)T,3),4),I7)(x)(P(x)Q(x)EG,6),请看上述推论的逆推导：,(5)错了！,2019/12/6,例5.3.4(续2),正确地推导：1)(x)P(x)(x)Q(x)P2)(x)P(x)T,1),I3)P(c)ES,2)4)(x)Q(x)T,1),I5)Q(b)ES,4)6)(P(c)Q(b)T,3),4),I7)(x)(y)(P(x)Q(y)EG,6),2019/12/6,例5.3.5证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),证明：1)(x)P(x)P(附加前提)2)(x)P(x)T,1),E3)P(c)ES,2)4)(x)(P(x)Q(x)P5)(P(c)Q(c)US,4)6)Q(c)T,3),5),I7)(x)Q(x)EG,6)8)(x)P(x)(x)Q(x)CP,1),7)9)(x)P(x)(x)Q(x)T,8),E,2019/12/6,5.3.4谓词逻辑推理的应用,例5.3.6每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。,证明设H(x)：x是人；P(x)：x喜欢坐汽车；Q(x)：x喜欢骑自行车；R(x)：x喜欢步行。则上述语句可符号化为：(x)(H(x)R(x)P(x)，(x)(H(x)P(x)Q(x)，(x)(H(x)Q(x)(x)(H(x)R(x),2019/12/6,例5.3.7,证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。证明设谓词如下：P(x)：x是哺乳动物；Q(x)：x是脊椎动物；R(x)：x是胎生动物。则有：(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),2019/12/6,请看下面推导：,1)(x)(P(x)R(x)P2)(P(x)R(x)US,1),错了！,2019/12/6,例5.3.6证明（续）,1)(x)(P(x)R(x)P2)(x)(P(x)R(x)T,1),E3)(P(c)R(c)ES,2)4)(P(c)R(c)T,3),E5)P(c)T,4),I6)R(c)T,4),I7)(x)(P(x)Q(x)P8)P(c)Q(c)US,7)9)Q(c)T,5),8),I10)Q(c)R(c)T,6),9),I11)(x)(Q(x)R(x)EG,10),对了！,2019/12/6,练习:P1487(1),7.将下列命题符号化,并用演绎法证明其论证是否正确.(1)每一个大学生,不是文科学生,就是理工科学生;有的大学生是优等生;小张不是文科生,但他是优等生.因此,如果小张是大学生,他就是理工科学生.,2019/12/6,作业,第147-148页5(4),7(4)(7)复习:第4章和第5章,2019/12/6,6指出下列推导中的错误,并改正.,1)(1)(x)P(x)Q(x)P,错了！,(2)P(y)Q(y)US,(1),(2)P(y)Q(x)US,(1),2)(1)P(a)Q(b)P,(2)(x)(P(x)Q(x)EG,(1),(2)(x)(y)(P(x)Q(y)EG,(1),错了！,2019/12/6,6指出下列推导中的错误,并改正.,3)(1)P(x)Q(c)P,错了！,(2)(x)(P(x)Q(x)EG,(1),(2)(y)(P(x)Q(y)EG,(1),4)(1)(x)(P(x)Q(x)P,(2)P(a)Q(b)US,(1),(2)P(a)Q(a)US,(1),错了！,2019/12/6,6指出下列推导中的错误,并改正.,5)(1)(x)P(x)P(2)P(c)ES,(1)(3)(x)Q(x)P,错了！,(4)Q(c)ES,(3),(4)Q(b)ES,(3),6)(1)(x)(y)(xy)P(2)(y)(zy)US,(1),(3)(zc)ES,(2)(4)(x)(xc)UG,(3)(5)ccUS,(4),错了！,(3)(zf(z)ES,(2),2019/12/6,6指出下列推导中的错误,并改正.,7)(1)(