1. 직관과 증명의 패러다임
1.1. 카드 문제
- 사실 : 모든 카드의 한쪽에는 알파벳, 다른 쪽에는 숫자 존재
- 주장 : 한쪽이 D라면 반대쪽은 3
- 주장이 사실임을 증명하기 위해 반드시 뒤집어보아야하는 카드는?
- 문제 : D F 3 7
정답은 D, 7 2개이다. F는 주장과 관련이 없으므로 뒤집어볼 필요가 없고, 3은 D가 있든 없든 영향을 주지 않는다. 7은 뒤집었을 때 D가 나온다면 주장이 성립하지 않게 되므로 확인해봐야 한다.
1.2. 맥주집 문제
- 규칙 : 20세 이하인 사람은 맥주를 마실 수 없음
- 17세 , 31세, 콜라, 맥주 - 4명 중 확인이 필요한 사람은?
정답은 17세, 맥주 2명이다. 카드 문제보다 맥주집 문제가 풀기 쉽게 느껴지지만 논리적 구성은 동일하다. 그렇다면 왜 맥주집 문제가 풀기 쉬운가? 이유는 맥주집은 일상에서 쉽게 접할 수 있는 상황이기 때문에 직관력을 사용했기 때문이다. 이러한 직관은 빠른 결론을 내릴 수 있지만, 정확하지 않고 강한 착각을 일으킨다는 것이다. 예를 들면 달리기 대회를 하고 있다고 생각해보자. 내가 현재 3등으로 달리고 있고 2등을 제쳤다. 나는 현재 몇등인가? 라는 질문에서 정답은 2등이지만 1등으로 답하는 착각이 생길 수 있다는 것과 비슷하다.
이러한 오류의 근원에는 알고리즘을 Soft Logic(직관)으로 이해하려고 하는 문제 때문이다. 프로그래밍은 표현들이 모두 논리학에서 나온 것으로 직관이 아닌 Hard Logic (증명)이 필요하다. 직관으로 이해가 되는 알고리즘도 존재하지만 알고리즘의 난이도가 올라간다면 직관으로 완전한 이해를 얻는 것은 불가능에 가깝다.
2. 논리
참 / 거짓 판단 문제
- 만약 0이 홀수라면, 미국에서 2040년에 월드컵이 열린다.
- 만약 12932312418527이 소수라면, 2는 짝수이다.
두 가지 모두 결과는 참이다.
1번 문제를 p 이면 q이다 에서 p 명제가 거짓이다. p명제가 거짓이면 q명제는 참/거짓 여부와 관계 없이 항상 참이다. 이를 Soft Logic에 빗대어보면 "수학 100점 맞으면 치킨 사줄게"로 예시를 들 수 있다. 100점을 맞는다면 q명제의 여부가 결과에 영향을 미치지만, p가 거짓이므로 항상 참이 되는 것이다.
2번 문제는 p : 모름 q : 사실 이다. 하지만 모든 명제는 대우가 참이다. ~q -> ~p에서 ~q는 거짓이 된다. 그러므로 1번의 예시와 같이 ~p의 참/여부와 상관없이 해당 명제는 참이 된다. 대우가 참이므로, 본 명제 또한 참이 된다.
- 명제 p -> q가 거짓이라면, 다음 명제식의 참 / 거짓
- ~p -> q : 참
- p V q ( V는 논리합 (or) ) : 참
- q -> p : 참
p -> q 가 거짓인 경우는 p : 참, q : 거짓인 경우 뿐이다. 따라서 ~p는 거짓이므로 ~p -> q는 참이다.
p V q 는 참 or(논리합) 거짓 이므로 참이 된다.
q -> p 이다는 거짓 -> 참 이므로 참이 된다.
3. 증명
- 증명이라 함은 근본적으로 명제식으로 표현할 수 있어야 한다. 증명에 대한 수 많은 오해는 p -> q를 p <-> q로 혼동한는 것에서 발생한다.
3.1. 당구공 문제
다음 모든 당구공의 색은 같다는 증명에서 잘못된 것은 ?
- 수학적 귀납법 : P(1) 이 참이고, P(N) -> P(N+1)이 참이면 P(N) 은 모든 자연수 N에 대해서 참이다.
- 모든 자연수 N에 대해 당구공 N개가 들어있는 집합에서 그 집합에 포함된 당구공은 모두 색이 같다는 것을 증명한다.
- P(1) : 당구공 1개가 들어있는 집합의 색은 모두 같다.
- P(N) -> P(N+1)을 증명하기 위해 P(N)이 참이라고 가정한다. (정답)
P(N) -> P(N+1) 이 참이라면 모든 당구공은 같은 색이다. 그 이유는 당구공이 N+1개가 있는 임의의 집합을 떠올려보자. 현 상황에서 모든 당구공의 색이 같다. 임의의 공을 계속 뺐다 넣어도 같은 색을 넣고 빼는 것이므로 항상 참이다.
하지만, P(N)이 참이라고 가정할 수 없다고 반론하는 경우가 있다. 잘 생각해보자. 아까 다룬 문제처럼 명제가 참이면 p의 참 / 거짓 여부는 상관이 없다. 그러므로 P(N)이 참이라고 가정할 필요가 없다. 거짓일 때도 참이기 때문
3.2. Prime Number
Prime Number (소수)의 개수는 무한히 많다는 증명은 옳은가?
- 소수의 개수가 유한한 K개라고 가정
- 모든 소수를 다 곱하고 1을 더한 수를 n이라 할 때, 이 수 n은 어떤 소수로 나누어도 나머지가 1이다.
- n은 어떤 소수 보다도 크므로 합성수이다.
- 합성수이지만 어떤 소수로도 나누어지지 않으므로 모순 발생
PrimeNumber가 무한히 없다는 것을 증명하기 위해 유한한 K를 가정했다. K개 있으므로 p1, p2, ... , pk 개가 있다고 보자. p1+p2+...+pk는 n이다. n은 당연히 소수가 아니다. 유한히 있다고 가정했고 모든 소수보다 크기 때문이다. 소수가 아니라면 소인수분해가 돼야하는데 n을 어떤 수로 나누어도 나머지가 1이라면 모순이 발생(나누어지지 않으면 소수)하게 된다. 즉, 소수는 무한히 많다라는 결론이 된다.
3.3. 수학적 귀납법
수학적 귀납법의 기본형 : P(1)이 참이고, P(N) -> P(N+1) 이 참이면 P(N)은 모든 자연수 N에 대해 참이다.
<code />
int sum(int x) {
if (x <= 0) return 0;
return x + sum(x-1);
}
- 1~x까지의 합을 구하는 예시
S(N) = S(N-1)+N이므로 답이 일치한다라는 결론은 Hard Logic의 증명에 부합하지 않다. 증명이 가능한 명제를 찾아야 한다.
"sum(x)가 리턴하는 값은 1+2+...+x의 값과 항상 같다." 라는 명제를 사용한다. 귀납법의 기본형인 P(1)이 참은 sum(1)이 리턴하는 값은 1이다를 증명한다. 이후 P(N) -> P(N+1)이 참이다는 sum(x-1)이 1+2+...+(x-1)을 리턴하면 sum(x) 는 1+2+...+x를 리턴한다를 증명하면 된다. 즉, (x-1) 이 리턴하는 값을 가정한 후 (블랙박스) 증명을 한다.
