离散数学推理理论.ppt

上传人:牧羊曲112 文档编号:6010468 上传时间:2023-09-14 格式:PPT 页数:18 大小:244KB
返回 下载 相关 举报
离散数学推理理论.ppt_第1页
第1页 / 共18页
离散数学推理理论.ppt_第2页
第2页 / 共18页
离散数学推理理论.ppt_第3页
第3页 / 共18页
离散数学推理理论.ppt_第4页
第4页 / 共18页
离散数学推理理论.ppt_第5页
第5页 / 共18页
点击查看更多>>
资源描述

《离散数学推理理论.ppt》由会员分享,可在线阅读,更多相关《离散数学推理理论.ppt(18页珍藏版)》请在三一办公上搜索。

1、1.6 推理理论,一、有效论证推理规则二、基本蕴涵式三、自然推理系统P四、推理证明的方法,一、有效论证与推理规则,定义:A1A2AnA,其为永真式,则称由前提A1,A2,An得到有效结论A;从前提公式得到有效结论的过程称为正确推理。若AB是永真式,则记为AB;若AB是永真式,则记为AB。前提一致和不一致:如果前提A1A2An为可满足式,则称为前提A1,A2,An一致。,实例分析,判断推理是否正确:张红不管有无空闲都不看电影。张红看了电影。所以张红有空闲时间又没有空闲时间。解:P:张红有空闲时间;Q:张红看电影。前提:A1=P P Q A2=Q 结论:A=P P 问题:该结论是否有效结论。(该推

2、理是否正确)。,所以,结论A是有效结论;该推理是正确的。而前提是不一致的。,基本蕴涵式,(AB)B A的证明,法一、真值表法:,(AB)B的证明,?第三种方法?,自然推理系统P,形式系统,自然推理系统,公理系统,特点:只能从几个给定的公理出发,应用系统中的推理规则进行推演,得到的结论是系统中的定理。,特点:可以从任意给定的前提出发,应用系统中的推理进行推演,得到的结论在系统中被认为是有效的。,自然推理系统P,自然推理系统P定义如下:1.字母表(1)命题常元,命题变元:P,Q,R,Pi,Qi,1,0(T,F)(2)命题联结词:、(3)括号:(,)2.合式公式:(略)3.推理规则:(1).前提引入

3、规则(P规则):在证明的任何步上,都可引入前提;(2).结论引用规则(T规则):在证明的任何步上,所得的结论都可作为证明得前提;(3).置换规则:在证明的任何步上,命题公式的任何子命题公式都可以用与之等价的命题公式置换。(4).永真蕴涵规则:使用基本蕴涵式,常常将条件用,分开。,基本蕴涵式证明的另一种方法,(AB)B的证明证明:(AB)(AB)A B A B B(简化式),(AB)B的证明,推理过程的证明形式,规范化的形式:序号 公式 理由 B1 E 或 I 或 P 或 的合取 或 cp B2.B3.,注意:1)并非B1B2B3 2)Bi的获取:前提、中间结论,构造下列的推理的证明:前提:PQ

4、,P R,SM,SR,M 结论:Q。证:,M P,SM P,S I拒取式,SR P,R I假言推理,P R P,P I拒取式,PQ P,Q I析取三段式,一公安人员审查一件案件。一致的事实如下:(1).张三或李四盗窃了录像机;(2).如果张三盗窃了录像机,则作案时间不能在午夜前;(3).如果李四证词正确,则午夜时屋内灯光未灭;(4).如果李四证词不正确,则作案时间在午夜前;(5).午夜时屋内灯灭了。,M P,SM P,S I拒取式,SR P,R I假言推理,P R P,P I拒取式,PQ P,Q I析取三段式,解:将已知事实符号化:设 P:张三盗窃录像机;Q:李四盗窃录像机;R:作案时间发生在

5、午夜前;S:李四证词正确;M:午夜时灯光未灭。,则前提为:(1)PQ,(2)P R,(3)SM,(4)SR,(5)M。结论未定。,所以,可以得出是李四盗了录像机。,例如,前提:p(rs)q),p,s结论:q。证明:p p规则 p(rs)q)p规则(rs)q I s p规则 s r I(rs)E q I,推理证明的方法,前提的合取结论 是永真式,间接证明法,推理证明,演绎证明,归纳证明,直接证明法,附加前提证法(CP),归谬法(反证法),附加前提证法(CP),针对这种情况:前提:A1,A2,An结论:AB,前提:A1,A2,An,A结论:B,例:前提:P,P(Q R S)结论:Q S,证明:(1)P cp规则(2)P(Q R S)cp规则(3)Q R S(1)(2)I(4)Q cp规则(5)R S(3)(4)I(6)S(5)I,课堂作业:前提:PQR,S P,Q 结论:SR,归谬法(反证法),针对这种情况:前提:A1,A2,An结论:A,前提:A1,A2,An,A结论:0(F),例:前提:RQ,RS,SQ,PQ 结论:P,证明:(P)否定结论引入(CP规则)P E PQ P Q I RQ P R I RS P S I SQ P Q I F 的合取,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号