[Logical Thinking] 1. 수학적 귀납법
예전에 트위터에 글을 쓰겠다고 말 해 놓고, 쓰지 않은 글들이 존재한다. 그 중 하나를 지금부터 다시 시작해보려고 한다.
블로그에 로지컬씽킹으로 논리적으로 생각하는 법에 대해서 써보려고 합니다. 아마 첫 글이 오늘 올라올 것 같네요 pic.twitter.com/h5Nk9c2QiI
— 이혜아@void (@mega_kina) August 28, 2017
아마 첫 두개는 이전 포스트의 내용을 다듬는 것이 될 것이다.
참고로 이 글에는 이해하기 어려울 수 있는 수학적인 내용이 들어있다. 이해하지 않고 읽기만 해도 되는 내용에는 ⁺표시를 해놓겠다. 이외의 내용은 최대한 이해하기 쉽게 작성하려고 했다.
프로그래머들은 대개로 셀 수 있는 것들을 다룬다. 그리고 객체에 번호를 붙이는 것에 익숙해져 있다. 예를들면 배열의 0번째 원소, 1번째 원소, 2번째 원소... 같은 식으로 하나 하나씩 배열의 원소와 자연수를 하나하나씩 대응을 해 준다.
우리는 이 "자연수"에 대해서 조금 더 알아보려고 한다. 여기서 말하는 자연수는 편의상 0을 포함하는 개념이다.
⁺자연수를 정의할 때, 가장 많이 쓰는 방법은 페아노 공리계이다. 페아노 공리계는 다음과 같이 9개의 조건을 만족하는 집합이다. (=과 S를 정의한다.)
- 자연수 x에 대해, x = x
- 자연수 x, y에 대해, x = y 이면 y = x
- 자연수 x, y, z에 대해, x = y이고 y = z 이면 x = z
- 자연수 x에 대해, x = y 이면 y도 자연수
- 0은 자연수
- 임의의 자연수 x에 대해, S(x)도 자연수
- 임의의 자연수 x에 대해, S(x) ≠ 0
- 임의의 자연수 x, y에 대해, S(x) = S(y) 이면 x = y
- 0이 K의 원소이고, x가 K의 원소일 때, S(x)가 K의 원소이면 K는 자연수 집합
페아노 공리계를 처음 본 사람이 바로 이해를 하기는 힘들것이다. 페아노 공리계를 다시 쉽게 설명을 해보도록 하자.
0은 자연수이다. 0의 다음 수인 1도 자연수이고, 1의 다음 수인 2도 자연수이고, 2의 다음 수인 3도 자연수이고, ... 이렇게, 숫자들을 전부 다 모은 것이 자연수라는 것이다. (이것은 위의 페아노 공리계에서의 5와 9에 해당한다.) 그리고, 다양한 예외처리들이 되어 있다. 예를들면 어떤 수의 다음 수를 계속 따라가는 것으로 다시 되돌아오지 않는다는 등등...
좀 더 다른 비유를 해보면, 도미노가 있다. 도미노가 쭉 길게 있는데, 도미노는 한쪽 방향으로만 놓아져 있다. 그리고 도미노 하나를 쓰러뜨리면, 그 다음 도미노도 같이 쓰러진다. 쓰러진 도미노를 모두 모으면 자연수가 된다.
사실 굳이 이렇게 더 어려운 비유을 한 이유는, 이것이 수학적 귀납법의 핵심 아이디어이기 때문이다.
수학적 귀납법
귀납법은, 가설을 세우고, 경험적 사실로 참/거짓을 판단하는 방법이다. 다시 말하면, "내가 본것들은 다 ~~하더라."이다.
귀납법의 예를 들어보자면
- 내가 학교에서 본 모든 고양이는 검정색이다.
- 그러므로, 학교에 있는 모든 고양이는 검정색일 것이다.
귀납법은 뭔가 흔히 아는 "논리적"이라고 말하는 것과는 차이가 있어 보인다. 수학적 귀납법은 귀납법이라는 이름을 가지고 있지만, 사실 귀납법과는 많이 다르다.
수학적 귀납법을 설명하자. 수식을 사용해서 쓰면 다음과 같다.
P(0)이고, 모든 자연수 k에 대해 P(k)->P(k+1)이면, 모든 n에 대해 P(n)이다.
쉽게 설명을 하면, n에 대한 명제에 대해, n = 0일때 참이고, n = k+1이라는 것을, n = k가 참이라는 가정에서 증명할 수 있으면, 모든 n에 대해 명제가 참이라는 것이다. 이 설명은 어려워 보일 수 있어도, 이해를 하고 넘어갔으면 한다.
이해를 돕기 위해 추가적인 설명을 하자면, 가장 처음 도미노를 쓰러트릴 수 있고, 한 도미노가 쓰러졌을 때, 그 앞의 도미노도 쓰러진다면, 모든 도미노가 쓰러진다는 것이다. 이 사실은 굉장히 당연하게 보인다.
수학적 귀납법으로 많이 쓰이는 증명의 예시는 다음이 있다.:
1 + 3 + 5 + ... + ( 2n - 1 ) = n2
이 문제에 대한 증명은 다음과 같다:
n = 0일때: 0 = 02이라 성립한다. (왼쪽에 아무 수도 더해지지 않기 때문에, 0이라고 썼다. 혹시 헛갈린다면, n = 1로 시작한다고 생각해도 좋다.)
n = k+1일때: ( 1 + 3 + ... + ( 2k - 1 ) ) + ( 2( k + 1 ) - 1 ) = ( k2 ) + ( 2k + 1 ) = ( k + 1 )2 (첫번째 등호에서, n = k일때의 결과를 가져다 썼다. 두번째 등호에서는, k2 + 2k + 1 = ( k + 1 )2 라는 사실을 이용했다.)
n = 0일때 명제가 성립하고, n = k -> n = k+1이 성립하기 때문에, 수학적 귀납법에 의해서, 모든 n에 대해서 명제는 성립한다. 증명 끝.
좀 더 쉽게 풀어 써보도록 하자.
n = 0일때: 0 = 02이라 성립한다.
n = 1일때: 1 = (0) + 1 = 02 + 2×0 + 1 = 12이라 성립한다.
n = 2일때: 1 + 3 = (1) + 3 = 12 + 2×1 + 1 = 22이라 성립한다.
n = 3일때: 1 + 3 + 5 = (1 + 3) + 5 = 22 + 2×2 + 1 = 32이라 성립한다.
n = 4일때: 1 + 3 + 5 + 7 = (1 + 3 + 5) + 7 = 32 + 2×3 + 1 = 42이라 성립한다.
n = 5일때: 1 + 3 + 5 + 7 + 9 = (1 + 3 + 5 + 7) + 9 = 42 + 2×4 + 1 = 52이라 성립한다.
...
같은 방법으로 모든 n에 대해서 성립한다.
위의 증명에서, 가장 처음에는, n = 0일때 등식이 성립한다는 것을 보이고, 두번째에는, 어떤 하나의 수에서 등식이 성립하면, 다음 수에서도 등식이 성립한다는 것을 보였다. (예를 들면, 1 + 3 + 5 + 7 + 9를 계산 할 때, (1 + 3 + 5 + 7) = 42이라는 사실을 가져다 썼다.) 그래서 우리는 이 논리적인 식들이 도미노 처럼 쓰러진다는 것을 알 수 있다.
사실, 우리는 2번 풀이같이 작은 n에 대해서 직접 확인해 보는 방법을 쓴다. 하지만, 논리적인 증명을 위해서는 2번 풀이에 있는 식을 잘 정리해서 1번처럼 식을 사용하는 방법을 알아야 한다. 직접 종이에 써보면서 풀어보는것을 권장한다.
수학적 귀납법에 대해 글을 썼다. 도미노를 생각하면 편하다. 프로그램의 증명에서 수학적 귀납법은 중요하게 사용되고, 뒤의 게시글에서 계속 사용될 내용이니, 꼭 알아두었으면 한다. 다음 게시글에는 Loop-invariant를 설명하려고 한다.
아래쪽에 풀어볼만한 연습문제들이 담겨있는 링크를 남겨놓겠다. 링크에 있는 연습문제는 좀 더 수학의 분야에 치우쳐져 있다. 풀이 등에 대한 질문이 있거나, 게시글에 개선할 사항은 덧글로 남겨줬으면 한다.
링크. http://mathsci.kaist.ac.kr/~sangil/home/wp-content/uploads/2015/01/induction.pdf
수정1. http://koosaga.com/190 에 링크에 대한 작성된 풀이가 일부 올라와 있다.