안녕하세요. 오랜만에 글을 쓰는데 거두절미하고 '증명의 소개'에 대해서 알아보겠습니다.
먼저 증명을 공부하기 전에 알아 두어야 할 용어들이 있습니다.
정리(theorem) : 참임을 보일 수 있는 하나의 진술
프로포지션(proposition) : 참임을 보일 수 있는 하나의 진술이지만 정리보다는 중요도가 낮음
공리(postulate) : 증명을 하지 않아도 참이라고 할 수 있는 진술
보조정리(lemma) : 증명하는데 도움이 되지만 덜 중요한 정리
계(corollary) : 증명된 정리로부터 직접적으로 귀결될 수 있는 정리
가설(conjecture) : 사람의 직감에 근거해서 참이라고 주장하는 문장. 만약 가설이 증명되면 가설은 정리가 됨. 거짓일 경우 정리가 될 수 없음
증명의 방법에는 여러가지 방법이 있습니다.
1. 직접 증명
2. 대우에 의한 증명
3. 공허한 증명과 자명한 증명
4. 모순에 의한 증명
5. 동치 증명
6. 반례
차례대로 살펴보겠습니다.
먼저 직접 증명입니다.
조건문 p → q를 직접 증명할 때 먼저 p를 참이라고 가정하고 그 후 추론 규칙들을 적용합니다.
마지막으로는 q가 참임을 보이면 증명이 완료됩니다.
즉, p가 참 일때 q가 참일 수 밖에 없음을 보이면 됩니다.
그렇게 되면 p->q가 참임을 보일 수 있습니다.
p가 참이라고 가정하고 공리나 정의, 이전에 했던 증명들, 추론 규칙들을 사용하면 됩니다.
말로만 설명하면 이해가 어려우니 예시를 하나 들어보겠습니다.
"만약 n이 홀수인 정수라면 n^2는 홀수인 정수이다"
위 문장을 증명하기 위해서 n = 2k + 1이라고 합니다, k는 정수입니다.
그렇다면 n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1이 됩니다.
k는 정수라고 정의했기 때문에 2(2k^2 + 2k)는 정수이고 짝수입니다.
따라서 짝수에 1을 더한 n^2는 홀수가 됩니다.
직접 증명은 정말 증명의 이름대로 직접 뛰어들어가서 이리 저리 돌려보면서 증명하는 것입니다.
두번째로는 대우에 의한 증명입니다.
우리는 아주 예전에 어떠한 명제가 참이는 그 명제의 대우도 참이라는 것을 배웠습니다.
따라서 우리가 증명해야할 정리를 대우시키고 그 대우시킨 정리가 참임을 증명한다면 원래의 명제가 참임을 보일 수 있겠습니다.
정말 유용합니다.
조건문 p → q 의 대우 ￢q → ￢p 가 동치라는 사실을 이용하는 것입니다. ￢q를 참이라고 가정하고 증명을 시작합니다.
보통 직접 증명하는 것이 어려울 때 대우에 의한 증명을 시도하면 운 좋게 쉽게 증명을 마칠 수도 있습니다.
예시를 보이겠습니다.
"만약 3n + 2가 홀수면 n은 홀수이다"
이 명제는 직접증명을 시도하면 중간에 턱 막히는 부분이 있습니다. (없으면 말고요)
그래서 대우에 의한 증명을 시도해보면 위 명제는 다음과 같이 다시 쓸 수 있습니다.
"만약 n이 짝수면 3n+2는 짝수다"
정수는 홀수나 짝수 뿐이니까 홀수의 부정은 짝수입니다.
n = 2k라고 합시다. k는 정수입니다.
따라서 3n + 2 = 3(2k) + 2 = 2(3k + 1) 이 됩니다.
3k + 1은 k가 정수이므로 정수입니다.
따라서 이 수의 2배를 한 수는 짝수입니다.
즉, 3n + 2는 짝수입니다.
n이 짝수일때 3n + 2는 짝수임을 증명했으므로 원래의 문장 "만약 3n + 2가 홀수면 n은 홀수이다" 라는 문장을 간접적으로 증명했습니다.
세 번째로는 공허한 증명과 자명한 증명입니다.
이건 사실 별게 있는 것은 아닙니다.
조건문 p → q 를 증명할 때 p가 애초에 거짓이라면 이 명제는 볼 것도 없이 참이 됩니다.
너무 공허합니다. vacuous. 이게 공허한 증명입니다.
지금 허한 느낌을 받으셨거나 '뭐가 이래?' 와 같은 생각이 들었다면 정상입니다.(아님 말고요)
자명한 증명은 조건문 p → q 가 q를 증명함으로써 증명되는 것입니다. 그럼 이때는 p가 참이든 거짓이든 조건문은 참이 되겠죠?
다음은 모순에 의한 증명입니다.
p라는 명제가 참임을 증명하는 과정이라고 생각해봅시다. 또한 ￢p → q가 참이 되도록하는 모순 q를 찾았다고 가정합시다. 모순은 항진과 모순할 때 모순입니다. ( ￢x ∧ x)
q가 모순이므로 거짓이고, 위에서 기재한 조건문이 참이 되기 위해서는 ￢p는 거짓이어야 합니다. 따라서 p는 참이됩니다.
따라서 여기서 저희가 해야할 것은 모순 q를 찾는 것입니다.
이렇게 증명하는 것이 모순을 이용한 증명입니다.
모순에 의한 증명도 간접 증명의 한 예가 되겠습니다.
이번에도 예시를 살펴보겠습니다.
"sqrt(2)가 무리수임을 보여라"
sqrt는 제곱근(루트) 입니다.
명제 p가 "sqrt(2)가 무리수다" 라고 한다면 ￢p는 "sqrt(2)는 유리수다"가 됩니다.
여기서 ￢p가 참이라고 가정합니다. 이렇게 했을 때 모순이 발생함을 보이면 됩니다.
sqrt(2)가 유리수라면 a/b로 표현할 수 있습니다. (기약분수입니다.)
여기서 양변을 제곱하면 2 = a^2 / b^2 이 됩니다. 조금 더 정리하면 2b^2 = a^2가 됩니다.
a^2은 b^2의 2배이기에 a^2은 짝수입니다.
여기서 a^2가 짝수이면 a도 짝수입니다. 따라서 a = 2c로 표현할 수 있습니다.
a^2 = 4c^2이 되겠죠.
이 식은 2b^2과 같은 식이므로 다음과 같이 쓸 수 있습니다.
2b^2 = 4c^2
어? 2로 나누어집니다. b^2 = 2c^2
따라서 b도 짝수입니다.
여기서 모순이 발생합니다. a와 b 둘 다 짝수라면 a와 b가 2로 나누어진다는 결론을 얻었습니다.
기약분수가 나누어진다는 것은 말이 안되기 때문에 ￢p가 거짓임을 알 수 있습니다.
그렇다면 p가 참이됩니다.
sqrt(2)가 무리수임을 보였습니다.
모순에 의한 증명은 조건문을 증명할 때에만 사용할 수 있습니다.
증명에서 결론의 부정을 참이라고 가정합니다. 그렇게 여러 도구들을 사용하면서 결론이 모순에 도달함을 보이는 것입니다.
이번에는 동치 증명입니다.
동치 증명은 상호 조건문 형태를 가지고 있는 정리를 증명하기 위해서 p → q와 q → p가 모두 참임을 보이면 됩니다.
이번에는 따로 예시들 들지는 않겠습니다. 위 일반 조건문 두 개를 증명하면 되는 것인데, 두 조건문의 증명은 위에서 다루었던 증명 방법들로 해결할 수 있기 때문입니다.
한 마디로 짬뽕한 것이기 때문에 넘어가겠습니다.
마지막으로 반례입니다.
반례는 쉽게 말해서 '한 놈만 걸려라!' 입니다.
어떠한 명제가 거짓임을 보이려면 거짓이 되도록 하는 변수를 찾으면 되는 것입니다.
만약 ∀xP(x)가 거짓임을 보이기 위해서는 이 명제를 만족하지 않는 x를 딱 한 놈만 잡으면 됩니다.
보통 여러가지 증명 방법들을 사용했음에도 불구하고 증명을 못하겠다라는 생각이 들때 최후의 보루로 사용합니다.
거진 3년 4년만에 글을 쓰게 되었는데 저도 쓸 줄 몰랐습니다.
글을 추가적으로 더 쓸지는 미정일 것 같아요.
그래도 읽어주셔서 감사합니다.
좋은 하루 되세요 :)
'지식 > 이산수학' 카테고리의 다른 글
| [이산수학] 1.5 추론 규칙 (3) | 2019.04.11 |
|---|---|
| [이산수학] 1.4 중첩된 한정기호 (7) | 2019.04.02 |
| [이산수학] 1.3 술어와 한정기호 (0) | 2019.03.26 |
| [이산수학] 1.2 명제의 동치 (0) | 2019.03.24 |
| [이산수학] 1.1 명제 논리 (2) | 2019.03.20 |
