山东科技大学离散数学离散数学.ppt

第一章 命题逻辑第6、7讲 上次课内容回顾 析取范式 第一章 第5讲 §1—8 推理理论 在数学和其它自然科学中，经常要考虑从某些前提A1，A2，…，An能够推导出什么结论。 例如： 从分子学说，原子学说，能够得到什么结论； 从光的波动学说，能得到什么结论。 我们一般地要对“假设”的内容作深入分析，并推究其间的关系，从而得到结论。 但也有一些推理，只需分析假设中的真值和联结词，便可获得结论。 在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，这些规则有关的理论称为推理理论。 在实际应用的推理中，我们常常把本门学科的一些定律、定理和条件，作为假设前提，尽管这些前提在数理逻辑中实非永真，但在推理过程中，却总是假设这些命题为T，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。 注意，必须把推理的有效性和结论的真实性区别开。 一、有效结论 1. 定义 定义1-8.1 设A和C是两个命题公式，当且仅当A→C为一重言式，即A ? C，称C是A的有效结论。或C可由A逻辑地推出。 二、证明方法 二、证明方法 1. 真值表法 例题1 一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。 我们列出真值表1-8.1如下 例题2 如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可得到解答。 列出真值表 真值表法证明 前真：看后真； 后假：前至少有一个假。 二、证明方法 2. 直接证法 直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。 例题1 证明 (P∨Q) ∧(P→R)∧(Q→S) ? S∨R 例题1 证明 (P∨Q) ∧(P→R)∧(Q→S) ? S∨R 证法2 (1) P→R P (2) P∨Q →R∨Q T(1) I (3) Q→S P (4) Q∨R →S∨R T(3) I (5) P∨Q →S∨R T(2),(4) I (6) P∨Q P (7) S∨R T(5),(6) I 例题2 证明 (W∨R) →V ,V→C∨S,S→U, ┐C∧ ┐U ? ┐W 二、证明方法 3. 间接证法 (1)定义 定义1-8.2 假设公式H1，H2，…，Hn 中的命题变元为P1，P2，…，Pn ， 对于P1，P2，…，Pn的一些真值指派，如果能使H1 ∧ H2 ∧ … ∧ Hn的真值为T，则称公式H1，H2，…，Hn 是相容的。 如果对于P1，P2，…，Pn的每一组真值指派使得H1 ∧ H2 ∧ … ∧ Hn的真值均为F，则称公式H1，H2，…，Hn是不相容的。 (2)证法 可以把不相容的概念应用于命题公式的证明。 设有一组前提H1，H2，…，Hn ，要推出结论C，即证H1 ∧ H2 ∧ … ∧ Hn ? C，记作S ? C，即┐C→ ┐S为永真，或C∨┐S为永真，故┐C ∧S为永假 。因此要证明H1 ∧ H2 ∧ … ∧ Hn ? C，只要证明H1，H2，…，Hn与是┐C是不相容的。即假定┐C为真，推出矛盾。 例题3 证明 A→B， ┐(B∨C)可逻辑推出┐A 例题4 证明 (P∨Q) ∧(P→R)∧(Q→S) ? S∨R (3) CP规则（ 结论为R → C时使用） 间接证法的另一种情况是：若要证H1 ∧ H2 ∧ … ∧ Hn ? (R → C)。 设H1 ∧ H2 ∧ … ∧ Hn 为S ，即证S ?(R → C) 或S ?( ┐ R∨C)，故S →( ┐ R∨C)为永真式。因为S →( ┐R∨C) ? ┐S∨( ┐R∨C) ? (┐S∨ ┐R)∨C? ┐(S ∧R)∨C ? (S ∧R) →C，所以若将R作附加前提，如有(S ∧R) ? C，即证得S ?(R→C)。 由(S ∧R) ? C，证得S ?(R→C)称为CP规则。 例题5 证明 A→(B→C)