1、电子科技大学离散数学课程组 国家级精品课程 双语示范课程离 散 数 学*电子科技大学计算机科学与工程学院电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-2*第 5章 推理与证明技术 数学归纳法的使用 3CP规则相关证明4命题逻辑的推理理论 1谓词逻辑的推理理论 2电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-3*1.1 本章学习要求1掌握各种不同类型的规则和公理，特别是命题逻辑和谓词逻辑的推理规则和公理3理解谓词逻辑的精髓，将其思想贯穿于所有的证明之中 2熟练掌握不同证明方法的证明原理、不同的应用场景 重点掌握 一般掌握 了解电子科技大学离散数学课程组 国家级
2、精品课程 双语示范课程105-4*5.2 命题逻辑的推理理论 概念描述问题的句子Add Your TexT判断对概念的肯定 与否定的判断推理从一个或多个前提推出结论的 思维过程认识世界的渐进过程电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-5*推理的有效性和结论的真实性有效的推理不一定产生真实的结论 ；而 产生真实结论的推理过程未必是有效的 。 有效的推理 中可能包含为 “ 假 ” 的前提 ，而 无效的推理 却可能得到为 “真 ” 的结论 。所谓 推理有效 ，指的是 它的结论是它前提的合乎逻辑的结果 。也即，如果它的 前提都为真，那么所得的结论也必然为真 ，而并不是要求前提或
3、结论一定为真或为假，如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-6*5.2.1 推理的基本概念和推理形式 定义 5.2.0 设 G,H是公式，对任意解释 I，如果 I满足 G，那么 I满足 H，则称 H是 G的逻辑结果 (或称 G蕴涵 H),记为 G ，此时称 G为前提 ， H为 结论 。 电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-7*判定定理定理 5.2.0 设 G,H是公式， H是 G的逻辑结果当且仅当 G 为永真公式。 证明： “ ” 若 G，但 GH 不是永真公式。于是，必存在一个
4、解释 I，使得 GH 为假，即在解释I下， G为真，而 H为假，这与 G矛盾，故 GH是永真公式。“ ” 若 GH 是永真式，但 G不成立，故存在G,H的一个解释 I，使得 G为真，而 H为假，从而在解释 I下， GH 为假，这与 GH 是永真公式矛盾，所以 G。电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-8*推广 定义 5.2.1 设 G1,G2, ,Gn,H是公式，称 H是 G1,G2, , Gn的逻辑结果 (G1,G2, ,Gn共同蕴涵 H),当且仅当 H是G1G 2 Gn的逻辑结果 (logic conclusion)。记为 G1,G2, ,Gn ，此时称 G1,G
5、2, ,Gn为 有效的 (efficacious),否则称为 无效的 (inefficacious)。 G1,G2, ,Gn称为一组前提 (Premise),有时用集合 来表示，记 =G 1,G2, ,Gn。 H称为 结论(conclusion)。又称 H是 前提集合 的逻辑结果。记为 H。 电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-9*判定定理定理 5.2.1 公式 H是前提集合 =G 1,G2, ,Gn的逻辑结果当且仅当 G1G 2 Gn 为永真公式。 证明： 略。电子科技大学离散数学课程组 国家级精品课程 双语示范课程105-10*“ ” 与 “ ” 的不同1.“” 仅是一般的 蕴涵联结词 ， GH 的结果仍是一个公式，而 “ ” 却描述了两个公式 G， H之间的一种逻辑蕴涵关系， G H的 “ 结果 ” ，是非命题公式；2. 用计算机来判断 G H是办不到的。然而计算机却可 “ 计算 ” 公式 GH 是否为永真公式。
