离散数学-第5章-推理与证明技术.pptVIP

离散数学06三月2025电子科技大学计算机科学与工程学院

2025/3/6第5章推理与证明技术数学归纳法的使用3CP规则相关证明4命题逻辑的推理理论1谓词逻辑的推理理论2

2025/3/61.1本章学习要求1掌握各种不同类型的规则和公理，特别是命题逻辑和谓词逻辑的推理规则和公理3理解谓词逻辑的精髓，将其思想贯穿于所有的证明之中2熟练掌握不同证明方法的证明原理、不同的应用场景重点掌握一般掌握了解

2025/3/65.2命题逻辑的推理理论概念描述问题的句子AddYourTexT判断对概念的肯定与否定的判断推理从一个或多个前提推出结论的思维过程认识世界的渐进过程

2025/3/6推理的有效性和结论的真实性有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论。所谓推理有效，指的是它的结论是它前提的符合逻辑的结果。也即，如果它的前提都为真，那么所得的结论也必然为真，而并不是要求前提或结论一定为真或为假，如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。

2025/3/65.2.1推理的根本概念和推理形式定义5.2.0设G,H是公式，对任意解释I，如果I满足G，那么I满足H，那么称H是G的逻辑结果(或称G蕴涵H),记为G?Ｈ，此时称G为前提，H为结论。

2025/3/6判定定理定理5.2.0设G,H是公式，H是G的逻辑结果当且仅当G→Ｈ为永真公式。证明：“?”假设G?Ｈ，但G→H不是永真公式。于是，必存在一个解释I，使得G→H为假，即在解释I下，G为真，而H为假，这与G?Ｈ矛盾，故G→H是永真公式。“?”假设G→H是永真式，但G?Ｈ不成立，故存在G,H的一个解释I，使得G为真，而H为假，从而在解释I下，G→H为假，这与G→H是永真公式矛盾，所以G?Ｈ。

2025/3/6推广定义5.2.1设G1,G2,…,Gn,H是公式，称H是G1,G2,…,Gn的逻辑结果(G1,G2,…,Gn共同蕴涵H),当且仅当H是G1∧G2∧…∧Gn的逻辑结果(logicconclusion)。记为G1,G2,…,Gn?Ｈ，此时称G1,G2,…,Gn?Ｈ为有效的(efficacious),否那么称为无效的(inefficacious)。G1,G2,…,Gn称为一组前提(Premise),有时用集合Г来表示，记Г={G1,G2,…,Gn}。H称为结论(conclusion)。又称H是前提集合Г的逻辑结果。记为Г?H。

2025/3/6判定定理定理公式H是前提集合Г={G1,G2,…,Gn}的逻辑结果当且仅当G1∧G2∧…∧Gn→Ｈ为永真公式。证明：略。

2025/3/6“?”与“→”的不同1.“→”仅是一般的蕴涵联结词，G→H的结果仍是一个公式，而“?”却描述了两个公式G，H之间的一种逻辑蕴涵关系，G?H的“结果”，是非命题公式；2.用计算机来判断G?H是办不到的。然而计算机却可“计算”公式G→H是否为永真公式。

2025/3/65.2.2判断有效结论的常用方法要求Г=｛G1,G2,…,Gn｝Г?H也就是G1∧G2∧…∧Gn→Ｈ为永真公式因而真值表技术、演绎法和间接证明方法

2025/3/61、真值表技术设P1,P2,…,Pn是出现在前提G1,G2,…,Gn和结论H中的一切命题变元，如果将P1,P2,…,Pn中所有可能的解释及G1,G2,…,Gn，H的对应真值结果都列在一个表中，根据“→”的定义，那么有判断方法如下：对所有G1,G2,…,Gn都具有真值T的行(表示前提为真的行),如果在每一个这样的行中，H也具有真值T，那么H是G1,G2,…,Gn的逻辑结果。对所有H具有真值为F的行(表示结论为假的行),如果在每一个这样的行中，G1,G2,…,Gn中至少有一个公式的真值为F(前提也为假),那么H是G1,G2,…,Gn的逻辑结果。

2025/3/6例5.2.1判断以下H是否是前提G1,G2的逻辑结果(1)H：Q； G1：P；G2：P→Q；(2)H：┐P； G1：P→Q；G2：┐Q；(3)H：Q； G1：┐P；G2：P→Q。解PQG1G2H00010010111010011111(1)PQG1G2H00111011011001011100(2)PQG1G2H00110011111000011011(3)是是否

2025/3/62推理定律设G，H，I，J是任意的命题公式，那么有：I1：G∧H?G(简化规那么)I2：G∧H?HI3：G?G∨H(添加规那么)I4：H?G∨HI5：┐G?G→HI6：H?G→HI7：┐(G→H)