证明方法 离散数学逻辑和证明 南京大学计算机科学与技术系
证明方法 离散数学─逻辑和证明 南京大学计算机科学与技术系
回顾 ·谓词逻辑 谓词,量词,论域 谓词的否定与嵌套 逻辑等价 逻辑推理 有效论证形式 推理规则与及用推理规则来论证 有关谓词逻辑的论证
回顾 ⚫ 谓词逻辑 ⚫ 谓词,量词,论域 ⚫ 谓词的否定与嵌套 ⚫ 逻辑等价 ⚫ 逻辑推理 ⚫ 有效论证形式 ⚫ 推理规则与及用推理规则来论证 ⚫ 有关谓词逻辑的论证
内容提要 引言 直接证明 反证法 分情形证明 等价性证明 ·存在性证明 唯一性证明 寻找反例 数学与猜想
内容提要 ⚫ 引言 ⚫ 直接证明 ⚫ 反证法 ⚫ 分情形证明 ⚫ 等价性证明 ⚫ 存在性证明 ⚫ 唯一性证明 ⚫ 寻找反例 ⚫ 数学与猜想
引言 定理(theorem) ●能够被证明为真的陈述,通常是比较重要的陈述。 ●证明( proof) 表明陈述(定理)为真的有效论证。 定理证明中可以使用的陈述: (当前)定理的前提 ●已经证明的定理(推论、命题、引理) ●公理(假定) 术语的定义 猜想( conjecture)
引言 ⚫ 定理(theorem) ⚫ 能够被证明为真的陈述,通常是比较重要的陈述。 ⚫ 证明(proof) ⚫ 表明陈述(定理)为真的有效论证。 ⚫ 定理证明中可以使用的陈述: ⚫ (当前)定理的前提 ⚫ 已经证明的定理(推论、命题、引理) ⚫ 公理(假定) ⚫ 术语的定义 猜想(conjecture)
引言 ·定理的陈述(举例) 如果x>y,其中x和y是正实数,那么x2>y2 如何理解 对所有正实数x和y,如果x>y,那么x2>y2 VxVy(x>y)→(x2>y2)论域为正实数 如何证明 定理的陈述为:Vx(P(x)→Q(x) 先证明,对论域中的任一元素c,P(c)→Q(c) 再使用全称生成,得到Vx(P(x)→Q(x)
引言 ⚫ 定理的陈述(举例) ⚫ 如果xy,其中x和y是正实数,那么 x 2y 2 。 ⚫ 如何理解 ⚫ 对所有正实数x和y,如果xy,那么 x 2y 2 。 ⚫ xy((xy)→ (x 2y 2 )) //论域为正实数 ⚫ 如何证明 ⚫ 定理的陈述为:x (P(x)→ Q(x)) ⚫ 先证明,对论域中的任一元素c, P(c)→ Q(c) ⚫ 再使用全称生成,得到x (P(x)→ Q(x))