离散数学第5章证明技术

离散数学电子科技大学计算机科学与工程学院主讲教师 王庆先Tel：

QQ:6176754242021年7月6日星期二第5章 证明技术数学归纳法2按定义证明方法3证明定理的方法2021/7/611.1本章学习要求3证明定理的方法一般掌握2熟练掌握不同证明方法的证明原理、不同的应用场景了解2021/7/65.2证明定理的方法2021/7/6在定理证明中，如果将证明中的已知看成是命题逻辑中的前提，将证明的结果看成是命题逻辑中的结论，则大多数定理都是一个蕴涵关系。要证明逻辑关系PQ，只需证明蕴涵式P→Q为永真公式。5.2.1基本证明技术2021/7/61、直接证明例5.2.1

证明：若n是奇数，那么n2是奇数。证明

假定这个蕴涵式的前件为真，即假定n为奇数，则n＝2k+1，其中k是整数。于是有：n2＝(2k+1)2=4k2+2k+1=2(2k2+k)+1所以n2是奇数。2、间接证明2021/7/6因为P→Q

等价于

Q→

P。通过证明

Q→

P来证明P→Q的方式称为间接证明。例5.2.22021/7/6设n是一个整数，证明：如果n2是奇数，那么n是奇数。证明

假设n是偶数，则n＝2k，这里k是一个整数。于是有：n2＝(2k)2=4k2=2(2k2)所以n2是偶数。因而证明了若n是偶数，则n2是偶数，它是已知命题的逆否式。因此，证明了所给的命题。例5.2.32021/7/6用间接证明方法证明：若3n+2是奇数，则n是奇数。证明

假设n是偶数，则n＝2k，这里k是一个整数。于是有：3n+2＝6k+2=2(3k+1)所以3n+2是偶数。它是已知命题的逆否式。因此，证明了所给的命题。例5.2.4证明不存在有理数P/q其平方为2，即证明2

是无理数。证明对某两个整数P和q，假设(P/q)2=2成立，并且P和q没有公因子。如果原来选择的P、q具有公因子，则可以用与它相等的无公因子的P、q来取代它。于是P2=2q2，所以P2是偶数，这就推出P是偶数，因为一个奇数的平方是奇数。因此存在某个整数n使得P＝2n成立。2021/7/6例5.2.4(续)2021/7/6因此2q2＝P2＝(2n)2=4n2，即有q2=2n2，所以q2是偶数，从而q是偶数，于是得到P和q都是偶数，故它们有一个公因子2，这与假设相矛盾。因此结论成立。5.2.2几种典型的证明技术对蕴涵式P→Q，其真值表如下：PQP→QOO1O111OO1、空证明2021/7/61

1

1例5.2.6证明命题P(0)为真，其中P(n)是命题函数

“若n>1,则n²>n”2.平凡证明对蕴涵式P→Q，其真值表如下：PQP→QOO1O111OO2、平凡证明1

1

1例5.2.7证明命题P(0)为真，其中P(n)是命题函数

“若a,b是整数，且a>b,则an>bn”2021/7/63.归谬证明对蕴涵式P→Q，其真值表如下：PQP→QOO12021/7/6对P→Q，假定可以找到矛盾式Q，使得P→Q为真，即P→F为真，则命题P必然为假，从而

P必为真。这种类型的证明称为归谬证明。例5.2.8证明“在任意22天中至少有4天属于一个星期的同一天”。4分情形证明2021/7/6为了证明形如P1∨P2∨…∨Pn→Q的蕴含式，可以用重言式P1∨P2∨…∨Pn→Q=(P1→Q)

∧(P2→Q)∧…∧(Pn→Q)来作为推理规则。这个推理规则说明，可以通过对i=1，2，…，n分别证明每个蕴含式(Pi→Q)来证明由命题P1，P2，…，Pn的析取式组成前件的原来的蕴含式。这种论证称为分情形证明。例5.2.112021/7/6用分情形证明法证明|xy|=|x||y|，其中x和y是实数。分析令P为“x和y是实数”，Q为“|xy|=|x||y|”注意P等价于P1∨P2∨P3∨P4，其中P1为“x≥0∧y≥0”，P2为“x≥0∧y＜0”，P3为“x＜0∧y≥0”，P4为“x＜0∧y＜0”因此要证明P→Q，我们可以证明(P1→Q)

，(P2→Q)，(P3→Q)和(P4→Q)。证明2021/7/6很显然(P1→Q)，若x≥0∧y≥0，则xy≥0，因此|xy|=xy=|x||y|；要证明(P2→Q)，若x≥0∧y＜0，则xy≤0，因此|xy|=-xy=x(-y)=|x||y|(因为y＜0，我们有|y|=-y)；要证明(P3→Q)，若x＜0∧y≥0，则xy≤0，因此|xy|=

-xy=(-x)y=|x||y|；要证明(P4→Q)，若x＜0∧y＜0，则xy≥0，因此|xy|=(-x)(-y)=|x||y|。5、等价性证明2021/7/6为了证明一个定理是双条件的，即形如P«Q的命题，其中P和Q都是命题，可以使用重言式：P«

Q=(P→Q)∧(Q→P)即如果证明了蕴含式“若P则Q”和“若Q则P”，那么就可以证明命题“P当且仅当Q”。例5.2.12证明定理“整数n是奇数当且仅当n2是奇数”。5.2.3带量词的证明技术2021/7/61、存在性证明许多定理都断言存在特定类型的对象。这种类型的定理形如($x)P(x)的命题，其中P为谓词，对形如

($x)P(x)的命题的证明称为存在性证明。例5.2.14构造性的存在性证明。2021/7/6证明存在某个正整数，可以用两种不同的方式将其表示为正整数的立方和。分析只要能找到一个数，使得可以表示成两组正整数的立方和即可。证明经过大量的计算（如使用计算机搜索）可找到1729=103+93=123+13因为1729满足题设要求，所以得证。2、惟一性证明2021/7/6一些定理断言具有特定性质的元素惟一存在。换句话说，这些定理断言恰有一个元素具有这个性质。要证明这类命题，需要证明有某个元素具有这个性质，且没有其他元素有此性质。惟一性证明的两个部分如下：存在性：证明存在某个元素x具有期望的性质。惟一性：证明若y≠x，则y不具有期望的性质。例5.2.162021/7/6证明，如果p是整数，那么存在惟一的整数q，使得p+q=0。证明显然存在一个整数q=-p使得p+q=0。另外要证明q的惟一性，假定有某个整数r且r≠q，使得

p+r=0.那么p+q=p+r。从等式两边减去p，得出

q=r，这与假定r≠q矛盾。因此，存在某个惟一的整数q满足p+q=0。5.2.4证明中的错误2021/7/6例5.2.19

下面这个著名的假定“证明”(即1=2)错在哪里

“证明”步骤如下，其中a和b是两个相等的正整数。步骤

1．a=b2．a2=ab3．a2-b2=ab-b2理由给定的前提步骤1两边乘以a步骤2两边减去b24．(a-b)(a+b)=b(a-b)

步骤3两边分解因式5．a+b=b6．2b=b7．2=1步骤4两边出去a-b步骤5把a替换成b，因为a=b并化简步骤6两边除以b例5.2.20下面的“证明”错在哪里？2021/7/6“定理”：如果n2是正数，则n是正数

“证明”：假定n2是正数。因为蕴含“如果n是正数，则n2是正数”为真，所以可得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却为负数。5.3

数学归纳法2021/7/65.3.1

数学归纳法原理假设要证明的命题能写成形式:"n≥n0，有P(n)其中n0是某个固定的整数，即：希望证明对所有的整数n≥n0都有P(n)为真。数学归纳法原理2021/7/6假设验证n＝n0，有P(n0)为真；

(归纳基础)假设对于n＝k(k≥n0)，有P(k)为真；(归纳假设)证明n＝k＋1，有P(k+1)为真。

(归纳结论)结论对所有的整数n≥n0，都有P(n)为真。谓词表示：($n0)(P(n0)∧("

n)((n＝k)∧P(k)→P(k+1))＝1例5.3.2用数学归纳法证明前n个正奇数之和是n2。分析设用P(n)表示命题：前n个正奇数之和是n2。此时必须首先完成基础步骤：即必须证明P(1)为真然后必须完成归纳步骤，即必须证明当假定P(k)为真时P(k+1)为真。2021/7/6例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)2这样证明了从P(k)得出P(k+1)。注意在第二个等式里使用了归纳假设P(k)，以便用k2来代替前k个正奇数之和2021。/7/6强形式数学归纳法原理2021/7/6假设1）验证n＝n0、n0

+1，有P(n0)、P(n0+1)为真；(归纳基础)2）假设对于n≤k(k≥n0)，有P(n)为真；(归纳假设)3）证明n＝k＋1，有P(k+1)为真。 (归纳结论)结论

对所有的整数n≥n0，都有P(n)为真。谓词表示：($n0)(P(n0)∧P(n0+1)∧("

n)((n≤k)∧P(n)→P(k+1))＝1例5.3.3用数学归纳法证明：对所有n≥1，有1+2+3+…+n=n(n

+

1)2证明归纳基础验证1=1(1+1)显然P(1)真值为1；2归纳假设假定对于n=k(k≥1)，有P(k)为真，即有1+2+3+…+k=

k(k

+

1)；2021/7/62例5.3.1证明归纳结论证明

对于n＝k＋1，有P(k+1)为真由数学归纳法原理得到，P(n)对所有n≥1为真。1+2+3+…+k+(k+1)=

k(k

+

1)

+(k+1)2=

(k

+

1)(2021/7/6+

1)

=

=k

(k

+

1)(k

+

2)

(k

+

1)((k

+

1)

+

1)2

2

2例5.3.42021/7/6对每个正整数n≥1，能惟一地写成其中Pi是素数且满足P1<P2<…<Ps。大于等于2的正整数，因此，n0＝2。pa1pa2

...pas，1

2

s1

2

s分析设P(n)

：n＝

pa1pa2

...pas

；由于素数一定是例5.3.42021/7/6证明归纳基础验证因为2=21，3=31，所以P(2)、P(3)为真；归纳假设假定对n≤k的所有正整数，都有P(n)为真，即sn＝

p

a

1

p

a

21

2.

.

.

p

a

s例5.3.4(续)2021/7/6归纳结论证明对n＝k＋1，需分两种情况讨论：如果n本身就是一个素数，则k＋1＝(k+1)1，即P(k+1)为真；如果n不是一个素数，则k＋1＝lm，其中2≤l≤k，2≤m≤k，此时由归纳假设有，其中，P1,P2,…,Ps是素数，且是包含l、m中全部分解因子，bi、ci≥0的自然数，1

2sl＝

p

b

1

p

b

2.

.

.

p

b

s1

2

sm＝p

c

1

p

c

2.

.

.

p

c

s例5.3.4(续)2021/7/6为此有k＋1＝lm由于P1,P2,…,Ps是素数，所以k+1能分解成素数的积，又因为l和m的因子分解是惟一的，所以k＋1的因子分解也是惟一的，所以P(k+1)是真的。由数学归纳法原理得到，P(n)对所有n≥1为真。1

2

sb

bb1

2

s＝p

p

...ppc1pc2

...pcs1

2

s＝pb1+c1pb2

+c2

...pbs

+cs

＝1

2

s

1

2

spa1pa2

...pas5.3.3数学归纳法应用2021/7/6例5.3.1用数学归纳法证明下列伪码程序的计算结果是两个正整数的最大公因子。其中伪码程序为：

FUNCTION

GCD(X,

Y)WHILE

(X„Y)IF

(X>Y)

THENX‹

X-YELSEY‹

Y-XRETURN(X)END

OF

FUNCTION

GCD证明2021/7/6归纳基础验证

因为在循环开始之前存在变量值X0＝X，Y0

＝Y，因此，P(0)是命题GCD(X0,

Y0)＝GCD(X,

Y)，显然命题为真；归纳假设假定

设P(k)

是命题GCD(Xk, Yk)

＝GCD(X,

Y)为真；证明(续)2021/7/6归纳结论证明首先考虑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)为真。为此，该伪码程序输出的结果必是两个正整数的最大公因子。铺瓦问题2021/7/6例5.3.2

一个直角三正方形，是一个由三个正方形组成的对象，如图1所示。如果我们从n×n(n为2的幂)正方形的板中去掉一个正方形，则余下的图形可用直角三正方形来铺成，如图2。此处的铺成是用直角三正方形正好覆盖全图的图形，每个直角三正方形不能有重叠，也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板，把此问题称为铺瓦问题。直角三正方形图1图22021/7/62k×2k2k×2k2k×2k2k×2k图3证明2021/7/6归纳基础验证

如k＝1，2×2缺方板本身就是一个直角三正方形。因此可由三正方形铺成；归纳假设假定

设我们可以把2k×2k的缺方板用直角三正方形铺成；证明(续)2021/7/6归纳结论证明部分对于2k＋1×2k＋1的缺方板问题，我们可以将其分成四个2k×2k的板，如图所示。旋转此板，使缺少的正方形在左上的四分之一中。由归纳假设，此左上的2k×2k缺方板可由直角三正方形铺成，把一个直角三正方形T放在中间，则另外三个四分之一都是2k×2k的缺方板。由归纳假设，它们的铺瓦问题都是可以解决的。于是2k＋1×2k＋1的缺方板可由直角三正方形铺成。由数学归纳法知，对任何的n，n×n正方形的铺瓦问题都是可以铺成的。5.4

按定义证明方法2021/7/6在离散数学中，我们大量的定义描述都是用蕴涵型“P→Q”的方式来描述的。如集合中子集的包含关系的定义描述为：A

˝

B ("