1、离散数学离离 散散 数数 学学Discrete Mathematics 陈明Email:mingchen_信息科学与工程学院二零一零年九月离散数学18 推理理论在数学和其它自然科学中，经常要考虑从某些前提 A1， A2， ， An能够推导出什么结论。例如：v 从分子学说，原子学说，能够得到什么结论；v 从光的波动学说，能得到什么结论。我们一般地要对 “假设 ”的内容作深入分析，并推究其间的关系，从而得到结论。但也有一些推理，只需分析假设中的真值和联结词，便可获得结论。 第一章 命题逻辑离散数学在实际应用的推理中，我们常常把本门学科的一些 定律、定理和条件，作为假设前提 ，尽管这些前提在数理逻辑
2、中 实非永真 ，但在推理过程中，却总是假设这些命题为 T，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是 论证 。如果 6是偶数，则 7被 2除不尽。或 5不是素数，或 7被 2除尽。但 5是素数。所以 6是奇数。离散数学任何一个推理都由 前提和结论 两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。 要研究推理，首先应该明确什么样的推理是有效的。离散数学符号化下列格式并且验证论证的有效性：如果 6是偶数，则 7被 2除不尽。或 5不是素数，或 7被2除尽。但 5是素数。所以 6是奇数。解：设 P： 6是偶数， Q： 7被 2除尽； R： 5是素
3、数则符号化为：(P- Q) (R Q) (R) P验证：设 (P- Q) (R Q) (R)为 T，那么 R为 T，并且 R Q为 T，故 Q为 T，再因为 P- Q为 T，得到 P为 T。离散数学1. 定义定义 1-8.1 设 A和 C是两个命题公式，当且仅当 AC 为一重言式，即 A C，称 C是 A的有效结论。或 C可由 A逻辑地推出。3 . 论证过程判别有效结论的过程就是论证过程。2. 推广有效结论定义可以推广到有 n个前提的情况。设 H1， H2， ， Hn， C是命题公式，当且仅当H1 H2 Hn C (A)称 C是一组前提 H1， H2， ， Hn的有效结论。一、有效结论离散数学
4、注意：必须把推理的 有效性 和结论的 真实性 区别开。 离散数学二、证明方法1. 真值表法2. 直接证法3. 间接证法离散数学1. 真值表法设 P1， P2， ， Pn是出现于前提 H1， H2， ， Hn和结论 C中的全部命题变元，假定对 P1， P2， ， Pn作了全部的真值指派，这样就能对应地确定 H1， H2， ， Hn和 C的所有真值，列出这个真值表，即可看出 (A)式是否成立。v H1， H2， ， Hn真值均为 T的行，对于每一个这样的行，若 C也有真值 T，则 (A)式成立；v 或者看 C的真值为 F的行，在每一个这样的行中，H1， H2， ， Hn的真值至少有一个为 F，则 (A)式也成立。离散数学例题 1 一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。解 设各命题变元为P：统计表格的错误是由于材料不可靠。Q：统计表格的错误是由于计算有错误。 本例可译为： Q是前提 P Q， P的有效结论，即P (P Q) Q
