山东科技大学 离散数学离散数学15课件.ppt

离 散 数 学 Discrete Mathematics ;上次课内容回顾;第一章 第5讲 §1—8 推理理论; 在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，这些规则有关的理论称为推理理论。 在实际应用的推理中，我们常常把本门学科的一些定律、定理和条件，作为假设前提，尽管这些前提在数理逻辑中实非永真，但在推理过程中，却总是假设这些命题为T，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。 注意，必须把推理的有效性和结论的真实性区别开。 ;一、有效结论 1. 定义 定义1-8.1 设A和C是两个命题公式，当且仅当A→C为一重言式，即A ? C，称C是A的有效结论。或C可由A逻辑地推出。;二、证明方法;二、证明方法;1. 真值表法;例题1 一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。;我们列出真值表1-8.1如下;例题2 如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可得到解答。;列出真值表;真值表法证明;二、证明方法; 2. 直接证法 直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。 ;常用的蕴含式（43页表1-8.3）;常用的等价式(43页表1-8.4);例题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)，┐D∨A ，B 重言蕴含D→C;例题6 设有下列情况，结论是否有效？ (a)或者是天晴，或者是下雨。 (b)如果是天晴，我去看电影。. (c)如果我去看电影，我就不看书。