离散数学第四讲-推理规则与证明方法ppt课件

第四讲推理规则和证明方法,讲授内容：1.推理和推理规则推理推理规则两规则替换规则2.证明方法直接证明方法CP规则反证法,讲授重点：推理规则，直接证明方法与CP规则讲授难点：直接证明方法，CP规则与反证法,1,什么是推理？,1.推理和推理规则,推理:从前提推出结论的思维过程。前提:指已知的命题公式。结论:从前提出发，应用推理规则推出的命题公式。,本节内容：从逻辑推理的角度来理解命题演算,前提结论,推理规则,推理,2,推理的例子：设x属于实数,P:x是偶数,Q:x2是偶数。,例1.如果x是偶数,则x2是偶数。x是偶数。x2是偶数。,例3.如果x是偶数,则x2是偶数。x不是偶数。x2不是偶数。,例2.如果x是偶数,则x2是偶数。x2是偶数。x是偶数。,例4.如果x是偶数,则x2是偶数。x2不是偶数。x不是偶数。,前提,-结论,四个例子的推理是否正确？所用依据是什么？,3,1、推理和推理规则,刚才的例子表明了研究推理规则的重要性。推理规则：正确推理的依据。任何一条永真蕴含式都可以作为一条推理规则。例：析取三段论：如果，P：他在钓鱼，Q：他在下棋前提：他在钓鱼或下棋；他不在钓鱼结论：所以他在下棋,4,定义1：若H1H2HnC,则称C是H1,H2,Hn的有效结论。特别若AB,则称B是A的有效结论，或从A推出B。,1、推理和推理规则,注意：不考虑前提的真假，推理正确结论为真。结论的真假取决于前提H1H2Hn的真假。前提为真，则结论为真；前提为假，则结论可真可假。因此，定义中只说C是H1,H2,Hn的有效结论而不说是正确结论。“有效”是指结论的推出合乎推理规则。,5,常用的推理规则1)恒等式(E1E24)2)永真蕴含式(I1I8,表1.5-1)3)替换规则，代入规则4)P规则和T规则P规则：(前提引入)在推导的任何步骤上，都可以引入前提。T规则：(结论引用)在推导任何步骤上所得结论都可以作为后继证明的前提。,1、推理和推理规则,6,表1.5-1常用推理规则,7,永真蕴含式,8,例1：考虑下述论证:1.如果这里有球赛,则通行是困难的。2.如果他们按时到达,则通行是不困难的。3.他们按时到达了。4.所以这里没有球赛。前3个断言是前提,最后1个断言是结论,要求我们从前提推出结论。,证：步骤断言(真)根据（1）RP（2）RQP（3）QT,(1),(2),I3（4）PQP（5）PT,(3),(4),I4,设P:这里有球赛,Q:通行是困难的,R:他们按时到达。即证PQ，RQ，RP,运用推理规则形式化证明,9,1).无义证明法证明PQ为真，只需证明P为假。2).平凡证明法证明PQ为真，只需证明Q为真。无义证明法和平凡证明法应用的次数较少,但对有限的或特殊的情况,它们常常是重要的。,3.证明方法,10,证：(1)CDP(2)(C)DT,(1),E1(3)CDT,(2),E14(4)DSP(5)CST,(3),(4),I6(6)CRP(7)RCT,(6),E24,(8)RST,(5),(7),I6(9)(R)ST,(8),E14(10)RST,(9),E1,3.证明方法,3).直接证明法H1H2HnC，由前提利用推理规则直接推出C。,例2：证明CD,CR,DSRS,11,4).间接证明法-（对原命题的逆否命题进行证明）证PQ只需证QP因为PQiffPQ永真iffQP永真iffQP5).(H1H2Hn)Q形式命题的证明H1H2HnQiffH1H2HnQ是重言式iff(H1H2Hn)Q是重言式iffH1H2HnQ是重言式iff(QH1)(QH2)(QHn)是重言式iff(QH1)(QH2)(QHn)是重言式若至少有一个i，使得使QHi,则原恒等式成立。,3.证明方法,12,6.CP规则（演绎定理）P1P2Pn(PQ)形式命题的证明证：P1P2PnPQ即证P1P2PnPQ因为P1P2PnPQiffP1P2Pn(PQ)永真iff(P1P2Pn)(PQ)永真iffP1P2PnPQ永真iff(P1P2PnP)Q永真iff(P1P2PnP)Q永真iffP1P2PnPQ永真iffP1P2Pn(PQ),6.证明方法,13,利用CP规则证明以下例题例3：证A(BC)，DA，BDC证：(1)DP（附加前提）(2)DAP(3)AT,(1),(2),I5(4)A(BC)P(5)BCT,(3),(4),I3(6)BP(7)CT,(5),(6),I3(8)DCCP规则,3.证明方法,14,7.分情况证明证明P1P2PnQ，只需证明对每一i，PiQ成立。,3.证明方法,因为P1P2PnQiffP1P2PnQ永真iff(P1P2Pn)Q永真iff(P1P2Pn)Q永真iff(P1Q)(P2Q)(PnQ)永真iff(P1Q)(P2Q)(PnQ)永真,15,8.反证法（又称归谬法、矛盾法）定义：设公式H1,H2,Hm中的原子命题变元是P1,P2,Pn,如果给P1,P2,Pn以某一指派,能使H1H2Hm的真值为真,则称命题公式集合H1,H2,Hm是一致的,否则称为非一致的。这个定义也可这样叙述:若H1H2HmRR,则H1,H2,Hm是非一致的,否则是一致的。,3.证明方法,16,8.反证法（又称归谬法、矛盾法）定理：设H1,H2,Hn是一致的,C是一命题公式,如果H1,H2,Hn,C非一致,则能从H1,H2,Hn推出C，即H1H2HnC。,3.证明方法,证明：H1H2HnCRRiffH1H2HnC永假(1)而H1,H2,Hn是一致的，所以存在一种指派使得H1H2Hn为真(2)由(1),(2)知存在一种指派使得C为假，即C为真。由肯定前件法可得H1H2HnC。,17,例4:PQR,RS,SPQ证：(1)(PQ)P,假设前提(2)PQT,(1),E10(3)PQT,(1),E1(4)PQRP(5)RT,(3),(4),I3(6)RSP(7)ST,(5),(6),I5(8)SP(9)SST,(7),(8),合取式,3.证明方法,18,作业：P321.5习题5(5)、8(3)(4)、9(1)、11(1)、12(4)、15(3),19,例5：(PQ)(PR)(QS)SR证:(1)(SR)P,假设前提(2)SRT,(1),E10(3)ST,(2),I2(4)(PQ)(PR)(Q