수학적 증명은 그럴듯한 예를 많이 모으는 일이 아니라, 주어진 가정에서 결론이 반드시 따라온다는 것을 보이는 과정이다. 추론 규칙은 그 과정의 작은 단위이고, 직접증명·대우증명·귀류법은 여러 단계를 구성하는 방법이다. 어떤 조건을 가정했는지, 그 조건을 어디에서 사용했는지 드러내며 쓰는 것이 중요하다.
연습문제로 바로 가기 · 먼저 풀어 본 뒤 각 문제의 해설 보기를 눌러 확인할 수 있다.
1. 타당한 논증과 참인 결론
전제가 , 결론이 인 논증은
가 항진명제일 때 **타당(valid)**하다. 전제가 모두 참인 경우에 결론이 거짓일 수 없다는 뜻이다. 논증의 형식이 타당하다는 것과 실제 전제가 참이라는 것은 다르다. 타당한 형식에 거짓 전제를 넣었다면 결론이 참이라고 보장할 수 없다. 타당하고 전제도 모두 참인 논증은 건전(sound)하다고 한다.
예를 들어 는 언제나 타당한 형식이다. 그러나 를 로 놓으면 전제 부터 거짓이다. 양수끼리의 비교에서 제곱해도 부등호가 유지된다는 추론은 맞지만, 거짓 전제를 사용해 얻은 가 참이 되는 것은 아니다.
2. 명제 논리의 추론 규칙
| 규칙 | 전제 | 결론 |
|---|---|---|
| 긍정 논법, Modus Ponens | , | |
| 부정 논법, Modus Tollens | , | |
| 가설적 삼단논법 | , | |
| 선언적 삼단논법 | , | |
| 가산논법 | ||
| 단순화 | ||
| 논리곱 도입 | , | |
| 용해법, Resolution | , |
긍정 논법은 가 항진명제라는 사실에 근거한다. 나머지 규칙도 전제를 모두 묶은 조건문이 항진명제임을 확인하면 된다.
“비가 오면 소풍이 취소된다”와 “취소되지 않았다”에서는 부정 논법으로 “비가 오지 않았다”를 얻는다. 반면 “취소되었다”에서 “비가 왔다”를 얻을 수는 없다. 다른 이유로 취소되었을 수 있기 때문이다. 이것이 후건 긍정의 오류다. 에서 를 얻는 전건 부정의 오류도 마찬가지다.
용해법은 의 진리값으로 나누면 이해하기 쉽다. 가 참이면 에서 이 참이어야 하고, 거짓이면 에서 가 참이어야 한다. 어느 경우든 은 참이다. 이 규칙은 자동 정리 증명과 논리 프로그래밍의 기초가 된다.
여러 규칙을 연결하는 예제
: 화창하다, : 어제보다 춥다, : 수영한다, : 카누를 탄다, : 해질녘까지 귀가한다고 하자. 전제는
이다. “화창할 때만 수영한다”가 라는 방향에 주의한다.
| 단계 | 얻은 식 | 근거 |
|---|---|---|
| 1 | 첫 전제의 단순화 | |
| 2 | 와 1의 부정 논법 | |
| 3 | 와 2의 긍정 논법 | |
| 4 | 와 3의 긍정 논법 |
다섯 변수의 진리표는 32행이 필요하지만, 필요한 전제를 따라가면 네 단계로 끝난다.
메일을 보내면 프로그램을 마치고(), 보내지 않으면 일찍 자고(), 일찍 자면 개운하게 일어난다()고 하자. 첫 전제의 대우 에 나머지를 연결하면 가 된다.
또 와 에서 를 얻으려면
로 분배한 뒤 를 꺼내고, 와 용해법을 적용한다.
추가로 에서는 부정 논법으로 를 얻고 다시 부정 논법으로 를 얻는다. 와 의 용해 결과는 다.
3. 한정 명제에 대한 추론
| 규칙 | 내용 | 주의할 조건 |
|---|---|---|
| 전칭 예시화(UI) | 에서 | 가 정의역의 원소 |
| 전칭 일반화(UG) | 임의의 에 대해 를 보여 | 특정 원소만의 성질에 의존하면 안 됨 |
| 존재 예시화(EI) | 의 증인을 새 이름 로 둠 | 이미 정해진 원소와 같다고 가정하면 안 됨 |
| 존재 일반화(EG) | 에서 | 실제로 조건을 만족하는 증인이 필요 |
와 에서 를 얻는 전칭 긍정 논법은 UI와 긍정 논법을 합친 것이다. 에서 를 얻는 전칭 부정 논법도 같은 방식이다.
“모든 사람은 죽는다”를 로 쓰고 소크라테스에 대입하면, 소크라테스가 사람이라는 전제에서 죽는다는 결론이 나온다. 양의 정수에 대해 이 참이라고 주어졌다면 을 대입해 을 얻는 것도 같은 형식이다.
존재 증인 하나를 끝까지 유지하기
는 이 반의 학생, 는 책을 읽었다, 는 시험에 합격했다는 뜻이라고 하자.
첫 전제의 증인을 새 이름 로 두면 다. 따라서 이고, 둘째 전제를 에 적용하면 다. 다시 로 묶고 존재 일반화하면
를 얻는다. 책을 읽지 않은 사람과 시험에 합격한 사람이 같은 라는 점이 핵심이다. 서로 다른 존재 전제의 증인을 이유 없이 같은 사람으로 두면 안 된다.
전칭 명제의 연쇄
에서 임의의 를 잡는다. 를 가정하면 , 다시 가 따라오므로 다. 에 특별한 조건을 쓰지 않았으므로 전칭 일반화하여 를 얻는다.
결론이 따라오지 않는 추론
다음 전제들을 살펴보자.
여기서 를 결론으로 삼을 수 있을까? 마지막 전제의 증인 를 잡으면 이므로 , 따라서 다. 와 부정 논법을 적용하면 오히려 가 나온다. 따라서 얻을 수 있는 결론은 다.
가 따라오지 않는다는 것은 반례 해석으로도 확인할 수 있다. 정의역을 로 두고 , , 로 두면 모든 전제는 참인데 는 거짓이다.
4. 증명에서 사용하는 정의
정리는 정의·공리·이미 증명된 정리와 추론 규칙으로 참임을 보인 주장이다. 다른 증명을 돕는 정리를 보조정리(lemma), 정리에서 바로 따라오는 결과를 따름정리(corollary)라고 한다. 추측(conjecture)은 아직 증명하지 않은 주장이다.
많은 수학 문장에는 전칭 한정이 생략되어 있다. “양의 실수 에서 이면 ”는 그런 모든 에 대한 주장이다. 반면 “모든 소수는 2보다 크다”는 전칭 명제지만, 2가 반례이므로 참인 정리가 아니다.
증명을 시작할 때는 정의를 식으로 풀어 쓴다.
5. 직접증명과 대우증명
직접증명은 를 가정하고 를 도출한다. 홀수 에 대해
이므로 제곱도 홀수다. 짝수 라면 로 짝수다. 두 홀수 , 의 합도
이므로 짝수다. 여기서 은 서로 다른 정수일 수 있으므로 같은 기호로 놓지 않는다.
유리수 , 에서 이면
분자는 정수이고 분모는 0이 아닌 정수이므로 합이 유리수다. 이 3의 배수일 때도 를 대입하면 이므로 제곱이 3의 배수임을 바로 보인다.
대우를 증명하는 편이 쉬운 경우
와 는 동치다. “가 홀수이면 은 홀수”는 대우를 사용하면 짧아진다. 로 놓으면
이므로 짝수다. “이 홀수이면 도 홀수”도 짝수의 제곱이 짝수임을 보여 증명한다. 반대로 “이 짝수이면 도 짝수”의 대우는 홀수의 제곱이 홀수라는 주장이다.
이고 가 양의 정수이면 또는 이다. 둘 다 보다 크다고 가정하면 이 되어 과 맞지 않는다. 두 인수가 모두 기준보다 크다는 부정 조건이 곱셈으로 바로 연결된다.
“두 정수의 곱이 홀수이면 두 정수가 모두 홀수”도 적어도 하나가 짝수이면 곱이 짝수임을 보이는 대우증명이 자연스럽다. 이 주장은 존재 명제가 아니므로 구성적·비구성적 존재증명 중 하나로 억지로 분류할 필요가 없다.
6. 귀류법과 동치 증명
귀류법은 보이려는 명제의 부정을 가정하고 모순을 얻는 방법이다.
제곱근 2의 무리성
라고 가정하되 는 서로소인 정수이고 이라고 하자. 그러면
이 짝수이므로 도 짝수다. 를 대입하면 , 즉 이므로 도 짝수다. 가 모두 2로 나누어져 서로소라는 가정과 모순이다. 따라서 는 무리수다.
도 같은 구조로 시작한다. 서로소 에 대해 라고 가정하면 다. 정수의 제곱을 3으로 나눈 나머지는 0 또는 1이므로 이면 다. 를 대입하면 여서 도 3의 배수다. 역시 모순이다.
무리수와 유리수의 합
무리수 와 유리수 의 합이 유리수 라고 가정하자. 그러면 인데, 유리수의 차는 유리수이므로 가 무리수라는 조건과 모순이다. 따라서 합은 무리수다.
22일 중 같은 요일이 네 번 나오는 이유
어떤 요일도 네 번 나타나지 않는다고 가정하면 각 요일은 최대 세 번이다. 요일은 일곱 종류이므로 고른 날짜는 최대 개여야 한다. 22개를 골랐다는 조건과 모순이므로 같은 요일인 날짜가 적어도 네 개 있다.
필요충분조건은 양쪽을 증명한다
를 증명하려면 와 가 모두 필요하다. 앞서 보인 두 방향을 합치면
다. 또한 이면 이고, 이면 이므로 “이 짝수”, “이 홀수”, “이 짝수”는 서로 동치다.
조건문에서 결론 자체가 참임을 확인하는 것은 자명한 증명이다. 예를 들어 은 와 무관하게 참이다. 전건이 거짓임을 확인하는 것은 공허한 증명이다. 는 와 무관하게 참이다. 단순히 전제가 제시되지 않은 문장을 마음대로 거짓 전건을 가진 조건문으로 바꾸는 것은 증명이 아니다.
7. 경우를 나누는 증명
모든 가능한 경우를 빠짐없이 나누고 각 경우에서 결론을 보인다.
이 짝수라는 주장은 두 경우면 충분하다. 이면 곱은 이고, 이면 이므로 곱은 이다.
정수에서 은 , , 로 나눈다. 첫 경우는 등호이고, 둘째는 의 양변에 양수 을 곱하면 된다. 셋째는 이다. 양의 정수 처럼 경우가 유한하고 적으면 값을 모두 확인하는 전수 증명도 가능하다. 예를 들어 은 각각 , , , 로 확인된다.
절댓값의 곱
는 부호에 따라 네 경우로 확인한다.
| 조건 | ||
|---|---|---|
모든 경우에서 두 값이 같다.
최대 연산의 결합법칙
라고 정의하자. 의 크기 순서는 여섯 경우로 나눌 수 있다. 또는 이면 와 는 모두 다. 가 최대인 두 경우에는 둘 다 , 가 최대인 두 경우에는 둘 다 다. 같은 값이 있는 경우도 이 부등식들에 포함된다. 따라서 두 식은 항상 로 같다.
정수 제곱의 마지막 자리
로 쓰되 , 로 잡으면
따라서 마지막 자리는 의 마지막 자리와 같다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 의 마지막 자리 | 0 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 |
정수의 제곱은 0, 1, 4, 5, 6, 9 중 하나로 끝난다. 몇 개의 제곱수를 관찰한 것과 달리, 이 표는 가능한 나머지를 모두 다루므로 증명이다.
일반성을 잃지 않는다는 말
와 가 모두 짝수이면 가 모두 짝수임을 보이자. 대우를 위해 둘 중 적어도 하나가 홀수라고 가정한다. 식들이 를 바꾸어도 같으므로 일반성을 잃지 않고 가 홀수라고 둘 수 있다. 가 짝수이면 합이 홀수이고, 가 홀수이면 곱이 홀수다. 따라서 둘 다 짝수일 수 없다. WLOG라는 표현은 이렇게 변수 교환의 대칭성이 있을 때만 경우를 줄이는 근거가 된다.
8. 존재·비존재·유일성
구성적 존재증명은 조건을 만족하는 대상을 직접 준다.
이므로 두 가지 서로 다른 방식으로 양의 정수 두 개의 세제곱 합으로 나타낼 수 있는 수가 존재한다. 도 12가 두 소수의 합이라는 구성적 증명이다.
비구성적 존재증명은 구체적인 증인을 확정하지 않고도 존재를 보인다. 를 생각하자. 가 유리수이면 가 무리수이면서 가 유리수인 예다. 가 무리수이면 로 잡아
를 얻는다. 두 경우 중 어느 것이 실제 경우인지 결정하지 않아도 존재는 증명된다. 비구성적 증명이 반드시 귀류법 형태여야 하는 것은 아니다.
타일링과 비존재 증명
8×8 체스판은 각 행을 가로 도미노 네 개로 채우면 총 32개로 덮인다. 이것은 배치 방법을 직접 제시한 구성적 증명이다.
모서리 한 칸을 제거하면 63칸이라 두 칸씩 덮는 도미노로 채울 수 없다. 대각선 양끝 모서리를 제거하면 62칸으로 짝수지만 여전히 덮을 수 없다. 대각선 모서리는 같은 색이어서 남은 칸의 색별 개수가 30과 32가 된다. 도미노 하나는 항상 흰 칸과 검은 칸을 하나씩 덮으므로 모든 칸을 덮으면 색별 개수가 같아야 한다. 이 불변량과 모순이 생긴다.
유일성은 존재성에 한 단계를 더한다
인 실수 에 대해 의 해는 유일하다. 먼저 를 대입하면 0이 되어 존재성이 확인된다. 다른 해 가 있다고 하면
따라서 유일하다. “해가 있다”만 보이거나 “두 해가 있다면 같다”만 보여서는 유일하게 존재한다는 전체 주장이 완성되지 않는다.
9. 반례와 증명 전략
전칭 명제를 반박할 때는 반례 하나가 충분하다. “모든 양의 정수는 세 정수의 제곱의 합이다”에 대해 7을 보자. 7 이하의 제곱은 0, 1, 4뿐이다. 4를 두 번 쓰면 7을 넘고, 한 번 쓰면 나머지 두 제곱의 합으로 3을 만들어야 하지만 불가능하다. 4를 쓰지 않으면 최대 합은 3이다. 따라서 7은 반례다.
“보다 작은 모든 소수의 합은 소수”도 에서 이므로 거짓이다. 반면 “5보다 큰 소수는 홀수”는 직접증명할 수 있다. 짝수인 소수는 2뿐이기 때문이다.
증명을 찾을 때는 가정에서 출발하는 전향 추론과 결론에 필요한 조건을 거슬러 찾는 후향 추론을 함께 쓸 수 있다. 양의 실수의 산술평균과 기하평균을 비교할 때
를 발견하면 가 따라온다. 양변이 음수가 아니므로 제곱을 비교해도 되며, 등호는 일 때만 성립한다. 증명을 찾으면서 결론에서 출발했더라도, 완성된 증명에서는 각 변형이 동치인지 또는 어느 방향의 함의인지 밝혀야 한다.
돌 15개에서 번갈아 1~3개를 가져가고 마지막 돌을 가져간 사람이 이기는 게임도 끝에서 거꾸로 생각할 수 있다. 상대에게 4개를 남기면 상대가 개 가져간 뒤 내가 개를 가져가 이긴다. 같은 방식으로 상대에게 8개, 12개를 남기면 된다. 따라서 처음에 3개를 가져가 12개를 남기고, 이후 상대와 내가 한 번씩 가져간 합을 항상 4로 맞추면 승리한다.
잘못된 대수 조작을 찾기
에서 를 얻고 인수분해하면
여기서 를 약분해 라고 하면 안 된다. 처음 가정에 의해 이기 때문이다. 나눗셈, 제곱근, 부등식의 곱셈처럼 조건이 필요한 연산에서는 그 조건을 확인해야 한다.
유한한 수치 검증과 일반적인 증명도 구별한다. 예를 들어 짝수는 반으로, 홀수는 세 배에 1을 더하는 반복에서
을 확인한 것은 시작값 13에 관한 결과다. 모든 양의 정수에 대한 주장을 이것만으로 증명할 수는 없다. 전칭 명제를 다룰 때는 경우별 증명 외에도 수학적 귀납법, 재귀 구조에 대한 구조적 귀납법, 무한집합에 대한 대각선법, 같은 대상을 두 방법으로 세는 조합론적 증명 등 주장에 맞는 도구를 선택한다.
10. 연습문제
문제를 읽고 풀이를 적어 본 뒤 해설을 펼쳐 비교해 보자. 계산 결과뿐 아니라 사용한 정의와 추론 근거까지 설명하는 연습을 한다.
01. 타당성 및 추론 규칙
- 전제와 결론은 무엇이며, 전제 에서 결론 가 타당할 조건은?
- “비가 오면 소풍이 취소된다”, “소풍이 취소되지 않았다”에서 무엇을 추론하는가?
- 다음에서 사용한 규칙을 쓰자: (가) 영하이다 → 영하이거나 비가 온다. (나) 영하이고 비가 온다 → 영하이다. (다) 오늘 비가 오면 오늘 바비큐를 안 한다; 오늘 안 하면 내일 한다 → 오늘 비가 오면 내일 한다. (라) Jasmine이 스키를 타거나 눈이 안 온다; 눈이 오거나 Bart가 하키를 한다 → Jasmine이 스키를 타거나 Bart가 하키를 한다.
- 에서 를 단계별로 얻자.
해설 보기
- 전제는 출발점으로 주어진 명제, 결론은 그 전제에서 도출하려는 명제다. 가 항진명제이면 타당하다.
- 부정 논법으로 “비가 오지 않았다”를 얻는다.
- 차례로 가산논법(), 단순화(), 가설적 삼단논법(), 용해법()이다.
- 전제를 단순화하여 와 를 각각 얻고, 긍정 논법으로 를 얻는다.
02. 명제 추론을 이어 붙이기
- 에서 를 도출하자. : 메일 보냄, : 프로그램 완성, : 일찍 잠, : 개운하게 일어남이다.
- 와 에서 를 도출하자.
- “모든 문제를 풀면 이산수학을 배운다. 이산수학을 배웠다. 따라서 모든 문제를 풀었다”는 타당한가?
- 에서 를 도출하자.
- 와 의 용해 결과를 쓰자.
해설 보기
- 첫 전제의 대우는 . 이를 와 연결하면 , 다시 와 연결하면 다.
- 분배하면 이다. 단순화로 , 둘째 전제에서 를 얻어 용해하면 다.
- 부당하다. 는 후건 긍정의 오류다. 이면 전제는 모두 참인데 결론은 거짓이다.
- 와 에 부정 논법을 적용해 , 즉 를 얻는다. 이어 와 로부터 를 얻는다.
- 와 를 제거하여 를 얻는다.
03. 한정 명제의 추론
- 모든 양의 정수 에서 이 참이라고 주어졌다. 을 도출하자.
- 모든 반 학생이 이산수학을 좋아하고 철수가 반 학생이다. 철수가 이산수학을 좋아함을 도출하는 두 규칙은?
- , 에서 를 도출하자.
해설 보기
- 전칭 예시화로 . 와 긍정 논법을 적용하면 결론이다. 전칭 명제 자체는 여기서 전제로 주어진 것이다.
- 전칭 예시화로 철수에 대한 조건문을 얻고 긍정 논법을 적용한다.
- 존재 예시화로 새 증인 를 잡아 를 얻는다. 단순화로 두 성분을 꺼내고, 전칭 예시화로 를 얻는다. 긍정 논법으로 , 논리곱 도입으로 , 존재 일반화로 결론을 얻는다. 처음부터 끝까지 같은 증인 를 사용한다.
04. 전칭 명제의 연쇄
와 에서 를 증명하자.
해설 보기
임의의 원소 를 잡는다. 전칭 예시화로 와 를 얻는다. 를 가정하면 두 번의 긍정 논법으로 , 가 따라온다. 가정을 해제하면 다. 가 임의였으므로 전칭 일반화하여 를 얻는다.
05. 결론이 실제로 따라오는지 확인하기
다음 전제에서 가 따라오는지 판단하자. 따라오지 않으면 반례 해석을 제시하고 실제로 도출되는 결론을 찾자.
해설 보기
는 따라오지 않는다. 정의역을 로 두고 로 두면 네 전제는 모두 참인데 는 거짓이다.
실제로는 를 도출할 수 있다.
| 단계 | 식 | 근거 |
|---|---|---|
| 1 | 존재 예시화, 새 증인 | |
| 2 | 전칭 예시화 | |
| 3 | 1, 2의 선언적 삼단논법 | |
| 4 | 전칭 예시화 | |
| 5 | 3, 4의 선언적 삼단논법 | |
| 6 | 전칭 예시화 | |
| 7 | 5, 6의 부정 논법 | |
| 8 | 존재 일반화 |
가 참이라고 해서 항상 가 거짓이라는 뜻은 아니다. 다른 원소에서 이 참일 수 있다. 위의 한 원소 반례가 보여 주는 것은 요청된 결론이 전제에 의해 보장되지 않는다는 점이다.
06. 직접증명과 대우증명
- 정수 이 짝수이면 이 짝수임을 직접증명하자.
- 두 유리수의 합이 유리수임을 보이자.
- 이 홀수이면 이 홀수임을 대우로 보이자.
- 양의 정수 와 에 대해 또는 임을 보이자.
- 두 홀수의 합이 짝수임을 직접증명하자.
해설 보기
- 인 정수 가 있으므로 다.
- 로 쓰되 는 정수이고 이다. 는 정수 분자와 0이 아닌 정수 분모의 비다.
- 대우인 “이 짝수이면 이 짝수”를 1에서 증명했다.
- 둘 다 보다 크다고 가정하면 으로 과 모순이다.
- 로 놓으면 이다. 서로 다른 홀수일 수 있으므로 을 따로 둔다.
07. 세 명제의 동치와 3의 배수
- 정수 에 대해 “이 짝수”, “이 홀수”, “이 짝수”가 동치임을 보이자.
- 이면 임을 직접증명하자.
- 이면 임을 보이자.
- 의 무리성을 귀류법으로 증명하려면 어떤 가정으로 시작하는가?
해설 보기
- 이면 이다. 반대로 이면 이다. 또한 짝수의 제곱은 짝수다. 역방향은 대우로, 이면 이 홀수임을 보이면 된다.
- 이므로 다.
- 대우가 바로 2번이다. 나누어떨어지지 않음을 직접 다루는 대신 배수의 정의를 쓸 수 있다.
- 인 서로소 정수 가 있으며 이라고 가정한다. 그러면 . 정수 제곱의 3에 대한 나머지는 0 또는 1이므로 . 를 대입하면 여서 도 따라와 서로소 조건과 모순이다.
08. 공허한 증명과 자명한 증명
- “모든 소수는 2보다 크다”에서 한정 기호를 쓰고 참인지 판정하자.
- “정수 에 대해 가 짝수다”를 공허하게 증명할 수 있는가? 공허한 증명이 가능한 조건을 설명하자.
- 공허한 증명과 자명한 증명을 비교하자.
해설 보기
- 다. 소수 2가 반례여서 거짓이다.
- 전건 없이 모든 정수에 대해 주장한다면 거짓이다. 에서 가 홀수다. 공허한 증명은 에서 전건 가 거짓임을 보일 때 가능하다. 존재하지 않는 전제를 임의로 붙여 주어진 주장을 증명했다고 할 수는 없다.
- 공허한 증명은 전건이 거짓이어서, 자명한 증명은 후건이 참이어서 조건문이 참임을 보인다. 예를 들어 는 공허하고, 는 실수 에서 자명하다.
09. 귀류법으로 무리수의 합 증명하기
무리수 와 유리수 의 합 가 무리수임을 귀류법으로 보이자.
해설 보기
가 유리수라고 가정한다. 유리수 로 쓰되 이면
이는 정수의 비이므로 유리수다. 가 무리수라는 가정과 모순이다. 따라서 는 무리수다. 두 무리수의 합까지 항상 무리수라는 뜻은 아니다. 예를 들어 이다.
10. 경우별 증명
- 모든 정수 에서 임을 보이자.
- 모든 실수 에서 임을 네 부호 경우로 보이자.
- 모든 정수 에서 이 짝수임을 보이자.
해설 보기
- 이면 등호다. 이면 에 양수 을 곱해 . 이면 이다. 정수는 이 세 경우로 빠짐없이 나뉜다.
- 다음 표에서 두 값이 항상 같다.
| 조건 | ||
|---|---|---|
- 이면 , 이면 로 모두 2의 배수다.
11. 존재·유일성·반례와 증명 방법 선택
- 구성적 존재증명과 비구성적 존재증명의 차이는?
- “두 정수의 곱이 홀수이면 두 정수 모두 홀수”에 적합한 증명 방법은?
- “보다 작은 모든 소수의 합은 소수다”를 판정하자.
- 유일하게 존재함을 보일 때 필요한 두 부분은?
- “이 짝수이면 이 짝수”에 대우증명이 편리한 이유는?
- 5보다 큰 모든 소수가 홀수임을 보이자.
- 12가 두 소수의 합임을 구성적으로 보이자.
해설 보기
- 구성적 증명은 조건을 만족하는 대상을 직접 제시한다. 비구성적 증명은 어떤 대상인지 확정하지 않고 존재를 보인다. 비구성적 증명이 반드시 귀류법인 것은 아니다.
- 대우증명이 자연스럽다. 적어도 하나가 짝수이면 곱이 짝수다. 예를 들어 이면 . 이 명제는 존재 명제가 아니므로 구성적/비구성적 존재증명 중 하나로 분류할 필요가 없다.
- 거짓이다. 이면 으로 소수가 아니다.
- 실제 해가 있다는 존재성과, 임의의 두 해가 같다는 유일성이 모두 필요하다.
- 이 홀수일 때 을 대입하면 이 되어 바로 홀수임을 보일 수 있다.
- 소수 의 약수는 1과 뿐이다. 는 어느 쪽도 아니므로 , 즉 는 홀수다.
- 이고 5와 7은 소수다. 조건을 만족하는 두 수를 실제 제시했으므로 존재가 증명된다.
Comments