离散数学1.8推理理论.pptVIP

* * 离散数学(Discrete Mathematics) * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 1.8.1常用的证明方法 1.8.2真值表法 (Truth Table) 1.8.3直接证法 (Direct Proof) 1.8.4 间接证法 (Indirect Proof) * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 1.8.1常用的证明方法 定义1.8.1 ：设Ａ和Ｃ是两个命题公式,当且仅当Ａ?Ｃ为一重言式，即Ａ?Ｃ,称Ｃ是Ａ的有效结论;或称Ｃ可由Ａ逻辑推出.一般地,如果有n个前提H1,H2,H3,.…,Hn , 若H1?H2?H3?....?Hn?C,则称C是一组前提H1,H2,…,Hn的有效结论。 注意:在形式逻辑中,我们并不关心结论是否真实,而主要关心结论是否可以由给定的前提推出来,我们只注意推理的形式是否正确.因此,有效结论并不一定是正确的,只有正确的前提经过正确的推理得到的逻辑结论才是正确的. * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 证明C是A的有效结论的方法就是判别重言蕴含的方法.前面我们介绍的论证方法有真值表法、等值演算法、主析（合）取范式法。论证方法千变万化，但最基本、最常用的方法有三种： 推理证明的方法 * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 1.8.2真值表法 (Truth Table) 构造命题公式H1 ∧ H2 ∧ …… ∧ Hn → C的真值表，若为永 真，H1 ∧ H2 ∧ …… ∧ Hn ? C 推理正确。 例：证明((P∨Q)∧┐Q) ? P P Q P∨Q ┐Q (P∨Q)∧┐Q ((P∨Q)∧┐Q)?P 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 由上面真值表可知((P∨Q)∧┐Q) ? P。 1.8.3直接证法 (Direct Proof) 直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式推演得到有效结论。 常用的推理规则 P规则:（也称前提引入规则）前提在推导过程中的任何 时候都可以引用。 T规则:在推导过程中，所证明的结论、已知的等价或蕴 含公式都可以作为后续证明的前提，命题公式中 的任何子公式都可以用与之等价的命题公式置换。 * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 常用的蕴含式和等价式见课本P43 表1-8.3、1-8.4 例1.如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我考试没有及格。 试对上述论证构造证明。 解：设P：我考试及格. Q：我高兴。R：我饭量增加。 则此论证可表为 (P→Q)?(Q→R)?┐R?┐P 证: * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 常用的蕴含式和等价式见课本P43 表1-8.3、1-8.4 例1.如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我考试没有及格。 试对上述论证构造证明。 解：设P：我考试及格. Q：我高兴。R：我饭量增加。 则此论证可表为 (P→Q)?(Q→R)?┐R?┐P 证: 1　P→Q P 2　Q→R P 3　 ┐R P 4　 ┐Q T，2，3 I12 5　 ┐P T，1，4 I12 * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 例2.证明 R?S是前提C?D，C→R,D→S的有效结论。 证： * 第一章 命题逻辑（Propositional Logic） 1.8推理理论(Inference Theory) 例2.证明 R?S是前提C?D，C→R,D→S的有效结论。 证：1.C?D P 2.C→R