第05章 证明技术

1、离离 散散 数数 学学20222022年年6 6月月1919日星期日日星期日电子科技大学计算机科学与工程学院电子科技大学计算机科学与工程学院48-48-2 22022-6-192022-6-19第第5 5章章 证明技术证明技术 数学归纳法数学归纳法 2按定义证明方法按定义证明方法3证明定理的方法证明定理的方法148-48-3 32022-6-192022-6-191.1 1.1 本章学习要求本章学习要求3证明定理的方证明定理的方法法2熟练掌握不熟练掌握不同证明方法同证明方法的证明原理、的证明原理、不同的应用不同的应用场景场景 一般掌握一般掌握了解了解48-48-4 45.2 5.2 证明定理的

2、方法证明定理的方法在定理证明中，如果将证明中的已知看成是命题逻在定理证明中，如果将证明中的已知看成是命题逻辑中的前提，将证明的结果看成是命题逻辑中的结辑中的前提，将证明的结果看成是命题逻辑中的结论，则大多数定理都是一个蕴涵关系。论，则大多数定理都是一个蕴涵关系。要证明逻辑关系要证明逻辑关系PQ，只需证明蕴涵式，只需证明蕴涵式PQ为永为永真公式。真公式。2022-6-192022-6-1948-48-5 55.2.1 5.2.1 基本证明技术基本证明技术1、直接证明、直接证明2022-6-192022-6-19例例5.2.1 5.2.1 证明：若证明：若n n是奇数，那么是奇数，那么n n2 2

3、是奇数。是奇数。 证明证明 假定这个蕴涵式的前件为真，即假定假定这个蕴涵式的前件为真，即假定n n为奇为奇数，则数，则n n2k+12k+1，其中，其中k k是整数。于是有：是整数。于是有： n n2 2(2k+1)(2k+1)2 2=4k=4k2 2+2k+1=2(2k+2k+1=2(2k2+k)+1)+1所以所以n n2 2是奇数。是奇数。 48-48-6 62022-6-192022-6-192、间接证明、间接证明因为因为PQ 等价于等价于 Q P。通过证明通过证明 Q P来证明来证明PQ的方式称为间接证的方式称为间接证明。明。48-48-7 72022-6-192022-6-19例例5

4、.2.2 5.2.2 设设n n是一个整数，证明：如果是一个整数，证明：如果n n2 2是奇数，那么是奇数，那么n n是奇是奇数。数。 证明证明 假设假设n n是偶数，则是偶数，则n n2k2k，这里，这里k k是一个整数。是一个整数。于是有：于是有： n n2 2(2k)(2k)2 2=4k=4k2 2=2(2k=2(2k2) )所以所以n n2 2是偶数。是偶数。 因而证明了若因而证明了若n n是偶数，则是偶数，则n n2 2是偶数，它是已知是偶数，它是已知命题的逆否式。因此，证明了所给的命题。命题的逆否式。因此，证明了所给的命题。 48-48-8 82022-6-192022-6-19例

5、例5.2.3 5.2.3 用间接证明方法证明：若用间接证明方法证明：若3n+23n+2是奇数，则是奇数，则n n是奇数。是奇数。 证明证明 假设假设n n是偶数，则是偶数，则n n2k2k，这里，这里k k是一个整数。是一个整数。于是有：于是有： 3 3n+2n+26k+2=2(3k+1)6k+2=2(3k+1)所以所以3 3n+2n+2是偶数。是偶数。它是已知命题的逆否式。因此，证明了所给的命题。它是已知命题的逆否式。因此，证明了所给的命题。 48-48-9 92022-6-192022-6-19例例5.2.45.2.4证明不存在有理数证明不存在有理数P/q其平方为其平方为2，即证明，即证明

6、 是无是无理数。理数。 证明证明 对某两个整数对某两个整数P和和q，假设，假设(P/q)2=2成立，并成立，并且且P和和q没有公因子。如果原来选择的没有公因子。如果原来选择的P、q具有公具有公因子，则可以用与它相等的无公因子的因子，则可以用与它相等的无公因子的P、q来取来取代它。代它。 于是于是P2=2q2，所以，所以P2是偶数，这就推出是偶数，这就推出P是偶是偶数，因为一个奇数的平方是奇数。数，因为一个奇数的平方是奇数。 因此存在某个整数因此存在某个整数n使得使得P2n成立。成立。2 248-48-10102022-6-192022-6-19例例5.2.4(5.2.4(续续) )因此因此2q

7、2P2(2n)2=4n2，即有即有q2=2n2，所以，所以q2是偶数，从而是偶数，从而q是偶数，于是是偶数，于是得到得到P和和q都是偶数，故它们有一个公因子都是偶数，故它们有一个公因子2，这与，这与假设相矛盾。假设相矛盾。 因此结论成立。因此结论成立。48-48-11115.2.2 5.2.2 几种典型的证明技术几种典型的证明技术对对蕴涵式蕴涵式PQ，其，其真值表真值表如下：如下：2022-6-192022-6-19PQPQO OO1O O111OO1111 1、空证明、空证明例例5.2.6 5.2.6 证明命题证明命题P(0)P(0)为真，其中为真，其中P(n)P(n)是命题函数是命题函数“

8、若若n1,n1,则则n nnn”48-48-12122.2.平凡证明平凡证明对对蕴涵式蕴涵式PQ，其，其真值表真值表如下：如下：2022-6-192022-6-19PQPQOO1O111OO1112 2、平凡证、平凡证明明例例5.2.7 5.2.7 证明命题证明命题P(0)P(0)为真，其中为真，其中P(n)P(n)是命题函数是命题函数“若若a,ba,b是整数，且是整数，且a=b,a=b,则则a an n=b=bn n”48-48-13133.3.归谬证明归谬证明对对蕴涵式蕴涵式PQ，其，其真值表真值表如下：如下：2022-6-192022-6-19PQPQOO1例例5.2.8 5.2.8 证

9、明证明“在任意在任意2222天中至少有天中至少有4 4天属于一个天属于一个星期的同一天星期的同一天”。对对 PQ ，假定可以找到矛盾式，假定可以找到矛盾式Q，使得，使得 PQ为真，即为真，即 PF为真为真，则命题，则命题 P必然为假，必然为假，从而从而P必为真。这种类型的证明称为必为真。这种类型的证明称为归谬证明归谬证明。48-48-14144 4 分情形证明分情形证明为了证明形如为了证明形如P1P2PnQ的蕴含式，可以的蕴含式，可以用重言式用重言式P1P2PnQ= (P1Q) (P2Q) (PnQ)来作为推理规则。这个推理规则说明来作为推理规则。这个推理规则说明，可以通过对，可以通过对i=1

10、，2，n分别证明每个蕴含式分别证明每个蕴含式(PiQ)来证明由命题来证明由命题P1，P2，Pn的析取式组成的析取式组成前件的原来的蕴含式。这种论证称为前件的原来的蕴含式。这种论证称为分情形证明分情形证明。2022-6-192022-6-1948-48-1515例例5.2.11 5.2.11 用分情形证明法证明用分情形证明法证明|xy|=|x|y|，其中，其中x和和y是实数。是实数。分析分析 令令P为为“x和和y是实数是实数”，Q为为“|xy|=|x|y|”注注意意P等价于等价于P1P2P3P4，其中，其中P1为为“x0y0”， P2为为“x0y0”， P3为为“x0y0”， P4为为“x0y0

11、”因此要证明因此要证明PQ，我们可以证明，我们可以证明(P1Q) ，(P2Q)，(P3Q)和和 (P4Q)。2022-6-192022-6-1948-48-1616证明证明很很显然显然(P1Q)，若，若x0y0，则，则xy0，因此，因此|xy|=xy=|x|y|；要证明要证明(P2Q)，若，若x0y0，则，则xy0，因此，因此|xy|= -xy=x(-y)=|x|y|(因为因为y0，我们有，我们有|y|=-y)；要证明要证明(P3Q)，若，若x0y0，则，则xy0，因此，因此|xy|= -xy=(-x)y=|x|y|；要证明要证明(P4Q)，若，若x0y0，则，则xy0，因此，因此|xy|=(

12、-x)(-y)=|x|y|。2022-6-192022-6-1948-48-17175 5、等价性证明等价性证明为了证明一个定理是双条件的，即形如为了证明一个定理是双条件的，即形如PQ的命的命题，其中题，其中P和和Q都是命题，可以使用重言式：都是命题，可以使用重言式：PQ=(PQ)(QP)即如果证明了蕴含式即如果证明了蕴含式“若若P则则Q”和和“若若Q则则P”，那么就可以证明命题那么就可以证明命题“P当且仅当当且仅当Q”。例例5.2.12 证明定理证明定理“整数整数n是奇数当且仅当是奇数当且仅当n2是奇是奇数数”。2022-6-192022-6-1948-48-18185.2.3 5.2.3

13、带量词的证明技术带量词的证明技术1、存在性证明、存在性证明许多定理都断言存在特定类型的对象。这种类型的许多定理都断言存在特定类型的对象。这种类型的定理形如定理形如( x)P(x)的命题，其中的命题，其中P为谓词，对形如为谓词，对形如( x)P(x)的命题的证明称为的命题的证明称为存在性证明存在性证明。2022-6-192022-6-1948-48-1919例例5.2.14 5.2.14 构造性的存在性证明。构造性的存在性证明。证明存在某个正整数，可以用两种不同的方式将其证明存在某个正整数，可以用两种不同的方式将其表示为正整数的立方和。表示为正整数的立方和。分析分析 只要能找到一个数，使得可以表

14、示成两组正整只要能找到一个数，使得可以表示成两组正整数的立方和即可。数的立方和即可。证明证明 经过大量的计算（如使用计算机搜索）可找到经过大量的计算（如使用计算机搜索）可找到 1729=103+93=123+13因为因为1729满足题设要求，所以得证。满足题设要求，所以得证。2022-6-192022-6-1948-48-20202 2、惟一性证明惟一性证明一些定理断言具有特定性质的元素惟一存在。换句一些定理断言具有特定性质的元素惟一存在。换句话说，这些定理断言恰有一个元素具有这个性质。话说，这些定理断言恰有一个元素具有这个性质。要证明这类命题，需要证明有某个元素具有这个性要证明这类命题，需要

15、证明有某个元素具有这个性质，且没有其他元素有此性质。质，且没有其他元素有此性质。惟一性证明惟一性证明的两个的两个部分如下：部分如下：存在性存在性：证明存在某个元素：证明存在某个元素x具有期望的性质。具有期望的性质。惟一性惟一性：证明若：证明若yx，则，则y不具有期望的性质。不具有期望的性质。2022-6-192022-6-1948-48-2121例例5.2.16 5.2.16 证明证明，如果，如果p是整数，那么存在惟一的整数是整数，那么存在惟一的整数q，使，使得得p+q=0。证明证明 显然存在一个整数显然存在一个整数q=-p使得使得p+q=0。另外要。另外要证明证明q的惟一性，假定有某个整数的

16、惟一性，假定有某个整数r且且rq，使得，使得p+r=0.那么那么p+q=p+r。从等式两边减去。从等式两边减去p，得出，得出q=r，这与假定，这与假定rq矛盾矛盾。因此因此，存在某个惟一的整数，存在某个惟一的整数q满足满足p+q=0。2022-6-192022-6-1948-48-22225.2.4 5.2.4 证明中的错误证明中的错误例例5.2.19 下面这个著名的假定下面这个著名的假定“证明证明”(即即1=2)错在哪里？错在哪里？“证明证明”步骤如下，其中步骤如下，其中a和和b是两个相等的正整数。是两个相等的正整数。步骤步骤 理由理由1a=b 给定的前提给定的前提2a2=ab 步骤步骤1两

17、边乘以两边乘以a3a2-b2=ab-b2 步骤步骤2两边减去两边减去b24(a-b)(a+b)=b(a-b) 步骤步骤3两边分解因式两边分解因式5a+b=b 步骤步骤4两边出去两边出去a-b62b=b 步骤步骤5把把a替换成替换成b，因为，因为a=b并化简并化简72=1 步骤步骤6两边除以两边除以b2022-6-192022-6-1948-48-2323例例5.2.20 5.2.20 下面的下面的“证明证明”错在哪里？错在哪里？“定理定理”：如果：如果n2是正数，则是正数，则n是正数是正数“证明证明”：假定：假定n2是正数。因为蕴含是正数。因为蕴含“如果如果n是正数是正数，则，则n2是正数是正

18、数”为真，所以可得为真，所以可得n是正数。是正数。解解 令令P(n)为为“n是正数是正数”，Q(n)为为“n2是正数是正数”，则，则前提是前提是Q(n)，命题，命题“如果如果n是正数，则是正数，则n2是正数是正数”也也就是就是( n)( P(n)Q(n)，从前提，从前提Q(n)和和( n)( P(n)Q(n)不能得出不能得出P(n)，因为没有使用有效的推理，因为没有使用有效的推理规则，相反，这是一个断言结论的谬误的实例，一个规则，相反，这是一个断言结论的谬误的实例，一个反例是当反例是当n=-1时，时，n2=1为正数，但为正数，但n却为负数。却为负数。2022-6-192022-6-1948-4

19、8-24242022-6-192022-6-195.3 5.3 数学归纳法数学归纳法 5.3.1 数学归纳法原理数学归纳法原理假设要证明的命题能写成形式假设要证明的命题能写成形式: nn0，有，有P(n) 其中其中n0是某个固定的整数，是某个固定的整数，即：希望证明对所有的整数即：希望证明对所有的整数nn0都有都有P(n)为真。为真。 48-48-25252022-6-192022-6-19数学归纳法原理数学归纳法原理假设假设 1）验证）验证nn0，有，有P(n0)为真；为真； (归纳基础归纳基础)2）假设对于）假设对于nk(kn0)，有，有P(k)为真；为真； (归纳假设归纳假设)3）证明）

20、证明nk1，有，有P(k+1)为真。为真。 (归纳结论归纳结论)结论结论 对所有的整数对所有的整数nn0，都有，都有P(n)为真。为真。谓词表示：谓词表示： ( n0)(P(n0)( n)(nk)P(k)P(k+1)1 48-48-2626例例5.3.2 5.3.2 用数学归纳法证明前用数学归纳法证明前n n个正奇数之和是个正奇数之和是n n2 2。分析分析 设用设用P(n)表示命题：前表示命题：前n个正奇数之和是个正奇数之和是n2。此时必须首先完成基础步骤：即必须证明此时必须首先完成基础步骤：即必须证明P(1)为真为真然后必须完成归纳步骤然后必须完成归纳步骤，即必须证明当假定即必须证明当假定

21、P(k)为为真时真时P(k+1)为真。为真。2022-6-192022-6-1948-48-2727例例5.3.2 5.3.2 证明证明证明证明归纳基础验证归纳基础验证 根据根据P(1)有：前有：前1个奇数之和为个奇数之和为12。这是真的，因为第。这是真的，因为第1个正奇数是个正奇数是1=12。归纳假设假定归纳假设假定 假定对正整数假定对正整数k来说来说P(k)为真；即：为真；即：1+3+5+(2k-1)=k2归纳结论证明归纳结论证明 需要证明需要证明P(k+1)为为真真，即，即 1+3+5+(2k-1)+(2k+1)= 1+3+5+(2k-1)+(2k+1)= k2+(2k+1) =(k+1

22、)2这样证明了从这样证明了从P(k)得出得出P(k+1)。注意在第二个等式里使。注意在第二个等式里使用了归纳假设用了归纳假设P(k)，以便用，以便用k2来代替前来代替前k个正奇数之和个正奇数之和。2022-6-192022-6-1948-48-28282022-6-192022-6-19强形式数学归纳法原理强形式数学归纳法原理 假设假设 1 1） 验证验证n nn n0 0 、n n0 0 +1+1，有，有P(nP(n0 0) )、 P(nP(n0 0+1)+1)为真；为真； ( (归纳基础归纳基础) )2 2）假设对于）假设对于n n k(knk(kn0 0) )，有，有P(n)P(n)为真

23、；为真； ( (归纳假设归纳假设) )3 3）证明）证明n nk k1 1，有，有P(k+1)P(k+1)为真。为真。 ( (归纳结论归纳结论) )结论结论 对所有的整数对所有的整数nnnn0 0，都有，都有P(n)P(n)为真。为真。谓词表示：谓词表示： ( n0)(P(n0)P(n0+1)( n)(nk)P(n)P(k+1)1 48-48-29292022-6-192022-6-19例例5.3.35.3.3用数学归纳法证明：用数学归纳法证明： 对所有对所有n1，有，有1+2+3+n= n n( (n n + + 1 1) )2 2证明证明 归纳基础验证归纳基础验证 1= 显然显然P(1)真

24、值为真值为1； 归纳假设假定归纳假设假定 对于对于n=k(k1)，有，有P(k)为真，为真，即有即有 1+2+3+k= ； 1 1( (1 1+ + 1 1) )2 2k k( (k k + + 1 1) )2 248-48-30302022-6-192022-6-19例例5.3.15.3.1证明证明归纳结论证明归纳结论证明 对于对于nk1，有，有P(k+1)为真为真 1+2+3+k+(k+1)= +(k+1) =由数学归纳法原理得到，由数学归纳法原理得到，P(n)对所有对所有n1为真。为真。k k( (k k + + 1 1) )2 2k(k +1)(k +2)(k +1)(k +1)+1)

25、(k +1)(+1) =22248-48-31312022-6-192022-6-19例例5.3.45.3.4对每个正整数对每个正整数n1，能惟一地写成，能惟一地写成 ，其中其中Pi是素数且满足是素数且满足P1P2Y) THEN 1. XX-Y b. ELSE 1. YY-X 2. RETURN(X) END OF FUNCTION GCD 48-48-36362022-6-192022-6-19证明证明归纳基础验证归纳基础验证 因为在循环开始之前存在变量值因为在循环开始之前存在变量值X0X，Y0Y，因此，因此，P(0)是命题是命题GCD(X0, Y0)GCD(X, Y)，显然命题为真；，显然

26、命题为真；归纳假设假定归纳假设假定 设设P(k)是命题是命题GCD(Xk, Yk)GCD(X, Y)为真；为真；48-48-37372022-6-192022-6-19证明证明( (续续) )归纳结论证明归纳结论证明 首先考虑首先考虑P(k1)的左边，的左边，即即GCD(Xk1, Yk1)。在通过。在通过k1次循环后，次循环后，或者或者Xk1Xk和和Yk1YkXk；或者或者Xk1XkYk和和Yk1Yk； 则由整数的基本性质知，则由整数的基本性质知，P(k1)GCD(Xk1, Yk1)GCD(Xk, Yk)GCD(X, Y)。 根据数学归纳法知：对所有根据数学归纳法知：对所有n 0，有，有P(n

27、)为真。为真。为此，该伪码程序输出的结果必是两个正整数的最为此，该伪码程序输出的结果必是两个正整数的最大公因子。大公因子。 48-48-38382022-6-192022-6-19铺瓦问题铺瓦问题例例5.3.2 一个一个直角三正方形直角三正方形，是一个由三个正方形，是一个由三个正方形组成的对象，如图组成的对象，如图1所示。如果我们从所示。如果我们从nn(n为为2的幂的幂)正方形的板中去掉一个正方形，则余下的图正方形的板中去掉一个正方形，则余下的图形可用直角三正方形来铺成，如图形可用直角三正方形来铺成，如图2。此处的铺成。此处的铺成是用直角三正方形正好覆盖全图的图形，每个直角是用直角三正方形正好

28、覆盖全图的图形，每个直角三正方形不能有重叠，也不许超出图形之外。我们三正方形不能有重叠，也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板，把此问题称缺少一个正方形的板称为一个缺方板，把此问题称为铺瓦问题。为铺瓦问题。 48-48-39392022-6-192022-6-19直角三正方形直角三正方形图图1 1图图2 22 2k k2 2k k2 2k k2 2k k2 2k k2 2k k2 2k k2 2k k图图3 348-48-40402022-6-192022-6-19证明证明归纳基础验证归纳基础验证 如如k1，22缺方板本身就是一个缺方板本身就是一个直角三正方形。因此可由三正方

29、形铺成；直角三正方形。因此可由三正方形铺成；归纳假设假定归纳假设假定 设我们可以把设我们可以把2k2k的缺方板用直的缺方板用直角三正方形铺成；角三正方形铺成；48-48-41412022-6-192022-6-19证明证明( (续续) )归纳结论证明部分归纳结论证明部分 对于对于2k12k1的缺方板问题，的缺方板问题，我们可以将其分成四个我们可以将其分成四个2k2k的板，如图所示。旋转的板，如图所示。旋转此板，使缺少的正方形在左上的四分之一中。由归此板，使缺少的正方形在左上的四分之一中。由归纳假设，此左上的纳假设，此左上的2k2k缺方板可由直角三正方形铺缺方板可由直角三正方形铺成，把一个直角三正方形成，把一个直角三正方形T放在中间，则另外三个四放在中间，则另外三个四分之一都是分之一都是2k2k的缺方板。由归纳假设，它们的铺的缺方板。由归纳假设，它们的铺瓦问题都是可以解决的。于是瓦问题都是可以解决的。于是2k12k1的缺方板可的缺方板可由直角三正方形铺成。由直角三正方形铺成。 由数学归纳法知，对任何的由数学归纳法知，对任何的n，nn正方形的铺正方形的铺瓦问题都是可以铺成的。瓦问题都是可以铺成的。 48-48-42422022-6-192022-6-195.4 5.4 按定义证明方法按定义证明方法 在离散数学中，我们大量的定义描述都是用在离散数学中，我们大量的定义描述都是用蕴涵型蕴涵