计算机问题求解-论题1-3一常用的证明方法
计算机问题求解– 论题1-3 - 常用的证明方法
PartI反证法和归纳法
Pythagoreans证明/2不是有理数Suppose, to the contrary, that V2 is rational. Then there exist inte-gers p and q (with q nonzero) such that 2 = p/q. We may assumethat p and q have no common factor, for if they did, we would sim-plify and begin again. Now, we have that V2g = p. Squaring bothsides, we obtain 2q? = p2. Thus p? is even. Since p? is even, weknow from Problem 3.1 that p must be even. Therefore, p = 2m forsome integer m. This means that 2q? 4m?. Dividing, we see thatg? = 2m?. But this means that q? is even. Again we know from Problem 3.1 that g is even. So p and g have a common factor 2, which iscompletely absurd, since we assumed they had no common factorTherefore our assumption that 2 is rational must be wrong and wehave completed the proof of the theorem
Pythagoreans证明 2 不是有理数
问题1：你能用上堂课的描述方式说明这个证明逻辑上的合理性吗？
反证法-Reductio ad Absurdum待证命题：V2不是有理数待证命题：A假设：2=p/g,p,q最大公约数为1一A（假设，其等价表述根据数学定义）C: gcd(p,q)=1 (数学性质:-A=C)推论：p是偶数E(p) (算术性质）E(q)推论：q是偶数(算术性质）-C推论：gcd(p,q)>1证明过程：.待证命题成立。-A= C-A=-CC ^-C=False即：-A=False永真式：((p→g)>(-q))→-p: -(-A), 即: A
反证法 – Reductio ad Absurdum 待证命题: 不是有理数 待证命题: A 假设 : = p/q, p,q最大公约数为1 A (假设, 其等价表述根据数学定义) C: gcd(p,q)=1 (数学性质: AC) 推论: p是偶数 E(p) (算术性质) 推论: q是偶数 E(q) (算术性质) 推论: gcd(p,q)>1 C 待证命题成立。 2 2 证明过程： A C A C C C False 即：A False 永真式：((p→q)(q))→ p (A), 即：A