数理逻辑—命题逻辑(4)

Discrete Mathematics

第一章 命题逻辑

1.6 推理理论

西南科技大学

1

计算机科学与技术学院

Discrete Mathematics 引言 推理是从已知前提推出结论的思维过程。 推理是从已知前提推出结论的思维过程。 是从已知前提推出结论的思维过程 例如 如果明天天气晴朗，则我去打球。

前提

明天天气晴朗。

结论

我去打球。 对应的推理规则：P→Q P 所以

西南科技大学

可表示成： (P→Q)∧P Q ∧

2 计算机科学与技术学院

Q

Discrete Mathematics 1.推理的形式结构 1.推理的形式结构 在命题逻辑中，前提是指已知的命题公式，结论是 在命题逻辑中，前提是指已知的命题公式，结论是 是指已知的命题公式 从前提出发应用推理规则得到的命题公式。 推理规则得到的命题公式 从前提出发应用推理规则得到的命题公式。前提可 有多个，由前提A 有多个，由前提 1、A2、…Ak 推出结论的定义如 下： 为重言式， 定义 若A1∧A2∧…∧Ak→B为重言式，则称由前提 ∧ 为重言式 A1、A2、…Ak推出结论 的推理正确。 推出结论B的推理正确。 也称B是 有效结论。 也称 是A1、A2、…Ak 的有效结论。 把 A1∧A2∧…∧Ak → B称为由前提 1、A2、…Ak ∧ 称为由前提A 推出结论B的 推出结论 的推理的形式结构

3

西南科技大学

计算机科学与技术学院

Discrete Mathematics 根据前面对重言式的定义： 根据前面对重言式的定义： 表示“ 是重言式； 用“ A B ”表示“A B ”是重言式； 表示 B 是重言式 表示“ 是重言式。 用“A B ”表示“A→B ”是重言式。 表示 是重言式 因而，在命题逻辑中，若由前提 因而，在命题逻辑中，若由前提A1、A2、…Ak 推导结论B的推理正确，可表示为： 推导结论B的推理正确，可表示为： A1∧A2∧…∧Ak B ∧ 于是，判断推理是否正确就转化为判断推理的 于是，判断推理是否正确就转化为判断推理的 形式结构是否是是重言蕴涵式。 是否是是重言蕴涵式 形式结构是否是是重言蕴涵式。下面分别介绍有 关的方法： 关的方法：

西南科技大学

4

计算机科学与技术学院

Discrete Mathematics 2.推理证明方法一 2.推理证明方法一 定义证明法—无义证明法、平凡证明法、 定义证明法—无义证明法、平凡证明法、直 接证明法、间接（逆反）证明法 接证明法、间接（逆反） 真值表法 主析( 主析(合)取范式法和逻辑等价演算法。即从 取范式法和逻辑等价演算法 定义出发证明前提的合取蕴涵结论 前提的合取蕴涵结论所构成的命 前提的合取蕴涵结论 题公式为永真式。

西南科技大学

5

计算机科学与技术学院

Discrete Mathematics 判断下面各推理是否正确： 例1 判断下面各推理是否正确： (1)如