人工智能教程 - 数学基础课程1.5 - 离散数学 - 反证法与数学归纳法

反证法和数学归纳法

反证法(a proof by contradiction)

反证法原理与矛盾推导

(So to prove a proposition p is true,you will assume P it’s false(not P is true).and then you use that hypothesis,namely the p to derive a falsehood.this is called deriving a contradiction.)

---

Ex: Thm: \sqrt2 is irrational

---

pf (by contradiction)

假设√2为有理数的矛盾推导

无理数证明与分数表示

\Rightarrow 2 = \frac{a^2}{b^2}

\Rightarrow a^2 = 2b^2

\Rightarrow a is even (2 | a)

\Rightarrow 4 能够整除 a^2

\Rightarrow 4 能够整除 2b^2

\Rightarrow 2 能够整除 b^2

\Rightarrow b is even (2 | b)