离散数学2.4命题逻辑推理理论ppt课件_第1页
离散数学2.4命题逻辑推理理论ppt课件_第2页
离散数学2.4命题逻辑推理理论ppt课件_第3页
离散数学2.4命题逻辑推理理论ppt课件_第4页
离散数学2.4命题逻辑推理理论ppt课件_第5页
已阅读5页,还剩17页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、2.4 命题逻辑推理实际命题逻辑推理实际 2.4.1 推理的方式构造推理的方式构造 推理的前提与结论推理的前提与结论,正确推理正确推理 推理定律推理定律 2.4.2 自然推理系统自然推理系统P 推理规那么推理规那么 直接证明法直接证明法, 附加前提证明法附加前提证明法, 归谬法归谬法(反证法反证法), 归结证明法归结证明法有效推理有效推理定义定义2.20 假设对于每组赋值假设对于每组赋值, A1A2 Ak 为假为假, 或者或者当当A1A2Ak为真时为真时, B也为真也为真, 那么称由前提那么称由前提A1,A2, Ak推推B的推理有效或推理正确的推理有效或推理正确, 并称并称B是有效的结论是有效

2、的结论定理定理2.8 由前提由前提A1, A2, , Ak 推出推出B 的推理正确当且仅当的推理正确当且仅当 A1A2AkB为重言式为重言式.推理的方式构造推理的方式构造方式方式(1) A1A2AkB方式方式(2) 前提前提: A1, A2, , Ak 结论结论: B 推理正确记作推理正确记作 A1A2AkB判别推理能否正确的方法判别推理能否正确的方法:真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法构造证明法构造证明法实例实例例例1 判别下面推理能否正确判别下面推理能否正确:(1) 假设今天是假设今天是1号号, 那么明天是那么明天是5号号. 今天是今天是1号号. 所以所以, 明天

3、是明天是5号号. 解解 设设 p: 今天是今天是1号号, q: 明天是明天是5号号 推理的方式构造为推理的方式构造为 (pq)pq证明证明 用等值演算法用等值演算法 (pq)pq (pq)p)q (pq)p)q pqq 1得证推理正确得证推理正确实例实例(续续)(2) 假设今天天冷,小王就穿羽绒服。小王就穿羽绒服。假设今天天冷,小王就穿羽绒服。小王就穿羽绒服。 所所以以,今天天冷。今天天冷。 解解 设设p:今天天冷今天天冷, q:小王穿羽绒服小王穿羽绒服. 推理的方式构造为推理的方式构造为 (pq)qp证明证明 用主析取范式法用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (

4、pq)(pq) (pq)(pq) m0m2m3 01是成假赋值是成假赋值, 所以推理不正确所以推理不正确.推理定律推理定律重言蕴涵式重言蕴涵式 A (AB) 附加律附加律 (AB) A 化简律化简律(AB)A B 假言推理假言推理(AB)B A 拒取式拒取式(AB)B A 析取三段论析取三段论(AB)(BC) (AC) 假言三段论假言三段论(AB)(BC) (AC) 等价三段论等价三段论(AB)(CD)(AC) (BD) 构造性二难构造性二难 (AB)(AB) B 构造性二难构造性二难(特殊方式特殊方式)(AB)(CD)( BD) (AC) 破坏性二难破坏性二难自然推理系统自然推理系统P自然推

5、理系统自然推理系统P由下述由下述3部分组成部分组成:1. 字母表字母表(1) 命题变项符号命题变项符号: p,q,r, pi,qi,ri,(2) 结合词结合词: , , , , (3) 括号与逗号括号与逗号: ( ), ,2. 合式公式合式公式3. 推理规那么推理规那么(1) 前提引入规那么前提引入规那么(2) 结论引入规那么结论引入规那么(3) 置换规那么置换规那么自然推理系统自然推理系统P(续续)(7) 拒取式规那么拒取式规那么 AB B A(8) 假言三段论规那么假言三段论规那么 AB BC AC (4) 假言推理规那么假言推理规那么 AB A B(5) 附加规那么附加规那么 A AB(

6、6) 化简规那么化简规那么 AB A 自然推理系统自然推理系统P(续续)(11) 破坏性二难推理规那破坏性二难推理规那么么 AB CD BD AC(12) 合取引入规那么合取引入规那么 A B AB (9) 析取三段论规那么析取三段论规那么 AB B A(10)构造性二难推理规那构造性二难推理规那么么 AB CD AC BD直接证明法直接证明法例例2 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明:前提前提: pq, qr, ps, s结论结论: r(pq)证明证明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 pq 前提引入前提引入 q 析取三段论析

7、取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(pq) 合取合取推理正确推理正确, r(pq)是有效结论是有效结论实例实例例例3 构造推理的证明构造推理的证明: 假设明天是星期一或星期三假设明天是星期一或星期三, 我就我就有有课课. 假设有课假设有课, 今天必需备课今天必需备课. 我今天下午没备课我今天下午没备课. 所以所以, 明明天天不是星期一和星期三不是星期一和星期三. 解解 设设 p:明天是星期一明天是星期一, q:明天是星期三,明天是星期三, r:我有课,我有课, s:我备课我备课前提前提: (pq)r, rs, s结论结论: pq 实例实例(续续)前提前提: (pq)r,

8、 rs, s结论结论: pq 证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (pq)r 前提引入前提引入 (pq) 拒取式拒取式 pq 置换置换结论有效结论有效, 即明天不是星期一和星期三即明天不是星期一和星期三附加前提证明法附加前提证明法欲证明欲证明 等价地证明等价地证明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C结论结论: CB 结论结论: B理由理由: (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B实例实例例例4 构造下面推理的证明构造下面推理的证明:前提前提: pq, q

9、r, rs结论结论: ps证明证明 p 附加前提引入附加前提引入 pq 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 析取三段论析取三段论 rs 前提引入前提引入 s 假言推理假言推理推理正确推理正确, ps是有效结论是有效结论归谬法归谬法(反证法反证法)欲证明欲证明前提:前提:A1, A2, , Ak 结论:结论:B将将B参与前提参与前提, 假设推出矛盾假设推出矛盾, 那么得证推理正确那么得证推理正确. 理由理由: A1A2AkB (A1A2Ak)B (A1A2AkB)括号内部为矛盾式当且仅当括号内部为矛盾式当且仅当 (A1A2AkB)为重言式为重言式实例实例例例5

10、 构造下面推理的证明构造下面推理的证明前提前提: (pq)r, rs, s, p结论结论: q证明证明 用归缪法用归缪法 q 结论否认引入结论否认引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式实例实例(续续) (pq)r 前提引入前提引入 (pq) 析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 pp 合取合取推理正确推理正确, q是有效结论是有效结论归结证明法归结证明法理由理由 (pq)(pr)(qr) (pq)(pr)(qr) (pq)(pr)qr (pq)q)(pr)r) (pq)(pr) 1归结规那么归结规那么 A B A C

11、 B C归结证明法归结证明法(续续)在自然推理系统在自然推理系统P中只需下述推理规那么中只需下述推理规那么:(1) 前提引入规那么前提引入规那么(2) 结论引入规那么结论引入规那么(3) 置换规那么置换规那么(4) 化简规那么化简规那么(5) 合取引入规那么合取引入规那么(6) 归结规那么归结规那么归结证明法的根本步骤归结证明法的根本步骤1. 将每一个前提化成等值的合取范式将每一个前提化成等值的合取范式, 设一切合取范式的设一切合取范式的全部简单析取式为全部简单析取式为A1, A2, At2. 将结论化成等值的合取范式将结论化成等值的合取范式B1B2Bs, 其中每个其中每个Bj是简单析取式是简单析取式3. 以以A1,A2,At为前提为前提, 运用归结规那么推出每一个运用归结规那么推出每一个Bj, 1js4. 由合取引入规那么得到结论由合取引入规那么得到结论B1B2Bs实例实例例例6 用归结证明法构造下面推理的证明用归结证明法构造下面推理的证明:前提前提: (pq)r, rs, s结论结论: (pq)(ps)解解 (pq)r (pq)r (pq)r (pr)(qr) rs rs (pq)(ps) (pq)(ps) (pq)(ps) p(qs)推理可表成推理可表成前提前提: pr, qr, rs, s结论结论: p(qs)实例实例(续续)

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论