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

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

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

引言 定理（theorem） 证明（proof） 定理证明中可以使用的陈述： 表明陈述（定理）为真的有效论证。 （当前）定理的前提 能够被证明为真的陈述，通常是比较重要的陈述。 证明（proof） 表明陈述（定理）为真的有效论证。 定理证明中可以使用的陈述： （当前）定理的前提 已经证明的定理（推论、命题、引理） 公理（假定） 术语的定义 猜想（conjecture）

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

直接证明 定义 定理：若n是奇数，则n2是奇数。 整数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 (Odd(n) Odd(n2))

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

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

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

归谬法（举例） 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, p2=2q2  p2 is even  p is even  p2 is multiple of 4  q2 is even  q is even  p,q have 2 as common factor  contradiction

反证法（广义） 原理 证明框架 p1 ...  pn  q  ¬q  p1  ...  pn  F ¬q, p1, ..., pn  矛盾 (比如p1 ¬ p1) 所以， p1 ...  pn  q

分情形证明 原理 证明框架 p1 ...  pn  q  (p1  q)  ...  (pn  q) p1 q …

分情形证明（举例） 当n是一个正整数，且n4时，(n+1)33n。 当n是一个整数时，有n2n。 (x+y)r < xr+yr, 这里x, y是正实数, r是0<r<1的实数. 不失一般性，假设x+y=1. x < xr， y < yr  x+y < xr+yr  (x+y)r < xr+yr

等价性证明 原理 证明框架 [ p1p2…pn] [( p1p2) ( p2p3) …( pnp1)] p1 p2

存在性证明 证明目标 构造性证明 非构造性证明 x P(x) 存在这样的正整数，有两种方式表示为正整数的立方和。 1729=103+93=123+13 非构造性证明 存在无理数x和y 使得x y是有理数 y2=2，x= y y，x y=(y y) y=y2=2 若x是无理数， x和y即为所求；否则，y和y即为所求。

唯一性证明 证明目标 举例，设a0, ax+b=c有唯一的解。 x (P(x)  y (yxP(y) ) x P(x)  y z (P(y)  P(z)  y = z) 举例，设a0, ax+b=c有唯一的解。

寻找反例 原理 举例 x P(x) x P(x) 每个正整数都是两个整数的平方和 3 每个正整数都是三个整数的平方和 7 每个正整数都是四个整数的平方和？

证明中的错误 以下证明“2=1”，错在哪里？ a=b 假设a和b是两个相等的正整数 a2=ab 两边乘以a a2-b2=ab-b2 两边减去b2 (a-b) (a+b) = (a-b) b (a+b) = b 两边除以(a-b) 2b = b 2 = 1

数学与猜想（费马大定理） Pierre de Fermat (1601-1665), France Fermat’s Last Theorem (1637) （费马大定理） xn+yn=zn (n2, xyz0)没有整数解 Andrew Wiles (1953- ), Oxford, England 1994/1995完成了费马大定理的证明（约10年时间） 椭圆曲线理论

数学与猜想（哥德巴赫猜想） Goldbach Conjecture（1742年给欧拉的信中） 欧拉版本（在给哥德巴赫的回信中） 任一大于5的整数都可写成三个质数之和。 欧拉版本（在给哥德巴赫的回信中） 任一大于2的偶数都可写成两个质数之和。 “a+b”猜想 任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和。 1966年陈景润（1933－1996）证明了“1+2”猜想

数学与猜想（四色猜想） Four Color Theorem Proposed by in Francis Guthrie 1852 Proven in 1976 by Kenneth Ira Appel (1932-, New York) and Wolfgang Haken (1928-, Berlin) Percy John Heawood (1861-1955, Britain) proved the five color theorem in 1890

世界数学难题 Hilbert’s problems (23), ICM’1900, Paris Millennium Prize Problems(7) by the Clay Mathematics Institute in 2000 1. P versus NP problem 2. Hodge conjecture 3. Poincaré conjecture (solved by Perelman) 4. Riemann hypothesis 5. Yang–Mills existence and mass gap 6. Navier–Stokes existence and smoothness 7. Birch and Swinnerton-Dyer conjecture

Grigori Perelman (1966-, Russian) In November 2002, Perelman posted the first of a series of eprints to the arXiv, ... He declined to accept Fields Medal award in 2006 Millennium Prize award in 2010

作业 教材内容：[Rosen] 1.6—1.7节 课后习题： 见课程主页或者微信群