수학적 귀납법과 명제

 

 

수학적 귀납법

수학적 귀납법의 기본형

1. Base : P(1)이 참이다
2. Step : P(n-1) → P(n)이 참이다 ( p→ q 형태 )
3. Result : P(n)은 모든 자연수에 대해 참이다

우리가 증명하려는 것은 전체가 참이라는 것을 보이는 것이다. 하나하나가 참인지 거짓인지는 알지 못해도 됨.

그 이유는, P(n-1)이 거짓일 때는 무조건 T가 되기 때문에 P(n-1)이 참일때 전체가 참이면 무조건 P(n)은 참이다.

 

* P : 무엇인지 모르는 것 > 이름, 명제 등

* n : 자연수

 

ex) Prove that \(1 + 2 + 3 ... + n =  \frac{n(n+1)}{2}\) for all \(n \epsilon \mathbb{N}\)

(1) Base : \(P(1) = 1 = \frac{1 \times 2}{2} = 1 \therefore\)성립

(2) Step :

\(P(n-1) = 1 + 2 + 3 + ...  + n-1 = \frac{(n-1)n}{2}\)이면 > 성립한다고 믿음 

\( P(n) = 1 + 2 + ... + n = \frac{n(n+1)}{2} = P(n-1) + n = \frac{(n-1)n}{2} + n = \frac{n^{2}+n}{2} = \frac{n(n+1)}{2} \)

\( \Rightarrow P(n) = P(n-1) + n \)

\( \therefore P(n-1) \rightarrow P(n)\)이 참이다

(3) Result : P(n)은 모든 자연수에 대해 참이다

 

수학적 귀납법의 강한 형태

p(1)이 참이고 

 

명제 \(P \rightarrow Q\)의 의미 

\(P\)	\(Q\)	전체
T	T	T
T	F	F
F	T	T
F	F	T

p가 거짓이면, 전제는 무조건 참이 됨 : 논의할 의미가 없으므로 항상 p가 참이라고 생각하고 논의해야함

아래 두개는 Vacuously True이다. 

 

* if \(3 > n \rightarrow n^2>3\) 은 vacuously true이다. n=1일 때도 true

\(p \rightarrow q \) vs \(p \rightarrow q \) & \(q \rightarrow p\)

\(p \rightarrow q \)

• 수학적 귀납법에서 사용
• p가 F일 때 의논하는 것은 의미가 없음 
• p : P(n-1) , q : P(n)으로 수학적 귀납법에서 사용함
• P가 거짓일 때 Q가 어떻다 라는 말 자체가 없음

\(p \rightarrow q\) & \(q \rightarrow p\)

• 보통 생각하는 조건의 정의
• p가 F이고 q가 T이면 전제는 F가 됨

 

ex) 총합을 구하는 재귀함수

int sum(int x){
	if(x<=0) return 0;
	return x + sum(x-1);
}

pf)

(1) Base : P(1)이 참이다 > 대입으로 증명 가능

(2) Step :

sum(x-1)이 1 + 2 + ... x-1을 리턴하면 (한다고 가정, 믿음) sum(x)는 1 + 2 + ... + x-1 + x를 리턴함

sum(x) = sum(x-1) + x를 리턴하므로 sum(x) = 1 + 2 ... x-1 + x 리턴

(3) Result : sum(x)는 1 + 2 + .. x를 리턴함

 

*재귀함수를 흔히 따라들어가서 생각하는데, 이를 따라들어가지 않고 귀납법으로 믿으면 쉽게 해결할 수 있음

The complexity

\(T(n) = 1 + T(n-1) = 1 + 1+ T(n-2) = ... = n\)

\( \therefore T(n) = O(n)\)