第5章证明技术.ppt

* 例5.3.4 对每个正整数n≥1，能惟一地写成 ， 其中Pi是素数且满足P1P2…Ps。 分析 设P(n) ：n＝ ； 由于素数一定是大于等于2的正整数，因此，n0＝2。 * 例5.3.4 证明 归纳基础验证 因为2=21，3=31，所以P(2)、P(3)为真； 归纳假设假定 对n≤k的所有正整数，都有P(n)为真，即 n＝ * 例5.3.4(续) 归纳结论证明 对n＝k＋1，需分两种情况讨论： （1） 如果n本身就是一个素数，则k＋1＝(k+1)1，即P(k+1)为真； （2） 如果n不是一个素数，则k＋1＝lm，其中2≤l≤k，2≤m≤k，此时由归纳假设有 l＝ ， m＝ 其中，P1, P2, …, Ps是素数，且是包含l、m中全部分解因子， bi、ci≥0的自然数， * 例5.3.4(续) 为此有 k＋1＝lm＝ ＝ ＝ 由于P1, P2, …, Ps是素数，所以k+1能分解成素数的积，又因为l和m的因子分解是惟一的，所以k＋1的因子分解也是惟一的，所以P(k+1)是真的。由数学归纳法原理得到，P(n)对所有n≥1为真。 * 5.3.3 数学归纳法应用 例5.3.1 用数学归纳法证明下列伪码程序的计算结果是两个正整数的最大公因子。其中伪码程序为： FUNCTION GCD(X, Y) 1. WHILE (X?Y) a. IF (XY) THEN 1. X?X-Y b. ELSE 1. Y?Y-X 2. RETURN(X) END OF FUNCTION GCD * 证明 归纳基础验证 因为在循环开始之前存在变量值X0＝X，Y0＝Y，因此，P(0)是命题GCD(X0, Y0)＝GCD(X, Y)，显然命题为真； 归纳假设假定 设P(k)是命题GCD(Xk, Yk)＝GCD(X, Y)为真； * 证明(续) 归纳结论证明 首先考虑P(k＋1)的左边， 即GCD(Xk＋1, Yk＋1)。在通过k＋1次循环后， 或者Xk＋1＝Xk和Yk＋1＝Yk－Xk； 或者Xk＋1＝Xk－Yk和Yk＋1＝Yk； 则由整数的基本性质知，P(k＋1)＝GCD(Xk＋1, Yk＋1)＝GCD(Xk, Yk)＝GCD(X, Y)。 根据数学归纳法知：对所有n?0，有P(n)为真。为此，该伪码程序输出的结果必是两个正整数的最大公因子。 * 铺瓦问题 例5.3.2 一个直角三正方形，是一个由三个正方形组成的对象，如图1所示。如果我们从n×n(n为2的幂)正方形的板中去掉一个正方形，则余下的图形可用直角三正方形来铺成，如图2。此处的铺成是用直角三正方形正好覆盖全图的图形，每个直角三正方形不能有重叠，也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板，把此问题称为铺瓦问题。 * 直角三正方形 图1 图2 2k×2k 2k×2k 2k×2k 2k×2k 图3 * 证明 归纳基础验证 如k＝1，2×2缺方板本身就是一个直角三正方形。因此可由三正方形铺成； 归纳假设假定 设我们可以把2k×2k的缺方板用直角三正方形铺成； * 证明(续) 归纳结论证明部分 对于2k＋1×2k＋1的缺方板问题，我们可以将其分成四个2k×2k的板，如图所示。旋转此板，使缺少的正方形在左上的四分之一中。由归纳假设，此左上的2k×2k缺方板可由直角三正方形铺成，把一个直角三正方形T放在中间，则另外三个四分之一都是2k×2k的缺方板。由归纳假设，它们的铺瓦问题都是可以解决的。于是2k＋1×2k＋1的缺方板可由直角三正方形铺成。 由数学归纳法知，对任何的n，n×n正方形的铺瓦问题都是可以铺成的。 * 5.4 按定义证明方法 在离散数学中，我们大量的定义描述都是用蕴涵型“P→Q”的方式来描述的。 如集合中子集的包含关系的定义描述为： A ? B ? (?a)(a∈A→a∈B) * 5.4.1 按定义证明方法原理 加上题目中的已知G1, G2,…,Gn 证明问题H中的Q 规则触发 引用公理 引入证明问题H中的 P 设有一组前提(或叫做已知条件)为Г={G1,G2, …,Gn}，证明问题H