第二章逻辑和证明（五）-Read.ppt

第二章 逻辑和证明 2.5 证明定理的方法 2.5.1 直接证明 直接证明：直接证明结论 对p→q形式的结论，把p也当作前提，证明q 例1 给出定理“若n是奇数，则n2是奇数”的直接证明。 解 假定这个蕴含式的条件为真。即假定n是奇数。则n=2k+1，其中k是整数。由此得出n2 = (2k+1) 2 = 4k2+4k+1= 2(2k2+2k)+1 。因此，n2是奇数（它是一个整数的两倍再加1）。 2.5.2 间接证明 间接证明： 对p→q形式的结论，证明其等价的逆否命题 ?q→?p (p→q) ? (?q→?p) 例2 给出定理“若3n+2是奇数，则n是奇数”的间接证明。 证明： 假定这个蕴含式的后件为假：即假定n是偶数。则对某个整数k来讲有n=2k。 所以3n+2=3(2k)+2=6k+2=2(3k+1)，所以3n+2是偶数（因为它是2的倍数）。因为对这个蕴含式后件的否定蕴含着前件为假，所以原来的蕴涵式为真。 2.5.3 空证明 空证明： 对p→q形式的结论，证明p为假 F→q永真 常用于证明定理的特殊情况和数学归纳法 例3 证明命题P(0)为真，其中P(n)是命题函数“若ｎ大于１， 则n2 n”。 证明： 注意命题P(0)是蕴含式“若0大于1，则020”. 因为前提01为假，所以蕴含式P(0)自动为真。 2.5.4 平凡证明 平凡证明： 对p→q形式的结论，证明q为真 p→T永真 常用于证明定理的特殊情况和数学归纳法 例4 设P(n)是命题“若a和b是满足a ? b的正整数，则an? bn 。”证明命题P(0)为真。 证明： 命题P(0)是“若a和b是满足a ? b的正整数，则a0?b0”。因为a0=b0=1，所以P(0)的后件为真。因此，P(0)为真。 2.5.5 归谬证明（反证法） 归谬证明： 为证明p，证明?p→F或?p→r??r（r是任意的某 个命题） （把?p也当作前提，证明F或r??r） 若前提? (?p→F)，则前提??p 例5 通过给出归谬证明来证明 是无理数。 证明： 设p是命题“ 是无理数”。假定?p为真。则 是有理数。将要证明它导致矛盾。 在 是有理数的假设下，存在整数a和b满足 =a/b，其中a和b没有公因子。因为 =a/b，所以当这个等式的两端都平方时，就得出2=a2/b2，因此2b2=a2。这意味着是a2偶数，它蕴含着a是偶数。另外因为a是偶数，对某个整数c来说有a=2c。 （接下页） 因此，2b2=4c2，所以b2=2c2。这意味着b2是偶数。因此b也必然是偶数。 已经证明了?p蕴含着 =a/b，其中a和b没有公因子，以及2整除a和b。这是矛盾的，因为证明了?p既蕴含了r，又蕴含了?r，其中r是命题：a和b是没有公因子的整数。因此?p为假，所以p：“ 是无理数”为真。 对p?q形式的结论，可采用归谬证明证明?(p ? q) ? F（ ? ） 可把p和? q都作为前提（? (p→q) ?p??q），证明F或r??r 例6 给出定理“若3n+2是奇数，则n是奇数”的归谬证明。 证明： 假定3n+2是奇数而n不是奇数，所以n是偶数。按照在上面例2解答里的同样步骤（这个定理的间接证明），可以证明若n是偶数，则3n+2是偶数。这与3n+2是奇数的假定矛盾。证毕。 2.5.6 分情况证明 分情况证明：为证明 (p1?p2?…?pn) →q，分别证明p1→q、p2→q、…、pn→q (p1?p2?…?pn) →q? (p1→q) ? (p2→q) ?…? (pn→q) 例7 证明蕴含式“若n是不能被3整除的整数，则n2?1 (mod 3)”。 证明： 设p是命题“n不能被3整除”，设q是命题“n2 ?1 (mod 3)”.则p等价于p1?p2，其中p1是“n?1 (mod 3)”而p2是“n?2 (mod 3)”。因此，为了证明p?q，可以证明p1?q和p2?q。容易给出这两个蕴含式的直接证明。 （接下页） 首先，假定p1为真，则n?1 (mod 3)，所以对某个整数k来说有n=3k+1.因此 n2=9k2+6k+1=3(3k2+2k)+1。 由此得出n2?1 (mod 3)。因此，蕴含是p1?q为真。其次，假定p2为真。则n?2 (mod 3)，所以对某个整数k来说有n=3k+2。因此，