第五讲 命题逻辑(下)

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