《离散数学 第2版 教学课件 ppt 作者 王元元 离散第12讲 证明的方法》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第12讲 证明的方法（19页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,指挥自动化学院计算机系,-2-,第12讲 证明的方法,PowerPoint Template_Sub,命题与逻辑联结词,逻辑等价式和逻辑蕴涵式,范式,证明的方法（补充）,证明的方法,离散数学第12讲,补充内容,-4-,第12讲 证明的方法,内容回顾,逻辑等价式和逻辑蕴涵式的三种证明方法 真值表法 对指派进行讨论 利用代入、替换进行推演,证明： (AB)A A,-5-,第12讲 证明的方法,内容回顾,逻辑等价式和逻辑蕴涵式的三种证明方法 真值表法 对指派进行讨论 利用代入、替换进行推演,证明： (AB)A A,假设任一指派 ，使得(
2、A ) = 0，要证(AB)A)=0 由(A)=0，得(AB)=1 又由(AB)=1， (A)=0，可得(AB)A)=0,-6-,第12讲 证明的方法,内容回顾,逻辑等价式和逻辑蕴涵式的三种证明方法 真值表法 对指派进行讨论 利用代入、替换进行推演,证明： (AB)A A (AB)A (AB)A 对E14用RS (AB)A 对E14用RR (AB)A 对E10用RR A 对E12用RS,-7-,第12讲 证明的方法,应用：推理,所谓推理是指从前提出发推出结论的思维过程，前提是已知的命题公式集合，结论是从前提出发应用推理规则推出的命题公式 定义：设A1, A2, , Ak和B都是命题公式，若对于
3、A1, A2, , Ak和B中出现的命题变元的任意一组指派，当A1 A2Ak为真时B也为真，则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的，并称B是有效的结论,-8-,第12讲 证明的方法,推理与重言式,定理：命题公式A1, A2, , Ak推B的推理正确当且仅当A1A2Ak B 判断下面的推理是否正确：,下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。 令 p:马芳下午去看电影; q:马芳下午去游泳 前提： pq， p 结论： q 根据I5， (pq) p q。所以，推理正确,-9-,第12讲 证明的方法,推理与重言式,定理：命题公式A1, A2, , Ak推
4、B的推理正确当且仅当A1A2Ak B 判断下面的推理是否正确：,若下午气温超过30C，则马芳必去游泳。若她去游泳，她就不去看电影了。所以，若马芳没去看电影，下午气温必超过30C。 令 p:下午气温超过30C；q:马芳去游泳; r:马芳去看电影 前提： p q， q r 结论： r p 当指派为(0, 0, 0)时，前提 (p q) (q r)真而结论 rp假(即(p q) (q r) r p不能成立. ) 所以，推理错误,-10-,第12讲 证明的方法,应用：证明,在实际应用中常见的情况是: 已知一个前提的集合，例如A,B,C,D，要求证一个 结论，例如K，或求解“K是否可以由前提集合推出”。
5、 我们可以怎么做？ （1）求证：AB CDK； 或证明AB CDK不能成立 （2）想想我们在“证明”中是怎样做的：建立一个 由A,B,C,D以及由它们用逻辑规则推理出的结果的序 列，而这个序列的末段是K。 如何完成这样的证明？可用哪些逻辑规则？这正是“证明技术”要告诉大家的。,-11-,第12讲 证明的方法,证明：常用规则,所有逻辑蕴涵式均可用做推理规则 为证AB，人们常以A为假设而证B。 已知AB并且AC,BC,那么C真。 (推理中分别情况进行证明的思想) 为证A，假设A导出矛盾BB。 (推理中运用反证法进行证明的思想),-12-,第12讲 证明的方法,实例1,已知： 1、只要你认真听课、认
6、真做作业，你考试就能及格； 2、你认真听课； 3、你考试不及格； 结论： 你没有认真做作业,p:你认真听课；q：你认真做作业；r：你考试及格； 1、pq r 2、p：你认真听课； 3、r：你考试不及格； 要证明： pqr, p, r q,-13-,第12讲 证明的方法,证明的例子,要证明： pqr, p, r q,1）r 前提,2）pqr 前提,3）r (pq) 由2）据ABBA,5）pq 由4）得到5）据(AB)AB，,6）p 前提,4）(pq) 由1）3）据A（AB） B,7）q 由6）5）据A（AB) B，,-14-,第12讲 证明的方法,实例,已知事实： （a）如果委员会拒绝通过新条令
7、，那么罢工不结束，或者罢工持续一年并且商行董事长辞职。 （b）罢工刚刚开始。 得出结论：如果委员会拒绝通过新条令,那么罢工不结束。 证明上述推理是正确的(有效的) 。 解.首先将事实和结论形式化。 p：委员会拒绝通过新条令。 q：罢工结束。 r：商行董事长辞职。 s：罢工持续一年。 于是,问题的已知事实是 p(q(rs),s,结论是pq 欲证p(q(rs)s pq,-15-,第12讲 证明的方法,方法一,（1） p(q(rs) 前提 （2） p 由结论的前提作当然假设 （3）q(rs) 由(1)(2)和I3 （3.1）q 由(3)作分支假设 （3.2）rs 由(3)作分支假设 （3.2.1）s
8、 由(3.2)和I2 （3.2.2）s 前提 （3.2.3）q 由(3.2.1)（3.2.2） 和逻辑蕴涵式A AB （4）q 分支假设证明结束 （5）pq 当然假设证明结束,-16-,第12讲 证明的方法,方法二,（1） p(q(rs) 前提 （2） p 由结论的前提作当然假设 （3） q 欲证q反证假设q （4）q(rs) 由(1)(2)和I3 （4.1）q 由(4)作分支假设 （4.1.1）q 由(3)(4.1)和反证法 （4.2）rs 由(4)作分支假设 （4.2.1）s 由(4.2)和I2 （4.2.2）s 前提 （4.2.3）q 由(4.2.1)(4.2.2)和反证法 （5）q 分
9、支假设证明结束 （6）pq 当然假设证明结束,-17-,第12讲 证明的方法,证明技术实例,已知事实： （a）如果委员会拒绝通过新条令，那么罢工不结束，或者罢工持续一年并且商行董事长辞职。 （b）罢工刚刚开始。 得出结论：如果委员会拒绝通过新条令,那么罢工结束。 证明上述推理是不正确的(无效的) 。 解.首先将事实和结论形式化。 p：委员会拒绝通过新条令。 q：罢工结束。 r：商行董事长辞职。 s：罢工持续一年。 于是,问题的已知事实是 p(q(rs),s,结论是pq 欲证p(q(rs)s pq 不成立。,-18-,第12讲 证明的方法,证明技术实例,为了证明 p(q(rs)s pq 不成立，只要给出一种指派，使得 p(q(rs) ，s均为真，但使pq 为假。 不难看出，这一指派应使得p为真，使得q为假，从而计算得这一指派应使s 为假(而对r可随意指派真假)。,-19-,第12讲 证明的方法,本讲小结,主要内容 推理、前提、结论、正确的推理 推理规则 证明的技术 作业 构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯；A曾到过受害者房间；如果A在11点以前离开房间，看门人会看见他；看门人没有看见他。所以，A是谋杀嫌犯。,
