22강에서 명제가 참임을 보이려면 임의의 원소로 논증해야 한다고 했습니다. 그 논증을 실제로 쓰는 방법이 이 강의의 내용입니다. 여기서부터는 읽는 쪽이 아니라 쓰는 쪽입니다.
증명을 쓸 때 가장 자주 막히는 곳은 계산이 아니라 시작점입니다. "이 짝수라고 하자"까지는 쓰는데 그다음 줄이 나오지 않습니다. 이 강의는 그 막힘을 정의를 식으로 옮기는 습관으로 풉니다. 짝수라는 말을 라는 식으로 바꾸는 순간 증명은 2강에서 하던 식 조작이 됩니다.
문제. "두 짝수의 합은 짝수입니다"를 증명하세요. 이 짝수라는 것은 인 정수 가 존재한다는 뜻입니다.
생각의 실마리. 처럼 예를 몇 개 확인하는 것으로는 증명이 되지 않습니다. 22강 문제 3에서 사례 개가 맞아도 번째에서 깨질 수 있음을 보았습니다. 대신 짝수라는 말을 식으로 바꾸고, 그 식으로 계산해서 결론도 같은 모양의 식으로 만들어 봅니다.
풀이. 증명할 명제를 기호로 적으면 , (이 짝수이고 이 짝수이면 이 짝수)입니다.
임의의 정수 과 을 잡고, 둘 다 짝수라고 가정합니다.
짝수의 정의에 따라 인 정수 가 존재하고 인 정수 가 존재합니다. 여기서 와 를 같은 문자로 쓰면 안 됩니다. 과 이 다른 수일 수 있기 때문입니다.
이제 합을 계산합니다.
와 가 정수이므로 도 정수입니다. 따라서 은 어떤 정수의 배 꼴이며, 짝수의 정의를 만족합니다.
과 은 조건을 만족하는 임의의 정수였으므로, 모든 그러한 정수쌍에 대해 성립합니다. 증명이 끝났습니다.
이 문제에서 배우는 것: 증명의 뼈대와 정의의 사용.
증명은 가정에서 출발해 이미 참으로 인정된 것만 써서 결론까지 가는 문장의 사슬입니다. 사슬의 각 고리는 정의, 앞서 증명된 정리, 그리고 계산 규칙 중 하나여야 합니다.
방금 쓴 증명의 뼈대는 다음 네 줄입니다.
이 중 2번이 시작점입니다. 말을 식으로 바꾸는 것이 증명의 첫 삽입니다. 정의를 정확히 알고 있어야 이 단계가 가능하므로, 증명이 막히면 먼저 정의를 다시 적어 봅니다.
이 강의에서 계속 쓸 정의를 여기에 모아 둡니다.
| 말 | 식 |
|---|---|
| 은 짝수입니다 | 인 정수 가 존재합니다 |
| 은 홀수입니다 | 인 정수 가 존재합니다 |
| 는 를 나눕니다 () | 인 정수 가 존재합니다 |
| 는 유리수입니다 | 인 정수 와 이 아닌 정수 가 존재합니다 |
한 가지 더 주의합니다. 서로 다른 대상에는 서로 다른 문자를 씁니다. , 라고 쓰면 을 가정한 것이 되어 증명이 무너집니다.
바로 확인.
확인 1-1. "짝수와 홀수의 합은 홀수입니다"를 증명하세요.
답. 이고 이라 하면 입니다. 가 정수이므로 홀수의 정의를 만족합니다.
확인 1-2. "두 홀수의 곱은 홀수입니다"를 증명하세요.
답. , 이라 하면 입니다. 괄호 안이 정수이므로 홀수입니다.
확인 1-3. "이고 이면 입니다"를 증명하세요.
답. 이고 인 정수 가 있습니다. 대입하면 이고 가 정수이므로 입니다.
문제. "모든 정수 에 대하여, 이 짝수이면 도 짝수입니다"를 증명하세요. 그리고 증명 안의 "임의의 정수 을 잡습니다"라는 문장이 왜 필요한지 설명하세요.
생각의 실마리. 일 때 이 짝수임을 보이는 것은 한 사례일 뿐입니다. 그런데 그 계산을 자세히 보면 라는 숫자가 어디에도 본질적으로 쓰이지 않습니다. 숫자 대신 문자를 두고 같은 계산을 하면 무엇이 달라지는지 봅니다.
풀이. 임의의 정수 을 잡고 이 짝수라고 가정합니다.
짝수의 정의에 따라 인 정수 가 존재합니다. 제곱하면
입니다. 가 정수이므로 도 정수이고, 따라서 은 짝수입니다.
에 대해 짝수라는 것 말고는 아무 성질도 쓰지 않았습니다. 그러므로 이 논증은 짝수인 어떤 정수를 넣어도 그대로 통합니다. 이것이 전칭 명제의 증명입니다.
이 문제에서 배우는 것: 임의의 원소 잡기.
를 증명하는 표준 방법은 다음과 같습니다.
의 원소 를 하나 잡되, 에 대해 의 원소라는 것 외에 아무것도 가정하지 않습니다. 그 상태에서 를 유도합니다.
이렇게 하면 논증이 의 어느 원소에도 통하므로 전체에 대한 증명이 됩니다. 이 방식을 임의의 원소 잡기라고 하고, "임의의 를 잡습니다" 또는 "라고 하자"라고 씁니다.
여기서 가장 흔한 실수는 잡은 원소에 몰래 추가 조건을 붙이는 것입니다. "임의의 정수 을 잡습니다. 이므로..."라고 쓰면 양수만 다룬 것이 되어 증명이 되지 않습니다. 증명을 다 쓴 뒤 잡은 대상에 어떤 성질을 썼는지 되짚어 보는 것이 좋은 습관입니다.
한편 의 증명은 반대입니다. 구체적인 를 하나 제시하고 를 확인합니다. 여기서는 원하는 성질을 마음껏 붙여도 됩니다. 22강 문제 1의 (나)에서 를 제시한 것이 그 예입니다.
바로 확인.
확인 2-1. "모든 정수 에 대하여 은 짝수입니다"를 로 묶어 설명해 보세요. 어떤 부분에서 경우를 나눠야 합니까?
답. 이고 연속한 두 정수 중 하나는 반드시 짝수이므로 곱이 짝수입니다. "하나는 반드시 짝수"라는 부분에서 이 짝수인 경우와 홀수인 경우로 나눠야 하며, 이것을 문제 4에서 정식으로 다룹니다.
확인 2-2. 다음 증명의 잘못을 지적하세요. "임의의 정수 을 잡습니다. 라고 하면 이므로 짝수입니다. 따라서 모든 정수의 제곱은 짝수입니다."
답. 임의로 잡았다고 해 놓고 곧바로 라는 추가 조건을 붙였습니다. 한 사례를 확인했을 뿐입니다. 게다가 결론 자체가 거짓이며 이 반례입니다.
확인 2-3. "어떤 정수 에 대하여 입니다"를 증명하세요.
답. 을 제시합니다. 이므로 성립합니다. 존재 명제이므로 하나만 제시하면 끝납니다.
문제. "모든 정수 에 대하여, 이 짝수이면 도 짝수입니다"를 증명하세요.
생각의 실마리. 문제 2와 방향이 반대입니다. 직접증명을 시도하면 에서 시작해야 하는데, 여기서 로 가면 정수라는 성질을 다루기 어려워집니다. 21강 문제 5에서 대우가 원래 명제와 동치임을 진리표로 확인했습니다. 대우를 적어 보고 그쪽이 다루기 쉬운지 봅니다.
풀이. 직접 시도하면 에서 의 모양을 뽑아내야 하는데, 제곱근을 취하면 정수라는 정보가 사라져 막힙니다.
대우를 적습니다. 원래 명제가 "이 짝수 이 짝수"이므로 대우는
입니다. 정수는 짝수이거나 홀수이므로 이것은 "이 홀수이면 도 홀수입니다"와 같습니다.
이제 대우를 증명합니다. 임의의 정수 을 잡고 홀수라고 가정하면 인 정수 가 존재합니다. 제곱하면
이고 가 정수이므로 은 홀수입니다.
대우가 참이므로 21강의 동치 에 의해 원래 명제도 참입니다.
이 문제에서 배우는 것: 대우증명.
를 증명하는 대신 를 증명하는 방법을 대우증명이라고 합니다. 두 명제가 동치이므로 어느 쪽을 증명해도 같습니다.
대우증명이 유리한 신호가 있습니다.
| 신호 | 이유 |
|---|---|
| 결론에 "아니다", "", "무리수" 같은 부정이 들어 있습니다 | 부정을 부정하면 다루기 쉬운 긍정형이 됩니다 |
| 가정에서 정보를 꺼내기 어렵습니다 | 대우에서는 결론이 가정 자리로 오므로 그쪽에서 정보를 꺼냅니다 |
| 결론이 제곱근이나 나눗셈을 요구합니다 | 대우에서는 그 계산이 곱셈 쪽으로 바뀝니다 |
이번 문제가 세 번째 신호에 해당합니다. 원래 명제에서는 에서 을 꺼내야 해서 제곱근이 필요했지만, 대우에서는 에서 으로 가면 되므로 곱셈만 하면 됩니다. 증명은 곱하기 쉬운 방향으로 흐르게 만드는 것이 요령입니다.
대우증명을 쓸 때 반드시 지킬 것은 대우를 정확히 만드는 것입니다. 앞뒤를 바꾸고 각각 부정해야 하며, 21강 문제 5에서 본 대로 역이나 이를 증명하면 아무것도 증명한 것이 아닙니다.
바로 확인.
확인 3-1. "이 홀수이면 은 홀수입니다"를 대우로 증명하세요.
답. 대우는 "이 짝수이면 은 짝수입니다"이고 이는 문제 2에서 이미 증명했습니다. 따라서 원래 명제가 참입니다.
확인 3-2. "가 짝수이면 은 짝수입니다"를 대우로 증명하세요.
답. 대우는 "이 홀수이면 는 홀수입니다"입니다. 이라 하면 이므로 홀수입니다.
확인 3-3. "가 무리수이면 도 무리수입니다"를 대우로 증명할 때 대우가 무엇인지 쓰세요.
답. 대우는 "이 유리수이면 도 유리수입니다"입니다. 무리수라는 부정형이 유리수라는 긍정형으로 바뀌므로 다루기 쉬워집니다.
문제. "모든 정수 에 대하여 은 짝수입니다"를 증명하세요.
생각의 실마리. 을 나 중 하나로 놓고 싶은데, 이 어느 쪽인지는 주어지지 않았습니다. 둘 다 가능하다면 어떻게 해야 빠뜨림 없이 다룰 수 있는지 생각합니다.
풀이. 모든 정수는 짝수이거나 홀수이고, 두 경우가 전부입니다. 각각 따로 확인합니다.
경우 1. 이 짝수인 경우. 인 정수 가 존재합니다.
괄호 안이 정수이므로 짝수입니다.
경우 2. 이 홀수인 경우. 인 정수 가 존재합니다.
괄호 안이 정수이므로 짝수입니다.
두 경우가 모든 정수를 덮고 각 경우에서 결론이 성립하므로 명제가 증명되었습니다.
이 문제에서 배우는 것: 경우 나누기.
증명 중에 대상이 여러 모양 중 하나일 수 있으면 경우를 나누어 각각에서 결론을 확인합니다. 이때 두 가지를 반드시 지킵니다.
첫째, 나눈 경우들이 전체를 덮어야 합니다. 하나라도 빠지면 그 경우에 대해서는 증명한 것이 없습니다.
둘째, 각 경우에서 결론이 같아야 합니다. 한 경우에서만 성립하면 증명이 아닙니다.
두 조건을 합치면 3강에서 인수분해를 확인할 때 썼던 것과 같은 원칙입니다. 빠짐없이 나누고 각각을 확인합니다.
정수를 다룰 때 자주 쓰는 경우 나누기를 정리해 둡니다.
| 기준 | 경우 |
|---|---|
| 로 나눈 나머지 | , |
| 으로 나눈 나머지 | , , |
| 부호 | , , |
| 절댓값 | 또는 |
마지막 줄은 8강에서 절댓값 부등식을 풀 때 이미 쓴 방식입니다. 그때 한 것이 경우 나누기였다는 사실을 이제 이름으로 확인합니다.
바로 확인.
확인 4-1. "모든 정수 에 대하여 는 짝수입니다"를 경우 나누기로 증명하세요.
답. 이 짝수면 첫 인수가 짝수이므로 곱이 짝수입니다. 이 홀수면 이 짝수이므로 곱이 짝수입니다. 두 경우가 전부이므로 증명이 끝납니다.
확인 4-2. "모든 실수 에 대하여 입니다"를 경우 나누기로 증명하세요.
답. 이면 이므로 입니다. 이면 이므로 입니다. 두 경우 모두 성립합니다.
확인 4-3. "모든 정수 에 대하여 을 으로 나눈 나머지는 또는 입니다"를 증명하세요.
답. 면 이므로 나머지가 입니다. 이면 이므로 나머지가 입니다. 면 이므로 나머지가 입니다. 세 경우가 전부이므로 나머지는 가 될 수 없습니다.
문제. 다음 세 명제 각각에 대해 직접증명과 대우증명 중 어느 쪽이 유리한지 판단하고, 그 근거를 적은 뒤 실제로 증명하세요.
(가) 모든 정수 에 대하여, 과 이 모두 홀수이면 은 짝수입니다.
(나) 모든 정수 에 대하여, 이 짝수이면 은 짝수입니다.
(다) 모든 실수 에 대하여, 이면 입니다.
생각의 실마리. 각 명제에서 가정과 결론을 나눈 뒤, 어느 쪽이 식으로 옮기기 쉬운지 봅니다. "이 짝수"에서 을 꺼내려면 세제곱근이 필요하고, ""는 부정형입니다. 문제 3의 표에 있는 세 신호를 하나씩 대 봅니다.
풀이. (가)는 가정이 홀수 두 개이고 결론이 짝수입니다. 가정을 , 로 바로 식으로 옮길 수 있고, 결론도 더하기만 하면 나옵니다. 직접증명이 유리합니다.
이 정수이므로 짝수입니다.
(나)는 가정 에서 을 꺼내려면 세제곱근이 필요해 정수라는 정보를 잃습니다. 문제 3의 세 번째 신호에 해당하므로 대우증명이 유리합니다.
대우는 "이 홀수이면 은 홀수입니다"입니다. 이라 하면
이고 괄호 안이 정수이므로 홀수입니다. 여기서 전개에는 2강의 곱셈 공식을 썼습니다.
(다)는 가정과 결론이 모두 부정형입니다. 문제 3의 첫 번째 신호에 해당하므로 대우증명이 유리합니다.
대우는 "이면 입니다"입니다. 를 대입하면 이므로 참입니다. 대입 한 번으로 끝납니다.
이 문제에서 배우는 것: 증명 방법의 선택.
증명을 시작하기 전에 방법을 고르는 것이 시간을 아낍니다. 판단 기준을 표로 정리합니다.
| 확인할 것 | 직접증명이 유리 | 대우증명이 유리 |
|---|---|---|
| 가정의 모양 | 정의로 바로 식이 됩니다 | 식으로 옮기기 어렵습니다 |
| 결론의 모양 | 계산으로 도달합니다 | 부정형입니다 |
| 계산 방향 | 곱하고 더하면 됩니다 | 근호나 나눗셈이 필요합니다 |
두 방법이 모두 가능하면 짧은 쪽을 고릅니다. (다)에서 직접증명을 시도하면 을 인수분해해 으로 만들고 여기서 를 끌어내야 하는데, 대우는 대입 한 번으로 끝납니다.
한 가지 더 기억할 것이 있습니다. 방법을 잘못 골라도 틀린 증명이 되지는 않습니다. 다만 길어지거나 막힐 뿐입니다. 막히면 다른 방법으로 갈아타면 되고, 두 방법이 모두 막히면 24강의 귀류법을 씁니다.
바로 확인.
확인 5-1. "이 의 배수가 아니면 도 의 배수가 아닙니다"는 어느 방법이 유리합니까?
답. 직접증명이 유리합니다. 가정을 또는 로 경우를 나누어 식으로 옮길 수 있고, 확인 4-3에서 이미 계산했습니다. 대우로 가면 이 의 배수라는 가정에서 을 꺼내야 해 어렵습니다.
확인 5-2. "이면 이거나 입니다"는 어느 방법이 유리합니까?
답. 대우증명이 유리합니다. 결론이 "또는"이라 직접 다루기 번거롭지만, 대우의 가정은 드모르간 법칙으로 "이고 "이 되어 두 부등식을 더하면 가 바로 나옵니다.
확인 5-3. 확인 5-2의 명제를 실제로 증명하세요.
답. 대우를 증명합니다. 이고 이면 두 부등식을 변끼리 더해 입니다. 따라서 대우가 참이고 원래 명제도 참입니다.
| 증명할 것 | 방법 |
|---|---|
| 임의의 를 잡고 를 유도합니다 | |
| 구체적인 를 제시하고 확인합니다 | |
| (직접) | 를 가정하고 계산해 에 도달합니다 |
| (대우) | 를 가정하고 계산해 에 도달합니다 |
| 대상이 여러 모양일 때 | 전체를 덮도록 경우를 나눕니다 |
| 막히는 자리 | 처방 |
|---|---|
| 첫 줄이 안 나옵니다 | 가정의 정의를 식으로 적습니다 |
| 결론이 부정형입니다 | 대우로 바꿉니다 |
| 근호를 벗겨야 합니다 | 대우로 바꿔 곱셈 방향으로 돌립니다 |
| 대상의 모양이 갈립니다 | 경우를 나눕니다 |
| 두 방법이 모두 막힙니다 | 24강의 귀류법을 씁니다 |
문제 6. "두 짝수의 곱은 의 배수입니다"를 증명하세요.
답. , 이면 이고 가 정수이므로 의 배수입니다.
문제 7. "이 홀수이면 은 의 배수입니다"를 증명하세요.
답. 이면 이고 이 정수이므로 의 배수입니다. 확인 4-1에 의해 실제로는 의 배수이기도 합니다.
문제 8. "이 홀수이면 은 짝수입니다"를 대우로 증명하세요.
답. 대우는 "이 홀수이면 은 짝수입니다"입니다. 이면 이므로 짝수입니다.
문제 9. "이면 입니다"를 증명하세요.
답. 인 정수 가 있으므로 이고 가 정수이므로 입니다.
문제 10. "이고 이면 입니다"를 증명하세요.
답. , 이므로 이고 가 정수이므로 성립합니다.
문제 11. "모든 정수 에 대하여 은 의 배수입니다"를 증명하세요.
답. 은 연속한 세 정수의 곱입니다. 연속한 세 정수 중 적어도 하나는 짝수이고 정확히 하나는 의 배수이므로 곱은 와 으로 나누어떨어지고, 와 이 서로소이므로 의 배수입니다.
문제 12. "가 유리수이고 가 유리수이면 도 유리수입니다"를 증명하세요.
답. , 이고 인 정수들이 있습니다. 4강의 통분으로 이고 분자가 정수, 분모 가 이 아닌 정수이므로 유리수입니다.
문제 13. "이 홀수이면 과 이 모두 홀수입니다"를 대우로 증명하세요.
답. 대우는 " 또는 이 짝수이면 은 짝수입니다"입니다. 라면 이므로 짝수이고, 이 짝수인 경우도 같습니다.
문제 14. "이면 입니다"가 거짓임을 보이고, 참이 되도록 가정을 최소한으로 보태세요.
답. , 이 반례입니다. 와 가 모두 이상이라는 가정을 붙이면 참이 됩니다.
문제 15. "을 로 나눈 나머지가 이면 은 완전제곱수가 아닙니다"를 증명하세요.
답. 확인 4-3과 같은 방식으로, 완전제곱수를 로 나눈 나머지는 또는 뿐입니다. 면 이고 이면 입니다. 나머지가 인 수는 이 두 형태에 들어가지 않습니다.
문제 16. 다음 증명의 잘못을 지적하세요. "이 짝수라고 하자. 그러면 이다. 양변에 제곱근을 취하면 이다. 따라서 은 짝수이다."
답. 마지막 문장이 근거 없이 나왔습니다. 라는 표현에서 이 의 배수라는 사실은 도출되지 않습니다. 문제 3처럼 대우로 증명해야 합니다.
문제 17. "이고 이면 입니다"의 대우를 쓰고, 어느 방법이 짧은지 판단하세요.
답. 대우는 "이면 이거나 입니다"입니다. 직접증명이 훨씬 짧습니다. 양수 두 개를 더하면 양수라는 8강의 부등식 성질을 한 번 쓰면 끝납니다.
문제 18. "모든 정수 에 대하여, 이 의 배수이면 은 짝수이고 의 배수입니다"를 증명하고, 역이 성립하는지 판정하세요.
답. 이면 이므로 짝수이고 이므로 의 배수입니다. 역도 성립합니다. 이 짝수이고 의 배수이면 인데 와 이 서로소이므로 가 의 배수여야 하고 은 의 배수가 됩니다.
심화 1. 대우증명이 왜 정당한지, 21강에서 얻은 결과를 들어 설명하세요.
답. 와 가 동치이기 때문입니다.
풀이. 21강 문제 5의 진리표에서 두 열이 네 줄 모두 일치함을 확인했습니다. 동치라는 것은 어떤 진리값 조합에서도 두 명제가 같은 값을 가진다는 뜻이므로, 하나가 참이면 다른 하나도 반드시 참입니다. 따라서 대우를 증명하는 것은 원래 명제를 증명하는 것과 완전히 같습니다.
남는 것. 대우증명은 새로운 증명 원리가 아니라 21강에서 얻은 동치를 적용한 것뿐입니다. 증명 기법이 늘어나는 것처럼 보이지만 실제로는 논리 법칙 하나를 쓰고 있을 뿐이며, 이 점을 알면 기법을 외우는 대신 필요할 때 만들어 쓸 수 있습니다.
심화 2. "모든 정수 에 대하여 을 로 나눈 나머지는 또는 입니다"를 증명하고, 이 결과로 을 만족하는 이 아닌 정수해가 왜 찾기 어려운지 한 걸음만 설명하세요.
답. 경우 나누기로 증명되며, 나머지를 세는 것만으로 강한 제약이 나옵니다.
풀이. 이면 이므로 나머지가 이고, 이면 이므로 나머지가 입니다.
이제 을 로 나눈 나머지는 , , 중 하나이므로 , , 입니다. 한편 에서 의 나머지가 이면 의 나머지는 이고, 이면 입니다. 양변의 나머지가 같아야 하므로 인 경우는 불가능하고 인 경우만 남습니다. 그러면 , , 가 모두 짝수여야 하며, 셋을 로 나눈 값들도 같은 방정식을 만족하므로 이 과정이 끝없이 반복됩니다.
남는 것. 나머지만 보고도 방정식의 해를 크게 제한할 수 있습니다. 여기서 쓴 "계속 절반으로 줄일 수 있으므로 불가능하다"는 논법이 24강 귀류법의 무한강하이며 가 무리수임을 보일 때 같은 방식이 쓰입니다.
심화 3. "와 가 정수이고 이 짝수이면 도 짝수입니다"를 증명하세요.
답. 대우 또는 경우 나누기로 증명됩니다.
풀이. 경우를 나눕니다. 와 가 모두 짝수면 이 짝수이고 도 짝수입니다. 모두 홀수면 과 이 각각 홀수이므로 합이 짝수이고, 도 홀수 둘의 합이라 짝수입니다. 하나만 홀수면 이 홀수가 되어 가정에 어긋나므로 이 경우는 가정 아래에서 생기지 않습니다. 남은 두 경우 모두에서 가 짝수입니다.
남는 것. 와 의 홀짝이 같다는 것이 실제 내용이고, 제곱은 홀짝을 보존하므로 의 홀짝과 의 홀짝이 함께 움직입니다. 홀짝만 남기고 나머지 정보를 버리는 이 관점이 정수론에서 계속 쓰이며, 나중에 배울 합동식의 출발점입니다.
심화 4. 다음 "증명"의 잘못을 찾으세요. "라고 하자. 양변에 를 곱하면 이다. 양변에서 을 빼면 이다. 인수분해하면 이다. 양변을 로 나누면 이다. 이므로 이고 따라서 이다."
답. 로 나눈 단계가 잘못되었습니다.
풀이. 라고 가정했으므로 입니다. 4강에서 확인한 대로 으로 나누는 것은 정의되지 않으므로 그 단계에서 증명이 무너집니다. 앞 단계까지는 모두 옳습니다.
남는 것. 식을 나눌 때는 나누는 것이 이 아님을 먼저 확인해야 합니다. 문자로 나눌 때 이 확인을 빠뜨리는 것이 가장 흔한 오류이며, 7강에서 연립방정식을 풀 때 소거 계수가 인지 살핀 것과 같은 주의입니다.
심화 5. "를 증명하려면 를 만족하는 원소가 실제로 있는지 확인해야 합니까?"라는 질문에 답하세요.
답. 확인할 필요가 없습니다.
풀이. 조건문은 가정이 거짓이면 공허하게 참입니다. 를 만족하는 원소가 에 하나도 없다면 모든 원소에서 가정이 거짓이므로 명제 전체가 참입니다. 따라서 증명은 "를 가정하고 를 유도한다"만 하면 충분하고, 를 만족하는 원소의 존재는 증명에 필요하지 않습니다.
남는 것. 다만 22강 심화 6에서 본 대로, 그 정리를 적용할 때는 가정을 만족하는 대상이 실제로 있는지 확인해야 합니다. 증명할 때와 적용할 때 요구되는 것이 다르다는 점을 구분합니다.
심화 6. 어떤 명제를 직접증명으로 쓴 다음 그 증명을 대우증명으로 바꿀 수 있습니까? 반대는 어떻습니까?
답. 원리적으로는 언제나 바꿀 수 있지만 실제로 짧아지는지는 별개입니다.
풀이. 두 명제가 동치이므로 한쪽이 증명 가능하면 다른 쪽도 증명 가능합니다. 그러나 증명의 길이와 난이도는 전혀 다를 수 있습니다. 문제 5의 (다)에서 대우증명은 대입 한 줄이지만 직접증명은 인수분해를 거쳐야 했습니다. 반대로 (가)에서 대우를 쓰면 "합이 홀수이면 둘 중 하나가 짝수이다"를 다시 경우 나누기로 증명해야 해서 길어집니다.
남는 것. 증명 방법의 선택은 참거짓의 문제가 아니라 경제성의 문제입니다. 어느 쪽으로도 갈 수 있으므로 막히면 미련 없이 갈아탑니다. 두 방향을 모두 짧게 시도해 보고 진행이 빠른 쪽을 택하는 것이 실전에서 가장 빠릅니다.
증명은 코드로 대신할 수 없지만, 증명한 명제가 유한한 범위에서 실제로 성립하는지 확인하면 증명에 오타나 부호 실수가 있는지 잡아낼 수 있습니다.
import numpy as np
n = np.arange(-1000, 1001)
# 문제 2와 문제 3: 제곱은 홀짝을 보존합니다.
print(bool(np.all((n % 2 == 0) == (n**2 % 2 == 0)))) # True
# 문제 4: n^2 + n 은 항상 짝수입니다.
print(bool(np.all((n**2 + n) % 2 == 0))) # True
# 문제 11: n^3 - n 은 항상 6의 배수입니다.
print(bool(np.all((n**3 - n) % 6 == 0))) # True
# 확인 4-3: n^2 을 3으로 나눈 나머지는 0 또는 1 뿐입니다.
print(np.unique(n**2 % 3)) # [0 1]
# 심화 2: n^2 을 4로 나눈 나머지는 0 또는 1 뿐입니다.
print(np.unique(n**2 % 4)) # [0 1]
# 문제 7: 홀수의 제곱에서 1을 빼면 8의 배수입니다.
odd = n[n % 2 != 0]
print(bool(np.all((odd**2 - 1) % 8 == 0))) # True
# 문제 14: x^2 = y^2 이라고 x = y 는 아닙니다.
print((1**2 == (-1)**2, 1 == -1)) # (True, False)
출력이 주석과 모두 일치합니다. 문제 7의 결과가 의 배수를 넘어 의 배수까지 성립한다는 점에 주목합니다. 손으로 까지 갔을 때 이 연속한 두 정수의 곱이라 짝수라는 사실을 한 번 더 쓰면 이 나오며, 코드가 그 사실을 먼저 알려 준 셈입니다. 이것이 코드 검산의 쓸모입니다. 증명을 대신하지는 못하지만 더 강한 결론이 가능한 자리를 알려 줍니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 에이가 비를 나눕니다 | 인 정수 가 존재합니다 | |
| 에이가 비를 나누지 않습니다 | 그런 정수 가 없습니다 | |
| 짝수 꼴 | 가 정수일 때 짝수를 나타냅니다 | |
| 홀수 꼴 | 가 정수일 때 홀수를 나타냅니다 | |
| \mathbb | 정수 전체 | 1강에서 약속한 기호입니다 |
다음 24강에서는 직접증명도 대우증명도 막힐 때 쓰는 귀류법을 배우고, 반례를 체계적으로 찾는 방법을 익힙니다. 심화 2에서 잠깐 쓴 "계속 절반으로 줄일 수 있으므로 불가능하다"는 논법이 그때 정식으로 등장합니다.