逻辑学 第六讲：命题逻辑的自然演绎系统三四节

1、第三节：条件证明规则第四节：间接证明规则规则概述规则应用第六讲：命题逻辑的自然演绎系统概论第三节：条件证明规则（一）条件证明规则概述AB /AAB 该推论的有效性可以用真值表方法予以验证。 我们引如一条新的推演规则，即条件证明规则（条件证明规则（PA-CP）：）： 如果从前提PR和假设P推出Q，那么，仅从前提PR可以推得PQ。 PR 前提 P 假设 Q 由PR或P推得的命题 PQ 结论假设域 （1）AB PR （2）A PA-CP （3）A （2），DN （4）B （1）、（3）， （5）AB （2）、（4） （6）AAB （2）（5），CP 条件证明规则与其它规则相比，它的最大特点在于，先引

2、入先引入假设然后撤出假设。假设然后撤出假设。 显然，条件证明规则实际上就是对移出律的运用条件证明规则实际上就是对移出律的运用。 在证明过程中，无论增加多少前提，都必须撤出，而撤出的在证明过程中，无论增加多少前提，都必须撤出，而撤出的目的在于保证结论仅由前提得出的。目的在于保证结论仅由前提得出的。 由条件证明所得的结论一定是蕴涵式，可见，条件证明规则最适合那些结论为蕴涵式的推论。（二）条件证明规则的应用 例1： PQRP /QR （证明略） 例2： P（QS）RP Q /RS （证明如下） 证明： （1）P（QS） PR （2）RP PR （3） Q PR （4）R PA-CP （5）R （4）

3、，DN （6）P （2）、（5）， （7）QS （1）、（6），MP （8）S （3）、（7），MP （9）RS （4）（8），CP 证毕 证明过程中局部使用条件证明规则。 需要注意的是，假设一旦被撤出，假设域内的任何一行都不假设一旦被撤出，假设域内的任何一行都不能再被使用，否则，就不能保证结论独立于假设。能再被使用，否则，就不能保证结论独立于假设。 例3： 如果外出忘记锁门则家里被盗，那么社会秩序不好；或者家里被盗或者安心工作；然而，如果外出忘记锁门，那么不安心工作；所以，社会秩序不好。 P：外出忘记锁门 Q：家里被盗 R：社会秩序好 S：安心工作（PQ）RQSPS /R 证明： （1）（P

4、Q）R PR （2）QS PR （3） PS PR （4）P PA-CP （5）S （3）、（4），MP （6）Q （2）、（5）， （7）PQ （4）（6），CP （8）R （1）、（7），MP 证毕 有的推论的证明只需一次使用条件证明规则，但是有的却需要多次使用条件证明规则。 例4： P（QR）R Q（PS） /PQ 例5： ABC CDE /A（DEC） （例4，结论： PQ ）证明：（1）P（QR） PR（2）R PR（3）Q（PS） PR （4）P PA-CP（5）QR （1）、（4），MP（6）Q （2）、（5），MT（7）PQ （4）（6），CP（8）Q PA-CP（9）PS （

5、3）、（8），（10）P （9），（11）QP （8）（10），CP（12）（PQ）（QP） （7）、（11），（13）PQ （12），Ep证毕例5，结论： A（DEC） 证明：（1）ABC PR（2）CDE PR（3）A PA-CP（4）D PA-CP（5）AB （3），（6）C （1）、（5），MP（7）CD （4）、（6），（8）E （2）、（7），MP（9）EC （6）、（8），（10）DEC （4）（9），CP（11）A（DEC） （3）（10），CP证毕条件证明规则小结： 一般来说，使用条件证明规则的推论具有如下形式：P1（P2（Pn Q） 那么，我们可以把P1，P2 ， Pn这n

6、个前件依次作为假设；由这些假设和前提PR推出Q后，再按相反的次序依次撤除它们。 PR 前提 P1 条件假设 P2 条件假设 Pn 条件假设 Q 由前提或假设推出 PnQ 条件证明 P2（PnQ） 条件证明 P1（P2（PnQ）结论第四节：间接证明规则（一）间接证明规则概述 间接证明又叫做归谬证明或反证法（间接证明又叫做归谬证明或反证法（PA-RAA）。）。 当我们要证明某一定理时，先引入该定理的否定为假设，然先引入该定理的否定为假设，然后由这一假设推出矛盾。由于矛盾是不可能的，所以假设一后由这一假设推出矛盾。由于矛盾是不可能的，所以假设一定错误，即该定理的否定不成立，由此就间接证明了该定理定错

7、误，即该定理的否定不成立，由此就间接证明了该定理成立。成立。 间接证明规则可以表达为如下模式： PR 前提 P 假设 AA 由前提或假设推出的逻辑矛盾 P 结论 所谓的逻辑矛盾，主要有以下这些：所谓的逻辑矛盾，主要有以下这些： 1，推出的结果与已知条件矛盾。 2，推出的结果与已知定义矛盾。 3，推出的结果与已知公理矛盾。 4，推出的结果与已知定理矛盾。 5，推出的结果与所做假设矛盾。 6，推出两个互相矛盾的结果。 一般来说，如下类型的待证命题更适合采用间接证明规则：一般来说，如下类型的待证命题更适合采用间接证明规则： 1，某些初始命题。 2，否定性命题。 3，以简单命题为结论的命题。 4，结论

8、与前提没有关系，结论是重言式的命题。（二）间接证明规则应用例1 （证明略）PQR（RS）PT /TS例2 （证明略）P（QR）RP /QR例3：PQ（DP）（QR）P /（P（DR）例4：PQRS（PTR ）（IRS） /（IT）证明：（1）PQ（DP） PR（2）（QR）P PR （3）P（DR） PA-RAA（4）P （3），（5）P （4），DN（6）（QR） （2）、（5），MT（7）QR （6），Impl、DeM（8）Q （7），（9）PQ （4）、（8），（10）DP （1）、（9），MP（11）R （7），（12）DR （3），（13）D （11）、（12），（14）P （10）

9、、（13），MP（15）PP （4）、（14）， （16） （P（DR） （3）（15），RAA证毕证明：（1）PQR PR（2）S PR（3） （PTR ）（IRS） PR（4） （IT） PA-RAA（5） IT （4），DN（6）P PA-CP（7）PQ （6），（8）R （1）、（7），MP（9）T （5），（10）TR （8）、（9），（11） PTR （6）（10），CP（12） IRS （3）、（11），MP（13）I （5），（14） RS （12）、（13），MP（15）S （14）， （16）SS （2）、（15）， （17） （IT） （4）（16）RAA证毕 补充材料一

10、：证明重言式证明重言式 有一种命题的真是无条件的，不依赖于其它命题。这样的命题就是重言式。 1，用条件证明方法证明重言式。，用条件证明方法证明重言式。 例：证明A（BA）是重言式。 2，用间接证明方法证明重言式。，用间接证明方法证明重言式。 例：证明A（AB）是重言式。 重言式的形式证明相当于一个只有结论而没有前提的推理的重言式的形式证明相当于一个只有结论而没有前提的推理的有效性。有效性。 补充材料二：无效推理的证明无效推理的证明 如果推理无效，那么运用推理规则不可能从前提推演出结论。这意味着形式证明方法不能证明推理是无效的。 1，用真值表证明推理是无效的。，用真值表证明推理是无效的。 如果一

11、个推理是无效的，至少存在一组赋值使得推理的前提真而结论假。 例：用真值表判定下列推理是否有效：C（AB），AC /BC 2，用归谬赋值法证明推理的有效或无效。，用归谬赋值法证明推理的有效或无效。 归谬赋值法的基本思路同间接证明方法类似。我们要证明一个推理是有效的，先假设它无效，这就是归谬。 例：判定下列推理是否有效：A（BC），（CD）F /AF 3，证明公式集合的协调性。，证明公式集合的协调性。（附录）练习题： 一，用条件证明规则构造以下推论： 1，JK /JJK 2，ZCB，QB /ZQ 3，P（QR），P（RQ） /P（QR） 二，使用间接证明构造以下推论： 1，PQ，PQ /P 2，FN，NBJ，BFD /D 3，PR，QS，PQ /RS思考题： 根据你的总结，完成一个形式证明还有哪些策略和技巧？本讲小结第六讲