第五讲命题逻辑下优秀PPT.ppt

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