직접증명, 대우와 모순

로그를 몇 번 살펴봐서 오류가 없었다고 프로그램의 모든 입력이 안전하다고 말할 수는 없습니다. 수학의 증명도 같은 구분에서 시작합니다. 예를 여러 번 확인하는 일과, 조건을 만족하는 모든 대상에 결론이 성립함을 보이는 일은 다릅니다.

준비와 학습 목표

조건명제와 추론 규칙을 먼저 익힙니다. 이 절을 마치면 가정·정의·결론을 구분하고, 직접증명·대우증명·모순증명 중 알맞은 방법을 골라 짧은 증명을 작성할 수 있습니다.

정수 $n$이 짝수라는 말은 어떤 정수 $k$에 대해 $n=2k$라는 뜻입니다. 홀수는 $n=2k+1$입니다. 0과 음의 정수에도 이 정의를 그대로 적용합니다. 예를 들어 $-3=2(-2)+1$이므로 -3도 홀수입니다. 정의를 식으로 바꾸는 것이 증명의 첫 동작입니다.

직접증명: 가정에서 결론까지 이어 쓰기

명제: 두 홀수의 합은 짝수이다.

1. 임의의 홀수 $a,b$를 잡습니다. 특정한 3과 5를 잡는 것이 아닙니다.
2. 정의에 따라 정수 $r,s$가 있어서 $a=2r+1$, $b=2s+1$입니다.
3. 더하면 $a+b=2r+1+2s+1=2(r+s+1)$입니다.
4. $r+s+1$은 정수입니다. 따라서 합은 정수의 두 배이고 짝수입니다.

마지막 줄은 단순한 계산 마무리가 아닙니다. 계산 결과를 짝수의 정의에 연결해 결론을 얻는 줄입니다. '$a+b$가 짝수니까 $a+b=2k$'라고 시작하면 증명해야 할 결론을 먼저 가정한 순환 논증이 됩니다.

대우증명: 동치인 명제를 선택하기

$P\to Q$의 대우는 $\neg Q\to\neg P$이며 둘은 논리적으로 동치입니다. 역 $Q\to P$를 증명하는 것과 구분합니다.

명제: 정수 $n$에 대해 $n^2$이 짝수이면 $n$은 짝수이다.

가정 $n^2=2k$에서 $n$의 모양을 바로 알아내기 어렵습니다. 대우인 '$n$이 홀수이면 $n^2$이 홀수이다'를 증명합니다. $n=2r+1$이라 두면

$$n^2=(2r+1)^2=4r^2+4r+1=2(2r^2+2r)+1.$$

$2r^2+2r$는 정수이므로 제곱은 홀수입니다. 대우가 참이므로 처음 명제도 참입니다. 이때 정수가 짝수와 홀수 중 정확히 하나라는 사실을 사용했습니다. 실수 전체에서는 이 논증의 분류를 적용할 수 없습니다.

모순증명: 결론을 부정해 모순 찾기

모순증명에서는 명제가 거짓이라고 가정한 다음 그 가정들이 동시에 참일 수 없음을 보입니다. 조건명제 $P\to Q$를 다룬다면 $P$와 $\neg Q$를 함께 가정합니다.

명제: $\sqrt2$는 무리수이다.

유리수라고 가정하여 $\sqrt2=a/b$로 씁니다. $a,b$는 서로소인 양의 정수이고 $b\ne0$입니다. 기약분수로 잡을 수 있는 이유는 공약수를 모두 약분할 수 있기 때문입니다.

양변을 제곱하면 $a^2=2b^2$입니다. $a^2$이 짝수이므로 방금 증명한 명제로 $a$도 짝수입니다. $a=2k$를 대입하면 $4k^2=2b^2$, 곧 $b^2=2k^2$이므로 $b$도 짝수입니다. 그러면 $a,b$가 모두 2로 나누어져 서로소라는 가정과 모순입니다. 따라서 유리수라는 가정은 거짓이고 $\sqrt2$는 무리수입니다.

무리수의 소수 자릿수가 '무작위'라서 무리수라고 판단하지 않습니다. 핵심은 정수의 비로 표현할 수 없음입니다. 실제 소수 전개를 몇 자리 확인하는 것만으로 이 결론을 얻을 수 없습니다.

혼동하기 쉬운 점

대우증명은 $\neg Q$에서 $\neg P$를 이끌어 끝내고, 모순증명은 부정한 가정으로 불가능한 결론을 만들어 끝냅니다. 비슷한 계산을 쓰더라도 논증의 출발점과 마무리를 표시해야 합니다. 공리는 선택한 체계의 출발 가정이고, 정리는 그 가정에서 증명한 명제입니다. 공리가 모든 상황에서 스스로 증명된 진리라는 뜻은 아닙니다.

스스로 풀어보기

문제 1. 짝수와 홀수의 합이 홀수임을 직접증명하세요.

힌트: 각각 $2r$, $2s+1$로 쓰고 합에서 2를 묶습니다.

풀이: 임의의 짝수 $a=2r$와 홀수 $b=2s+1$에 대해 $a+b=2(r+s)+1$입니다. $r+s$가 정수이므로 홀수의 정의를 만족합니다. 예시만 나열하는 대신 임의의 정수 매개변수 두 개로 모든 경우를 다뤘습니다.

문제 2. 정수 $n$에 대해 $n^2$이 홀수이면 $n$이 홀수임을 대우증명하세요. 역명제도 참인가요?

힌트: 대우는 '$n$이 짝수이면 $n^2$이 짝수이다'입니다.

풀이: $n=2k$이면 $n^2=4k^2=2(2k^2)$이고 $2k^2$가 정수이므로 짝수입니다. 대우가 참이어서 원명제도 참입니다. 역명제인 '홀수의 제곱은 홀수'는 앞의 $2r+1$ 계산으로 참입니다. 역이 참이라는 판단은 별도 증명에서 나왔으며, 원명제만으로 자동 보장되지는 않습니다.

복습과 다음 단계

증명마다 '어떤 집합의 대상인가', '무엇을 가정했나', '어느 정의로 끝냈나'를 표시해 보세요. 논증 방향이 헷갈리면 추론 규칙으로 돌아갑니다. 다음 존재증명과 반례에서는 하나의 예로 충분한 주장과 모든 경우를 다뤄야 하는 주장을 구분합니다.