离散数学方世昌第5节.ppt

《离散数学方世昌第5节.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.5推理规则和证明方法讲授重点：推理规则，直接证明方法与CP规则讲授难点：直接证明方法，CP规则与反证法1什么是推理？1.推理和推理规则推理:从前提推出结论的思维过程。前提:指已知的命题公式。结论:从前提出发，应用推理规则推出的命题公式。本节内容：从逻辑推理的角度来理解命题演算前提结论推理规则推理2推理的例子：设x属于实数,P:x是偶数,Q:x2是偶数。例1.如果x是偶数,则x2是偶数。x是偶数。x2是偶数。例3.如果x是偶数,则x2是偶数。x不是偶数。x2不是偶数。例2.如果x是偶数,则x2是偶数。x2是偶

2、数。x是偶数。例4.如果x是偶数,则x2是偶数。x2不是偶数。x不是偶数。√√××前提-------------结论四个例子的推理是否正确？所用依据是什么？31、推理和推理规则推理规则：正确推理的依据。任何一条永真蕴含式都可以作为一条推理规则。例：析取三段论：如果，P：他在钓鱼，Q：他在下棋前提：他在钓鱼或下棋；他不在钓鱼结论：所以他在下棋4定义1：若H1∧H2∧…∧HnC,则称C是H1,H2,…,Hn的有效结论。特别若AB,则称B是A的有效结论，或从A推出B。1、推理和推理规则注意：不考虑前提的真假，推理

3、正确≠结论为真。结论的真假取决于前提H1∧H2∧…∧Hn的真假。前提为真，则结论为真；前提为假，则结论可真可假。因此，定义中只说C是H1,H2,…,Hn的有效结论而不说是正确结论。“有效”是指结论的推出合乎推理规则。5有效结论如Q是P→Q，P的一个有效结论。即证P∧(P→Q)永真蕴含Q也就是要证：P∧(P→Q)→Q是重言式.设P∧(P→Q)取值为真，则P为真，且P→Q为真，故Q为真故P∧(P→Q)→Q是重言式.假言推理P®QPQ6如：Q是ØP，(PÚQ)的有效结论。即ØPÙ(PÚQ)→Q是一个永真式。析取三段

4、论规则PÚQØPＱ7推理的形式结构形式(1)H1ÙH2Ù…ÙHn®C形式(2)前提:H1,H2,…,Hn结论:C推理正确记作H1ÙH2Ù…ÙHnÞC注1.Þ与®的区别8推理的形式结构形式(1)H1ÙH2Ù…ÙHn®C形式(2)前提:H1,H2,…,Hn结论:C推理正确记作H1ÙH2Ù…ÙHnÞC对于实际中给出的推理:将推理中的（简单）命题符号化写出前提和结论判断该推理是否正确正确：给出一个证明序列不正确：给出反例9常用的推理规则1)恒等式(E1~E24)2)永真蕴含式(I1~I8,表1.5-1)3)替换规则，

5、代入规则4)P规则和T规则P规则：(前提引入)在推导的任何步骤上，都可以引入前提。T规则：(结论引用)在推导任何步骤上所得结论都可以作为后继证明的前提。1、推理和推理规则10永真蕴含式11(4)拒取式规则P®QØQØP(3)假言推理规则P®QPQ(1)加法规则PPÚQ(2)简化规则PÙQP(5)析取三段论规则PÚQØQP12推理规则(9)破坏性二难推理规则P®QR®SØQÚØSØPÚØR(8)构造性二难推理规则P®QR®SPÚRQÚS(7)合取引入规则PQPÙQ(6)前提三段论规则P®QQ®R

6、P®R13例1：考虑下述论证:1.如果这里有球赛,则通行是困难的。2.如果他们按时到达,则通行是不困难的。3.他们按时到达了。4.所以这里没有球赛。前3个断言是前提,最后1个断言是结论,要求我们从前提推出结论。设P:这里有球赛,Q:通行是困难的,R:他们按时到达。即证P→Q，R→¬Q，R¬P运用推理规则形式化证明14证：步骤断言(真)根据（1）RP（2）R→¬QP（3）¬QT,(1),(2),I3（4）P→QP（5）¬PT,(3),(4),I4即证P→Q，R→¬Q，R¬P151.5.2证明方法定理常见的形式

7、是“P当且仅当Q”，“如果P，那么Q”。而前者又相当于P→Q并且Q→P，所以归根结底，定理的主要形式是P→Q。至于其它形式，诸如：P形式，只需证明P是假;P∧Q形式，只需证明P、Q俱真;P∨Q形式，可转化为P→Q形式。　　我们主要从策略意义上说明如何证明P→Q形式的命题，具体的技巧，仍需通过例题来学习。161).无义证明法证明PQ为真，只需证明P为假。2).平凡证明法证明PQ为真，只需证明Q为真。无义证明法和平凡证明法应用的次数较少,但对有限的或特殊的情况,它们常常是重要的。3.证明方法（P→Q）173.

8、证明方法3).直接证明法假设P是真，如果能推得Q是真，则P→Q是真H1∧H2∧…∧HnC，由前提利用推理规则直接推出C。例2：证明CD,C→R,D→SRS18证：(1)CDP(2)¬(¬C)DT,(1),E1(3)¬C→DT,(2),E14(4)D→SP(5)¬C→ST,(3),(4),I6(6)C→RP(7)¬R→¬CT,(6),E24(8)¬R→ST,(5),(7),I