증명(직접 증명과 반례, 기타 증명법, 수학적 귀납법)

직접 증명과 반례

증명의 이해

공리(Axiom)

별도의 증명 없이 항상 참으로 이용되는 명제

예) 어떤 자연수 n에 대하여, n + 1 이 존재한다.

 

정의(Definition)

용어 또는 기호의 의미를 확실하게 규정한 문장이나 식

예) n! = n X (n-1) X … 3 X 2 X 1

 

정리(Theorem)

공리와 정의를 통해 참으로 확인된 명제

예) 피타고라스의 정리

 

증명(Proof)

명제가 진릿값을 확인하는 과정

 

직접증명

조건명제 p → q를 증명하기 위해 p를 참이라 가정한 상태에서 q도 참임을 증명하는 방법이다.

예시) 짝수와 홀수를 더하면 홀수가 됨을 보여라

p : 숫자 m은 짝수이고 숫자 n은 홀수이다.

q : m + n은 홀수이다.

증명)

정의에 의하여 m은 2로 나누어 떨어지는 수고, n은 2로 나누었을 때 나머지가 1인 수이다.

따라서 m을 2로 나누었을 때의 몫을 k라고 하고 n을 2로 나누었을 때의 몫을 l이라고 하면,

m = 2k, n = 2l +1 이 된다.

이 때 m + n = 2k + 2l + 1 = 2(k + l) +1이고, 이를 2로 나눈 몫은 k + l 이고 나머지는 1인 홀수이다.

∴ 명제 "짝수와 홀수를 더하면 홀수이다."는 참이다.

 

예시)모든 홀수의 제곱은 8로 나눈 나머지가 1임을 보여라
p : 자연수 m은 홀수이다.
q : m^2은 8로 나눈 나머지가 1이다.
증명)
m = 2k+1가 되는 k가 존재한다.
m^2 = (2k+1)^2 = 4k(k+1)+1 = 4k^2+4k+1
연속한 두 정수 중에 하나는 반드시 짝수이다.
따라서 k(k+1)은 2의 배수이고, 4k(k+1)은 8의 배수이다.
따라서 m^2은 8의 배수이다.

∴ 명제 "모든 홀수의 제곱은 8로 나눈 나머지가 1이다."는 참이다.

 

반례증명법

주어진 명제에 모순이 되는 예를 찾아서 명제가 거짓임을 증명하는 방법이다.

예시) 다음 명제의 진릿값을 구하시오.

모든 양수 x에 대하여 x^2 > x 이다.

증명)

x = 0.1 일 때, x^2은 0.01 이고, x는 0.1이므로 0.1^2 < 0.1이다.

∴ 반례가 존재하므로 모든 양수 x에 대하여 x^2 > x 이 성립한다는 명제는 거짓인 명제이다.

 

기타 증명법

모순증명

결론을 부정하였을 때 모순이 발생함을 보여 결론이 성립함을 증명하는 방법이다.

예시)√2는 무리수임을 보이시오.

증명)

√2가 유리수라고 가정하자. 유리수에 정의에 의하여 어떤 서로소인 정수 a, b가 존재하여 √2 = a / b 이다.

양변에 b를 곱하면 b √2=a가 되고 제곱을 하면 2b^2= a^2이 된다. 따라서 a^2이 2의 배수이므로 a는 짝수이다.

이제 a를 2로 나눈 몫을 k라고 하면 a=2k가 되고 2b^2= a^2에 대입하면

2b^2= 4k^2 이므로 b^2= 2k^2이 되어 b도 2의 배수가 된다.

그런데 a와 b는 서로소 이므로 둘이 동시에 2의 배수인 것은 가정에 모순이다.

∴ √2는 무리수이다.

 

동치증명법

주어진 명제와 동치인 명제를 증명하여 본 명제가 참임을 증명하는 방법이다.

예시) 두 정수 m, n의 곱이 홀수이면, m, n은 모두 홀수임을 증명하라

p : 두 정수 m, n의 곱이 홀수이다. => ~p : 두 정수 m, n의 곱이 짝수이다.

q : m, n은 모두 홀수이다. => ~q : m, n이 모두 홀수는 아니다.

증명)

p → q와 ~q → ~p가 동치이므로 ~q → ~p임을 보이면 충분하다. m이 짝수라고 가정하자.

m을 2로 나눈 몫을 k라고 하면 m = 2k가 되고 mn = 2kn이 되어 두 수의 곱은 짝수이다.

따라서 두 정수 m, n의 곱은 짝수이다.

n이 짝수라고 가정하여도 똑같은 방법으로 증명 가능하다.

 

경우(Case) 증명법

주어진 명제를 여러 경우(case)로 나누어서 증명하는 방법이다.

예시) 실수 x에 대하여 x ≤ |x| 임을 보이시오.

증명)

경우1) 0 ≤ x 인 경우

|x| = x 이기 때문에 x ≤ |x| 이 성립한다.

 

경우2) 0 ≥ x 인 경우

절댓값은 항상 0보다 크거나 같으므로 x ≤ 0 ≤ |x|이다.

∴ 모든 실수 x에 대하여 x ≤ |x| 이 성립한다.

 

존재증명법

주어진 명제가 존재성을 증명하는 문제일 때, 명제를 만족하는 예를 찾아 증명하는 방법이다.

예시) 임의의 실수 a, b에 대하여 a < b라고 하자. 이 때, a < x < b를 만족하는 x가 존재함을 보이시오.

증명)

x = a+b / 2 라고 하자. 이는 정확히 a와 b의 중간에 있는 숫자이므로 a < x < b를 만족한다.

따라서 a < x < b를 만족하는 x가 존재한다.

 

수학적 귀납법

자연수에 n에 대하여 정의된 명제함수 P(n)에 대하여 아래의 순서에 따라 증명하는 방법이다.

(1) 기본가정 : n = 1일 때, P(1)은 참임을 보인다.

(2) 귀납가정 : 어떤 자연수 k에 대하여 P(k)가 참일 경우 P(k+1)도 참임을 보인다.

(1)에 의해 P(1)은 참이다.

(2)에 의해 P(1)이 참이므로 P(2)도 참이다.

(2)에 의해 P(2)이 참이므로 P(3)도 참이다.

이를 반복하여 적용하면 모든 자연수 n에 대하여 P(n)이 참이다.

 

예시) 자연수 n에 대하여 1에서부터 n까지의 합이 n(n+1) / 2 임을 보이시오.

증명)

(1) n = 1일 때, 1(1+1) / 2 = 1이다.

(2) 어떤 자연수 k에 대하여 1에서 k까지의 합이 k(k+1) / 2 라고 하자. 1에서 k+1까지의 합은 k(k+1) / 2 +(k+1)이다.

결합법칙에 의해 (k+1)로 묶으면 (k+1)(k / 2 +1) = (k+1)(k+2 / 2)이고,

교환법칙에 의해 (k+1)(k+2 / 2) = (k+1)(k+2) / 2 이다.

따라서, 1에서 k + 1까지의 합은 (k+1)(k+2) / 2 이다.

∴ 수학적 귀납법에 의해 주어진 명제는 성립한다.

 

증명)

S = 1 + 2 + 3 ...
S = n + (n-1) + (n-2) ...

위의 양변을 각각 더한다.
2S = (n+1) + (n+2) ...
     = n(n+1)
따라서 S = n(n+1) / 2 이다.