22개정 · 집합과 명제
명제의 역, 이, 대우와 증명
조건명제의 가정과 결론을 정확히 찾고 부정의 위치를 추적하면 역, 이, 대우를 혼동하지 않을 수 있습니다. 명제와 대우의 동치 관계는 어려운 증명을 더 다루기 쉬운 형태로 바꾸는 핵심 도구입니다.
1. 조건명제의 구조
두 조건 p, q에 대하여 “p이면 q이다” 꼴의 명제를 조건명제라고 하며 \(p\to q\)로 나타냅니다. p는 가정, q는 결론입니다.
문장의 어순만 보고 가정과 결론을 정하면 안 됩니다. “q이기 위한 충분조건은 p이다”도 \(p\to q\)를 뜻하므로 의미를 기호로 번역하는 습관이 중요합니다.
2. 조건명제의 진리값
\(p\to q\)는 p가 참인데 q가 거짓인 경우에만 거짓입니다. 가정을 만족하는 모든 대상이 결론도 만족하는지를 판단하는 구조입니다.
| \(p\) | \(q\) | \(p\to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
따라서 조건명제가 거짓임을 보이려면 p는 참이고 q는 거짓인 반례 하나를 찾으면 됩니다.
3. 명제의 부정
“p이면 q이다”의 부정은 “p이지만 q가 아니다”입니다. 가정이 거짓인 경우는 원래 명제를 깨뜨리지 못합니다.
예를 들어 “\(n\)이 4의 배수이면 짝수이다”의 부정은 “\(n\)이 4의 배수이고 짝수가 아니다”입니다.
4. 역, 이, 대우 만들기
가정과 결론의 자리 교환과 각 조건의 부정을 따로 추적하면 네 문장을 정확히 만들 수 있습니다.
| 이름 | 기호 | 만드는 방법 |
|---|---|---|
| 명제 | \(p\to q\) | 원래 가정에서 원래 결론으로 |
| 역 | \(q\to p\) | 가정과 결론의 자리만 교환 |
| 이 | \((\sim p)\to(\sim q)\) | 자리 유지, 두 조건을 각각 부정 |
| 대우 | \((\sim q)\to(\sim p)\) | 자리 교환 후 두 조건을 각각 부정 |
5. 네 문장 비교하기
\(p:\ n\text{은 }4\text{의 배수}\), \(q:\ n\text{은 짝수}\)로 놓고 정수 전체에서 살펴봅시다.
- 명제 \(p\to q\): 4의 배수이면 짝수이다. 참.
- 역 \(q\to p\): 짝수이면 4의 배수이다. 거짓. 반례는 6.
- 이 \((\sim p)\to(\sim q)\): 4의 배수가 아니면 짝수가 아니다. 거짓. 반례는 6.
- 대우 \((\sim q)\to(\sim p)\): 짝수가 아니면 4의 배수가 아니다. 참.
원래 명제가 참이라고 해서 역도 참인 것은 아닙니다. 반면 명제와 대우, 역과 이는 각각 반드시 같은 진리값을 가집니다.
6. 동치 관계
진리표를 비교하면 다음 두 쌍의 마지막 열이 항상 일치합니다.
첫 번째 관계가 대우증명법의 논리적 근거입니다. 원래 명제 대신 대우를 증명해도 같은 명제를 증명한 것이 됩니다.
7. 진리집합으로 해석하기
조건 p, q의 진리집합을 각각 P, Q라고 합시다. “모든 \(x\)에 대하여 \(p(x)\to q(x)\)”가 참이라는 것은 p를 만족하는 모든 값이 q도 만족한다는 뜻입니다.
대우의 진리집합 관계 \(Q^c\subseteq P^c\)는 \(P\subseteq Q\)와 같은 내용입니다.
8. 충분조건과 필요조건
\(p\to q\)가 참이면 p는 q이기 위한 충분조건, q는 p이기 위한 필요조건입니다.
“4의 배수이면 짝수이다”에서 ‘4의 배수’는 ‘짝수’가 되기에 충분하지만 꼭 필요한 조건은 아닙니다. ‘짝수’는 ‘4의 배수’가 되기 위해 반드시 필요하지만 그것만으로 충분하지는 않습니다.
- \(P\subsetneq Q\): p는 q의 충분조건일 뿐이고, q는 p의 필요조건일 뿐입니다.
- \(P=Q\): p와 q는 서로 필요충분조건입니다.
- 포함 관계가 없으면 어느 쪽도 다른 쪽의 충분조건이 아닙니다.
9. 필요충분조건
\(p\to q\)와 \(q\to p\)가 모두 참이면 p와 q는 서로 필요충분조건이고 \(p\leftrightarrow q\)로 나타냅니다.
필요충분조건을 증명할 때는 정방향과 역방향을 각각 증명해야 합니다. 한 방향만 보이면 충분조건 또는 필요조건만 확인한 것입니다.
10. 직접증명
가정 p에서 출발하여 정의, 이미 알려진 성질, 대수적 계산을 이용해 결론 q를 이끌어 내는 방법입니다.
예제. 정수 \(n\)이 홀수이면 \(n^2\)도 홀수임을 증명하세요.
증명. \(n\)이 홀수이므로 어떤 정수 \(k\)에 대하여 \(n=2k+1\)로 쓸 수 있습니다. 따라서
\(2k^2+2k\)는 정수이므로 \(n^2\)은 홀수입니다. 가정을 정의의 형태로 바꾸고 결론의 형태를 만들어 낸 것이 핵심입니다.
11. 대우증명법
원래 명제 \(p\to q\)를 직접 다루기 어렵다면 동치인 대우 \((\sim q)\to(\sim p)\)를 증명합니다.
예제. 정수 \(n\)에 대하여 \(n^2\)이 짝수이면 \(n\)도 짝수임을 증명하세요.
대우. \(n\)이 홀수이면 \(n^2\)도 홀수이다.
증명. \(n=2k+1\)로 놓으면 \(n^2=2(2k^2+2k)+1\)이므로 \(n^2\)은 홀수입니다. 대우가 참이므로 원래 명제도 참입니다.
결론의 부정이 가정보다 구체적인 형태를 줄 때 대우증명이 특히 효과적입니다.
12. 귀류법
증명하려는 명제가 거짓이라고 가정한 뒤, 그 가정에서 이미 알려진 사실과 충돌하는 모순을 이끌어 냅니다. 모순이 생기므로 처음의 부정이 거짓이고 원래 명제가 참입니다.
예제. \(\sqrt2\)가 무리수임을 증명하세요.
증명. 반대로 \(\sqrt2\)가 유리수라고 가정하면 서로소인 자연수 \(a,b\)에 대하여 \(\sqrt2=\frac ab\)로 쓸 수 있습니다. 양변을 제곱하면
\(a^2\)이 짝수이므로 a도 짝수입니다. \(a=2k\)를 대입하면 \(b^2=2k^2\)이므로 b도 짝수입니다. 그러면 a와 b는 모두 2를 약수로 가져 서로소라는 가정과 모순입니다. 따라서 \(\sqrt2\)는 무리수입니다.
13. 반례와 증명의 차이
- 모든 명제가 거짓임을 보일 때는 반례 하나면 충분합니다.
- 몇 개의 예가 맞는다고 해서 모든 명제가 참이라고 증명되지는 않습니다.
- 어떤 명제가 참임을 보일 때는 조건을 만족하는 구체적인 예 하나면 충분합니다.
- 증명 과정에서는 가정하지 않은 결론을 중간에 몰래 사용하면 안 됩니다.
예를 들어 \(n^2+n+41\)은 여러 자연수에서 소수가 되지만 \(n=41\)이면 \(41^2+41+41=41\cdot43\)이므로 “모든 자연수에서 소수”라는 명제는 거짓입니다.
14. 증명 방법 선택하기
- 가정과 결론을 p, q로 분리합니다.
- 짝수·홀수, 배수, 유리수처럼 정의를 식으로 바꿀 수 있으면 직접증명을 먼저 시도합니다.
- 결론을 직접 만들기 어렵고 결론의 부정이 다루기 쉬우면 대우를 씁니다.
- “존재하지 않는다”, “무리수이다”처럼 부정형 결론이거나 서로소 조건이 있으면 귀류법을 검토합니다.
- 필요충분조건은 두 방향을 빠짐없이 나누어 증명합니다.
- 마지막에 사용한 가정과 얻은 결론을 문장으로 연결합니다.
15. 절대부등식의 간단한 증명
변수의 모든 허용값에서 성립하는 부등식을 절대부등식이라고 합니다. 제곱은 항상 0 이상이라는 사실을 자주 이용합니다.
예제. 모든 실수 a, b에 대하여 \(a^2+b^2\ge2ab\)임을 증명하세요.
등호는 \(a-b=0\), 즉 \(a=b\)일 때 성립합니다. 부등식 증명에서는 식뿐 아니라 등호 성립 조건도 함께 확인하세요.
16. 자주 하는 실수
- 역과 대우를 혼동하여 자리만 바꾸거나 부정만 합니다.
- \(x>3\)의 부정을 \(x<3\)으로 써서 \(x=3\)을 빠뜨립니다.
- 원래 명제가 참이면 역도 참이라고 생각합니다.
- “p는 q의 충분조건”을 \(q\to p\)로 거꾸로 번역합니다.
- 필요충분조건에서 한 방향만 증명합니다.
- 귀류법에서 무엇과 무엇이 모순인지 밝히지 않습니다.
17. 연습문제
(1) 명제 “정수 \(n\)이 6의 배수이면 \(n\)은 3의 배수이다”의 가정과 결론을 쓰세요.
(2) (1)의 역, 이, 대우를 각각 쓰세요.
(3) (1)의 명제, 역, 이, 대우의 진리값을 판단하고 거짓인 문장에는 반례를 제시하세요.
(4) \(p\to q\)의 부정을 p, q와 논리기호로 나타내세요.
(5) “실수 \(x\)에 대하여 \(x>2\)이면 \(x^2>4\)이다”의 대우를 쓰고 진리값을 판단하세요.
(6) \(U=\mathbb R\), \(p(x):x>3\), \(q(x):x>1\)일 때 p와 q 중 어느 것이 다른 것의 충분조건인지 말하세요.
(7) \(U=\mathbb Z\), \(p(n):n\text{은 }6\text{의 배수}\), \(q(n):n\text{은 }3\text{의 배수}\)일 때 필요조건과 충분조건의 관계를 설명하세요.
(8) 정수 \(n\)에 대하여 “n이 짝수이다”와 “\(n^2\)이 짝수이다”가 필요충분조건임을 두 방향으로 설명하세요.
(9) 두 홀수의 합이 짝수임을 직접증명하세요.
(10) 정수 \(n\)에 대하여 \(n^2\)이 홀수이면 n이 홀수임을 대우증명법으로 증명하세요.
(11) 유리수 a, b에 대하여 \(a+b\)가 유리수임을 직접증명하세요.
(12) 모든 실수 a, b에 대하여 \(a^2+b^2\ge2ab\)임을 증명하고 등호 성립 조건을 쓰세요.
(13) 명제 “모든 소수는 홀수이다”의 역을 만들 수 있도록 p와 q를 조건으로 표현하고, 원래 명제가 거짓임을 보이는 반례를 쓰세요.
(14) “정수 \(n\)이 3의 배수일 필요충분조건은 \(n^2\)이 3의 배수인 것이다”를 증명할 때 정방향과 역방향에서 각각 무엇을 보여야 하는지 쓰세요.
연습문제 해설 보기
(1) 가정은 “n이 6의 배수이다”, 결론은 “n이 3의 배수이다”입니다.
(2) 역: 3의 배수이면 6의 배수이다. 이: 6의 배수가 아니면 3의 배수가 아니다. 대우: 3의 배수가 아니면 6의 배수가 아니다.
(3) 명제와 대우는 참입니다. 역과 이는 거짓이며 반례로 \(n=3\)을 들 수 있습니다.
(4) \(p\land(\sim q)\).
(5) 대우는 “\(x^2\le4\)이면 \(x\le2\)이다”입니다. \(x=-3\)처럼 \(x^2>4\)인 값은 대우의 가정을 만족하지 않습니다. \(-2\le x\le2\)이면 \(x\le2\)이므로 대우와 원래 명제는 참입니다.
(6) 진리집합 \((3,\infty)\subset(1,\infty)\)이므로 p는 q의 충분조건이고, q는 p의 필요조건입니다.
(7) 6의 배수이면 3의 배수이므로 p는 q의 충분조건, q는 p의 필요조건입니다.
(8) n이 짝수이면 \(n=2k\)이므로 \(n^2=2(2k^2)\)은 짝수입니다. 반대 방향은 대우 “n이 홀수이면 \(n^2\)도 홀수”를 보이면 됩니다.
(9) 두 홀수를 \(2a+1,2b+1\)로 놓으면 합은 \(2(a+b+1)\)이므로 짝수입니다.
(10) 대우는 “n이 짝수이면 \(n^2\)도 짝수이다”입니다. \(n=2k\)이면 \(n^2=2(2k^2)\)이므로 대우가 참이고 원래 명제도 참입니다.
(11) \(a=\frac mn\), \(b=\frac rs\)라 하자. 여기서 m, r은 정수이고 n, s는 0이 아닌 정수입니다. \(a+b=\frac{ms+rn}{ns}\)는 정수의 비이므로 유리수입니다.
(12) \((a-b)^2\ge0\)을 전개하면 됩니다. 등호는 \(a=b\)일 때 성립합니다.
(13) 전체집합을 자연수로 두고 p(n): “n은 소수”, q(n): “n은 홀수”로 놓으면 원래 명제는 \(p\to q\)입니다. 반례는 \(n=2\)입니다.
(14) 정방향에서는 \(3\mid n\Rightarrow3\mid n^2\), 역방향에서는 \(3\mid n^2\Rightarrow3\mid n\)을 보여야 합니다. 역방향은 대우 \(3\nmid n\Rightarrow3\nmid n^2\)를 이용할 수 있습니다.
'자연수 n이 4의 배수이면 n은 짝수이다'의 역, 이, 대우를 쓰고 각각의 진리값을 판단하세요. 거짓인 문장에는 반례도 제시하세요.
정답과 해설 보기
역은 “n이 짝수이면 4의 배수이다”로 거짓이고 반례는 \(n=2\)입니다. 이는 “n이 4의 배수가 아니면 짝수가 아니다”로 거짓이며 같은 반례 \(n=2\)를 사용할 수 있습니다. 대우는 “n이 짝수가 아니면 4의 배수가 아니다”로 참입니다. 원래 명제와 대우는 참, 역과 이는 거짓으로 각각 진리값이 일치합니다.