命题逻辑中几种常见的推理证明方法.doc

ljlj

逻
辑
学
论
文

数学科学学院
09级3班
吴洁琼
学号2009040288

命题逻辑中几种常见的推理证明方法
吴洁琼
哈尔滨师范大学
（黑龙江·哈尔滨 150025）
【摘 要】：命题逻辑的推理证明是《离散数学》课程的重点难点内容，其主要原因有两个： 一是内容比较抽象且方法较独特，其灵活性很大, 故很难掌握；二是题型以证明题居多, 大多数题的知识面涉及较广, 故习题较难。而命题逻辑又是数理逻辑的基础, 熟练而灵活地掌握好命题逻辑中推理证明的方法既是学习命题逻辑的重点, 又会为进一步学习谓词逻辑打下良好的基础。本文结合适当的例题讲解，总结了命题逻辑中几种常见的推理证明方法，并进行了分析和探讨,以加深学生的理解，以及知识的灵活使用。 以期在帮助学生掌握命题逻辑的推理证明方法的同时, 又能对学生进行逻辑思维能力的训练,培养学生分析问题和解决问题的能力。
【关键词】：命题逻辑；推理；证明方法
数理逻辑是《离散数学》课程的主要内容之一，它主要包括命题逻辑和谓词逻辑两大部分, 而命题逻辑又是谓词逻辑的基础,其中的内容也比较抽象，所以学好命题逻辑又是学好数理逻辑的关键。学好数理逻辑既能加强学生的逻辑思维能力，又同时能够帮助同学学习数字电路和人工智能等其它课程。数理逻辑中关于命题逻辑证明题比较多，学好数理逻辑的关键是能不能很好的掌握这些证明题。
一、命题逻辑中推理的相关概念
定义1：一个命题公式序列，，，；，即称为推理形式，其中序列最后一项称为推理的结论，，，，称为推理的条件。
定义2：对于命题公式序列，，，；的命题变元组的任意指派存在使为真，而为假，则称此推理为无效推理，否则是有效推理。
证明命题公式为有效结论的过程就是命题逻辑推理证明的过程。而证明推理形式，，，；是有效的充要条件是为重言式。
二、常见证明方法
命题逻辑的推理证明有六种常用证明方法，分别是直接证明法，真值表法,范式法，间接证明法。其中间接证明法里面常见的是CP规则证明法和反证法，本文就这几种方法进行论述。
1、直接证明法
直接证明法就是由一组前提，利用一些公认的推理规则，根据已知的等价或者蕴含公式，推演得到有效的结论。在学生熟悉了逻辑恒等式和常用的推理规则后，大多数证明题都可以用直接证明法方便证明出。
例1、用直接证明法证明，，推导出.
分析：本题目需要证明的结论是个析取式可以用过蕴含表达式转换为蕴含式，
即，所以本题实际只要推导出为真即可得证。
具体证明过程如下：
证明：
(1) 前提
(2) (1)置换
(3) 前提
(4) (2)、(3)假言三段论
(5) (4)置换
(6) 前提
(7) (5)、（6)假言三段论
(8) (7)置换
2、真值表法
推理是从条件推出结论的过程, 条件是已知的命题公式, 结论是从前提出发应用推理规则推出的命题公式. 由于判断推理正确的方法就是判断重言蕴含式的方法, 因此可用真值表去判断推理是否正确的问题.
例2、证明逻辑等价式
证明逻辑等价式是有两种方法，一种是真值表法，一种是利用逻辑等价式替换，这里就介绍用真值表法来证明。的真值表如下：
P q r
q→r
p→(q→r)
p→q
p→r
(p→q)→(p→r)
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1

显然, 不论p、q、r 的真假情况怎样,p→(q→r)总是和(p→q)→(p→r)的真假相同，所以有。
3、范式法
析取范式和合取范式是命题公式的两种等价形式, 在等价的意义下, 任何一个命题公式都有唯一的一个析取范式和一个合取范式, 析取范式和合取范式可以用于判断某个命题公式是否为重言式或矛盾式。而证明某个推理形式是有效的充要条件是这个推理形式为重言式。所以我们可以把这种唯一的范式形式用于推理论证中, 去证明一些命题公式。
例3、证明.
证：即判断是否为重言式。
先求合取范式：

得到的结果中，四个合取项都为重言式，从而该命题公式为重言式，得证。
4、CP规则法
CP规则的内容：前提是,,,，欲证明结论成立（结论是条件式），则将条件式作为附加前提证得即可。设,由前提证明，即证明永真，而等价于，因此证明永真即可。
这种证明方法比较适用于证明结论中带有蕴含连接词，也就是说结论是形如的命题公式，用CP规则证明可能比较简便。再复杂的结论如形如的命题公式，也可以通过连续使用两次CP规则的方式来证明。
例4、证明.
证：（1） 附加前提
（2） 前提
（3） （1）（2）否析规则
（4） 前提
（5） （3）（4）分离规则
（6） 前提
（7） （5）（6）分离规则
（8） CP规则

4、反证法
反证法是一种间接证明问题的方法。由反证法推理规则可知，直接证困难时，可改证，也就是假定不真，设法推出矛盾，从而肯定，这就是反证法。它的步骤：（1）否定结论；（2）找出矛盾；（3）肯定题设。
例5、用反证法证明.
分析：用反证法证明首先要假设结论部分命题公式的否定为真，并作为附加前提，在证明过程证得到任意形式的两个互相矛盾的命题公式证明即结束。
具体证明过程如下：
（1） 附加前提（假设）
（2） 前提
（3） （1）、（2）分离规则
（4） 前提
（5） （4）置换
（6） （5） 合简规则
（7） （矛盾） （5）、（6）合取规则
所以推得.
三、结束语
不论是离散数学还是其它的数学课程, 注意对不同题型的解题方法的总结, 才能熟能生巧, 提高解题技巧。以上介绍了一些常用的命题公式证明方法，在同学们遇到此类证明题时，如果能够灵活运用这些方法，都会迎刃而解的。同学们在运用这些方法证明推理时, 也要主动找出其内在联系, 达到系统掌握命题逻辑的推理论证的目的，进而也达到把握命题逻辑知识的目的。

【参考文献】：
[1]王玉文、鲍曼编，数学逻辑基础[M].哈尔滨：哈尔滨师范大学出版社，15-22.
[2]耿素云、屈婉玲等编,离散数学[M].北京:清华大学出版社,1999，5-11.
[3]左孝陵等编,离散数学[M].上海: 上海科学技术文献出版社,1998.6-15.
[4]陈慕泽编，数理逻辑教程[M].上海: 上海人民出版社，2002,40-59.

【英文翻译】：
Some Familiarly Inferential Proof Methods
in the Propositional Logic
WuJieQiong
Harbin normal university
(heilongjiang Harbin 150025)
【Abstract】: Inferential Proof Methods in the Propositional Logic is the difficult 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 broader, 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 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