南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 03 证明方法

1 证明方法

证明方法 1

回顾 问题1：如何基于命题逻辑进行推理？ ·蕴含永真式导出推理规则 问题2：什么是（一阶）谓词逻辑？ ~命题逻辑+谓词+量词；量化表达式 问题3：如何基于谓词逻辑进行推理？ ~命题逻辑的推理+全称/存在例示/生成

回顾 问题1：如何基于命题逻辑进行推理？ - 蕴含永真式导出推理规则 问题2：什么是(一阶)谓词逻辑？ - 命题逻辑+谓词+量词；量化表达式 问题3：如何基于谓词逻辑进行推理？ - 命题逻辑的推理+全称/存在 例示/生成

本节提要 问题1：什么叫证明？ 问题2：常见的证明方法有哪些？ 问题3：什么是猜想？有哪些有意思的猜想？

本节提要 问题1：什么叫证明？ 问题2：常见的证明方法有哪些？ 问题3：什么是猜想？有哪些有意思的猜想？

定理与证明 4 口定理(heorem) 口能够被证明为真的陈述，通常是比较重要的陈述。 口证明(proof) 口表明陈述（定理）为真的有效论证。 口定理证明中可以使用的陈述： 口公理（不证自明的基本事实） 口（当前）定理的前提 口已经证明的定理（推论、命题、引理）

定理与证明  定理(theorem)  能够被证明为真的陈述，通常是比较重要的陈述。  证明(proof)  表明陈述(定理)为真的有效论证。  定理证明中可以使用的陈述:  公理(不证自明的基本事实)  (当前)定理的前提  已经证明的定理(推论、命题、引理) 4

例 5 口定理的陈述（举例） 口如果x>y,其中x和y是正实数，那么x2>y2。 口如何表达 ▣廿xy(x>y)→(x2>y2)/论域为正实数 口如何证明 ▣定理的陈述为：x(P(x)→Q(x) 口先证明，对论域中的任一元素c,P(c)→Q(c) ▣再使用全称引入，得到x(P(x)→Q(x)

例  定理的陈述(举例)  如果x>y，其中x和y是正实数，那么 x 2>y2 。  如何表达  xy((x>y) → (x2>y2 )) //论域为正实数  如何证明  定理的陈述为: x(P(x) → Q(x))  先证明，对论域中的任一元素c， P(c) → Q(c)  再使用全称引入，得到x (P(x) → Q(x)) 5

归纳推理的证明方式 证明的本质是“保证真实性”， 其涵义根据领域 的不同有所差异： 科学中的“证明”指利用归纳推理 (inductive reasoning)去证实(prove)某个假设(hypothesis). 人们将大量特殊的信息收集( 归纳)起来并根据自身 的知识和经验去观察，并推断（推理）「 哪些是真实的 此类“证明”不产生定论(mathematical certainty)

归纳推理的证明方式 6

归纳推理的证明方式 7 日常生活中“证明”的例子： 我们观察到：小王今早上课迟到了。 。我们观察到：小王今天没梳头。 。经验：小王平时对发型相当在意。 0结论：小王今天睡过头了。 ■这类“证明”方式一般在数学中用于提出假设

归纳推理的证明方式 7

演绎推理的证明方式 8 证明的本质是“保证真实性”，其涵义根据领域 的不同有所差异 数学中的“证明”指利用演绎推理(deductive reasoning)和逻辑规则去推证某个命题 数学证明中每一步推理过程都根据某些前提条件 (premise)展示出一个结论 称为逻辑推论 所有的证明过程必须是严密的(rigorous),每一步 都必须提供确信的证据来支持中间结论，最终结论称 为系统中的定理(theorem)

演绎推理的证明方式 8

演绎推理的证明方式 用于数学的证明方式称为形式化证明或推导(derivation) 定义（形式化证明）：对一个命题的基于公理化系统的 一系列逻辑演绎的有限过程 例：欧几里德平面几何的公理集合 公理1.任意两点可以通过一条直线连接。 公理2.任意线段可无限延伸为一条直线。 公理3.给定任意线段，可以以其一个端点作为圆心，该线段作为半径作 一个圆。 公理4.所有直角都全等。 公理5.若两条直线都与第三条直线相交，并且在同一边的内角之和小于 两个直角，则这两条直线在这一边必定相交

演绎推理的证明方式 9

本节提要 问题1：什么叫证明？ -表明定理为真的有效论证（演绎推理) 问题2：常见的证明方法有哪些？ 问题3：什么是猜想？有哪些有意思的猜想？

本节提要 问题1：什么叫证明？ - 表明定理为真的有效论证（演绎推理） 问题2：常见的证明方法有哪些？ 问题3：什么是猜想？有哪些有意思的猜想？