离散数学-24命题逻辑推理理论

课件,1,2.4命题逻辑推理理论,2.4.1推理的形式结构推理的前提与结论,正确推理推理定律2.4.2自然推理系统P推理规则直接证明法,附加前提证明法,归谬法(反证法),归结证明法,课件,2,有效推理,定义2.20若对于每组赋值,A1A2Ak为假,或者当A1A2Ak为真时,B也为真,则称由前提A1,A2,Ak推B的推理有效或推理正确,并称B是有效的结论定理2.8由前提A1,A2,Ak推出B的推理正确当且仅当A1A2AkB为重言式.,课件,3,推理的形式结构,形式(1)A1A2AkB形式(2)前提:A1,A2,Ak结论:B推理正确记作A1A2AkB判断推理是否正确的方法:真值表法等值演算法主析取范式法构造证明法,课件,4,实例,例1判断下面推理是否正确:(1)若今天是1号,则明天是5号.今天是1号.所以,明天是5号.解设p:今天是1号,q:明天是5号推理的形式结构为(pq)pq证明用等值演算法(pq)pq(pq)p)q(pq)p)qpqq1得证推理正确,课件,5,实例(续),(2)若今天是1号,则明天是5号.明天是5号.所以,今天是1号.解设p:今天是1号,q:明天是5号.推理的形式结构为(pq)qp证明用主析取范式法(pq)qp(pq)qp(pq)q)pqp(pq)(pq)(pq)(pq)m0m2m301是成假赋值,所以推理不正确.,课件,6,推理定律重言蕴涵式,A(AB)附加律(AB)A化简律(AB)AB假言推理(AB)BA拒取式(AB)BA析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B构造性二难(特殊形式)(AB)(CD)(BD)(AC)破坏性二难,课件,7,自然推理系统P,自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,pi,qi,ri,(2)联结词:,(3)括号与逗号:(),2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则,课件,8,自然推理系统P(续),课件,9,自然推理系统P(续),课件,10,直接证明法,例2在自然推理系统P中构造下面推理的证明:前提:pq,qr,ps,s结论:r(pq)证明ps前提引入s前提引入p拒取式pq前提引入q析取三段论qr前提引入r假言推理r(pq)合取推理正确,r(pq)是有效结论,课件,11,实例,例3构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一和星期三.解设p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(pq)r,rs,s结论:pq,课件,12,实例(续),前提:(pq)r,rs,s结论:pq证明rs前提引入s前提引入r拒取式(pq)r前提引入(pq)拒取式pq置换结论有效,即明天不是星期一和星期三,课件,13,附加前提证明法,欲证明等价地证明前提:A1,A2,Ak前提:A1,A2,Ak,C结论:CB结论:B,理由:(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B,课件,14,实例,例4构造下面推理的证明:前提:pq,qr,rs结论:ps证明p附加前提引入pq前提引入q析取三段论qr前提引入r析取三段论rs前提引入s假言推理推理正确,ps是有效结论,课件,15,归谬法(反证法),欲证明前提：A1,A2,Ak结论：B将B加入前提,若推出矛盾,则得证推理正确.,理由:A1A2AkB(A1A2Ak)B(A1A2AkB)括号内部为矛盾式当且仅当(A1A2AkB)为重言式,课件,16,实例,例5构造下面推理的证明前提:(pq)r,rs,s,p结论:q证明用归缪法q结论否定引入rs前提引入s前提引入r拒取式,课件,17,实例(续),(pq)r前提引入(pq)析取三段论pq置换p析取三段论p前提引入pp合取推理正确,q是有效结论,课件,18,归结证明法,理由(pq)(pr)(qr)(pq)(pr)(qr)(pq)(pr)qr(pq)q)(pr)r)(pq)(pr)1,课件,19,归结证明法(续),在自然推理系统P中只需下述推理规则:(1)前提引入规则(2)结论引入规则(3)置换规则(4)化简规则(5)合取引入规则(6)归结规则,课件,20,归结证明法的基本步骤,1.将每一个前提化成等值的合取范式,设所有合取范式的全部简单析取式为A1,A2,At2.将结论化成等值的合取范式B1B2Bs,其中每个Bj是简单析取式3.以A1,A2,At为前提,使用归结规则推出每一个Bj,1js4.由合取引入规则得到结论B1B2Bs,课件,21,实例,例6用归结证明法构造下面推理的证明:前提:(pq)r,rs,s结论:(pq)(ps)解(pq)r(pq)r(pq)r(pr)(qr)rsrs(pq)(ps)(pq)(ps)(pq)(ps)p(qs)推理可表成前提:pr,qr,rs,s结论:p(qs),课件,22,实例(续),前提:pr,qr,rs,s结论:p(qs)证明qr前提引入rs前提引入qs归结s前提引入s0置换r0归结pr前提引入p0归结p置换p(qs)合取引入,课件,23,实例：公安