离散数学屈婉玲第三章

上传人:guoc****ang 文档编号:243722198 上传时间:2024-09-29 格式:PPT 页数:25 大小:289KB
返回 下载 相关 举报
离散数学屈婉玲第三章_第1页
第1页 / 共25页
离散数学屈婉玲第三章_第2页
第2页 / 共25页
离散数学屈婉玲第三章_第3页
第3页 / 共25页
点击查看更多>>
资源描述
单击此处编辑母版标题样式,*,1,主要内容,推理的形式结构,推理的正确与错误,推理的形式结构,判断推理正确的方法,推理定律,自然推理系统,P,形式系统的定义与分类,自然推理系统,P,在,P,中构造证明,:,直接证明法、附加前提证明法、归谬法,第三章 命题逻辑的推理理论,2,3.1,推理的形式结构,定义,3.1,设,A,1,A,2, ,A,k,B,为命题公式,.,若对于每一组赋值,,A,1,A,2,A,k,为假,或当,A,1,A,2,A,k,为真时,,B,也为真,,则称由,前提,A,1,A,2, ,A,k,推出,结论,B,的,推理,是,有效的,或,正确,的,并称,B,是,有效结论,.,定理,3.1,由命题公式,A,1,A,2, ,A,k,推出,B,的推理正确当且仅当,A,1,A,2,A,k,B,为重言式,注意,:,推理正确不能保证结论一定正确,3,推理的形式结构,2.,A,1,A,2,A,k,B,若推理正确,记为,A,1,A,2,A,k,B,3.,前提:,A,1,A,2, ,A,k,结论:,B,判断推理是否正确的方法,:,真值表法,等值演算法,主析取范式法,推理的形式结构,1. ,A,1,A,2, ,A,k,B,若推理正确,记为,A,1,A,2,A,n,B,4,推理实例,例,1,判断下面推理是否正确,(1),若今天是,1,号,则明天是,5,号,.,今天是,1,号,.,所以,明天是,5,号,.,(2),若今天是,1,号,则明天是,5,号,.,明天是,5,号,.,所以,今天是,1,号,.,解 设,p,:今天是,1,号,,q,:明天是,5,号,.,(1),推理的形式结构,:,(,p,q,),p,q,用等值演算法,(,p,q,),p,q,(,p,q,),p,),q,p,q,q,1,推理正确,5,推理实例,(2),推理的形式结构,:,(,p,q,),q,p,用主析取范式法,(,p,q,),q,p,(,p,q,),q,p,(,p,q,),q,),p,q,p,(,p,q,),(,p,q,),(,p,q,),(,p,q,),m,0,m,2,m,3,推理不正确,6,推理定律,重言蕴涵式,1.,A,(,A,B,),附加律,2. (,A,B,),A,化简律,3. (,A,B,),A,B,假言推理,4. (,A,B,),B,A,拒取式,5. (,A,B,),B,A,析取三段论,6. (,A,B,),(,B,C,),(,A,C,),假言三段论,7. (,A,B,),(,B,C,),(,A,C,),等价三段论,8. (,A,B,),(,C,D,),(,A,C,),(,B,D,),构造性二难,(,A,B,),(,A,B,),B,构造性二难,(,特殊形式,),9. (,A,B,),(,C,D,),(,B,D,),(,A,C,),破坏性二难,每个等值式可产生两个推理定律,如,由,A,A,可产生,A,A,和 ,A,A,7,3.2,自然推理系统,P,定义,3.2,一个,形式系统,I,由下面四个部分组成:,(1),非空的字母表,记作,A,(,I,),.,(2),A,(,I,),中符号构造的合式公式集,记作,E,(,I,),.,(3),E,(,I,),中一些特殊的公式组成的公理集,记作,A,X,(,I,),.,(4),推理规则集,记作,R,(,I,),.,记,I,=,其中,是,I,的,形式语言,系统, ,是,I,的,形式演算系统,.,自然推理系统,:,无公理集,即,A,X,(,I,)=,公理推理系统,有公理集,推出的结论是系统中的重言式,称,作,定理,8,自然推理系统,P,定义,3.3,自然推理系统,P,定义,如下,:,1.,字母表,(1),命题变项符号:,p,q,r, ,p,i,q,i,r,i, ,(2),联结词符号:,(3),括号与逗号:,(, ),,,2.,合式公式(同定义,1.6,),3.,推理规则,(1),前提引入规则,(2),结论引入规则,(3),置换规则,9,推理规则,(4),假言推理规则,(6),化简规则,(8),假言三段论规则,A,B,A,B,A,A,B,A,B,A,(5),附加规则,(7),拒取式规则,(9),析取三段论规则,A,B,B,A,A,B,B,C,A,C,A,B,B,A,10,推理规则,(10),构造性二难推理规则,(11),破坏性二难推理规则,(12),合取引入规则,A,B,C,D,A,C,B,D,A,B,C,D,B,D,A,C,A,B,A,C,11,在自然推理系统,P,中构造证明,设前提,A,1,A,2,A,k,结论,B,及公式序列,C,1,C,2,C,l,.,如果每,一个,C,i,(1,i,l,),是某个,A,j,或者可由序列中前面的公式应用推理,规则得到,并且,C,l,=,B,则称这个公式序列是由,A,1,A,2,A,k,推,出,B,的,证明,例,2,构造下面推理的证明:,若明天是星期一或星期三,我明天就有课,.,若我明天有课,今天必备课,.,我今天没备课,.,所以,明天不是星期一,也不,是星期三,.,解,(1),设命题并符号化,设,p,:明天是星期一,,q,:明天是星期三,,r,:我明天有课,,s,:我今天备课,12,直接证明法,(2),写出证明的形式结构,前提:,(,p,q,),r,r,s,s,结论:,p,q,(3),证明,r,s,前提引入,s,前提引入,r,拒取式,(,p,q,),r,前提引入,(,p,q,) ,拒取式,p,q,置换,13,附加前提证明法,附加前提证明法,适用于结论为蕴涵式,欲证,前提:,A,1,A,2, ,A,k,结论:,C,B,等价地证明,前提:,A,1,A,2, ,A,k,C,结论:,B,理由:,(,A,1,A,2,A,k,),(,C,B,),(,A,1,A,2,A,k,),(,C,B,),(,A,1,A,2,A,k,C,),B,(,A,1,A,2,A,k,C,),B,14,附加前提证明法实例,例,3,构造下面推理的证明,2,是素数或合数,.,若,2,是素数,则,是无理数,.,若,是无理数,则,4,不是素数,.,所以,如果,4,是素数,则,2,是合数,.,解 用附加前提证明法构造证明,(1),设,p,:,2,是素数,,q,:,2,是合数,,r,:,是无理数,,s,:,4,是素数,(2),推理的形式结构,前提:,p,q,p,r,r,s,结论:,s,q,15,附加前提证明法实例,(3),证明,s,附加前提引入,p,r,前提引入,r,s,前提引入,p,s,假言三段论,p,拒取式,p,q,前提引入,q,析取三段论,16,归谬法(反证法),归谬法,(,反证法,),欲证,前提:,A,1,A,2, ,A,k,结论:,B,做法,在前提中加入,B,,推出矛盾,.,理由,A,1,A,2,A,k,B,(,A,1,A,2,A,k,),B,(,A,1,A,2,A,k,B,),(,A,1,A,2,A,k,B,),0,A,1,A,2,A,k,B,0,17,归谬法实例,例,4,前提:,(,p,q,),r,r,s,s,p,结论:,q,证明 用归缪法,q,结论否定引入,r,s,前提引入,s,前提引入,r,拒取式,(,p,q,),r,前提引入,(,p,q,) ,析取三段论,p,q,置换,p,析取三段论,p,前提引入,p,p,合取,18,第三章 习题课,主要内容,推理的形式结构,判断推理是否正确的方法,真值表法,等值演算法,主析取范式法,推理定律,自然推理系统,P,构造推理证明的方法,直接证明法,附加前提证明法,归谬法,(,反证法,),19,基本要求,理解并记住推理形式结构的两种形式:,1. (,A,1,A,2,A,k,),B,2.,前提:,A,1,A,2, ,A,k,结论:,B,熟练掌握判断推理是否正确的不同方法(如真值表法、等值演算法、主析取范式法等),牢记,P,系统中各条推理规则,熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法,会解决实际中的简单推理问题,20,练习,1,:判断推理是否正确,1.,判断下面推理是否正确,:,(,1),前提:,p,q,q,结论:,p,解 推理的形式结构,:,(,p,q,),q,p,方法一:等值演算法,(,p,q,),q,p,(,p,q,),q,),p,(,p,q,),q,p,(,p,q,),(,q,q,),p,p,q,不是重言式,所以推理不正确,.,21,练习,1,解答,方法二:主析取范式法,,(,p,q,),q,p,(,p,q,),q,),p,p,q,M,2,m,0,m,1,m,3,未含,m,2,不是重言式,推理不正确,.,22,练习,1,解答,方法三 真值表法,不是重言式,推理不正确,1,1,1,0,0,1,1,1,0,1,0,0,(,p,q,),q,p,q,p,p,q,0,1,1,1,(,p,q,),q,0,0,1,0,方法四 直接观察出,10,是成假赋值,23,练习,1,解答,用等值演算法,(,q,r,),(,p,r,),(,q,p,),(,q,r,)(,p,r,),(,q,p,),(,q,r,)(,p,r,)(,q,p,),(,q,p,)(,q,r,)(,r,p,)(,q,p,), (,q,p,)(,q,r,)(,r,p,)(,q,p,),1,推理正确,(2),前提:,q,r,p,r,结论:,q,p,解 推理的形式结构:,(,q,r,),(,p,r,),(,q,p,),24,练习,2,:构造证明,2.,在系统,P,中构造下面推理的证明:,如果今天是周六,我们就到颐和园或圆明园玩,.,如果颐和,园游人太多,就不去颐和园,.,今天是周六,并且颐和园游,人太多,.,所以,我们去圆明园或动物园玩,.,证明,:,(1),设,p,:今天是周六,,q,:到颐和园玩,,r,:到圆明园玩,,s,:颐和园游人太多,t,:到动物园玩,.,(2),前提:,p,(,q,r,),s,q,p,s,结论:,r,t,25,练习,2,解答,(3),证明:,p,(,q,r,),前提引入,p,前提引入,q,r,假言推理,s,q,前提引入,s,前提引入,q,假言推理,r,析取三段论,r,t,附加,
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 图纸专区 > 小学资料


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!