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

ljlj

逻辑学论文

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

学号

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

吴洁琼

哈尔滨师范大学

（黑龙江·哈尔滨150025）

【摘要】：命题逻辑的推理证明是《离散数学》课程的重点难点内容，其主要原因有两个：一是内容比较抽象且方法较独特，其灵活性很大,故很难掌握；二是题型以证明题居多,大多数题的知识面涉及较广,故习题较难。而命题逻辑又是数理逻辑的基础,熟练而灵活地掌握好命题逻辑中推理证明的方法既是学习命题逻辑的重点,又会为进一步学习谓词逻辑打下良好的基础。本文结合适当的例题讲解，总结了命题逻辑中几种常见的推理证明方法，并进行了分析和探讨,以加深学生的理解，以及知识的灵活使用。以期在帮助学生掌握命题逻辑的推理证明方法的同时,又能对学生进行逻辑思维能力的训练,培养学生分析问题和解决问题的能力。

【关键词】：命题逻辑；推理；证明方法

数理逻辑是《离散数学》课程的主要内容之一，它主要包括命题逻辑和谓词逻辑两大部分,而命题逻辑又是谓词逻辑的基础,其中的内容也比较抽象，所以学好命题逻辑又是学好数理逻辑的关键。学好数理逻辑既能加强学生的逻辑思维能力，又同时能够帮助同学学习数字电路和人工智能等其它课程。数理逻辑中关于命题逻辑证明题比较多，学好数理逻辑的关键是能不能很好的掌握这些证明题。

一、命题逻辑中推理的相关概念

定义1：一个命题公式序列?，?，?，?；?，即(???????)??称为推

1 2 n 1 2 n

理形式，其中序列最后一项?称为推理的结论，?，?，?，?称为推理的条件。

1 2 n

定义2：对于命题公式序列?，?

1 2

，?，?

n

；?的命题变元组(p,p

1 2

,?,p

n

;p)的

任意指派(t,t

1 2

,?,t

n

;t)存在使???

1 2

????

n

为真，而?为假，则称此推理为无效推理，

否则是有效推理。

证明命题公式?为有效结论的过程就是命题逻辑推理证明的过程。而证明推理形式?1，

?2，?，?n；?是有效的充要条件是(?1??2????n)??为重言式。

二、常见证明方法

命题逻辑的推理证明有六种常用证明方法，分别是直接证明法，真值表法,范式法，间接证明法。其中间接证明法里面常见的是CP规则证明法和反证法，本文就这几种方法进行论述。

1、直接证明法

直接证明法就是由一组前提，利用一些公认的推理规则，根据已知的等价或者蕴含公式，推演得到有效的结论。在学生熟悉了逻辑恒等式和常用的推理规则后，大多数证明题都可以用直接证明法方便证明出。

例1、用直接证明法证明(p?q)，(p?r)，(q?s)推导出s?r.

分析：本题目需要证明的结论是个析取式可以用过蕴含表达式转换为蕴含式，即s?r?s?r，所以本题实际只要推导出s?r为真即可得证。

具体证明过程如下：

证明：

p?q 前提

p?q (1)置换

q?s 前提

p?s (2)、(3)假言三段论

s?p (4)置换

p?r 前提

s?r (5)、（6)假言三段论

s?r (7)置换

2、真值表法

推理是从条件推出结论的过程,条件是已知的命题公式,结论是从前提出发应用推理规则推出的命题公式.由于判断推理正确的方法就是判断重言蕴含式的方法,因此可用真值表去判断推理是否正确的问题.

例2、证明逻辑等价式p?(q?r)?(p?q)?(p?r)

证明逻辑等价式是有两种方法，一种是真值表法，一种是利用逻辑等价式替换，这里就介绍用真值表法来证明。p?(q?r)?(p?q)?(p?r)的真值表如下：

P

q

r

q→r

p→(q→r)

p→q

p→r

(p→q)→(p→r)

1

1

1

1

1

1

1

1

1

1

0

0

0

1

0

0

1

0

1

1

1

0

1

1

1

0

0

1

1

0

0

1

0

1

1

1

1

1

1

1

0

1

0

0

1

1

1

1

0

0

1

1

1

1

1

1

0

0

0

1

1

1

1

1

显然,不论p、q、r的真假情况怎样,p→(q→r)总是和(p→q)→(p→r)的真假相同，所以有p (q r) (p q) (p r)。

3、范式法

析取范式和合取范式是命题公式的两种等价形式,在等价的意义下,任何一个命题公式都有唯一的一个析取范式和一个合取范式,析取范式和合取范式可以用于判断某个命题公式是否为重言式或矛盾式。而证明某个推理形式是有效的充要条件是这个推理形式为重言式。所以我们可以把这种唯一的范式形式用于