命题逻辑推理理论

命题逻辑推理理论,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,命题逻辑推理理论,命题逻辑推理理论,定义2.20 假设对于每组赋值,A1A2 Ak 为假,或者,当A1A2Ak为真时,B也为真,那么称由前提A1,A2,Ak,推B的推理有效或推理正确,并称B是有效的结论,定理2.8 由前提A1,A2,Ak 推出B 的推理正确当且仅当,A1A2AkB,为重言式.,2,命题逻辑推理理论,形式(1),A,1,A,2,A,k,B,形式(2)前提:,A,1,A,2,A,k,结论:,B,推理正确记作,A,1,A,2,A,k,B,判断推理是否正确的方法:,真值表法,等值演算法,主析取范式法,构造证明法,3,命题逻辑推理理论,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,),破坏性二难,4,命题逻辑推理理论,例1 判断下面推理是否正确:,(1)假设今天是1号,那么明天是5号.今天是1号.所以,明天是5号.,解 设 p:今天是1号,q:明天是5号,推理的形式构造为 (pq)pq,证明 用等值演算法,(pq)pq,(pq)p)q,(pq)p)q,pqq 1,得证推理正确,5,命题逻辑推理理论,(2)假设今天是1号,那么明天是5号.明天是5号.所以,今天是1号.,解 设p:今天是1号,q:明天是5号.,推理的形式构造为 (pq)qp,证明 用主析取范式法,(pq)qp,(pq)qp,(pq)q)p,qp,(pq)(pq)(pq)(pq),m0m2m3,01是成假赋值,所以推理不正确.,6,(3),前提：,1.如果明天天晴，我们准备外出旅游。PQ,2明天确实天晴。P,结论：我们外出旅游。Q,可描述为：(PQ)PQ,(4),前提：,1.如果一个人是单身汉，那么他不幸福。PQ,2.如果一个人不幸福，那么他死得早。QR,结论：单身汉死得早。PR,可描述为：(PQ)(QR)PR,命题逻辑推理理论,7,(5)前提：,1.如果某同学为省二级以上运发动，那么他将被大学录取。PR,2.如果某同学高考总分在560分以上，那么将被大学录取。QR,3.某同学高考总分在560分以上或者是省二级运发动。PQ,结论：该同学被大学录取。R,那么上述例子可描述为：,(PR)(QR)(PQ)R(构造性二难),命题逻辑推理理论,8,(6)某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得,前提：,1.凶手为王某或陈某。PQ,2.如果王某是凶手，那么他在作案当晚必外出 PR,3.王某案发之晚并未外出。R,结论：陈某是凶手。Q,那么可描述为：(PR)RP(拒取式),(PQ)PQ(析取三段论),命题逻辑推理理论,9,命题逻辑推理理论,自然推理系统P由下述3局部组成:,1.字母表,(1)命题变项符号:p,q,r,pi,qi,ri,(2)联结词:,(3)括号与逗号:(),2.合式公式,3.推理规那么,(1)前提引入规那么,(2)结论引入规那么：将结论作为后继证明前提,(3)置换规那么：子公式用与之等值的公式置换,10,命题逻辑推理理论,(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,11,命题逻辑推理理论,(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,12,命题逻辑推理理论,如何根据前提得到结论，需要有推理的规那么。下面先介绍两个推理规那么。,规那么P(引入前提规那么)：在推理过程中，可以随时引入前提。,规那么T(引入结论规那么)：在推理过程中，如果前边有一个或几个公式永真蕴涵公式S，那么可将S纳入推理过程中。,在推理过程中，还要应用教材69页表中的永真蕴涵式和49-50页中等价公式(常用的公式要熟记),下面主要介绍三种推理方法：,直接证明法、附加前提证明法、反证法及归结证明法,13,命题逻辑推理理论,例2 在自然推理系统P中构造下面推理的证明:,前提:pq,qr,ps,s,结论:r(pq),分析：因为前提中有pq，因此只需要有r即可通过合取规那么得到结论。,证明 ps 前提引入,s 前提引入,p 拒取式,pq 前提引入,q 析取三段论,qr 前提引入,r 假言推理,r(pq)合取,推理正确,r(pq)是有效结论,思考：格式中应包含哪些？,步骤号,给定前提或得出的结论,推理时所用规那么,此结论是从哪几步得到的及所用公式,14,命题逻辑推理理论,例3 构造推理的证明:假设明天是星期一或星期三,我就有,课.假设有课,今天必需备课.我今天下午没备课.所以,明天,不是星期一和星期三.,解 设 p:明天是星期一,q:明天是星期三，,r:我有课，s:我备课,前提:(pq)r,rs,s,结论:pq,15,命题逻辑推理理论,前提:(,p,q,),r,r,s,s,结论:,p,q,证明,r,s,前提引入,s,前提引入,r,拒取式,(,p,q,),r,前提引入,(,p,q,),拒取式,p,q,置换,结论有效,即明天不是星期一和星期三,16,命题逻辑推理理论,用直接证明法在自然推理系统,P,中构造下面推理的证明:,前提:,p,q,r,q,r,s,结论:,p,s,证明,p,q,前提引入,p,q,蕴含等值式,r,q,前提引入,q,r,蕴含等值式,p,r,假言,三段论,r,s,前提引入,p,s,假言三段论,推理正确,p,s,是有效结论,17,命题逻辑推理理论,用直接证明法在自然推理系统,P,中构造下面推理,的有效性：,如果我学习，那么我数学不会不及格。如果我不热衷于玩朴克，那么我将学习。但是我数学不及格。因此，我热衷于玩朴克。,解设,P,：我学习。,Q,：我数学及格。,R,：我热衷于玩朴克。,18,命题逻辑推理理论,定理：,欲证明 等价地证明,前提:,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,19,命题逻辑推理理论,此定理告诉我们，如果要证明的结论是蕴涵式(RS)形式，那么可以把结论中蕴涵式的前件R作为附加前提，与给定的前提一起推出后件S即可。,我们把上述定理写成如下规那么：,规那么CP(Conditional roof)：,如果H1H2.HnR S，那么,H1H2.Hn RS,20,命题逻辑推理理论,例4 构造下面推理的证明:,前提:,p,q,q,r,r,s,结论:,p,s,证明,p,附加前提引入,p,q,前提引入,q,析取三段论,q,r,前提引入,r,析取三段论,r,s,前提引入,s,假言推理,推理正确,p,s,是有效结论,21,命题逻辑推理理论,用附加前提证明方法证明下面推理的有效性：,如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，那么体育馆没有球赛。,证明 先将命题符号化。,设 p：体育馆有球赛。,q：青年大街交通拥挤。,r：小王提前出发。,s：小王迟到。,前提：pq，(qr)s,结论：(rs)p,证明,(1)rs 附加前提,(2)r (2)化前提简律,(3)s (1)化简律,(4)(qr)s 前提引入,(5)(qr)(3)(4)拒取式,(6)qr (5)德摩根置换,(7)q (2)(6)析取三段论,(8)pq 前提引入,(9)p (7)(8)拒取式,(10)(rs)p CP规那么,22,命题逻辑推理理论,欲证明,前提：A1,A2,Ak,结论：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,),为重言式,23,命题逻辑推理理论,例5 构造下面推理的证明,前提:(pq)r,rs,s,p,结论:q,证明 用归缪法,q 结论否认引入,rs 前提引入,s 前提引入,r 拒取式,(pq)r 前提引入,(pq)析取三段论,pq 置换,p 析取三段论,p 前提引入,pp 合取,推理正确,q是有效结论,24,命题逻辑推理理论,前提：,p,q,r,q,r,s,结论：,p,前提：,p,q,p,r,q,s,结论：,r,s,25,命题逻辑推理理论,理由,(,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,26,命题逻辑推理理论,在自然推理系统P中只需下述推理规那么P70-71:,(1)前提引入规那么,(2)结论引入规那么,(3)置换规那么,(4)化简规那么,(5)合取引入规那么,(6)归结规那么,27,命题逻辑推理理论,1.将每一个前提化成等值的合取范式,设所有合取范式的,全部简单析取式为A1,A2,At,2.将结论化成等值的合取范式B1B2Bs,其中每个Bj,是简单析取式,3.以A1,A2,At为前提,使用归结规那么推出每一个Bj,1js,4.由合取引入规那么得到结论B1B2Bs,28,命题逻辑推理理论,例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,),29,命题逻辑推理理论,前提:,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,),合取引入,注意：不同思路，前提引用顺序不同，因此证明过程也略有差异。但结果是一样的。,30,命题逻辑推理理论,习题：用归结法证明以下命题,前提：pq,pr,rs,结论：qs,前提：p,pr,r s,结论：s,前提：p(qs),r p,q,结论：r s,31,命题逻辑推理理论,知识网络：,命 题,原子命题,复合命题,联结词,命题公式,永真式,永真蕴涵式,等价公式,范式,命题逻辑推理,直接推理,间接推理,条件论证,反证法,析取,合取,主析取,主合取,32,主要内容,1.等值式与等