2. 수학적 귀납법

  수학적 귀납법은 모든 자연수에 대하여 주어진 성질이 만족하는가 판단하는 중요한 증명 방법이다. 앞으로 프로그래밍을 하면서 풀게 되는 여러 명제들의 증명 방법에 대해 알기 쉬워지고, 동적 프로그래밍과도 연관성이 있기 때문에 수리논리학에서 기초적으로 많이 나오는 방법이다. 수학적 귀납법을 통하여 여러가지 명제에 대해 증명하는 법을 배워보자.

1. 공리와 귀납 논증

  수학적 귀납법을 이해하기 위해서는 우선 공리에 대한 이해가 필요하다. 우리는 "1+1=2이다."라는 명제를 직관적으로 사용한다. 이와 같은 명제는 별도의 증명이 필요가 없다. 우리가 사용하는 수학 체계에서는 위 명제는 마치 진리와 같게 사용된다. 귀납 논증은 바로 공리에서 부터 시작된다.

  귀납 논증은 '구체적 사실로 부터 보편적인 사실을 추론해 내는 것'이다. 예를들어 '오늘 아침에 해가 떴다'라는 구체적 사실이 존재한다고 하자. 그리고, 그 다음날 역시 아침에 해가 떴다. 2일후, 3일후에도 계속 아침에 해가 뜨면 이는 사실이 되고, 이를 통해 보편적인 사실을 추론하는 방식이다. 이 사실들을 통해 우리는 매일 아침 해가 뜬다는 보편적 사실을 추론한다.

  이처럼 귀납 논증은 확률적인 모델에 크게 의존한다. 일부의 구체적 사실을 통해 보편적 정의도 그럴 것이라는 것이다. 앞서 보여준 명제를 예시로 들자면, 겨우 4일 동안 아침마다 해가 뜬다는 사실을 통해 지구가 탄생한 이래 몇십억년 동안 모두 태양이 뜰 것이라는 명제가 참이라고 추론하는 것이다. 만약 내일 태양이 뜨지 않는 다면 위 명제는 거짓이 된다.

  귀납 논증의 경우 아래와 같은 반례가 나올 수 있다.

- 구체적 사실

1. 카페 A의 아메리카노는 샷이 총 2번 들어간다.

2. 카페 B의 아메리카노는 샷이 총 2번 들어간다.

3. 카페 C의 아메리카노는 샷이 총 2번 들어간다.

따라서, 모든 카페의 아메리카노는 샷이 총 2번 들어간다.

  위 명제는 귀납 논증의 한계를 보여준다. 확률적 보편성에 의존하기 때문에 위의 3가지 사실로 섣부르게 전체를 판단할 수 있다. 직관적으로 본다고 해도 위 명제는 거짓이다. 어떤 카페는 아메리카노의 샷이 3번 들어갈 수도, 1번 들어갈 수도 있다. 이런 맹점이 있으니 귀납 논증을 적용할 때는 항상 주의해야 한다.

  이런 맹점에도 불구하고 우리가 귀납 논증을 많이 사용하는 이유는, 명제 증명을 위한 전체 조사가 현실적으로 불가능하다. 앞의 명제를 증명하기 위해서 모든 카페 매장을 돌아다니면서 샷의 개수를 조사할 수는 없다. 그래서 현실의 문제들에서는 실제로 몇가지 사실만 가지고 전체를 추론 하는 수밖에 없다. 우리가 흔히 보는 프로그램의 시청률 등 확률 통계 자료들은 대부분 귀납 논증에 근거한다.

2. 연역 논증

  귀납 논증과 함께 논리학에서 양대 산맥을 이루는 논증 방법이 바로 연역 논증이다. 연역 논증은 "보편적 사실로 부터 구체적인 사실을 추론해내는 방식"이다. 반드시 참인 사실들로 명제가 참인지 증명한다. 이때 필요한 전제가 반드시 옳다면은 귀납 논증과 달리 반례가 나오지 않는다. 연역 논증의 예시를 아래와 같다.

- 전제

1: 나는 사람이다.

2: 사람은 언젠가 죽는다.

- 결론

나는 언젠가 죽는다.

  우리가 흔히 사용하는 삼단 논법이 연역 논증에 대한 좋은 예시가 된다. 첫번째 기본 전제와 보편적 진리가 있다면, 쉽게 구체적 사실의 참/ 거짓을 알아 낼 수 있다. 연역 논증이 반드시 참인 이유는 구체적 사실을 도출해 내는 것이기 때문이다. 귀납 논증의 경우 보편적 사실을 도출해야 하므로 앞의 사례 처럼 반례가 나올 가능성이 매우 크다. 반면 연역 논증은 이미 존재하는 사실로부터 구체적 사실을 알아 내기 때문에 귀납 논증과 달리 반드시 참임을 증명 할 수 있다.

3. 수학적 귀납법

  수학적 귀납법은 자연수를 이용한 사실을 도출해내는데 정말 강력한 증명 방법이다. 귀납법이라는 이름과 달리 수학적 귀납법은 연역 논증에 속한다. 앞에서 배운 귀납 논증과 연역 논증에 대한 이해가 완료 되었다면 수학적 귀납법이 왜 참인지를 쉽게 알게 된다. 우리가 흔히 알고있는 자연수에 대한 약속 (1+1=2 등)을 통해 우리는 자연수 명제를 쉽게 증명 한다.

  수학적 귀납법의 정의는 아래와 같다.

1. P(0)은 참이다.

2. 자연수 n에 대하여, P(n)이 참이라고 가정하면, P(n+1)도 참이다.

  이 두개의 명제가 참이라면, 모든 자연수 n에 대하여 P(n)은 항상 참이 된다.

  수학적 귀납법을 통해 한번 문제를 풀어보자.

Ex) 홀수의 합 공식 ( ) 예시

  명제 : 만약 n이 자연수라면, n개의 홀수의 합에 대한 공식은 이다.

P(1)은  이 되므로 항상 참이다.

P(n)이 참이라고 가정하면, P(n+1)도 참이 될 수 있는지 살펴보자

양변에 2(n+1)을 더하면 아래와 같다.

따라서, P(n)이 참이라면 P(n+1)도 자동으로 참이 된다.

따라서 홀수의 합 공식은 수학적 귀납법을 통해 참이라는 사실을 알 수 있다.

4. 동적 프로그래밍에 적용

  나중에 다시 살펴 보겠지만, 동적 프로그래밍에 대한 증명 역시 수학적 귀납법으로 할 수 있다. 아래와 같이 팩토리얼을 구하는 코드가 있다고 가정하자.

factorial(n) {
    if (n<=1) return 1;
    else return n * factorial(n-1);
}

 factorial의 정의는 아래와 같다.

 if문의 조건에 따라서 factorial(1) = 1이다.

 그리고 P(n)이 참이라고 가정하면, P(n+1)도 참이 되어야 한다.

else 문에 따라 아래 식 역시 만족한다는 것을 알 수 있다.

  

  수학적 귀납법은 프로그래밍을 하는데 필수적 요소는 아니지만, 앞으로 많은 문제를 푸는데 있어 프로그램에 대한 이해도를 높이고, 뒤에 보여드릴 동적 프로그래밍이 왜 성립하는지 보여주는 좋은 예시이다. 논리와 귀납법을 통해 프로그램 문제를 분석하고 이를 증명하는 방법에 대해서 배웠다. 앞으로 자료구조, 알고리즘을 통한 다양한 문제를 풀어갈 것이다.