离散数学命题逻辑推理理论推选.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学命题逻辑推理理论,1,有效推理,定义2.20,若对于每组赋值,A,1,A,2,A,k,为假,或者,当,A,1,A,2,A,k,为真时,B,也为真,则称由前提,A,1,A,2,A,k,推,B,的,推理有效,或,推理正确,并称,B,是,有效的结论,由前提,A,1,A,2,A,k,推出,B,的推理正确当且仅当,A,1,A,2,A,k,B,为重言式.,2,(10)构造性二难推理规则,r 拒取式,所以,明天是5号.,结论:p(qs),(11)破坏性二难推理规则,B,(pq)qp,(8)假言三段论规则,推理的形式结构为 (pq)qp,r0 归结,rs 前提引入,前提:(pq)r,rs,s,推理的形式结构,形式(1),A,1,A,2,A,k,B,形式(2),前提:,A,1,A,2,A,k,结论:,B,推理正确记作,A,1,A,2,A,k,B,判断推理是否正确的方法:,真值表法,等值演算法,主析取范式法,构造证明法,3,实例,例1,判断下面推理是否正确:,(1)若今天是1号,则明天是5号.今天是1号.所以,明天是5号.,解 设,p,:,今天是1号,q,:,明天是5号,推理的形式结构为 (,p,q,),p,q,证明 用等值演算法,(,p,q,),p,q,(,p,q,),p,),q,(,p,q,),p,),q,p,q,q,1,得证推理正确,4,实例,(,续,),(2)若今天是1号,则明天是5号.明天是5号.所以,今天是1号.,解 设,p,:,今天是1号,q,:,明天是5号.,推理的形式结构为 (,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,01是成假赋值,所以推理不正确.,5,推理定律,重言蕴涵式,A,(,A,B,),附加律,(,A,B,),A,化简律,(,A,B,),A,B,假言推理,(,A,B,),B,A,拒取式,(,A,B,),B,A,析取三段论,(,A,B,),(,B,C,),(,A,C,),假言三段论,(,A,B,),(,B,C,),(,A,C,),等价三段论,(,A,B,),(,C,D,),(,A,C,),(,B,D,),构造性二难,(,A,B,),(,A,B,),B,构造性二难(特殊形式),(,A,B,),(,C,D,),(,B,D,),(,A,C,),破坏性二难,6,自然推理系统,P,自然推理系统,P,由下述3部分组成:,1.字母表,(1)命题变项符号:,p,q,r,p,i,q,i,r,i,(2)联结词:,(3)括号与逗号:(),2.合式公式,3.推理规则,(1)前提引入规则,(2)结论引入规则,(3)置换规则,7,自然推理系统,P,(,续),(7),拒取式规则,A,B,B,A,(8),假言三段论规则,A,B,B,C,A,C,(4)假言推理规则,A,B,A,B,(5),附加规则,A,A,B,(6)化简规则,A,B,A,8,自然推理系统,P,(,续),(11)破坏性二难推理规则,A,B,C,D,B,D,A,C,(12),合取引入规则,A,B,A,B,(9)析取三段论规则,A,B,B,A,(10),构造性二难推理规则,A,B,C,D,A,C,B,D,9,直接证明法,例2,在自然推理系统,P,中构造下面推理的证明:,前提:,p,q,q,r,p,s,s,结论:,r,(,p,q,),证明,p,s,前提引入,s,前提引入,p,拒取式,p,q,前提引入,q,析取三段论,q,r,前提引入,r,假言推理,r,(,p,q,),合取,推理正确,r,(,p,q,),是有效结论,10,实例,例3,构造推理的证明:若明天是星期一或星期三,我就有,课.若有课,今天必需备课.我今天下午没备课.所以,明天,不是星期一和星期三.,解 设,p,:,明天是星期一,q,:,明天是星期三，,r,:,我有课，,s,:,我备课,前提:(,p,q,),r,r,s,s,结论:,p,q,11,实例,(,续,),前提:(,p,q,),r,r,s,s,结论:,p,q,证明,r,s,前提引入,s,前提引入,r,拒取式,(,p,q,),r,前提引入,(,p,q,),拒取式,p,q,置换,结论有效,即明天不是星期一和星期三,12,附加前提证明法,欲证明 等价地证明,前提:,A,1,A,2,A,k,前提:,A,1,A,2,A,k,C,结论:,C,B,结论:,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,13,实例,例4,构造下面推理的证明:,前提:,p,q,q,r,r,s,结论:,p,s,证明,p,附加前提引入,p,q,前提引入,q,析取三段论,q,r,前提引入,r,析取三段论,r,s,前提引入,s,假言推理,推理正确,p,s,是有效结论,14,归谬法,(,反证法,),欲证明,前提：,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,),为重言式,15,实例,例5,构造下面推理的证明,前提:,(,p,q,),r,r,s,s,p,结论:,q,证明 用归缪法,q,结论否定引入,r,s,前提引入,s,前提引入,r,拒取式,16,实例(续),(,p,q,),r,前提引入,(,p,q,),析取三段论,p,q,置换,p,析取三段论,p,前提引入,p,p,合取,推理正确,q,是有效结论,17,归结证明法,理由,(,p,q,),(,p,r,),(,q,r,),(,(,p,q,),(,p,r,),(,q,r,),(,p,q,),(,p,r,),q,r,(,(,p,q,),q,),(,p,r,),r,),(,p,q,),(,p,r,),1,归结规则,A,B,A,C,B,C,18,归结证明法,(,续,),在自然推理系统,P,中只需下述推理规则:,(1)前提引入规则,(2)结论引入规则,(3)置换规则,(4)化简规则,(5)合取引入规则,(6)归结规则,19,归结证明法的基本步骤,1.将每一个前提化成等值的合取范式,设所有合取范式的,全部简单析取式为,A,1,A,2,A,t,2.将结论化成等值的合取范式,B,1,B,2,B,s,其中每个,B,j,是简单析取式,3.以,A,1,A,2,A,t,为前提,使用归结规则推出每一个,B,j,1,j,s,4.由合取引入规则得到结论,B,1,B,2,B,s,20,实例,例6,用归结证明法构造下面推理的证明:,前提:,(,p,q,),r,r,s,s,结论:,(,p,q,)(,p,s,),解,(,p,q,),r,(,p,q,),r,(,p,q,),r,(,p,r,),(q,r,),r,s,r,s,(,p,q,)(,p,s,)(,p,q,)(,p,s,)(,p,q,),(,p,s,),p,(,q,s,),推理可表成,前提:,p,r,q,r,r,s,s,结论:,p,(,q,s,),21,实例,(,续,),前提:,p,r,q,r,r,s,s,结论:,p,(,q,s,),证明,q,r,前提引入,r,s,前提引入,q,s,归结,s,前提引入,s,0,置换,r,0,归结,p,r,前提引入,p,0,归结,p,置换,p,(,q,s,),合取引入,22,精品课件,！,23,pp 合取,(10)构造性二难推理规则,s 前提引入,p(qs),AC,(AB)B A 析取三段论,CD,AB,CD,(A1A2AkB),(AB)(CD)(AC)(BD)构造性二难,r:我有课，s:我备课,AB,r 拒取式,rs rs,解 设 p:明天是星期一,q:明天是星期三，,(11)破坏性二难推理规则,精品课件,！,24,实例：公安破案,一个公安人员审查一件盗窃案，已知的事实如下：,A,或,B,盗窃了钻石；若,A,盗窃了钻石，则作案时间不能发生在午夜前；若,B,证词正确，则在午夜时屋里灯光未灭；若,B,证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。谁盗窃了钻石呢？,25,感谢观看,