六章节命题逻辑.ppt
《六章节命题逻辑.ppt》由会员分享,可在线阅读,更多相关《六章节命题逻辑.ppt(28页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、离散数学1六章节命题逻辑 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望离散数学26.5 推理理论推理理论6.5.1 前提与有效结论前提与有效结论6.5.2 证明方法证明方法6.5.1 推理定律和规则推理定律和规则6.5.2 直接证明法直接证明法6.5.3 间接证明法间接证明法离散数学3推理推理推理推理:由前提,依据推理规则,推导出结论的思维过程。:由前提,依据推理规则,推导出结论的思维过程。命题逻辑中,前提和结论都用命题公式表示命题逻辑中,前提和结论都用命题公式
2、表示若前提为:若前提为:P1、P2、Pn;有效结论:;有效结论:Q 由前提由前提P1、P2、Pn推出有效结论推出有效结论Q 证明当前提证明当前提P1、P2、Pn都成立(为真)时,都成立(为真)时,Q成立(为真)成立(为真)P1 P2 Pn Q (P1,P2,Pn Q)离散数学4证明永真蕴涵式的方法:证明永真蕴涵式的方法:证明证明A AB B:真值表法真值表法命题命题(等价等价)演算法演算法利用等价公式和永真蕴涵公式证明利用等价公式和永真蕴涵公式证明假设推理法。假设推理法。(假设前提为真,证明结论必为真假设前提为真,证明结论必为真)主析取范式法主析取范式法离散数学5所以,P (P Q)(P Q)
3、Q 1例例1.6.1 证明证明Q是前提是前提P,PQ,(PQ)的有效结论的有效结论证明证明:等价于证明等价于证明P (PQ)(PQ)Q(1)真值表法真值表法 离散数学6 (2)命题演算命题演算 (3)利用等价公式和永真蕴涵公式证明利用等价公式和永真蕴涵公式证明离散数学7(4)假设推理法假设推理法 P (PQ)(PQ)Q 假设假设P(PQ)(PQ)为真,为真,则则P和和(PQ)为真为真,所以所以PQ为假,因而为假,因而Q为假。为假。即即Q为真。这就证明了为真。这就证明了P(PQ)(PQ)Q。离散数学8(5)主范式法主范式法 离散数学96.5 推理理论推理理论6.5.1 前提与有效结论前提与有效结
4、论6.5.2 证明方法证明方法6.5.2.1 直接证明法直接证明法6.5.2.2 间接证明法间接证明法离散数学10直接证明法直接证明法 由一组前提,利用一些公认的推理规则,根据已知的等价或由一组前提,利用一些公认的推理规则,根据已知的等价或 蕴含公式,推演得到有有效的结论。蕴含公式,推演得到有有效的结论。直接证明法遵循两条规则直接证明法遵循两条规则(TP规则规则):P规则规则:前提在推导过程中的任何时候都可以:前提在推导过程中的任何时候都可以引入使用引入使用T规则规则:在推导中,如果有一个或多个公式、永真蕴含着:在推导中,如果有一个或多个公式、永真蕴含着公式公式S,则,则S可可引入推导引入推导
5、中中离散数学11推理定律推理定律永真蕴涵式永真蕴涵式 A (A B)(A B)A (A B)A B (A B)B A (A B)B A (A B)(B C)(A C)(A B)(B C)(A C)(A B)(C D)(A C)(B D)(AB)(AB)(AA)B (AB)(CD)(BD)(AC)离散数学12直接证明法例直接证明法例1:请用直接证明法证明:请用直接证明法证明:(P Q),(PR),(QS)R S 证明证明:(1)P Q p (2)PQ T(1)(3)QS P (4)PS T(2)(3)(5)PR P (6)R P T(5)(7)RS T(4)(6)(8)R S T(7)离散数学1
6、3直接证明法例直接证明法例 2证明:证明:P Q,Q R,R,(P S)S./*逗号逗号“,”和和“”的含义相同的含义相同*/证明证明 (1)Q R 利用利用P规则,引入前提规则,引入前提 (2)QR 利用利用P规则,引入前提规则,引入前提 (3)R 利用利用P规则,引入前提规则,引入前提 (4)Q 由由(2),(3),利用,利用T规则规则 (5)P Q 利用利用P规则,引入前提规则,引入前提 (6)P由由(4),(5),利用,利用T规则规则 (7)(P S)P利用利用P规则,引入前提规则,引入前提 (8)P S由由(7),利用,利用T规则规则 (9)S由由(6),(8),利用,利用T规则规则
7、 离散数学14直接证明法例直接证明法例 3证明证明(A B)(C D),(D F)E A E/*逗号逗号“,”和和“”的含义相同的含义相同*/证明证明(1)(A B)(C D)P(2)(A B)(C D)T(1)(3)(A B)C)(A B)D)T(2)(4)(A B)D T(3)(5)(A B)D T(4)(6)(A D)(B D)T(5)离散数学15直接证明法例直接证明法例3证明证明(A B)(C D),(D F)E A E证明(续)证明(续)(6)(A D)(B D)T(5)(7)A DT(6)(8)A D T(7)(9)(D F)E P(10)(D F)ET(9)(11)(D F)ET
8、(10)(12)(D E)(F E)T(11)(13)D ET(12)(14)D ET(13)(15)A E T(8),(14)离散数学16例例 4:请给出下面语句的前提和结论以及推理过程请给出下面语句的前提和结论以及推理过程:或者天晴,或者下雨。或者天晴,或者下雨。如果天晴,我去看电影。如果天晴,我去看电影。如果我去看电影,我就不看书。如果我去看电影,我就不看书。我在看书。我在看书。所以天在下雨。所以天在下雨。推理过程:推理过程:“如果我去看电影,我就不看书如果我去看电影,我就不看书”但但“我在看书我在看书”所以所以“我没去看电影我没去看电影”而而“如果天晴,我去看电影如果天晴,我去看电影”
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章节 命题逻辑
限制150内