1、Discrete Mathematics 西南科技大学 计算机科学与技术学院1第一章 命题逻辑 1.6 推理理论 Discrete Mathematics 西南科技大学 计算机科学与技术学院2引言推理 是从已知前提推出结论的思维过程。例如 如果明天天气晴朗，则我去打球。明天天气晴朗。我去打球。前提结论对应的推理规则： PQP所以 Q可表示成：(PQ) P QDiscrete Mathematics 西南科技大学 计算机科学与技术学院31.推理的形式结构在命题逻辑中 ， 前提 是指已知的命题公式， 结论 是从前提出发应用 推理规则 得到的命题公式。前提可有多个，由前提 A1、 A2、 A k 推
2、出结论的定义如下： 定义 若 A1 A2 AkB 为重言式，则称由前提 A1、 A2、 A k推出结论 B的 推理正确 。也称 B是 A1、 A2、 A k 的 有效结论 。 把 A1 A2 Ak B称 为由前提 A1、 A2、 A k推出结论 B的 推理的形式结构Discrete Mathematics 西南科技大学 计算机科学与技术学院4u 根据前面对重言式的定义：用 “ A B ”表示 “A B ”是重言式；用 “A B ”表示 “AB ”是重言式。u 因而，在命题逻辑中，若由前提 A1、 A2、 A k推导结论 B的推理正确，可表示为：A1 A2 Ak Bu 于是，判断推理是否正确就转
3、化为 判断推理的形式结构 是否是是 重言蕴涵式 。下面分别介绍有关的方法：Discrete Mathematics 西南科技大学 计算机科学与技术学院52.推理证明方法一 q定义证明法 无义证明法、平凡证明法、直接证明法、间接（逆反）证明法q真值表法q主析 (合 )取范式法和逻辑等价演算法 。即从定义出发证明 前提的合取 蕴涵 结论 所构成的命题公式为永真式。Discrete Mathematics 西南科技大学 计算机科学与技术学院6例 1 判断下面各推理是否正确：(1)如果天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。(2)如果我上街，我一定去新华书店。我没上街，所以我没去新华书店
4、。Discrete Mathematics 西南科技大学 计算机科学与技术学院7解： （ 解上述类型的推理问题，应先将命题符号化，然后写出前提、结论和推理的形式结构，最后进行判断。）(1)p：天气凉快； q：小王去游泳。则该论断的前提为： ， p。 结论为： 推理的形式结构为： (*)接下来就是判断 (*)是否为重言式。Discrete Mathematics 西南科技大学 计算机科学与技术学院8 真值表法 真值表的最后一列全为 1，因而 (*)是重言式，所以推理正确。 等值演算法 ，可以判断推理正确。 主析取范式法 可以判断推理正确。Discrete Mathematics 西南科技大学 计算机科学与技术学院9(2) p：我上街； q：我去新华书店。 前提： ， 。结论： 。推理的形式结构为 : 。 (*)。 可见 (*)不是重言式，所以推理不正确。Discrete Mathematics 西南科技大学 计算机科学与技术学院102.推理证明方法二 构造证明法在推理过程中，如果命题变元比较多，以上三种方法都不方便，因而需要引入另一种证明方法 构造证明法 。这种方法是在给定的 推理规则 下进行，而推理规则是建立在基本 重言蕴涵式 的基础之上的。基本的重言蕴涵式主要有以下几个：
