第五讲命题逻辑下

第五讲命题逻辑下第一页，共四十三页，编辑于2023年，星期四一、基本推导规则1组合规则（∧+）

pq∴p∧q

2简化规则（∧-）

p∧q∴p第二页，共四十三页，编辑于2023年，星期四3假言三段论（∨-）

p∨qp∴q4附加规则（∨+）

p∴p∨q第三页，共四十三页，编辑于2023年，星期四5分离规则（MP）

p→qp∴q

6逆分离规则（MT）

p→qq∴p第四页，共四十三页，编辑于2023年，星期四7假言三段论（HS）

p→qq→r∴p→r8二难推理（CD）(p→q)∧(r→s)p∨r∴q∨s第五页，共四十三页，编辑于2023年，星期四等值替换规则9、交换律（COM）

(p∧q)(q∧p)(p∨q)(q∨p)

10、结合律（Ass）((p∧q)∧r)(p∧(q∧r))((p∧q)∧r)(p∧(q∧r))第六页，共四十三页，编辑于2023年，星期四11、德摩根律

（DeM）

(p∧q)(p∨q)(p∨q)(p∧q)

12、分配律（Dist）(p∧(q∨r))((p∧q)∨(p∧r))(p∨(q∧r))((p∨q)∧(p∨r))第七页，共四十三页，编辑于2023年，星期四13、实质蕴涵（Impl）

(p→q)(p∨q)

14、假言易位（Tran）(p→q)

(q→p)第八页，共四十三页，编辑于2023年，星期四15、移出律（Esp）

((p∧q)→r)(p→(q→r))16、实质等值（Equi）

(pq)((p→q)∧(q→p))第九页，共四十三页，编辑于2023年，星期四17双否律（DN）p

p

18重言律

（Taut）

p(p∧p)p(p∨p)第十页，共四十三页，编辑于2023年，星期四2．2有效推理的形式证明

在命题演算系统中对推理有效性的证明称作形式证明。形式证明的定义一个形式证明是一个命题公式序列A1，A2，…，An。其中的任一Ai（1≤i≤n）或者是前提，或者是由前面的公式根据推理规则得到的。序列的最后一个公式An恰好是结论。第十一页，共四十三页，编辑于2023年，星期四例3如果他主张减轻农民的税负，他将赢得农民的支持。如果他主张政府增加对社会福利的投入，他将赢得工人的支持。如果他既赢得农民的支持又赢得工人的支持，他就肯定能当选。但是他没有当选。所以，或者他不主张减轻农民的税负，或者不主张政府增加对社会福利的投入。第十二页，共四十三页，编辑于2023年，星期四①A→B

P②C→D

P③（B∧D）→E

P④E

P\∴A∨C⑤（B∧D）③④MT⑥B∨D⑤DeM⑦（A→B）∧（C→D）①②∧+⑧（B→A）∧(D→C)⑦Tran⑨A∨C⑥⑧CD第十三页，共四十三页，编辑于2023年，星期四2．4条件证明规则C.P为什么要引入C.P?例如下列推理

A→（B→C）∴（A→B）→（A→C）第十四页，共四十三页，编辑于2023年，星期四条件证明规则的根据?有效推理的逻辑特征是：前提真时结论必真，不存在有使其前提真而结论假的例示。

蕴涵式的逻辑特征:就不可能前件真而后件假，即前提真时结论必真。第十五页，共四十三页，编辑于2023年，星期四如果我们以有效推理的前提的合取为前件，结论为后件就能得到一个蕴涵式。这个蕴涵式是个重言式当且仅当这个推理形式是有效的。

第十六页，共四十三页，编辑于2023年，星期四移出律Exp：((p∧q)→r)(p→(q→r))

(p∧q)→r对应于

p

•

•

•

q∴rp→(q→r)对应于

p

•

•

•

∴q→r

第十七页，共四十三页，编辑于2023年，星期四这两个推理式有何区别？命题公式“q”在左边的推理式中是前提，而在边的推理式中是结论的构成部分。就是说，右边的推理式比左边的少了一个前提“q”，并且它们有不同的结论：左边推理式的结论是“r”，右边推理式的则是“q→r”，“q”从前提中消去而变成了结论的前件。第十八页，共四十三页，编辑于2023年，星期四结论：由于两个蕴涵式是逻辑等值的，即如果一个是重言式，另一个也必是；一个不是重言式，另一个也必不是。因此这两个推理式是等价的。条件证明规则C.Pp

•

•q∴p→q第十九页，共四十三页，编辑于2023年，星期四例4A→（B→C）\∴（A→B）→（A→C）解：①A→（B→C）P②（A∧B）→C①Exp③（B∧A）→C②Com④B→（A→C）③Exp ⑤A→B⑥A→（A→C）④⑤HS⑦（A∧A）→C⑥Exp⑧A→C⑦Taut⑨（A→B）→（A→C）⑤-⑧C•P第二十页，共四十三页，编辑于2023年，星期四我们在引入附加前提⑤的同时就用线段标明了这个附加前提的辖域。

注意：凡引入附加前提必须标明该前提的辖域。而辖域没有封闭，证明就不能结束，因为这时推演出的公式还依赖于附加前提，即依赖于给定前提之外的东西。

第二十一页，共四十三页，编辑于2023年，星期四A→（B∧D）

B→（（C→（C∨E））→F）/∴A→F

解：①A→（B∧D）P②B→（（C→（C∨E））→F）P③A④B∧D①③MP⑤B④∧-⑥（C→（C∨E））→F②⑤MP⑦C⑧C∨E⑦∨+⑨C→（C∨E）⑥-⑦C•P⑩F⑥⑨MP⑾A→F③-⑩C•P第二十二页，共四十三页，编辑于2023年，星期四2．5间接证明规则RAA原理：间接证明又叫做归谬证明或反证法。在数学定理的证明过程中，先引入该定理的否定为假设。然后由这一假设推导出矛盾。由于矛盾是不可能的，假设一定错误，即该定理的否定不成立。由此就间接地证明了该定理成立。第二十三页，共四十三页，编辑于2023年，星期四启发：当我们为一有效推理建立形式证明时，不是直接去证明由前提推演出结论，而是将结论的否定作为一个补充前提引入形式证明。然后由扩充的前提集合推演出一个矛盾：即演出一个形式为“p∧p”的命题公式。由这个矛盾我们实际上推演出对这个补充前提的否定，即对结论的否定的否定，再根据双否律DN，就相当于推演出结论。第二十四页，共四十三页，编辑于2023年，星期四

A→（B∧C）

（B∨D）→E

D∨A/∴E

解⑴A→（B∧C）P⑵（B∨D）→EP⑶D∨AP/∴E⑷ERAA⑸（B∨D）⑵⑷MT⑹B∧D⑸DeM⑺D⑹COM，∧-⑻A⑶⑺∨-⑼B∧C⑴⑻MP⑽B⑼∧-⑾B⑹∧-⑿B∧B⑽⑾∧+第二十五页，共四十三页，编辑于2023年，星期四2．6间接证明方法的应用——证明重言式有一种命题的真是无条件的，不依赖于其它命题。这样的命题就是重言式。形式证明同样适用于证明重言式。可以证明重言式是不需要任何前提就可以推演出的命题。第二十六页，共四十三页，编辑于2023年，星期四证明重言式不需要任何前提，但建立形式证明需要有出发点。这意味着我们只能用条件证明或者间接证明的方法来证明重言式，因为只有这两种方法可以引入假设前提。我们以假设前提为出发点就能建立重言式的形式证明。第二十七页，共四十三页，编辑于2023年，星期四证明A→（B→A）是重言式。证：①A ②A∨B①∨+③B∨A②Com④B→A③Impl⑤A→(B→A)①-④C•P第二十八页，共四十三页，编辑于2023年，星期四证明（（p→q）∧p）→q是个重言式。证：①（p→q）∧p②p→q①∧-③p①Com,∧-④q②③MP⑤（（p→q）∧p）→q①-④C•P第二十九页，共四十三页，编辑于2023年，星期四证明A→（A∨B）是重言式。

证：①（A→（A∨B））②（A∨（A∨B））①Impl③A∧（A∨B）②DeM④A∧（A∧B）③DeM⑤（A∧A）∧B④Ass⑦A∧A⑤∧-第三十页，共四十三页，编辑于2023年，星期四第三节无效推理的证明

命题逻辑具有可判定性.问题:形式证明能否证明无效推理?3．1用真值表证明推理的无效性第三十一页，共四十三页，编辑于2023年，星期四思路:如果一个推理是无效的，其前提真时结论可真可假。因此只要在真值表上找到一组变元的赋值使得前提真而结论假，那么推理就是无效的。第三十二页，共四十三页，编辑于2023年，星期四C→（A∧B），A∨C/∴B→C证：给出相应的真值表：ABCA∧BC→（A∧B）A∨CB→CTTTTTTTTTFTTTFTFTFFTTTFFFTTTFTTFFTTFTFFTFFFFTFFTTFFFFFFT第三十三页，共四十三页，编辑于2023年，星期四例11判定如下推理是否有效：如果水稻长得好，那么水分充足并且肥料充足。只要风调雨顺，这块地就水分充足。所以，只要风调雨顺，那么如果这块地肥料充足水稻就长得好。证：A→（B∧C）

D→B∴D→（C→A）第三十四页，共四十三页，编辑于2023年，星期四只要找到一组对变元的赋值，使得推理的前提真而结论假，就足以证明该推理是无效的。现将这组赋列举如下：ABCDA→（B∧C）D→BD→（C→A）FTTT

TTF第三十五页，共四十三页，编辑于2023年，星期四上述简化真值表方法通过列出一组赋值，使得推理前提真而结论假，简洁清晰地证明了推理的无效性。但这种方法只适用于无效推理，它不能说明推理的有效性。

3．2用归谬赋值法证明推理的有效或无效性第三十六页，共四十三页，编辑于2023年，星期四思路:归谬赋值法的基本思路同间接证明方法类似。我们要证明一个推理是有效的，先假设它无效，这就是归谬。然后根据假设对前提和结论进行赋值，即给命题公式的变元指派确定的真值，以使得推理的前提真而结论假。

第三十七页，共四十三页，编辑于2023年，星期四如果找到这样一组的赋值使得假设成立，那么就说明推理是无效的。我们可以运用上述简化真值表方法把这一组赋值列出来，以证明推理的无效性。如果找不到使假设成立的赋值，那么就说明假设不成立，推理是有效的。所谓找不到使假设成立的赋值是指，根据假设对前提和结论赋值必将导致矛盾，即不可避免地要对同一个变元既赋值T又赋值F。第三十八页，共四十三页，编辑于202