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

Presentation on theme: "离散数学─逻辑和证明 南京大学计算机科学与技术系"— Presentation transcript:

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

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

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

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

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

6 直接证明 定义 定理：若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))

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

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

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

10 归谬法（举例） 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

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

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

13 分情形证明（举例） 当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

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

15 存在性证明 证明目标 构造性证明 非构造性证明 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即为所求。

16 唯一性证明 证明目标 举例，设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有唯一的解。

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

18 证明中的错误 以下证明“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

19 数学与猜想（费马大定理） 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年时间） 椭圆曲线理论

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

21 数学与猜想（四色猜想） 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 ( , Britain) proved the five color theorem in 1890

22 世界数学难题 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

23 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

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