《命题逻辑中几种常见的推理证明方法》由会员分享，可在线阅读，更多相关《命题逻辑中几种常见的推理证明方法（6页珍藏版）》请在金锄头文库上搜索。
1、ljlj逻辑学论文数学科学学院09 级 3 班吴洁琼学号 2009040288命题逻辑中几种常见的推理证明方法吴洁琼哈尔滨师范大学（黑龙江哈尔滨 150025）【摘 要】：命题逻辑的推理证明是离散数学课程的重点难点内容，其主要原因有两个：一是内容比较抽象且方法较独特，其灵活性很大, 故很难掌握；二是题型以证明题居多, 大多数题的知识面涉及较广, 故习题较难。而命题逻辑又是数理逻辑的基础, 熟练而灵活地掌握好命题逻辑中推理证明的方法既是学习命题逻辑的重点, 又会为进一步学习谓词逻辑打下良好的基础。本文结合适当的例题讲解，总结了命题逻辑中几种常见的推理证明方法，并进行了分析和探讨,以加深学生的理解
2、，以及知识的灵活使用。 以期在帮助学生掌握命题逻辑的推理证明方法的同时, 又能对学生进行逻辑思维能力的训练,培养学生分析问题和解决问题的能力。【关键词】：命题逻辑；推理；证明方法数理逻辑是离散数学课程的主要内容之一，它主要包括命题逻辑和谓词逻辑两大部分, 而命题逻辑又是谓词逻辑的基础,其中的内容也比较抽象，所以学好命题逻辑又是学好数理逻辑的关键。学好数理逻辑既能加强学生的逻辑思维能力，又同时能够帮助同学学习数字电路和人工智能等其它课程。数理逻辑中关于命题逻辑证明题比较多，学好数理逻辑的关键是能不能很好的掌握这些证明题。一、命题逻辑中推理的相关概念定义1：一个命题公式序列 ， ， ， ； ，即
3、称为12 n)(21n推理形式，其中序列最后一项 称为推理的结论， ， ， ， 称为推理的条件。12定义2：对于命题公式序列 ， ， ， ； 的命题变元组 的12 n );,(21ppn任意指派 存在使 为真，而 为假，则称此推理为无效推理，);,(21ttn 否则是有效推理。证明命题公式 为有效结论的过程就是命题逻辑推理证明的过程。而证明推理形式 ， 1， ， ； 是有效的充要条件是 为重言式。2 n )(21n二、常见证明方法命题逻辑的推理证明有六种常用证明方法，分别是直接证明法，真值表法,范式法，间接证明法。其中间接证明法里面常见的是CP规则证明法和反证法，本文就这几种方法进行论述。 1
4、、直接证明法直接证明法就是由一组前提，利用一些公认的推理规则，根据已知的等价或者蕴含公式，推演得到有效的结论。在学生熟悉了逻辑恒等式和常用的推理规则后，大多数证明题都可以用直接证明法方便证明出。例1、用直接证明法证明 ， ， 推导出 .)(qp)(r)(sqr分析：本题目需要证明的结论是个析取式可以用过蕴含表达式转换为蕴含式，即 ，所以本题实际只要推导出 为真即可得证。rss具体证明过程如下：证明：(1) 前提qp(2) (1)置换(3) 前提s(4) (2)、(3) 假言三段论p(5) (4)置换s(6) 前提r(7) (5)、 （6)假言三段论s(8) (7)置换r2、真值表法 推理是从条
5、件推出结论的过程, 条件是已知的命题公式, 结论是从前提出发应用推理规则推出的命题公式. 由于判断推理正确的方法就是判断重言蕴含式的方法, 因此可用真值表去判断推理是否正确的问题.例2、证明逻辑等价式 )()()( rpqrqp证明逻辑等价式是有两种方法，一种是真值表法，一种是利用逻辑等价式替换，这里就介绍用真值表法来证明。 的真值表如下：)()()(P q r qr p(qr) pq pr (pq)(pr)1 1 11 1 01 0 11 0 00 1 10 1 01011101011111100111010111011110 0 10 0 01111111111显然, 不论p 、q 、r
6、的真假情况怎样,p(qr)总是和(pq)(pr)的真假相同，所以有 。)()()( rp3、范式法析取范式和合取范式是命题公式的两种等价形式, 在等价的意义下, 任何一个命题公式都有唯一的一个析取范式和一个合取范式, 析取范式和合取范式可以用于判断某个命题公式是否为重言式或矛盾式。而证明某个推理形式是有效的充要条件是这个推理形式为重言式。所以我们可以把这种唯一的范式形式用于推理论证中, 去证明一些命题公式。例3、证明 .)()()( rprqp证：即判断 是否为重言式。先求合取范式： )()()( rprqp )()(rpq)()()()( rpqr)()rpqrppq 得到的结果中，四个合取
7、项都为重言式，从而该命题公式为重言式，得证。4、CP规则法CP规则的内容：前提是 , , , ，欲证明结论 成立（结论是条件式） ，1H2 nSR则将条件式作为附加前提证得 即可。设 ,由前提 证明 ，SnH21 SR即证明 永真，而 等价于 ，因此证明)(RH)(SR永真即可。S这种证明方法比较适用于证明结论中带有蕴含连接词，也就是说结论是形如 的qp命题公式，用CP规则证明可能比较简便。再复杂的结论如形如 的命题公式，)(rqp也可以通过连续使用两次CP规则的方式来证明。例4、证明 .rsqpsrqp)()(证：（1） 附加前提s（2） 前提（3） （1） （2）否析规则p （4） 前提)
8、(rqp（5） （3） （4）分离规则（6） 前提（7） （5） （6）分离规则 r（8） CP规则s4、反证法反证法是一种间接证明问题的方法。由反证法推理规则 可知，直psp)(接证 困难时，可改证 ，也就是假定 不真，设法推出矛盾，从而肯定 ，p)(sp这就是反证法。它的步骤：（1）否定结论；（2）找出矛盾；（3）肯定题设。例5、用反证法证明 .pq)(分析：用反证法证明首先要假设结论部分命题公式的否定为真，并作为附加前提，在证明过程证得到任意形式的两个互相矛盾的命题公式证明即结束。具体证明过程如下：（1） 附加前提（假设）p（2） 前提q（3） （1） 、 （2）分离规则（4） 前提s（
9、5） （4）置换q（6） （5） 合简规则（7） （矛盾） （5） 、 （6）合取规则所以推得 .psqp)(三、结束语不论是离散数学还是其它的数学课程, 注意对不同题型的解题方法的总结, 才能熟能生巧, 提高解题技巧。以上介绍了一些常用的命题公式证明方法，在同学们遇到此类证明题时，如果能够灵活运用这些方法，都会迎刃而解的。同学们在运用这些方法证明推理时, 也要主动找出其内在联系, 达到系统掌握命题逻辑的推理论证的目的，进而也达到把握命题逻辑知识的目的。【参考文献】：1王玉文、鲍曼编，数学逻辑基础M.哈尔滨：哈尔滨师范大学出版社，15-22.2耿素云、屈婉玲等编,离散数学M.北京:清华大学出版
10、社,1999，5-11.3左孝陵等编,离散数学M.上海: 上海科学技术文献出版社,1998.6-15.4陈慕泽编，数理逻辑教程M.上海: 上海人民出版社，2002,40-59.【英文翻译】：Some Familiarly Inferential Proof Methods in the Propositional LogicWuJieQiongHarbin normal university(heilongjiang Harbin 150025)【Abstract】: Inferential Proof Methods in the Propositional Logic is the dif
11、ficult content in the discrete mathematics course, there are two main reasons: one is that it is abstract and its methods are quite unique, so its flexibility is too big, and it is difficult to master; Another is that most of its subjects are proof ones, the knowledge of most questions involving a b
12、roader, so the topics are more difficult. And Propositional logic is the basis of mathematical logic. It is important to study propositional logic and master inferential proof methods. At the same time, it is the basis of predicate logic. This paper explained the appropriate examples, and summarizes
13、 the proposition logic reasoning in several common proof method, and analyzed and discussed, and to deepen the students understanding and the knowledge of the flexible use. It helps the students to master the proposition logic reasoning method proved, and they can undertake to the student logical thinking ability training, training students analysis and problem solving abilities at the same time.【key words】: propositional logic; Inference; proof methods
