[이산수학] 증명

1. 증명

공리(Axiom)
별도의 증명 없이 항상 참으로 이용되는 명제
ex) 어떤 자연수 n에 대하여 n + 1 이 존재한다

정의(Definition)
용어 또는 기호의 의미를 확실하게 규정한 문장이나 식
ex) n! = n X (n - 1) X ... 3 X 2 X 1

정리(Theorem)
공리와 정의를 통해 참으로 확인된 명제
ex) 피타고라스의 정리

증명(Proof)
명제의 진릿값을 확인하는 과정

 

직접 증명법

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

ex) 짝수와 홀수를 더하면 홀수가 됨을 증명 하시오

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인 홀수이다.
명제 "짝수와 홀수를 더하면 홀수이다"는 참이다

 

반례 증명법

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

ex) 다음 명제의 진릿값을 구하시오
모든 양수 x에 대하여 x² > x 이다.

증명)
x = 0.1 일 때, x²은 0.01이고 x는 0.1이므로 0.1² < 0.1 이다.
반례가 존재하므로 모든 양수 x에 대하여 x² > x 가 성립한다는 명제는 거짓인 명제이다.

 

모순 증명법

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

ex) √2 는 무리수임을 증명하시오

증명)
√2 가 유리수라고 가정하자
유리수에 정의에 의하여 어떤 서로소인 정수 a, b가 존재하여
√2 = a/b 이다
양변에 b를 곱하면 b√2 = a 가 되고 제곱을 하면 2b² = a² 이 된다
따라서 a²이 2의 배수이므로 a는 짝수이다
이제 a를 2로 나눈 몫을 k라고 하면 a = 2k 가 되고 2b² = a² 에 대입하면
2b² = 4k² 이므로 b² = 2k² 이 되어 b도 2의 배수가 된다
그런데 a와 b는 서로소 이므로 둘이 동시에 2의 배수인 것은 가정에 모순이다
따라서 √2 는 무리수이다

 

동치 증명법

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

ex) 두 정수 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이 짝수라고 가정하여도 똑같은 방법으로 증명 가능하다

 

경우 증명법

- 주어진 명제를 여러 경우로 나누어서 증명하는 방법

ex) 실수 x에 대하여 x ≤ |x| 임을 증명하시오

증명)
경우 1) 0 ≤ x 인 경우
|x| = x 이기 때문에 x ≤ |x| 이 성립한다

경우 2) x ≤ 0 인 경우
절댓값은 항상 0보다 크거나 같으므로 x ≤ 0 ≤ |x| 이다

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

 

존재 증명법

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

ex) 임의의 실수 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)이 참이다