수학적 귀납법을 사용해 재귀를 증명하기

0. 글을 쓰는 이유와 잡다한 이야기

이번 학기에는 <알고리즘>이라는 과목을 수강한다. 나는 알고리즘을 통한 문제해결(Problem Solving)에 관심이 많아서 혼자 여러 알고리즘들을 공부해왔다. 군대를 다녀오기 전, 새내기 시절에는 동아리 내에서 알고리즘 대회를 열어 문제를 출제하기도 했었다.

코로나의 여파가 가시질 않아 이번 학기도 대부분의 과목들이 비대면으로 진행했고, 알고리즘 또한 그랬다. 1주차 강의밖에 듣지 않았지만, 느낀 게 꽤나 많다. 나의 알고리즘 공부법이 완벽하게 틀렸다고 할 수 있을 정도였다. 여러 알고리즘 유형의 문제들을 풀어왔지만, 문제에 대한 정당성이나 증명을 러프하게 넘기거나, 흔히들 말하는 Proof by AC (맞았습니다로 증명하기)로 퉁쳤기 때문이다. 지금 생각해 보면 굉장히 나쁜 습관임에도 고치기가 어렵다. 증명은 귀찮고, 코드를 짜서 맞히면 기분이 좋다. 맞힌 문제들은 뒷전이 된다. 내 실력 향상에는 큰 도움이 되지 않았다.

고등학교 때에도 수학이라는 과목은 재미있어했지만, 성적이 잘 나오지 않아서 속상했던 일이 자주 있었다. 그 이유도 수학 문제를 푸는 방법만 익혔지, 그 원리나 증명에 대해서 깊게 파고들지 않았기 때문이다.. 내가 공부해왔던 방법은 이론과 그 정당성을 증명하는 것과는 거리가 멀었다. 이미 풀이가 존재하는 문제를 풀어가면서 머릿속으로 그 절차를 받아들이는 것이었다. 그것이 전자보다는 훨씬 편했으니까.

이번 학기에는 증명과 관련된 과목을 많이 듣게 됐다. 그만큼 내가 고통을 받을 것이라는 거겠지… 😥 다시 지금처럼 나쁜 습관을 가지고 공부하는 것을 멀리하기 위해서 이 글을 쓴다 !

강의 내용을 이해하고 정리하는 과정에서 글에 오류가 있을 수 있습니다.
혹시라도 발견하신다면 댓글로 바로잡아주시길 부탁드립니다 🙌

1. 명제와 Vacuous Truth

재귀를 증명하기 위해서 수학적 귀납법을 사용하는데, 이 과정에서 ‘직관과 충돌해서 받아들이기 어려운’ 케이스가 존재한다.

$P \rightarrow Q$ 라는 명제가 있다. ‘$P$ 이면 $Q$ 이다’ 라고 읽는다. 자연어에서는 $P$ 가 일어나야 $Q$ 가 일어난다라고 해석되고, 그게 자연스럽다. 예를 들면,

비가 오면, 우산을 쓴다

라는 문장이 있다고 하자. $P \rightarrow Q$ 라는 명제로 위 문장을 나타낸다면 $P$ 는 비가 온다가 되고, $Q$ 는 우산을 쓴다가 된다. 우리는 이 문장을 읽을 때 자연스럽게 비가 오니까 우산을 쓴다고 말한다. $P$ 와 $Q$ 사이에서 인과관계를 찾기 위해 애쓴다. 비가 오’니까’ 우산을 쓴다고 말하는게 더 자연스럽기 때문이다. 하지만 수학적으로 접근하기 위해서는 이 직관을 잠시 내려놓아야 한다. 자연어는 그 뒤에 숨겨진 뜻도 있고, 문장을 여러 의미로 해석될 수 있지만, 수학적으로 정의된 명제는 보이는 그대로가 전부여야 한다.

$P \rightarrow Q$ 는 아래와 같이 표로 그 결과를 나타낼 수 있다.

🌧 ($P$)	☂($Q$)	🌧☂❓($P \rightarrow Q$)
TRUE	TRUE	TRUE
TRUE	FALSE	FALSE
FALSE	TRUE	TRUE
FALSE	FALSE	TRUE

가장 위 두 줄은 우리의 직관과 일치한다. $P$ 이면 $Q$ 이니까, 명제가 참이 되려면 $P$ 가 TRUE일 때 $Q$ 도 TRUE여야 한다는 것은 받아들이기 쉽다.

문제가 되는 건 아래 두 줄이다. 애초에 $P$ 가 거짓일 때에 $P \rightarrow Q$ 의 결과가 어떻게 되느냐인데, 이걸 위의 자연어 문장처럼 받아들이는 건 참 쉽지 않다.

친구와 약속을 했다고 하자. 약속은 아래와 같다.

명제 1: 시험에서 100점을 맞는다면, 치킨을 사 주겠다. (💯$\rightarrow$🐓🍗)

💯 ($P$)	🐓 ($Q$)	💯🐓❓($P \rightarrow Q$)
TRUE	TRUE	😁 happy
TRUE	FALSE	🤬 angry
FALSE	TRUE	🙄 good anyways?
FALSE	FALSE	👌 never mind

자연어의 직관을 내려놓으라고 했는데도 이렇게 해석을 하는 이유는, 내가 받아들이기가 어렵기도 하고 예시를 들어 봐야 이해가 되기도 하기 때문이다. 일부러 충돌을 일으키고 그에 대한 해소를 통해 이해하는 것은 다른 의미에서 중요하다고 생각한다.

다시 표로 돌아와서, $P$ 가 TRUE인 경우는 둘 다 자연스럽다. 그렇지 않은 두 경우를 생각해보자. 100점을 못 받았을 때 치킨을 못 받는다면? 약속을 어긴 것이 되는 건 아니다. 애초에 $P$ 가 일어나지 않았으므로 $Q$ 가 어떻게 되든 상관이 없음을 의미한다. 반대로 100점을 못 받았는데 치킨을 얻어먹는다면? 이것 또한 약속을 어긴 것이라고 보기는 어렵다.

이처럼, “$P$ 이면” 이라는 것이 애초에 거짓인 상태를 Vacuous 라고 한다.

(번역하면 ‘공허’라고 한다는데, 이런 건 확실히 원어로 받아들여야 하는 듯하다..)

Vacuous를 TRUE / FALSE 중 하나도 정해야 한다면, 위 예시에서 TRUE로 생각했을 때 어렵지 않게 받아들일 수 있다. 하지만 FALSE로 생각한다면 받아들이기 어렵다. TRUE라고 해도 아주 이상하지는 않지만, FALSE로 이야기하는 것은 불가능하다. 아래 두 줄의 경우를 ‘약속을 어겼다’라고 이야기할 수 없기 때문이다.

위 예시에서는 Vacuous도 하나의 상태로 두고 TRUE / FALSE / VACUOUS 라는 세 가지 상태로 나타내도 크게 껄끄럽지 않다. 그런데 왜 Vacuous를 하나의 상태로 두지 않고, TRUE라고 하는 걸까?

다음과 같은 명제를 살펴보자.

명제 2: 정수 $n$ 에 대해서 $n > 3$ 이면, $n > 1$ 이다.

사람들에게 위 명제를 보여주면, 항상 사실이라고 답한다.

항상 사실이라고 이야기하는 사람들에게 아래와 같이 되묻는다.

꼬리 질문: $n = 1$ 인 경우에는 어떻게 되나요? 이 때에도 사실인가요?

라고 물어보면 말을 바꿀 수도 있겠지만, 그들은 사실이라고 대답해야 한다. 위에서 명제는 항상 사실이라고 대답했기 때문이다. 위에서 ‘항상 사실’이라고 대답할 때, $n > 3$ 이 아닌 경우도 이미 내포되어있다고 말할 수 있다. (하지만 실제로 대답할 때, $n > 3$ 이 아닌 경우를 생각하지 않았다)

명제 2의 경우에는 Vacuous라는 것을 두고 따지기에는 애매한 상황이 발생한다. ‘항상 사실’이라고 대답을 하는 과정에서 Vacuous를 생각할 수 없다. “$n > 3$ 인 경우에는 사실이고, $n = 1$ 인 경우에는 Vacuous입니다” 라고 대답할 수 있을까? 거의 모든 사람이 “명제 2는 항상 참입니다” 라고 대답할 것이다.

그래서 Vacuous를 FALSE로 생각하는 것보다, TRUE로 생각하는 것이 편리하고, 실제로도 Vacuous Truth이라고 이야기하며 해당 경우는 TRUE이다.

2. 수학적 귀납법

$P \rightarrow Q$ 를 위에서 설명한 이유는, 아래 수학적 귀납법과 관련이 있다.

수학적 귀납법의 기본형 :

$P(1)$ 이 참이고, $P(n-1) \rightarrow P(n)$ 이 참이면, $P(n)$ 은 모든 자연수 $n$에 대해서 참이다.

수학적 귀납법의 강한 형태:

$P(1)$ 이 참이고, $P(1) \land P(2) \land \cdots \land P(n-1) \land P(n)$ 이 참이면, $P(n)$ 은 모든 자연수 $n$ 에 대해서 참이다.

우선 기본형을 보자. 수학적 귀납법은 $P(n)$ 이 모든 자연수 $n$ 에 대해서 참임을 보이기 위해 쓰는 증명 방법 중 하나이다. 두 가지를 증명한다면, 결론을 증명하는 게 된다.

$P(1)$ 이 참인 것(Base)과 $P(n-1) \rightarrow P(n)$ 이 참인 것(Step)을 증명하면 $P(n)$ 은 모든 자연수 $n$에 대해서 참이다.

간단한 문장을 수학적 귀납법으로 증명해 보자.

$P(n) = “n>0″$
Base: $P(1)$은 $1>0$ 이므로 사실이다.
Step: $P(n-1)\rightarrow P(n)$ 은 $n-1\gt 0\rightarrow n\gt 0$ 이다.
Proof of step:
ⓐ $a>0$ 이고 $b>0$ 이면, $a+b>0$이다. (axiom)
ⓑ $n-1+1 = n$
ⓐ의 $a$ 에 $n-1$ 를, $b$ 에 $1$ 을 대입하면
ⓑ에 따라 $n-1+1 = n$ 이므로, $n>0$ 이다 (증명 끝!)

3. 수학적 귀납법을 사용해 재귀를 증명하기

그럼 이제는 재귀를 수학적 귀납법을 통해 증명해 보자. $\sum_{n=1}^{x}{n}$ 를 구하는 코드를 재귀적으로 나타내면 아래와 같다.

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

위 재귀가 항상 우리가 원하는 값을 가짐을 수학적 귀납법을 사용해 증명해 보자. 직관을 사랑하는 나로서는 이 재귀를 머릿속으로 아래와 같이 생각한다. $\texttt{sum}(4)$ 를 호출한다고 생각해 보자.

$$ \begin{aligned} &\texttt{sum}(4) \\ &\rightarrow 4+\texttt{sum}(3) \\ &\rightarrow 4+(3+\texttt{sum}(2)) \\ &\rightarrow 4+(3+(2+\texttt{sum}(1))) \\ &\rightarrow 4+(3+(2+(1+\texttt{sum}(0)))) \\ &\rightarrow 4+(3+(2+(1+0)))) \\ &\rightarrow 10 \end{aligned}$$

4부터 시작해서 3, 2, 1, 0을 머릿속으로 재귀를 굴려가며 어떻게 될 지 생각한다. 이는 재귀가 조금만 복잡해져도 머리가 지끈해지고, 직관과는 더 거리가 멀어진다. 이 문장을 위에서 서술한 내용을 바탕으로 증명해 보자.

증명에 사용되는 것은 기계적이어야 한다. 나타나지 않은 식을 등장시키는 식으로 증명하게 된다면 이는 증명한 것이 아니다!

증명해야 하는 문장 : $\texttt{sum}(x)$ 은 항상 $\sum_{n=1}^{x}{n}$ 를 리턴한다.

Base : $\texttt{sum}(1)$ 은 $1$ 을 리턴한다. (사실, 코드에 1을 대입하게 되면, 기계적으로 1이라는 결괏값이 리턴된다)

Step: $\texttt{sum}(x-1)$ 이 $\sum_{n=1}^{x-1}{n}$ 을 리턴한다면, $\texttt{sum}(x)$ 는 $\sum_{n=1}^{x}{n}$ 를 리턴한다.

우리는 $P(n-1) \rightarrow P(n)$ 를 증명할 때, $P(n-1)$ 가 TRUE이면 $P(n)$ 을 따져봐야 하지만, FALSE인 경우에는 어떻게 돼도 TRUE임을 알았다! 따라서 믿음을 가지고 (사실은 뭐가 돼도 상관 없다는 의미가 좀 더 강하다) $P(n)$ 에 집중할 수 있게 된다. 앞의 문장이 참이라고 가정하고 생각해도 증명에는 아무 결함이 없다는 이야기가 된다.

따라서, $\texttt{sum}(x-1)$ 이 무엇이 됐든, 사실이라고 믿고 $\texttt{sum}(x)$ 가 $\sum_{n=1}^{x}{n}$ 를 리턴하는지만을 확인하면 된다. (이 부분이 정말 머리가 멍해졌던 순간이다..)

$\texttt{sum}(x-1)$ 가 $\sum_{n=1}^{x-1}{n}$ 을 리턴한다고 믿고 있고, 코드를 들여다보면 $\texttt{sum}(x)$ 는 $x+\texttt{sum}(x-1)$ 를 리턴한다고 같다고 되어 있으므로(기계적) $\texttt{sum}(x)$ 는 $\sum_{n=1}^{x}{n}$ 를 리턴한다는 것이 증명된다.

증명이 되었으므로, 내 재귀 코드가 어떻게 동작할지를 단번에 알아챌 수 있게 된다. 굳이 x에 특정 값을 넣어서 Base까지 내려가서 다시 리턴을 합할 필요가 없게 된다. 재귀 코드를 보고 리턴값을 확인할 때, 믿음을 가지고 코드를 보는 시야를 가지게 된다면 증명도 어렵지 않게 할 수 있다.

아직까지는 조금 어려운 감이 있다. 엄밀하게 수학적인 내용을 증명하는 게 나에게는 익숙하지 않아서, 강의를 진행하면서 꾸준히 증명하는 법을 연습해야겠다 !

글을 쓰면서 참고한 것

교수님의 강의
https://en.wikipedia.org/wiki/Vacuous_truth
https://blogshine.tistory.com/126