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

反证法和数学归纳法

反证法(a proof by contradiction)

为了证明命题p为真，先假设它为假(非P是真)。然后用这个假设P为假来推导出一个错误。换句话，你证明了一个错误是真的。这叫做推导出矛盾。

(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: 2 \sqrt2 2 ​ is irrational

pf (by contradiction)

Assume for the purpose of contradiction that 2 \sqrt2 2 ​ is rational

⇒ 2 = a / b \Rightarrow \sqrt2=a/b ⇒2 ​=a/b(既约分数a fraction in lowest terms)

⇒ 2 = a 2 / b 2 \Rightarrow 2=a^2/b^2 ⇒2=a2/b2

⇒ 2 b 2 = a 2 \Rightarrow 2b^2=a^2 ⇒2b2=a2

$\Rightarrow$ a is even (2 | a)

⇒ 4 ∣ a 2 \Rightarrow 4 | a^2 ⇒4∣a2

⇒ 4 ∣ 2 b 2 \Rightarrow 4 | 2b^2 ⇒4∣2b2

⇒ 2 ∣ b 2 \Rightarrow 2 | b^2 ⇒2∣b2

$\Rightarrow$ b is even (2 | b)

$\Rightarrow$ a/b is not in lowest terms

$\Rightarrow$ contradiction

$\Rightarrow$ 2 \sqrt2 2 ​ is irrational $\square$

数学归纳法(Induction axiom)

let P(n) be a predicate.(令P(n)为谓词).If P(0) is true,

and $\forall n\in \mathbb{N},(P(n)\Rightarrow P(n+1))$is true

then $\forall n\in \mathbb{N},P(n)$ is true

另一种不带$\forall$的说法：

If $P(0),P(0)\Rightarrow P(1),P(1)\Rightarrow P(2),...$ are true,

then P(0),P(1),P(2),… are true

就像是多米诺骨牌(domino)

Thm: ∀ n ≥ 0 , 1 + 2 + 3 + . . . + n = n ( n + 1 ) 2 \forall n\geq 0 , 1+2+3+...+n=\frac{n(n+1)}{2} ∀n≥0,1+2+3+...+n=2n(n+1)​

If $n=0$, 1+2+…+n=1

If $n\le 0$ 1+2+…+n=0

("…"also called ∑ i = 1 n i , ∑ 1 ≤ i ≤ n i , ∑ 1 ≤ i ≤ n i \sum_{i=1}^{n}i,\sum^{1\leq i\leq n}i,\sum_{1\leq i\leq n}i ∑i=1n​i,∑1≤i≤ni,∑1≤i≤n​i)

Pf: by induction

predicate:(谓词)

Let P(n) be proposition that ∑ i = 1 n i = n ( n + 1 ) 2 \sum_{i=1}^{n}i=\frac{n(n+1)}{2} ∑i=1n​i=2n(n+1)​

Base case(基本情形) : P(0) is true

∑ i = 1 0 i = 0 = 0 ( 0 + 1 ) 2 \sum_{i=1}^{0}i=0=\frac{0(0+1)}{2} ∑i=10​i=0=20(0+1)​

Inductive Step:(归纳步骤)

$\forall n\ge 0,showP(n)\Rightarrow P(n+1)$ is true

Assume P(n) is true for purposes of induction

(i.e,assume 1 + 2 + 3 + . . . + n = n ( n + 1 ) 2 1+2+3+...+n=\frac{n(n+1)}{2} 1+2+3+...+n=2n(n+1)​

need to show 1 + 2 + 3 + . . . + ( n + 1 ) = ( n + 1 ) ( n + 2 ) 2 1+2+3+...+(n+1)=\frac{(n+1)(n+2)}{2} 1+2+3+...+(n+1)=2(n+1)(n+2)​

$1+2+3+...+(n+1)$=$1+2+3+...+n+(n+1)$

= n ( n + 1 ) 2 + n + 1 = n 2 + n + 2 n + 2 2 = ( n + 1 ) ( n + 2 ) 2 =\frac{n(n+1)}{2}+n+1=\frac{n^2+n+2n+2}{2}=\frac{(n+1)(n+2)}{2} =2n(n+1)​+n+1=2n2+n+2n+2​=2(n+1)(n+2)​$\square$

Conclusion:(结论)

$\therefore \forall n\ge 0,P(n)\Rightarrow P(n+1)$

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！