第五讲命题逻辑下推选优秀ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五(d w)讲命题逻辑下,第一页，共43页。,一、基本推导(tudo)规则,1 组合(zh)规则（+）,p,q,pq,2 简化(jinhu)规则（-）,pq,p,第二页，共43页。,3 假言(ji yn)三段论（-）,pq,p,q,4 附加(fji)规则（+）,p,pq,第三页，共43页。,5 分离(fnl)规则（MP）,pq,p,q,6 逆分离(fnl)规则（MT）,pq,q,p,第四页，共43页。,7 假言(ji yn)三段论（HS）,pq,qr,pr,8 二难(r nn)推理（CD）,(pq)(rs),pr,q s,第五页，共43页。,等值替换(t hun)规则,9,、交换律（,COM,）,(pq),(qp),(pq),(qp),10,、结合律（,Ass,）,(pq)r),(p(qr),(pq)r),(p(qr),第六页，共43页。,11,、德摩根律,（,DeM,）,(pq),(,p,q),(pq),(,p,q),12,、分配律（,Dist,）,(p(qr),(pq)(pr),(p(qr),(pq)(pr),第七页，共43页。,13、实质(shzh)蕴涵（Impl）,(pq)(pq),14、假言(ji yn)易位（Tran）,(pq),(q p),第八页，共43页。,15,、移出律（,Esp,）,(,(pq)r),(p(qr),16、实质(shzh)等值（Equi）,(pq)(pq)(qp),第九页，共43页。,17,双否律（,DN,）,p,p,18,重言律,（,Taut,）,p,(pp),p,(pp),第十页，共43页。,22 有效推理的形式(xngsh)证明,在命题演算系统中对推理有效性的证明称作形式证明。,形式证明的定义 一个形式证明是一个命题公式序列A1，A2，An。其中的任一Ai（1in）或者是前提，或者是由前面的公式根据推理规则(guz)得到的。序列的最后一个公式An恰好是结论。,第十一页，共43页。,例3 如果他主张减轻农民的税负，他将赢得农民的支持。如果他主张政府增加对社会福利的投入(tur)，他将赢得工人的支持。如果他既赢得农民的支持又赢得工人的支持，他就肯定能当选。但是他没有当选。所以，或者他不主张减轻农民的税负，或者不主张政府增加对社会福利的投入(tur)。,第十二页，共43页。,AB,P,CD,P,（,BD,）,E,P,E,P ,A,C,（,BD,）,MT,B,D,DeM,（,AB,）（,CD,）,+,（,B,A,）,(,D,C),Tran,A,C,CD,第十三页，共43页。,24 条件证明(zhngmng)规则,为什么要引入C.P?,例如下列(xili)推理,A（BC）,（AB）（AC）,第十四页，共43页。,条件证明(zhngmng)规则的根据?,有效推理的逻辑特征(tzhng)是：前提真时结论必真，不存在有使其前提真而结论假的例示。,蕴涵式的逻辑特征(tzhng):就不可能前件真而后件假，即前提真时结论必真。,第十五页，共43页。,如果我们以有效推理的前提的合取为前件(qin jin)，结论为后件就能得到一个蕴涵式。,这个蕴涵式是个重言式当且仅当这个推理形式是有效的。,第十六页，共43页。,移出律,Exp,：,(,(pq)r),(p(qr),(pq)r 对应(duyng)于,p,q,r,p(qr)对应(duyng)于,p,qr,第十七页，共43页。,这两个(lin)推理式有何区别？,命题公式“q”在左边的推理式中是前提，而在边的推理式中是结论的构成部分。就是说，右边的推理式比左边的少了一个前提“q”，并且(bngqi)它们有不同的结论：左边推理式的结论是“r”，右边推理式的则是“qr”，“q”从前提中消去而变成了结论的前件。,第十八页，共43页。,结论(jiln)：,由于(yuy)两个蕴涵式是逻辑等值的，即如果一个是重言式，另一个也必是；一个不是重言式，另一个也必不是。因此这两个推理式是等价的。,条件证明(zhngmng)规则C.P,p,q,pq,第十九页，共43页。,等值替换(t hun)规则,第三十八页，共43页。,证：先假定公式集合(jh)的每个元素为真，然后根据假设进行赋值：,AF -CP,A B C D E A（BC）（BD）E AE,BA Com,如果找不到使假设成立的赋值，那么就说明假设不成立，推理是有效的。,33 证明(zhngmng)公式集合的协调性,然后由这一假设推导(tudo)出矛盾。,F F T F F T T,我们以假设前提为出发点就能建立重言式的形式证明。,例,4 A,（,BC,）,（,AB,）（,AC,）,解：,A,（,BC,）,P,（,AB,）,C Exp,（,BA,）,C Com,B,（,AC,）,Exp,AB,A,（,AC,）,HS,（,AA,）,C Exp,AC Taut,（,AB,）（,AC,）,-C,P,第二十页，共43页。,我们在引入附加前提的同时就用线段标明(biomng)了这个附加前提的辖域。,注意：凡引入附加前提必须标明(biomng)该前提的辖域。而辖域没有封闭，证明就不能结束，因为这时推演出的公式还依赖于附加前提，即依赖于给定前提之外的东西。,第二十一页，共43页。,A,（,BD,）,B,（,C,（,CE,）,F,）,/AF,解：,A,（,BD,）,P,B,（,C,（,CE,）,F,）,P,A,BD MP,B -,（,C,（,CE,）,F MP,C,CE +,C,（,CE,）,-C,P,F MP,AF -C,P,第二十二页，共43页。,25 间接(jin ji)证明规则RAA,原理：间接证明又叫做归谬证明或反证法。在数学定理的证明过程中，先引入该定理的否定为假设。然后由这一假设推导(tudo)出矛盾。由于矛盾是不可能的，假设一定错误，即该定理的否定不成立。由此就间接地证明了该定理成立。,第二十三页，共43页。,启发：当我们为一有效推理建立形式证明时，不是直接去证明由前提推演出结论，而是将结论的否定作为一个补充(bchng)前提引入形式证明。然后由扩充的前提集合推演出一个矛盾：即演出一个形式为“pp”的命题公式。由这个矛盾我们实际上推演出对这个补充(bchng)前提的否定，即对结论的否定的否定，再根据双否律DN，就相当于推演出结论。,第二十四页，共43页。,A,（,BC,）（,BD,）,EDA /E,解 ,A,（,BC,）,P,（,BD,）,E P,DA P/E,E RAA,（,BD,）,MT,B,D DeM,D COM,，,-,A -,BC MP,B -,B -,B,B +,第二十五页，共43页。,26 间接证明(zhngmng)方法的应用证明(zhngmng)重言式,有一种命题的真是无条件的，不依赖于其它命题。这样的命题就是重言式。形式(xngsh)证明同样适用于证明重言式。可以证明重言式是不需要任何前提就可以推演出的命题。,第二十六页，共43页。,证明重言式不需要(xyo)任何前提，但建立形式证明需要(xyo)有出发点。这意味着我们只能用条件证明或者间接证明的方法来证明重言式，因为只有这两种方法可以引入假设前提。我们以假设前提为出发点就能建立重言式的形式证明。,第二十七页，共43页。,证明(zhngmng)A（BA）是重言式。,证：,A,A,B +,BA Com,BA Impl,A(BA)-C,P,第二十八页，共43页。,（pq）p）q -CP,第四十二页，共43页。,我们可以运用上述简化真值表方法(fngf)把这一组赋值列出来，以证明推理的无效性。,证明重言式不需要(xyo)任何前提，但建立形式证明需要(xyo)有出发点。,A（BD）B（C（CE）F）/AF,10、结合律（Ass）,因此这两个推理式是等价的。,归谬赋值法的基本思路同间接证明方法类似。,（BD）MT,12、分配律（Dist）,AB +,如果他既赢得农民的支持又赢得工人的支持，他就肯定能当选。,31 用真值表证明推理的无效性,这两个(lin)推理式有何区别？,例如下列(xili)推理,证明(zhngmng)（pq）p）q是个重言式。,证：（,pq,）,p,pq -,p Com,-,q MP,（,pq,）,p,）,q -C,P,第二十九页，共43页。,证明(zhngmng)A（AB）是重言式。,证：,（,A,（,AB,）,（,A,（,AB,）,Impl,A,（,AB,）,DeM,A,（,A,B,）,DeM,（,A,A,）,B Ass,A,A -,第三十页，共43页。,第三节 无效(wxio)推理的证明,命题逻辑具有(jyu)可判定性.,问题:形式证明能否证明无效推理?,31 用真值表证明推理的无效性,第三十一页，共43页。,思路:,如果一个推理是无效的，其前提真时结论可真可假。因此只要(zhyo)在真值表上找到一组变元的赋值使得前提真而结论假，那么推理就是无效的。,第三十二页，共43页。,C（AB），AC /BC,证：给出相应(xingyng)的真值表：,A B C AB C（AB）AC BC,T T T T T T T,T T F T T T F,T F T F F T T,T F F F T T T,F T T F F T T,F T F F T F F,F F T F F T T,F F F F F F T,第三十三页，共43页。,例11 判定如下推理是否有效：,如果水稻长得好，那么水分(shufn)充足并且肥料充足。只要风调雨顺，这块地就水分(shufn)充足。所以，只要风调雨顺，那么如果这块地肥料充足水稻就长得好。,证：A（BC）,DB,D（CA）,第三十四页，共43页。,只要找到一组对变元的赋值，使得推理的前提(qint)真而结论假，就足以证明该推理是无效的。现将这组赋列举如下：,A B C D A（BC）DB D（CA）,F T T T T T F,第三十五页，共43页。,上述简化真值表方法通过列出一组赋值，使得推理前提真而结论假，简洁清晰地证明(zhngmng)了推理的无效性。但这种方法只适用于无效推理，它不能说明推理的有效性。,32 用归谬赋值法证明(zhngmng)推理的有效或无效性,第三十六页，共43页。,思路:,归谬赋值法的基本思路同间接证明方法类似。我们要证明一个推理是有效(yuxio)的，先假设它无效，这就是归谬。然后根据假设对前提和结论进行赋值，即给命题公式的变元指派确定的真值，以使得推理的前提真而结论假。,第三十七页，共43页。,如果找到这样一组的赋值使得假设成立，那么就说明推理是无效的。我们可以运用上述简化真值表方法(fngf)把这一组赋值列出来，以证明推理的无效性。,如果找不到使假设成立的赋值，那么就说明假设不成立，推理是有效的。所谓找不到使假设成立的赋值是指，根据假设对前提和结论赋值必将导致矛盾，即不可避免地要对同一个变元既赋值T又赋值F。,第三十八页，共43页。,例12 判定下列(xili)推理是否有效：,A（BC）,（CD）F,AF,第三十九页，共43页。,33 证明(zhngmng)公式集合的协调性,思路:,一个公式集合的协调性也就是无矛盾性。一个命题公式集合是协调的，当且仅当，存在一组赋值使得(sh de)该集合的每个公式都真。因此，只要把这样一组赋值列出来，就证明了公式集合的协调性。,第四十页，共43页。,例13 证明公式集合A（BC），（BD）E，AE是协调(xitio)的。,证：从如下简化真值表可见，该公式