离散数学24命题逻辑推理理论课件.ppt
《离散数学24命题逻辑推理理论课件.ppt》由会员分享,可在线阅读,更多相关《离散数学24命题逻辑推理理论课件.ppt(22页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1有效推理有效推理定义定义2.20 若对于每组赋值若对于每组赋值, A1 A2 Ak 为假为假, 或者或者当当A1 A2 Ak为真时为真时, B也为真也为真, 则称由前提则称由前提A1,A2, Ak推推B的的推理有效推理有效或或推理正确推理正确, 并称并称B是是有效的结论有效的结论定理定理2.8 由前提由前提A1, A2, , Ak 推出推出B 的推理正确当且仅当的推理正确当且仅当 A1 A2 AkB为重言式为重言式.2推理的形式结构推理的形式结构形式形式(1) A1 A2 AkB形式形式(2) 前提前提: A1, A2, , Ak 结论结论: B 推理正确记作推理正确记作 A1 A2 AkB
2、判断推理是否正确的方法判断推理是否正确的方法:真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法构造证明法构造证明法3实例实例例例1 判断下面推理是否正确判断下面推理是否正确:(1) 若今天是若今天是1号号, 则明天是则明天是5号号. 今天是今天是1号号. 所以所以, 明天是明天是5号号. 解解 设设 p: 今天是今天是1号号, q: 明天是明天是5号号 推理的形式结构为推理的形式结构为 (pq) pq证明证明 用等值演算法用等值演算法 (pq) pq ( p q) p) q (pq)p) q pq q 1得证推理正确得证推理正确4实例实例(续续)(2) 若今天是若今天是1号号, 则
3、明天是则明天是5号号. 明天是明天是5号号. 所以所以, 今天是今天是1号号. 解解 设设p: 今天是今天是1号号, q: 明天是明天是5号号. 推理的形式结构为推理的形式结构为 (pq) qp证明证明 用主析取范式法用主析取范式法 (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 01是成假赋值是成假赋值, 所以推理不正确所以推理不正确.5推理定律推理定律重言蕴涵式重言蕴涵式 A (A B) 附加律附加律 (A B) A 化简律化简律(AB) A B 假言推理假言推理(AB)B A 拒取式拒取式(A B)B A
4、析取三段论析取三段论(AB) (BC) (AC) 假言三段论假言三段论(AB) (BC) (AC) 等价三段论等价三段论(AB) (CD) (A C) (B D) 构造性二难构造性二难 (AB) ( AB) B 构造性二难构造性二难(特殊形式特殊形式)(AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难6自然推理系统自然推理系统P自然推理系统自然推理系统P由下述由下述3部分组成部分组成:1. 字母表字母表(1) 命题变项符号命题变项符号: p,q,r, pi,qi,ri,(2) 联结词联结词: , , , , (3) 括号与逗号括号与逗号: ( ), ,2. 合式公式合式公式3.
5、推理规则推理规则(1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规则置换规则7自然推理系统自然推理系统P(续续)(7) 拒取式规则拒取式规则 AB B A(8) 假言三段论规则假言三段论规则 AB BC AC (4) 假言推理规则假言推理规则 AB A B(5) 附加规则附加规则 A A B(6) 化简规则化简规则 A B A 8自然推理系统自然推理系统P(续续)(11) 破坏性二难推理规则破坏性二难推理规则 AB CD BD AC(12) 合取引入规则合取引入规则 A B A B (9) 析取三段论规则析取三段论规则 A B B A(10)构造性二难推理规则构造性
6、二难推理规则 AB CD A C B D9直接证明法直接证明法例例2 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明:前提前提: p q, qr, ps, s结论结论: r(p q) )证明证明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(p q) ) 合取合取推理正确推理正确, , r(p q) )是有效结论是有效结论10实例实例例例3 构造推理的证明构造推理的证明: 若明天是星期一或星期三若明天是星期一或星期三, 我就有我就有课课. 若有课若有课
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 24 命题逻辑 推理 理论 课件
限制150内