离散数学屈婉玲第三章

单击此处编辑母版标题样式,*,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,附加,