推理与证明技术

《推理与证明技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学电子科技大学计算机科学与工程学院示范性软件学院02九月2021第5章推理与证明技术数学归纳法的使用3CP规则相关证明4命题逻辑的推理理论1谓词逻辑的推理理论25.1本章学习要求1掌握各种不同类型的规则和公理，特别是命题逻辑和谓词逻辑的推理规则和公理3理解谓词逻辑的精髓，将其思想贯穿于所有的证明之中2熟练掌握不同证明方法的证明原理、不同的应用场景重点掌握一般掌握了解5.2命题逻辑的推理理论概念描述问题的句子；AddYourText判断对概念的肯定与否定的判断；推理从一个或多个前提推出结论的思维过程。推理的有效性和结论的真实性有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是

2、有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论。推理的有效性和结论的真实性所谓推理有效，指的是它的结论是它的前提的合乎逻辑的结果。即，如果它的前提都为真，那么所得的结论也必然为真，而并不是要求前提或结论一定为真或为假；如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。5.2.1推理的基本概念和推理形式定义5.2.1设G1,G2,…,Gn,Ｈ是公式，称H是G1,G2,…,Gn的逻辑结果(G1,G2,…,Gn共同蕴涵H)，当且仅当H是G1∧G2∧…∧Gn的逻辑结果(logicconclusion)。记G1,G2,…,GnＨ，此时称G1,G2,…,

3、GnＨ为有效的(efficacious)，否则称为无效的（inefficacious）。G1,G2,…,Gn称为一组前提(Premise)，有时用集合Г来表示，记Г={G1,G2,…,Gn}。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为ГH。判定定理定理5.2.1公式H是前提集合Г={G1,G2,…,Gn}的逻辑结果当且仅当G1∧G2∧…∧Gn→Ｈ为永真公式。证明：“”若G1,G2,…,GnＨ，但G1∧G2∧…∧Gn→H不是永真式。于是，必存在G1,G2,…,Gn，H的一个解释I，使得G1∧G2∧…∧Gn为真，而H为假，因此对于该解释I，有G1,G2,…,Gn

4、都为真，而H为假，这就与推理形式G1,G2,…,GnＨ是有效的相矛盾.故：G1∧G2∧…∧Gn→H是永真公式。判定定理（续）“”若G1∧G2∧…∧Gn→H是永真式，但G1,G2,…,GnＨ不是有效的推理形式，故存在G1,G2,…,Gn,H的一个解释I，使得G1,G2,…,Gn都为真，而H为假，故G1∧G2∧…∧Gn为真，而H为假，即是说G1∧G2∧…∧Gn→H为假，这就与G1∧G2∧…∧Gn→H是永真式相矛盾，所以G1,G2,…,GnＨ是有效的推理形式。“”与“→”的不同1.“→”仅是一般的蕴涵联结词，G→H的结果仍是一个公式，而“”却描述了两个公式G，H之间的一种逻辑蕴涵关系，

5、GH的“结果”，是非命题公式；2.用计算机来判断GH是办不到的。然而计算机却可“计算”公式G→H是否为永真公式。5.2.2判断有效结论的常用方法要求Г=｛G1,G2,…,Gn｝ГH也就是G1∧G2∧…∧Gn→Ｈ为永真公式因而真值表技术、演绎法和间接证明方法1、真值表技术设P1,P2,…,Pn是出现在前提G1,G2,…,Gn和结论H中的一切命题变元，如果将P1,P2,…,Pn中所有可能的解释及G1,G2,…,Gn，H的对应真值结果都列在一个表中，根据“→”的定义，则有判断方法如下：对所有G1,G2,…,Gn都具有真值T的行(表示前提为真的行)，如果在每一个这样的行中，H也具有真值T，则H

6、是G1,G2,…,Gn的逻辑结果。对所有H具有真值为F的行(表示结论为假的行),如果在每一个这样的行中，G1,G2,…,Gn中至少有一个公式的真值为F(前提也为假)，则H是G1,G2,…,Gn的逻辑结果.例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)2推理定律设G，H，I，J是任意的命题公

7、式，则有：I1：G∧HG(简化规则)I2：G∧HHI3：GG∨H(添加规则)I4：HG∨HI5：┐GG→HI6：HG→HI7：┐(G→H)GI8：┐(G→H)┐HI9：G,HG∧H2推理定律(续)6）I10：┐G,G∨HH(选言/析取三段论)I11：┐G,GHH7）I12：G,G→HH(分离规则)8）I13：┐H,G→H┐G(否定后件式)9）I14：G→H,H→IG→I(假言三段论