第一章命题逻辑（PropositionalLogic）1.6推理理论(InferenceTheory)1.6.1常用的证明方法1.6.2真值表法(Truth Table)1.6.3直接证法(Direct Proof)1.6.4间接证法(IndirectProof2026/3/15计算机科学与工程系1
2026/3/15 计算机科学与工程系 1 第一章 命题逻辑（Propositional Logic） 1.6推理理论(Inference Theory) 1.6.1常用的证明方法 1.6.2真值表法 (Truth Table) 1.6.3直接证法 (Direct Proof) 1.6.4 间接证法 (Indirect Proof)
第一章命题逻辑（PropositionalLogic)1.6推理理论(InferenceTheory)1.6.1常用的证明方法定义1.6.1：设A和C是两个命题公式,当且仅当A→C为一重言式，即A=C,称C是A的有效结论或称C可由A逻辑推出.一般地,如果有n个前提Hi,H2,H3，·.….,Hn若Hi^H2^H3^.···^Hn=>C，则称C是一组前提Hi,H2，..,Hn的有效结论。注意：在形式逻辑中,我们并不关心结论是否真实,而主要关心结论是否可以由给定的前提推出来,我们只注意推理的形式是否正确.因此,有效结论并不一定是正确的,只有正确的前提经过正确的推理得到的逻辑结论才是正确的，2026/3/15计算机科学与工程系2
2026/3/15 计算机科学与工程系 2 第一章 命题逻辑（Propositional Logic） 1.6推理理论(Inference Theory) 1.6.1常用的证明方法 ◼ 定义1.6.1 ：设Ａ和Ｃ是两个命题公式,当且仅当Ａ→Ｃ 为一重言式，即ＡＣ,称Ｃ是Ａ的有效结论;或称Ｃ可 由Ａ逻辑推出.一般地,如果有n个前提H1,H2,H3,.,Hn , 若H1H2H3.HnC,则称C是一组前提H1,H2,.,Hn的 有效结论。 ◼ 注意:在形式逻辑中,我们并不关心结论是否真实,而主要 关心结论是否可以由给定的前提推出来,我们只注意推理 的形式是否正确.因此,有效结论并不一定是正确的,只有 正确的前提经过正确的推理得到的逻辑结论才是正确的
第一章命题逻辑（PropositionalLogic）1.6推理理论(InferenceTheory)证明C是A的有效结论的方法就是判别蕴含式是否是重言的.前面我们介绍的论证方法有真值表法、等值演算法、主析（合）取范式法。论证方法千变万化但最基本、最常用的方法有三种：真值表法直接证法推理证明的方法归谬法间接证法附加前提证明法2026/3/15计算机科学与工程系3
2026/3/15 计算机科学与工程系 3 第一章 命题逻辑（Propositional Logic） 1.6推理理论(Inference Theory) ◼ 证明C是A的有效结论的方法就是判别蕴含式是否是 重言的.前面我们介绍的论证方法有真值表法、等值 演算法、主析（合）取范式法。论证方法千变万化， 但最基本、最常用的方法有三种： 推理证明的方法 间接证法 直接证法 真值表法 附加前提证明法 归谬法
第一章命题逻辑（PropositionalLogic）1.6推理理论(InferenceTheory)1.6.2真值表法 (Truth Table)构造命题公式H^H2^^H，→C的真值表，若为永真，H1^H2^.^Hn=→C推理正确。例：证明((PVQ)^Q)=PPQPvQ7 Q(PVQ)^- Q ((PVQ) Q)-P0001010001110111111110012026/3/15计算机科学与工程系4
2026/3/15 计算机科学与工程系 4 第一章 命题逻辑（Propositional Logic） 1.6推理理论(Inference Theory) 1.6.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
第一章命题逻辑（PropositionalLogic）1.6推理理论(InferenceTheory)由上面真值表可知((PVQ)^Q)=P。1.6.3直接证法(Direct Proof)直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式推演得到有效结论。常用的推理规则P规则：（也称前提引入规则）前提在推导过程中的任何时候都可以引用。T规则:在推导过程中，所证明的结论、已知的等价或蕴含公式都可以作为后续证明的前提，命题公式中的任何子公式都可以用与之等价的命题公式置换。2026/3/15计算机科学与工程系5
2026/3/15 计算机科学与工程系 5 第一章 命题逻辑（Propositional Logic） 1.6推理理论(Inference Theory) 由上面真值表可知((P∨Q)∧┐Q) P。 ◼ 1.6.3直接证法 (Direct Proof) ◼ 直接证法：由一组前提，利用一些公认的推理规则， 根据已知的等价或蕴含公式推演得到有效结论。 ◼ 常用的推理规则 P规则:（也称前提引入规则）前提在推导过程中的任何 时候都可以引用。 T规则:在推导过程中，所证明的结论、已知的等价或蕴 含公式都可以作为后续证明的前提，命题公式中 的任何子公式都可以用与之等价的命题公式置换
推理定律重言蕴涵式重要的推理定律附加律A = (AvB)化简律(A^B) = A假言推理(A-→B)A= B拒取式(A-→B)^-B A析取三段论(AVB)^-B = A假言三段论(A→B)^(B→C) = (A→C)等价三段论(AB)^(B>C) = (AC)构造性二难(A-→B)^(C-→D)^(AVC) = (BVD)2026/3/156计算机科学与工程系
2026/3/15 计算机科学与工程系 6 推理定律——重言蕴涵式 重要的推理定律 A (AB) 附加律 (AB) A 化简律 (A→B)A B 假言推理 (A→B)B A 拒取式 (AB)B A 析取三段论 (A→B)(B→C) (A→C) 假言三段论 (AB)(BC) (AC) 等价三段论 (A→B)(C→D)(AC) (BD) 构造性二难
推理定律(续）构造性二难（特殊形式）(A-→B)^(-A→B) = B(A-→>B)^(C->D)^(-BV-D) = (-AV-C)破坏性二难说明：A,B,C为元语言符号若某推理符合某条推理定律，则它自然是正确的AB产生两条推理定律:A= B,B=A2026/3/15计算机科学与工程系
2026/3/15 计算机科学与工程系 7 推理定律 (续) (A→B)(A→B) B 构造性二难（特殊形式） (A→B)(C→D)( BD) (AC) 破坏性二难 说明： A, B, C为元语言符号 若某推理符合某条推理定律，则它自然是正确的 AB产生两条推理定律: A B, B A
推理规则(6)化简规则前提引入规则(1) AΛB(2)结论引入规则.:A(3) 置换规则(7)拒取式规则(4)假言推理规则A-→BA→B-BA..-A.:. B(8）假言三段论规则(5) 附加规则A-→BAB→>C..AvB:.A-C2026/3/15计算机科学与程系
2026/3/15 计算机科学与工程系 8 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 A→B A \ B (5) 附加规则 A \AB (6) 化简规则 AB \A (7) 拒取式规则 A→B B \A (8) 假言三段论规则 A→B B→C \A→C
推理规则(续）破坏性二难推理(11)(9)析取三段论规则规则AvBA-→B-BC-D:A-BV-D(10)构造性二难推理规则.:.-AV-C(12)合取引入规则A→BAC-DBAvC:.AΛB..BVD2026/3/15计算机科学与工程系9
2026/3/15 计算机科学与工程系 9 推理规则(续) (11) 破坏性二难推理 规则 A→B C→D BD \AC (12) 合取引入规则 A B \AB (9) 析取三段论规则 AB B \A (10)构造性二难推理 规则 A→B C→D AC \BD
第一章命题逻辑（PropositionalLogic）1.6推理理论(InferenceTheory)例1.如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我考试没有及格。试对上述论证构造证明。解：设P：我考试及格：Q：我高兴。R：我饭量增加。则此论证可表为(P-→Q) ^(Q→R) ^ R=> P证:2026/3/15计算机科学与工程系10
2026/3/15 计算机科学与工程系10 第一章 命题逻辑（Propositional Logic） 1.6推理理论(Inference Theory) 例1.如果考试及格，那我高兴。若我高兴，那么我饭 量增加。我的饭量没增加，所以我考试没有及格。 试对上述论证构造证明。 解：设P：我考试及格. Q：我高兴。R：我饭量增加。 则此论证可表为 (P→Q)(Q→R)┐R┐P 证: