离散数学第2版作者王元元离散第12讲证明的方法课件

计算机专业基础课程授课人：王元元单位：计算机理论教研室指挥自动化学院计算机系·PowerPoint

Template_Sub1命题与逻辑联结词2逻辑等价式和逻辑蕴涵式3范式4证明的方法（补充）2第12讲证明的方法·证明的方法《离散数学》第12讲补充内容·内容回顾·逻辑等价式和逻辑蕴涵式的三种证明方法·真值表法·对指派进行讨论·利用代入、替换进行推演证明：(A→B)→A┝A第12讲证明的方法4ABA→B(A→B)→A((A→B)→A)

→A00101011011001111111·内容回顾·逻辑等价式和逻辑蕴涵式的三种证明方法真值表法对指派进行讨论利用代入、替换进行推演((A→B)→A)=0第12讲证明的方法5证明：(A→B)→A┝A假设任一指派

，使得由

(A)=0，得(A)=0，要证

(A→B)=1又由

(A→B)=1，

(A)=0，可得((A→B)→A)=0·内容回顾第12讲证明的方法6·逻辑等价式和逻辑蕴涵式的三种证明方法·真值表法·对指派进行讨论·利用代入、替换进行推演证明：(A→B)→A┝A(A→B)→A┝┐(A→B)∨A

对E14用RS┝┐(┐A∨B)∨A

对E14用RR┝

(A∧┐B)∨A对E10用RR┝

A对E12用RS·应用：推理第12讲证明的方法7·所谓推理是指从前提出发推出结论的思维过程，前提是已知的命题公式集合，结论是从前提出发应用推理规则推出的命题公式·定义：设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变元的任意一组指派，

当A1

∧A2∧…∧Ak为真时B也为真，则称由前提A1,A2,…,Ak推出结论B的推理是有效的或正确的，并

称B是有效的结论·推理与重言式·定理：命题公式A1,A2,…,Ak推B的推理正确当且仅当A1∧A2∧…∧Ak

┝B·判断下面的推理是否正确：下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。第12讲证明的方法8q:马芳下午去游泳令p:马芳下午去看电影;前提：p∨q，┐p结论：q根据I5，(p∨q)∧┐p┝q。所以，推理正确·推理与重言式·定理：命题公式A1,A2,…,Ak推B的推理正确当且仅当A1∧A2∧…∧Ak

┝B·判断下面的推理是否正确：若下午气温超过30C，则马芳必去游泳。若她去游泳，她就不去看电影了。所以，若马芳没去看电影，下午气温必超过30C。r:马芳去看电影令p:下午气温超过30C；q:马芳去游泳;前提：p→q，q→┐r结论：┐r→p当指派为(0,0,0)时，前提(p→q)∧(q→┐r)真而结论→p假(即(p→q)∧(q→┐r)╞r→p不能成立.)9所以，第推12讲理证错明的误方法·应用：证明第12讲证明的方法10（1）求证：ABCD╞K；或证明ABCD╞K不能成立·在实际应用中常见的情况是:已知一个前提的集合，例如{A,B,C,D}，要求证一个结论，例如K，或求解“K是否可以由前提集合推出”。·我们可以怎么做？（2）想想我们在“证明”中是怎样做的：建立一个由A,B,C,D以及由它们用逻辑规则推理出的结果的序

列，而这个序列的末段是K。·如何完成这样的证明？可用哪些逻辑规则？这正是

“证明技术”要告诉大家的。·证明：常用规则第12讲证明的方法11·所有逻辑蕴涵式均可用做推理规则·为证A→B，人们常以A为假设而证B。·已知A∨B并且A→C,B→C,那么C真。

(推理中分别情况进行证明的思想)·为证

A，假设A导出矛盾B∧

B。

(推理中运用反证法进行证明的思想)·实例1·已知：·1、只要你认真听课、认真做作业，你考试就能及格；·2、你认真听课；·3、你考试不及格；·结论：·你没有认真做作业p:你认真听课；q：你认真做作业；r：你考试及格；1、p∧q→r2、p：你认真听课；3、┐r：你考试不及格；要证明：{p∧q→r,p,┐r}┝┐q第12讲证明的方法12·证明的例子要证明：{p∧q→r,p,┐r}┝┐q1）┐r

前提2）p∧q→r

前提由2）据A→B┝┥┐B→┐A5）┐p∨┐q6）p由4）得到5）据┐(A∧B)┝┥┐A∨┐B，前提3）┐r

→┐(p∧q)4）┐(p∧q)由1）3）据A （A→B）┝

B7）┐q

由6）5）据┐A∧（A B)┝

B，第12讲证明的方法13·实例已知事实：如果委员会拒绝通过新条令，那么罢工不结束，或者罢工持续一年并且商行董事长辞职。罢工刚刚开始。得出结论：如果委员会拒绝通过新条令,那么罢工不结束。证明上述推理是正确的(有效的)。解.首先将事实和结论形式化。p：委员会拒绝通过新条令。q：罢工结束。r：商行董事长辞职。s：罢工持续一年。于是,问题的已知事实是{p→(┐q∨(r∧s)),┐s},结论是p→欲证p→(┐q∨(r∧s))∧┐s╞p→┐q第12讲证明的方法14·方法一第12讲证明的方法15前提由结论的前提作当然假设由(1)(2)和I3由(3)作分支假设由(3)作分支假设由(3.2)和I2前提（1）

p→(┐q∨(r∧s))（2）

p（3）┐q∨(r∧s)（3.1）┐q（3.2）r∧s（3.2.1）s（3.2.2）┐s（3.2.3）┐q由(3.2.1)（3.2.2）（4）┐q（5）p→┐q和逻辑蕴涵式A

┐A╞B分支假设证明结束当然假设证明结束·方法二第12讲证明的方法16（1）

p→(┐q∨(r∧s))（2）

p（3）

q（4）┐q∨(r∧s)（4.1）┐q（4.1.1）┐q（4.2）r∧s（4.2.1）s（4.2.2）┐s（4.2.3）┐q（5）┐q（6）p→┐q前提由结论的前提作当然假设欲证┐q反证假设q由(1)(2)和I3由(4)作分支假设由(3)(4.1)和反证法由(4)作分支假设由(4.2)和I2前提由(4.2.1)(4.2.2)和反证法分支假设证明结束当然假设证明结束·证明技术实例已知事实：如果委员会拒绝通过新条令，那么罢工不结束，或者罢工持续一年并且商行董事长辞职。罢工刚刚开始。得出结论：如果委员会拒绝通过新条令,那么罢工结束。证明上述推理是不正确的(无效的)。解.首先将事实和结论形式化。p：委员会拒绝通过新条令。q：罢工结束。r：商行董事长辞职。s：罢工持续一年。于是,问题的已知事实是p→(┐q∨(r∧s)),┐s,结论是p→q欲证p→(┐q∨(r∧s))∧┐s╞p→q不成立。第12讲证明的方法17·证明技术实例第12讲证明的方法18·为了证明p→(┐q∨(r∧s))∧┐s╞p→q不成立，出一种指派，使得p→(┐q∨(r∧s))，┐s均为真，

p→q为假。·不难看出，这一指派应使得p为真，使得q为假，从而计算得这一指派应使s为假(而对