离散数学---推理理论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,西华大学 制作,1.6,推理理论,一、有效论证推理规则,二、基本蕴涵式,三、自然推理系统,P,四、推理证明的方法,一、有效论证与推理规则,定义：,A,1,A,2,A,n,A,其为永真式，则称由,前提,A,1,A,2,A,n,得到,有效结论,A,；,从前提公式得到有效结论的过程称为,正确推理,。,若,A,B,是永真式，则记为,AB,；,若,A,B,是永真式，则记为,A,B,。,前提一致和不一致：,如果前提,A1A2An,为可满足式，则称为前提,A1,A2,An,一致。,实例分析,判断推理是否正确：张红不管有无空闲都不看电影。张红看了电影。所以张红有空闲时间又没有空闲时间。,解：,P:,张红有空闲时间；,Q,：,张红看电影。,前提：,A1=P,P,Q,A2=Q,结论：,A=P,P,问题：,该结论是否有效结论。,(,该推理是否正确,),。,0,1,0,1,0,0,0,0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,0,0,(P,P,Q)Q P,P,Q,P,所以，结论,A,是有效结论；该推理是正确的。而前提是不一致的。,基本蕴涵式,名称,蕴涵关系式,化简式,A,B,A,A,B,B,(,AB),A,(,AB),B,附加式,A,A,B,B,A,B,A,A,B B,A,B,假言推理,(A,B)A,B,拒取式,(A,B),B,A,析取三段式,(A,B),A,B,假言三段式,(A,B)(BC),A,C,等价三段式,(A,B),(B,C)AC,二难推论,(A,B)(CD)(AC),B,D,(A,B),B,A,的证明,A,B,(A,B),B,A,0,0,1,1,1,1,1,0,1,1,0,0,1,1,1,0,0,0,1,1,0,1,1,1,0,0,1,0,法一、真值表法：,0,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,0,0,0,(,A B),B,B,A,法二、利用等值演算法证明：,证：,(,A B),B,(,AB),B,(AB),B,(,AB),B,A(B,B),AT,T,所以,(,AB),B,(,AB),B,的证明,?,第三种方法,?,自然推理系统,P,形式系统,自然推理系统,公理系统,特点,：,只能从,几个给定的公理,出发，应用系统中的推理规则进行推演，得到的结论是系统中的,定理,。,特点,：可以从,任意给定的前提,出发，应用系统中的推理进行推演，得到的结论在系统中被认为是,有效的,。,自然推理系统,P,自然推理系统,P,定义如下,：,1.,字母表,(1),命题常元，命题变元：,P,Q,R,P,i,Q,i,1,0(T,F),(2),命题联结词：,、,、,(3),括号：,(,),2.,合式公式：,(,略,)3.,推理规则：,(1).,前提引入规则,(P,规则,),：在证明的任何步上，都可引入前提；,(2).,结论引用规则,(T,规则,),：在证明的任何步上，所得的结论都可作为证明得前提；,(3).,置换规则：,在证明的任何步上，命题公式的任何子命题公式都可以用与之等价的命题公式置换。,(4).,永真蕴涵规则：,使用基本蕴涵式，常常将条件用，分开。,基本蕴涵式证明的另一种方法,(,AB),B,的证明,证明：,(,AB),(,AB),A,B,A,B,B (,简化式）,(AB),B,的证明,推理过程的证明形式,规范化的形式：,序号 公式 理由,B,1,E,或,I,或,P,或,的合取 或,cp,B,2B,3,.,注意：,1),并非,B,1,B,2,B,3,2)B,i,的获取：前提、中间结论,构造下列的推理的证明：,前提：,PQ,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:,作案时间发生在午夜前；,S:,李四证词正确；,M:,午夜时灯光未灭。,则前提为,:(1)PQ,(2)P,R,(3)SM,(4),SR,(5),M,。,结论未定。,所以，可以得出是李四盗了录像机。,例如,前提：,p,(,(,r,s),q),，,p,，,s,结论：,q,。,证明：,p p,规则,p,(,(,r,s),q,),p,规则,(,r,s),q,I,s,p,规则,s,r I,(,r,s),E,q I,推理证明的方法,前提的合取,结论 是永真式,间接证明法,推理证明,演绎证明,归纳证明,直接证明法,附加前提证法,(CP),归谬法,(,反证法,),附加前提证法,(CP),针对这种情况：,前提：,A,1,，,A,2,，,，,A,n,结论：,AB,前提：,A,1,，,A,2,，,，,A,n,，,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,结论,：,S,R,归谬法,(,反证法,),针对这种情况：,前提：,A,1,，,A,2,，,，,A,n,结论：,A,前提：,A,1,，,A,2,，,，,A,n,，,A,结论：,0,（,F,）,A,(,A),例：前提：,R,Q,，,RS,，,S,Q,，,PQ,结论：,P,证明：,(,P),否定结论引入（,CP,规则）,P E,PQ P,Q,I,R,Q P,R I,RS,P,S,I,S,Q P,Q,I,F,的合取,