（本科）第5章 证明技术ppt课件.ppt

《（本科）第5章 证明技术ppt课件.ppt》由会员分享，可在线阅读，更多相关《（本科）第5章 证明技术ppt课件.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程主讲人：（本科）第（本科）第5 5章章 证明技术证明技术pptppt课件课件电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程离离 散散 数数 学学20222022年年5 5月月1616日星期一日星期一电子科技大学离散数学课程组电子科技大学离散数学课程组电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-32022-5-162022-5-16第第5 5章章 证明技术证明技术 数学归纳法数学归纳法 2按定义证明方法按定义证明方法3证明定理的方法证明定理的方法1电子科技大学离散数

2、学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-42022-5-162022-5-161.1 1.1 本章学习要求本章学习要求3证明定理的方证明定理的方法法2熟练掌握不熟练掌握不同证明方法同证明方法的证明原理、的证明原理、不同的应用不同的应用场景场景 一般掌握一般掌握了解了解电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-55.2 5.2 证明定理的方法证明定理的方法在定理证明中，如果将证明中的已知看成是命题逻在定理证明中，如果将证明中的已知看成是命题逻辑中的前提，将证明的结果看成是命

3、题逻辑中的结辑中的前提，将证明的结果看成是命题逻辑中的结论，则大多数定理都是一个蕴涵关系。论，则大多数定理都是一个蕴涵关系。要证明逻辑关系要证明逻辑关系PQ，只需证明蕴涵式，只需证明蕴涵式PQ为永为永真公式。真公式。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-65.2.1 5.2.1 基本证明技术基本证明技术1、直接证明、直接证明2022-5-162022-5-16例例5.2.1 5.2.1 证明：若证明：若n n是奇数，那么是奇数，那么n n2 2是奇数。是奇数。 证明证明 假定这个蕴涵式

4、的前件为真，即假定假定这个蕴涵式的前件为真，即假定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-72022-5-162022-5-162、间接证明、间接证明因为因为PQ 等价于等价于 Q P。通过证明通过证明 Q P来证明来证明PQ的方式称为间接证的方式称为间接证明。明。电子科

5、技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-82022-5-162022-5-16例例5.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是偶数，它是已知

6、是偶数，它是已知命题的逆否式。因此，证明了所给的命题。命题的逆否式。因此，证明了所给的命题。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-92022-5-162022-5-16例例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是偶数。是偶数

7、。它是已知命题的逆否式。因此，证明了所给的命题。它是已知命题的逆否式。因此，证明了所给的命题。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-102022-5-162022-5-16例例证明不存在有理数证明不存在有理数P/q其平方为其平方为2，即证明，即证明 是无是无理数。理数。 证明证明 对某两个整数对某两个整数P和和q，假设，假设(P/q)2=2成立，并成立，并且且P和和q没有公因子。如果原来选择的没有公因子。如果原来选择的P、q具有公具有公因子，则可以用与它相等的无公因子的因子，则可以用与它相等的无公因子的P、q来取来取代

8、它。代它。 于是于是P2=2q2，所以，所以P2是偶数，这就推出是偶数，这就推出P是偶是偶数，因为一个奇数的平方是奇数。数，因为一个奇数的平方是奇数。 因此存在某个整数因此存在某个整数n使得使得P2n成立。成立。2 2电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-112022-5-162022-5-16例例5.2.4(5.2.4(续续) )因此因此2q2P2(2n)2=4n2，即有即有q2=2n2，所以，所以q2是偶数，从而是偶数，从而q是偶数，于是是偶数，于是得到得到P和和q都是偶数，故它们有一个公因子都是偶数，故它们有一个公

9、因子2，这与，这与假设相矛盾。假设相矛盾。 因此结论成立。因此结论成立。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-125.2.2 5.2.2 几种典型的证明技术几种典型的证明技术对对蕴涵式蕴涵式PQ，其，其真值表真值表如下：如下：2022-5-162022-5-16PQPQOO1O111OO111例例5.2.6 5.2.6 证明命题证明命题P(0)P(0)为真，其中为真，其中P(n)P(n)是命题函数是命题函数“若若n1,n1,则则n nnn”电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程

10、双语示范课程双语示范课程48-132.2.平凡证明平凡证明对对蕴涵式蕴涵式PQ，其，其真值表真值表如下：如下：2022-5-162022-5-16PQPQOO1O111OO111例例5.2.7 5.2.7 证明命题证明命题P(0)P(0)为真，其中为真，其中P(n)P(n)是命题函数是命题函数“若若a,ba,b是整数，且是整数，且ab,ab,则则a an nbbn n”电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-143.3.归谬证明归谬证明对对蕴涵式蕴涵式PQ，其，其真值表真值表如下：如下：2022-5-162022-5-16

11、PQPQOO1例例5.2.8 5.2.8 证明证明“在任意在任意2222天中至少有天中至少有4 4天属于一个天属于一个星期的同一天星期的同一天”。对对 PQ ，假定可以找到矛盾式，假定可以找到矛盾式Q，使得，使得 PQ为真，即为真，即 PF为真，则命题为真，则命题 P必然为假，必然为假，从而从而P必为真。这种类型的证明称为必为真。这种类型的证明称为归谬证明归谬证明。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-154 4 分情形证明分情形证明为了证明形如为了证明形如P1P2PnQ的蕴含式，可以的蕴含式，可以用重言式用重言式P1P

12、2PnQ= (P1Q) (P2Q) (PnQ)来作为推理规则。这个推理规则说来作为推理规则。这个推理规则说明，可以通过对明，可以通过对i=1，2，n分别证明每个蕴含分别证明每个蕴含式式(PiQ)来证明由命题来证明由命题P1，P2，Pn的析取式的析取式组成前件的原来的蕴含式。这种论证称为组成前件的原来的蕴含式。这种论证称为分情形证分情形证明明。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-16例例5.2.11 5.2.11 用分情形证明法证明用分情形证明法证明|xy|=|x|y|，其中，其中x和

13、和y是实数。是实数。分析分析 令令P为为“x和和y是实数是实数”，Q为为“|xy|=|x|y|”注注意意P等价于等价于P1P2P3P4，其中，其中P1为为“x0y0”， P2为为“x0y0”， P3为为“x0y0”， P4为为“x0y0”因此要证明因此要证明PQ，我们可以证明，我们可以证明(P1Q) ，(P2Q)，(P3Q)和和 (P4Q)。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-17证明证明很显然很显然(P1Q)，若，若x0y0，则，则xy0，因此，因此|xy|=xy=|x|y|；要证

14、明要证明(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|=(-x)(-y)=|x|y|。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-185 5、等价性证明、等价性证明为了证明一个定理是双条件的，即形如为了证明一个定理是双条件

15、的，即形如PQ的命的命题，其中题，其中P和和Q都是命题，可以使用重言式：都是命题，可以使用重言式：PQ=(PQ)(QP)即如果证明了蕴含式即如果证明了蕴含式“若若P则则Q”和和“若若Q则则P”，那么就可以证明命题那么就可以证明命题“P当且仅当当且仅当Q”。例例5.2.12 证明定理证明定理“整数整数n是奇数当且仅当是奇数当且仅当n2是奇是奇数数”。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-195.2.3 5.2.3 带量词的证明技术带量词的证明技术1、存在性证明、存在性证明许多定理都断言存

16、在特定类型的对象。这种类型的许多定理都断言存在特定类型的对象。这种类型的定理形如定理形如( x)P(x)的命题，其中的命题，其中P为谓词，对形如为谓词，对形如( x)P(x)的命题的证明称为的命题的证明称为存在性证明存在性证明。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-20例例5.2.14 5.2.14 构造性的存在性证明。构造性的存在性证明。证明存在某个正整数，可以用两种不同的方式将其证明存在某个正整数，可以用两种不同的方式将其表示为正整数的立方和。表示为正整数的立方和。分析分析 只要能

17、找到一个数，使得可以表示成两组正整只要能找到一个数，使得可以表示成两组正整数的立方和即可。数的立方和即可。证明证明 经过大量的计算（如使用计算机搜索）可找到经过大量的计算（如使用计算机搜索）可找到 1729=103+93=123+13因为因为1729满足题设要求，所以得证。满足题设要求，所以得证。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-212 2、惟一性证明、惟一性证明一些定理断言具有特定性质的元素惟一存在。换句一些定理断言具有特定性质的元素惟一存在。换句话说，这些定理断言恰有一个元素具

18、有这个性质话说，这些定理断言恰有一个元素具有这个性质。要证明这类命题，需要证明有某个元素具有这。要证明这类命题，需要证明有某个元素具有这个性质，且没有其他元素有此性质。个性质，且没有其他元素有此性质。惟一性证明惟一性证明的两个部分如下：的两个部分如下：存在性存在性：证明存在某个元素：证明存在某个元素x具有期望的性质。具有期望的性质。惟一性惟一性：证明若：证明若yx，则，则y不具有期望的性质。不具有期望的性质。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-22例例5.2.16 5.2.16 证明

19、，如果证明，如果p是整数，那么存在惟一的整数是整数，那么存在惟一的整数q，使，使得得p+q=0。证明证明 显然存在一个整数显然存在一个整数q=-p使得使得p+q=0。证明证明q的惟一性，假定有某个整数的惟一性，假定有某个整数r且且rq，使得，使得p+r=0.那么那么p+q=p+r。从等式两边减去。从等式两边减去p，得出，得出q=r，这与假定，这与假定rq矛盾。矛盾。因此，存在某个惟一的整数因此，存在某个惟一的整数q满足满足p+q=0。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-235.2.4

20、 5.2.4 证明中的错误证明中的错误例例5.2.19 下面这个著名的假定下面这个著名的假定“证明证明”(即即1=2)错在哪里？错在哪里？“证明证明”步骤如下，其中步骤如下，其中a和和b是两个相等的正整数。是两个相等的正整数。步骤步骤 理由理由1a=b 给定的前提给定的前提2a2=ab 步骤步骤1两边乘以两边乘以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两边除以两边除以b

21、2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-24例例5.2.20 5.2.20 下面的下面的“证明证明”错在哪里？错在哪里？“定理定理”：如果：如果n2是正数，则是正数，则n是正数是正数“证明证明”：假定：假定n2是正数。因为蕴含是正数。因为蕴含“如果如果n是正数是正数，则，则n2是正数是正数”为真，所以可得为真，所以可得n是正数。是正数。解解 令令P(n)为为“n是正数是正数”，Q(n)为为“n2是正数是正数”，则，则前提是前提是Q(n)，命题，命题“如果如果n是正数，则是正数，则n2是正

22、数是正数”也也就是就是( n)( P(n)Q(n)，从前提，从前提Q(n)和和( n)( P(n)Q(n)不能得出不能得出P(n)，因为没有使用有效的推理，因为没有使用有效的推理规则，相反，这是一个断言结论的谬误的实例，一个规则，相反，这是一个断言结论的谬误的实例，一个反例是当反例是当n=-1时，时，n2=1为正数，但为正数，但n却为负数。却为负数。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-252022-5-162022-5-165.3 5.3 数学归纳法数学归纳法 5.3.1 数学归纳法

23、原理数学归纳法原理假设要证明的命题能写成形式假设要证明的命题能写成形式: nn0，有，有P(n) 其中其中n0是某个固定的整数，是某个固定的整数，即：希望证明对所有的整数即：希望证明对所有的整数nn0都有都有P(n)为真。为真。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-262022-5-162022-5-16数学归纳法原理数学归纳法原理假设假设 1）验证）验证nn0，有，有P(n0)为真；为真； (归纳基础归纳基础)2）假设对于）假设对于nk(kn0)，有，有P(k)为真；为真；(归纳假设归纳假设)3）证明）证明nk1，有

24、，有P(k+1)为真。为真。 (归纳结论归纳结论)结论结论 对所有的整数对所有的整数nn0，都有，都有P(n)为真。为真。谓词表示：谓词表示： ( n0)(P(n0)( n)(nk)P(k)P(k+1)1 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-27例例5.3.2 5.3.2 用数学归纳法证明前用数学归纳法证明前n n个正奇数之和是个正奇数之和是n n2 2。分析分析 设用设用P(n)表示命题：前表示命题：前n个正奇数之和是个正奇数之和是n2。此时必须首先完成基础步骤：即必须证明此时必须首先完成基础步骤：即必须证明P(1)

25、为真为真然后必须完成归纳步骤然后必须完成归纳步骤，即必须证明当假定即必须证明当假定P(k)为为真时真时P(k+1)为真。为真。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-28例例5.3.2 5.3.2 证明证明证明归纳基础验证证明归纳基础验证 根据根据P(1)有：前有：前1个奇数之和为个奇数之和为12。这是真的，因为第。这是真的，因为第1个正奇数是个正奇数是1=12。归纳假设假定归纳假设假定 假定对正整数假定对正整数k来说来说P(k)为真；即：为真；即：1+3+5+(2k-1)=k2归纳结论

26、证明归纳结论证明 需要证明需要证明P(k+1)为真为真，即，即 1+3+5+(2k-1)+(2k+1)= 1+3+5+(2k-1)+(2k+1)= k2+(2k+1) =(k+1)2这样证明了从这样证明了从P(k)得出得出P(k+1)。注意在第二个等式里使。注意在第二个等式里使用了归纳假设用了归纳假设P(k)，以便用，以便用k2来代替前来代替前k个正奇数之个正奇数之和。和。2022-5-162022-5-16电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-292022-5-162022-5-16强形式数学归纳法原理强形式数学归纳法

27、原理 假设假设 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)为真；为真； ( (归纳假设归纳假设) )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

28、+1)1 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-302022-5-162022-5-16例例用数学归纳法证明：用数学归纳法证明： 对所有对所有n1，有，有1+2+3+n= n n( (n n + + 1 1) )2 2证明证明 归纳基础验证归纳基础验证 1= 显然显然P(1)真值为真值为1； 归纳假设假定归纳假设假定 对于对于n=k(k1)，有，有P(k)为真，为真，即有即有 1+2+3+k= ； 1 1( (1 1+ + 1 1) )2 2k k( (k k + + 1 1) )2 2电子科技大学离散数学课程组电子科技

29、大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-312022-5-162022-5-16例例证明证明归纳结论证明归纳结论证明 对于对于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)(k +1)(+1) =222电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-322022-5-162022

30、-5-16例例对每个正整数对每个正整数n1，能惟一地写成，能惟一地写成 ，其中其中Pi是素数且满足是素数且满足P1P2Y) THEN 1. XX-Y b. ELSE 1. YY-X 2. RETURN(X) END OF FUNCTION GCD 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-372022-5-162022-5-16证明证明归纳基础验证归纳基础验证 因为在循环开始之前存在变量值因为在循环开始之前存在变量值X0X，Y0Y，因此，因此，P(0)是命题是命题GCD(X0, Y0)GCD(X, Y)，显然命题为真；，显然

31、命题为真；归纳假设假定归纳假设假定 设设P(k)是命题是命题GCD(Xk, Yk)GCD(X, Y)为真；为真；电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-382022-5-162022-5-16证明证明( (续续) )归纳结论证明归纳结论证明 首先考虑首先考虑P(k1)的左边，的左边，即即GCD(Xk1, Yk1)。在通过。在通过k1次循环后，次循环后，或者或者Xk1Xk和和Yk1YkXk；或者或者Xk1XkYk和和Yk1Yk； 则由整数的基本性质知，则由整数的基本性质知，P(k1)GCD(Xk1, Yk1)GCD(Xk,

32、Yk)GCD(X, Y)。 根据数学归纳法知：对所有根据数学归纳法知：对所有n 0，有，有P(n)为真。为真。为此，该伪码程序输出的结果必是两个正整数的最为此，该伪码程序输出的结果必是两个正整数的最大公因子。大公因子。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-392022-5-162022-5-16铺瓦问题铺瓦问题例例 一个一个直角三正方形直角三正方形，是一个由三个正方形组成，是一个由三个正方形组成的对象，如图的对象，如图1所示。如果我们从所示。如果我们从nn(n为为2的幂的幂)正方形的板中去掉一个正方形，则余下的图形可用

33、正方形的板中去掉一个正方形，则余下的图形可用直角三正方形来铺成，如图直角三正方形来铺成，如图2。此处的铺成是用直。此处的铺成是用直角三正方形正好覆盖全图的图形，每个直角三正方角三正方形正好覆盖全图的图形，每个直角三正方形不能有重叠，也不许超出图形之外。我们缺少一形不能有重叠，也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板，把此问题称为铺瓦个正方形的板称为一个缺方板，把此问题称为铺瓦问题。问题。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-402022-5-162022-5-16直角三正方形直角三正方形图图1 1图图2

34、 22 2k k2 2k k2 2k k2 2k k2 2k k2 2k k2 2k k2 2k k图图3 3电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-412022-5-162022-5-16证明证明归纳基础验证归纳基础验证 如如k1，22缺方板本身就是一个缺方板本身就是一个直角三正方形。因此可由三正方形铺成；直角三正方形。因此可由三正方形铺成；归纳假设假定归纳假设假定 设我们可以把设我们可以把2k2k的缺方板用直的缺方板用直角三正方形铺成；角三正方形铺成；电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国

35、家级精品课程 双语示范课程双语示范课程48-422022-5-162022-5-16证明证明( (续续) )归纳结论证明部分归纳结论证明部分 对于对于2k12k1的缺方板问题，的缺方板问题，我们可以将其分成四个我们可以将其分成四个2k2k的板，如图所示。旋转的板，如图所示。旋转此板，使缺少的正方形在左上的四分之一中。由归此板，使缺少的正方形在左上的四分之一中。由归纳假设，此左上的纳假设，此左上的2k2k缺方板可由直角三正方形铺缺方板可由直角三正方形铺成，把一个直角三正方形成，把一个直角三正方形T放在中间，则另外三个四放在中间，则另外三个四分之一都是分之一都是2k2k的缺方板。由归纳假设，它们的

36、铺的缺方板。由归纳假设，它们的铺瓦问题都是可以解决的。于是瓦问题都是可以解决的。于是2k12k1的缺方板可的缺方板可由直角三正方形铺成。由直角三正方形铺成。 由数学归纳法知，对任何的由数学归纳法知，对任何的n，nn正方形的铺正方形的铺瓦问题都是可以铺成的。瓦问题都是可以铺成的。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-432022-5-162022-5-165.4 5.4 按定义证明方法按定义证明方法 在离散数学中，我们大量的定义描述都是用在离散数学中，我们大量的定义描述都是用蕴涵型蕴涵型“PQ”的方式来描述的。的方式来描

37、述的。如集合中子集的包含关系的定义描述为：如集合中子集的包含关系的定义描述为：A B ( a)(aAaB)电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-442022-5-162022-5-165.4.1 5.4.1 按定义证明方法原理按定义证明方法原理加上题目中加上题目中的 已 知的 已 知 G1, G2,Gn证明问题证明问题H中的中的Q规则触发规则触发引用公理引用公理引入证明问引入证明问题题H中的中的 P 设有一组前提设有一组前提(或叫做已知条件或叫做已知条件)为为=G1,G2,Gn，证明问题，证明问题H = PQ，则利用，则

38、利用CP规则的证规则的证明方式，将证明问题明方式，将证明问题H中的前提中的前提P作为附加前提，加作为附加前提，加入到前提集合当中，构成一组新前提入到前提集合当中，构成一组新前提=G1,G2,Gn,P，此时，证明这组新前提，此时，证明这组新前提 Q Q，即有，即有 H Q QCPCP电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-452022-5-162022-5-165.4.2 5.4.2 按定义证明方法应用按定义证明方法应用例例 设设A、B是两个任意集合，证明是两个任意集合，证明 A B P(A) P(B) 证明证明 （1）必要

39、性必要性“”： 对任意对任意xP(A)， 则则x A， 由于由于A B， 所以所以x B，即，即 有有xP(B)。P(A) P(B)。 即即 A B P(A) P(B) 由由CP规则知：规则知：电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-462022-5-162022-5-16例例5.4.1(5.4.1(续续) )（2）充分性充分性“”： 对任意对任意xA，则，则xP(A)，由于，由于P(A) P(B)，所以所以xP(B)，即有，即有xB。由。由CP规则知：规则知：A B。 即即 P(A) P(B) A B。 原式得证。原式得

40、证。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-472022-5-162022-5-16例例5.4.2 5.4.2 如果如果A B，则，则ABB且且ABA 证明证明两个集合相等两个集合相等，即是证明，即是证明两个集合相互包两个集合相互包含含，请学生自证。，请学生自证。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程48-482022-5-162022-5-162. 2. 4.4.6.6.8.8.10.10.13.13.16.16.19(1)19(1)22222828习题习题156156158158页页注意注意下次上课时：下次上课时：交作业；交作业；1)单元测验单元测验电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程