离散数学第四讲-推理规则与证明方法.ppt
《离散数学第四讲-推理规则与证明方法.ppt》由会员分享,可在线阅读,更多相关《离散数学第四讲-推理规则与证明方法.ppt(20页珍藏版)》请在三一文库上搜索。
1、1,第四讲 推理规则和证明方法,讲授内容: 1.推理和推理规则 推理 推理规则 两规则 替换规则 2. 证明方法 直接证明方法 CP规则 反证法,讲授重点:推理规则,直接证明方法与CP规则 讲授难点:直接证明方法,CP规则与反证法,2,什么是推理?,1.推理和推理规则,推理:从前提推出结论的思维过程。 前提:指已知的命题公式。 结论:从前提出发,应用推理规则推出的命题公式。,本节内容:从逻辑推理的角度来理解命题演算,前提 结论,推理规则,推理,3,推理的例子:设x属于实数, P: x是偶数, Q: x2是偶数。,例1. 如果x是偶数, 则x2是偶数。 x是偶数。 x2是偶数。,例3. 如果x是
2、偶数, 则x2是偶数。 x不是偶数。 x2不是偶数。,例2. 如果x是偶数, 则x2是偶数。 x2是偶数。 x是偶数。,例4. 如果x是偶数, 则x2是偶数。 x2不是偶数。 x不是偶数。,前提,- 结论,四个例子的推理是否正确? 所用依据是什么?,4,1、推理和推理规则,刚才的例子表明了研究推理规则的重要性。 推理规则:正确推理的依据。 任何一条永真蕴含式都可以作为一条推理规则。 例:析取三段论: 如果,P:他在钓鱼,Q:他在下棋 前提:他在钓鱼或下棋; 他不在钓鱼 结论:所以他在下棋,5,定义1:若H1H2 Hn C, 则称C是H1, H2, , Hn的有效结论。 特别若A B, 则称B是
3、A的有效结论,或从A推出B。,1、推理和推理规则,注意: 不考虑前提的真假,推理正确结论为真。 结论的真假 取决于 前提H1H2 Hn的真假。 前提为真,则结论为真; 前提为假,则结论可真可假。 因此,定义中只说C 是H1, H2, , Hn 的有效结论而不说是正确结论。“有效”是指结论的推出合乎推理规则。,6,常用的推理规则 1) 恒等式(E1E24) 2) 永真蕴含式(I1I8,表1.5-1) 3) 替换规则,代入规则 4) P规则和T规则 P规则:(前提引入) 在推导的任何步骤上,都可以引入前提。 T规则:(结论引用) 在推导任何步骤上所得结论都可以作为后继证明的前提。,1、推理和推理规
4、则,7,表1.5-1 常用推理规则,8,永真蕴含式,9,例1:考虑下述论证: 1. 如果这里有球赛, 则通行是困难的。 2. 如果他们按时到达, 则通行是不困难的。 3. 他们按时到达了。 4. 所以这里没有球赛。 前 3 个断言是前提, 最后1个断言是结论, 要求我们从前提推出结论。,证: 步骤 断言(真) 根 据 (1) R P (2) R Q P (3) Q T,(1),(2),I3 (4) PQ P (5) P T,(3),(4),I4,设P: 这里有球赛, Q: 通行是困难的, R: 他们按时到达。 即证 PQ,R Q,R P,运用推理规则形式化证明,10,1). 无义证明法 证明
5、P Q为真,只需证明P为假。 2). 平凡证明法 证明 P Q为真,只需证明Q为真。 无义证明法和平凡证明法应用的次数较少, 但 对有限的或特殊的情况, 它们常常是重要的。,3. 证明方法,11,证: (1) CD P (2) ( C) D T,(1),E1 (3) C D T,(2),E14 (4) D S P (5) C S T,(3),(4),I6 (6) C R P (7) RC T,(6),E24,(8) R S T,(5),(7),I6 (9) ( R)S T,(8),E14 (10) R S T, (9), E1,3. 证明方法,3).直接证明法 H1H2 Hn C,由前提利用推
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第四 推理 规则 证明 方法
链接地址:https://www.31doc.com/p-2071772.html