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

证明方法 离散数学逻辑和证明 南京大学计算机科学与技术系

证明方法 离散数学─逻辑和证明 南京大学计算机科学与技术系

回顾 ·谓词逻辑 谓词,量词,论域 谓词的否定与嵌套 逻辑等价 逻辑推理 有效论证形式 推理规则与及用推理规则来论证 有关谓词逻辑的论证

回顾 ⚫ 谓词逻辑 ⚫ 谓词，量词，论域 ⚫ 谓词的否定与嵌套 ⚫ 逻辑等价 ⚫ 逻辑推理 ⚫ 有效论证形式 ⚫ 推理规则与及用推理规则来论证 ⚫ 有关谓词逻辑的论证

内容提要 引言 直接证明 反证法 分情形证明 等价性证明 ·存在性证明 唯一性证明 寻找反例 数学与猜想

内容提要 ⚫ 引言 ⚫ 直接证明 ⚫ 反证法 ⚫ 分情形证明 ⚫ 等价性证明 ⚫ 存在性证明 ⚫ 唯一性证明 ⚫ 寻找反例 ⚫ 数学与猜想

引言 定理(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)

引言 ⚫ 定理的陈述（举例） ⚫ 如果xy，其中x和y是正实数，那么 x 2y 2 。 ⚫ 如何理解 ⚫ 对所有正实数x和y，如果xy，那么 x 2y 2 。 ⚫ xy((xy)→ (x 2y 2 )) //论域为正实数 ⚫ 如何证明 ⚫ 定理的陈述为：x (P(x)→ Q(x)) ⚫ 先证明，对论域中的任一元素c， P(c)→ Q(c) ⚫ 再使用全称生成，得到x (P(x)→ Q(x))

直接证明 ·定义 整数n是偶数,如果存在一个整数k使得n=2k;整数n是奇 数,如果存在一个整数k使得n=2k+1 备注:一个整数要么是偶数,要么是奇数。 ·定理:若n是奇数,则n2是奇数。 任意给定一个奇数n,存在一个整数k,n=2k+1 n2=2(2k2+2k)+1 n2是奇数 所以,对任意奇数n,n2是奇数n(dd(n)→dd(n2)

直接证明 ⚫ 定义 ⚫ 整数n是偶数，如果存在一个整数k使得n=2k;整数n是奇 数，如果存在一个整数k使得n=2k+1。 ⚫ 备注：一个整数要么是偶数，要么是奇数。 ⚫ 定理：若n是奇数，则n 2是奇数。 ⚫ 任意给定一个奇数n，存在一个整数k ，n=2k+1 ⚫ n 2=2(2k2+2k)+1 ⚫ n 2是奇数 ⚫ 所以，对任意奇数n，n 2是奇数。 n (Odd(n)→ Odd(n 2 ))

反证法 ·原理 p→q=q→ 证明框架 ●q→p 所以,p→q成立

反证法 ⚫ 原理 ⚫ p→q  ¬q→¬p ⚫ 证明框架 ⚫ ¬q  ¬p ⚫ 所以，p→ q 成立

反证法(举例) ·若3n+2是奇数,则n是奇数。 ●∥直接证明的设想不奏效。 假设结论不存立(-q) n是偶数,存在一个整数k使得n=2k ●3n+2=2(3k+1) 3n+2是偶数(-p) 因此,若3n+2是奇数,则n是奇数(p→q)

反证法（举例） ⚫ 若3n+2是奇数，则n是奇数。 ⚫ //直接证明的设想不奏效。 ⚫ 假设结论不存立(¬q) ⚫ n是偶数，存在一个整数k使得n=2k ⚫ 3n+2=2(3k+1) ⚫ 3n+2是偶数 (¬p) ⚫ 因此，若3n+2是奇数，则n是奇数 (p→ q)

归谬法 原理 ●qq→F 证明框架 ●q→r^r 所以,q成立

归谬法 ⚫ 原理 ⚫ q  ¬q→F ⚫ 证明框架 ⚫ ¬q  r¬r ⚫ 所以，q 成立

归谬法(举例) There is no rational number whose square is 2. ● Proof Extra hypothesis: (plg)2=2, and p, are integers which have no common factors except for 1. Then,p2=2q2→p2 is even is even→p2 is multiple of4 →q2 is even→ is even→p, have2 as common factor→ contradiction

归谬法（举例） ⚫ There is no rational number whose square is 2. ⚫ Proof ⚫ Extra hypothesis: (p/q) 2=2, and p,q are integers which have no common factors except for 1. ⚫ Then, p 2=2q 2  p 2 is even  p is even  p 2 is multiple of 4  q 2 is even  q is even  p,q have 2 as common factor  contradiction