방송대 방통대 이산수학 3강 - 증명 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 3강 - 증명

수학적 명제가 참임을 논리적으로 보이는 여러 증명 방법을 학습한다. 공리·증명·정리의 관계에서 출발하여 직접증명법과 수학적 귀납법, 대우·모순·반례·존재 증명법, 전수·조합·컴퓨터를 이용한 증명법을 예제와 함께 정리한다.

1. 증명의 기본 개념

공리, 증명, 정리

공리(axiom)는 다른 명제를 증명하기 위한 전제로 사용하는 가장 기본적인 가정이다. 별도의 증명 없이 참으로 받아들이며, 하나의 수학 체계를 세우는 출발점이 된다. 유클리드 기하학의 “두 점을 지나는 직선을 그릴 수 있다”, 페아노 공리의 “모든 자연수에는 그 다음 수가 존재한다”, 공리적 집합론의 “아무것도 포함하지 않는 집합이 존재한다” 등이 그 예이다.

증명(proof)은 특정한 공리들을 가정하고 그 가정 아래에서 제안된 명제가 참임을 입증하는 논리적 작업이다. 증명은 단순히 여러 사례에서 결론이 맞는지 확인하는 일이 아니라, 허용된 정의·공리·이미 증명된 결과를 사용하여 결론이 반드시 따라옴을 보여야 한다.

정리(theorem)는 공리로부터 증명된 명제이다. 큰 정리를 증명하는 중간 단계에서 사용하는 증명된 명제를 보조정리(lemma)라고 하며, 정리로부터 비교적 쉽게 도출되는 부가적인 명제를 따름정리(corollary)라고 한다.

용어	의미	역할
공리	증명 없이 참으로 이용하는 기본 명제	수학 체계의 출발점
증명	명제가 참임을 논리적으로 입증하는 작업	전제에서 결론을 도출
정리	공리와 기존 결과로부터 증명된 명제	새로운 증명의 근거
보조정리	더 큰 결과를 얻기 위한 중간 명제	정리 증명의 발판
따름정리	정리에서 쉽게 따라오는 부가 명제	정리의 직접적 결과 제시

증명 방법의 큰 분류

강의에서는 직접증명법, 수학적 귀납법, 간접증명법을 중심으로 다룬다. 간접증명법에는 대우증명법, 모순증명법, 반례증명법, 존재증명법이 포함된다. 이 밖에도 가능한 경우를 모두 살피는 전수증명법, 두 집합 사이의 대응을 이용하는 조합적 증명법, 복잡한 계산을 수행하는 컴퓨터 증명법이 있다.

시험 핵심: 어떤 증명법이 더 우월한 것이 아니라 명제의 형태와 가능한 경우의 수에 따라 적절한 방법을 선택하는 것이 중요하다.

2. 직접증명법

직접증명의 원리

직접증명법(direct proof)은 연역법이라고도 한다. 명제를 다른 형태로 바꾸지 않고 공리, 정의, 이미 증명된 정리를 논리적으로 직접 연결하여 결론을 이끌어 낸다. 조건명제 P → Q를 증명한다면 P가 참이라고 놓고, 정의와 알려진 사실을 차례로 적용해 Q가 참임을 보이는 방식이다.

연역법(deduction)은 이미 증명된 하나 이상의 명제를 전제로 삼아 새로운 명제를 결론으로 도출하는 것이다. 따라서 직접증명의 각 단계는 앞선 전제에서 논리적으로 따라와야 하며, 증명하고 싶은 결론을 몰래 전제로 사용해서는 안 된다.

두 홀수의 합

두 홀수 x와 y를 각각 x=2a+1, y=2b+1로 둔다. 여기서 a와 b는 정수이다. 그러면 x+y=2a+1+2b+1=2(a+b+1)이고, a+b+1도 정수이므로 x+y는 2의 정수배이다. 따라서 두 홀수의 합은 짝수이다.

두 유리수의 합

유리수 r과 s를 r=a/b, s=c/d로 둔다. a, b, c, d는 정수이고 b≠0, d≠0이다. 그러면 r+s=(ad+bc)/bd이다. 분자 ad+bc와 분모 bd는 정수이고 bd≠0이므로 r+s는 유리수의 정의를 만족한다.

파스칼 항등식의 직접증명

파스칼 삼각형의 이항계수는 C(n+1,k)=C(n,k)+C(n,k-1)을 만족한다. 이항계수의 계승 표현 C(n,k)=n!/[k!(n-k)!]을 오른쪽에 대입하고 공통분모로 통분하면 (n+1)!/[k!(n+1-k)!]이 되어 왼쪽과 같아진다. 정의를 대수적으로 변형하여 결론과 같음을 보이므로 직접증명에 해당한다.

직접증명에서는 대상의 정의를 정확히 펼치는 일이 핵심이다. 짝수·홀수는 2k와 2k+1, 유리수는 분모가 0이 아닌 두 정수의 비, 이항계수는 계승식으로 표현하면 증명의 실마리가 드러난다.

3. 수학적 귀납법

귀납법의 세 단계

수학적 귀납법(mathematical induction)은 모든 자연수 n에 대해 주어진 명제가 참임을 증명할 때 유용하다. 도미노의 첫 조각이 넘어지고, 어느 조각이 넘어지면 다음 조각도 넘어짐을 보이면 모든 조각이 넘어지는 것과 같은 구조이다.

단계	해야 할 일	의미
기본단계	출발점에서 명제 S(n)이 성립함을 확인	귀납의 시작점을 확보
귀납가정	n=k일 때 S(k)가 참이라고 가정	다음 단계 증명에 사용할 전제
귀납단계	S(k)를 이용해 S(k+1)이 참임을 증명	참이 다음 자연수로 전달됨을 보임

세 단계 가운데 하나라도 빠지면 모든 자연수에 대한 증명이 완성되지 않는다. 기본단계만 확인하면 몇몇 사례를 계산한 것에 불과하고, 귀납단계만 보이면 명제가 시작될 지점을 확보하지 못한다. 또한 귀납가정은 증명할 결론 S(k+1)을 미리 참이라고 두는 것이 아니라 바로 앞 단계 S(k)를 임시로 가정하는 것이다.

1부터 n까지의 합 증명

명제 S(n)을 1+2+⋯+n=n(n+1)/2라고 하자. 기본단계 n=1에서 왼쪽은 1이고 오른쪽은 1(1+1)/2=1이므로 성립한다.

귀납가정으로 S(k), 즉 1+2+⋯+k=k(k+1)/2가 참이라고 가정한다. 이제 n=k+1인 합에 마지막 항을 더하면 1+2+⋯+k+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2가 된다. 이는 S(k+1)의 오른쪽과 같으므로 귀납단계가 성립하고, 수학적 귀납법에 의해 모든 자연수 n에서 명제가 참이다.

귀납법 작성 순서: 증명할 명제 S(n)을 먼저 분명히 쓰고, 기본단계 → 귀납가정 → 귀납단계를 구분한다. 귀납단계에서는 귀납가정을 실제로 어디에 사용했는지 드러내야 한다.

4. 간접증명법의 구조

간접증명법(indirect proof)은 증명할 명제를 그대로 다루기 어려울 때, 논리적으로 동치이면서 더 증명하기 쉬운 형태로 바꾸어 증명하는 방법이다. 대표적으로 대우증명법, 모순증명법, 반례증명법, 존재증명법이 있다.

방법	논리적 출발	주요 용도
대우증명법	P→Q 대신 ¬Q→¬P를 증명	결론의 부정에서 전제의 부정을 얻기 쉬울 때
모순증명법	P와 결론의 부정을 함께 가정해 모순 유도	귀류법, 배리법으로도 부름
반례증명법	전칭명제를 거짓으로 만드는 한 사례 제시	“모든 x”라는 명제가 거짓임을 보일 때
존재증명법	∃xP(x)의 타당성을 보임	조건을 만족하는 대상의 존재를 보일 때

대우와 원래 조건명제는 논리적으로 동치이므로 대우를 증명하면 원래 명제도 증명된다. 반면 역 Q→P는 일반적으로 원래 명제와 동치가 아니므로 대우와 혼동해서는 안 된다.

5. 대우증명법과 모순증명법

대우증명법

조건명제 P→Q의 대우는 ¬Q→¬P이다. “x²이 홀수이면 x는 홀수이다”를 직접 다루는 대신 대우인 “x가 홀수가 아니면, 즉 짝수이면 x²도 홀수가 아니다”를 보일 수 있다. x=2k로 두면 x²=4k²=2(2k²)이므로 x²은 짝수이다. 대우가 참이므로 원래 명제도 참이다.

모순증명법

모순증명법(proof by contradiction)은 증명하려는 명제의 부정을 가정한 뒤, 그 가정으로부터 이미 알려진 사실과 양립할 수 없는 모순을 이끌어 내는 방법이다. 조건명제 P→Q의 경우 P∧¬Q를 가정하여 거짓에 이르는 구조로 이해할 수 있다.

√2가 무리수임을 보이기 위해 반대로 √2가 유리수라고 가정한다. 그러면 서로소인 정수 a, b와 b≠0에 대해 √2=a/b로 나타낼 수 있다. 양변을 제곱하면 a²=2b²이므로 a²과 a는 짝수이다. a=2c를 대입하면 b²=2c²이 되어 b도 짝수이다. 이는 a와 b가 모두 2를 공약수로 가져 서로소라는 가정과 모순된다. 따라서 √2는 유리수가 아니며 무리수이다.

모순증명에서 중요한 것은 단지 “이상하다”는 결론이 아니라, 가정과 양립할 수 없는 구체적인 사실을 제시하는 것이다. √2의 예에서는 a와 b가 서로소라는 조건과 둘 다 짝수라는 결론이 충돌한다.

6. 반례증명법과 존재증명법

반례증명법

전칭명제 ∀xP(x)가 거짓임을 보이려면 P(x)를 거짓으로 만드는 x 하나를 찾으면 충분하다. 이것을 반례(counterexample)라고 한다. 예를 들어 “모든 실수 a, b에 대해 a²=b²이면 a=b이다”는 거짓이다. a=-2, b=2이면 a²=b²=4이지만 a≠b이므로 반례가 된다.

반례 한 개는 전칭명제를 무너뜨릴 수 있지만, 여러 사례가 참이라는 관찰만으로 전칭명제가 증명되지는 않는다. 따라서 반례증명법은 보편적 주장에 대한 거짓을 보이는 도구이다.

구성적 존재증명법

구성적 존재증명법은 ∃xP(x)를 증명할 때 P(x)를 참으로 만드는 구체적인 대상을 실제로 제시한다. 강의록의 예처럼 “a^b이 무리수가 되는 유리수 a, b가 존재한다”는 명제에서 a=2, b=1/2를 선택하면 a^b=2^1/2=√2가 무리수이므로 존재가 증명된다.

비구성적 존재증명법

비구성적 존재증명법은 조건을 만족하는 대상을 직접 특정하지 않고 논리적인 경우 구분을 통해 존재를 보인다. q=(√2)^√2라고 하자. q가 유리수라면 a=b=√2에서 a와 b는 무리수이고 a^b는 유리수이다. q가 무리수라면 a=q, b=√2로 두었을 때 a^b=((√2)^√2)^√2=(√2)²=2로 유리수이다. 어느 경우든 유리수가 되는 a^b를 만드는 무리수 a, b가 존재한다.

구분: 구성적 증명은 증인이 되는 대상을 직접 내놓는다. 비구성적 증명은 대상의 존재를 보장하지만 어떤 경우의 대상이 실제 증인인지는 확정하지 않을 수 있다.

7. 전수·조합·컴퓨터 증명법

전수증명법

전수증명법(exhaustive proof)은 명제에서 가능한 경우의 수가 적을 때 모든 경우를 빠짐없이 조사하는 방법이다. 강의록에서는 n이 5 이하의 자연수일 때 (n+1)²≥2ⁿ임을 n=1, 2, 3, 4, 5에 각각 대입하여 확인한다. 유한한 모든 경우를 확인했으므로 해당 범위의 명제가 증명된다.

조합적 증명법

조합적 증명법(combinatorial proof)은 두 집합의 원소 개수가 같음을 보일 때 사용한다. 전단증명은 원소가 n개인 집합 A와 원소가 m개인 집합 B 사이에 일대일 대응을 만들어 n=m임을 보인다. 중복산정은 동일한 집합의 원소를 서로 다른 두 방법으로 세고, 두 계산 결과가 각각 n과 m이라면 n=m임을 보인다.

컴퓨터를 이용한 증명

증명 과정이 매우 복잡하거나 조사할 경우가 많을 때 컴퓨터의 데이터 처리 능력을 이용할 수 있다. 대표적인 사례로 평면을 유한개의 부분으로 나누어 인접한 부분을 다른 색으로 칠할 때 네 가지 색으로 충분하다는 4색 정리가 소개된다. 컴퓨터 증명은 많은 경우를 빠르게 검사할 수 있지만, 프로그램과 알고리즘이 모든 필요한 경우를 올바르게 처리하는지도 검토해야 한다.

8. 상황에 맞는 증명법 선택

명제의 문장 구조를 먼저 읽으면 증명법 선택이 쉬워진다. 정의를 펼쳐 결론까지 자연스럽게 계산할 수 있으면 직접증명법을, 자연수 전체에 대한 연쇄적 성질이면 수학적 귀납법을 고려한다. P→Q를 직접 다루기 어렵고 ¬Q에서 ¬P로 가는 길이 분명하면 대우증명법이 적합하다.

어떤 명제가 참이라고 가정했을 때 알려진 사실과 충돌할 것 같으면 모순증명법을 사용할 수 있다. “모든”으로 시작하는 명제가 거짓임을 보일 때는 반례 하나를 찾고, “존재한다”는 명제를 보일 때는 구체적인 증인을 제시할 수 있는지 먼저 살핀다. 가능한 경우가 유한하고 적다면 전수증명법이 간단하며, 집합의 크기나 경우의 수가 문제라면 조합적 증명법을 검토한다.

명제의 특징	우선 고려할 방법
정의와 대수적 변형으로 결론을 얻기 쉬움	직접증명법
모든 자연수 n에 대한 성질	수학적 귀납법
조건명제의 대우가 더 다루기 쉬움	대우증명법
명제의 부정이 기존 사실과 충돌함	모순증명법
전칭명제가 거짓임을 보임	반례증명법
조건을 만족하는 대상의 존재를 보임	구성적·비구성적 존재증명법
가능한 경우가 유한하고 적음	전수증명법
두 집합의 원소 수가 같음을 보임	조합적 증명법

핵심 개념 정리

공리는 증명 없이 받아들이는 출발점이고, 증명은 공리와 이미 알려진 결과에서 명제의 참을 논리적으로 이끌어 내는 과정이며, 정리는 그렇게 증명된 명제이다. 보조정리는 큰 정리의 중간 발판이고 따름정리는 정리에서 쉽게 도출되는 결과이다.

직접증명법은 명제를 변형하지 않고 정의와 정리를 연결한다. 수학적 귀납법은 기본단계, 귀납가정, 귀납단계의 세 부분을 모두 갖추어야 한다. 간접증명법에는 원래 명제와 동치인 대우를 증명하는 방법, 명제의 부정에서 모순을 유도하는 방법, 전칭명제를 깨뜨리는 반례, 존재를 보이는 구성적·비구성적 방법이 있다.

전수증명법은 유한한 모든 경우를 조사하고, 조합적 증명법은 일대일 대응이나 중복산정으로 두 집합의 원소 수를 비교한다. 컴퓨터를 이용한 증명은 사람이 처리하기 어려운 많은 경우를 계산하는 데 활용된다.

최종 정리: 좋은 증명은 결론만 맞는 계산이 아니라 전제와 결론 사이의 논리적 연결이 명확한 설명이다. 먼저 명제의 논리 구조와 대상의 범위를 확인한 뒤 가장 자연스러운 증명법을 선택하고, 각 단계에서 사용한 정의·가정·정리를 분명히 밝혀야 한다.

예상문제 20선

1. 공리(axiom)에 대한 설명으로 옳은 것은?

① 정리에서 쉽게 도출되는 부가 명제이다. ② 다른 명제를 증명하기 위한 전제로서 증명 없이 참으로 이용하는 기본 명제이다. ③ 명제가 거짓임을 보이는 하나의 사례이다. ④ 컴퓨터로만 확인할 수 있는 명제이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
공리는 수학 체계의 출발점으로, 다른 명제를 증명할 때 전제로 사용하며 별도의 증명 없이 참으로 받아들인다.

2. 보조정리(lemma)의 역할로 가장 적절한 것은?

① 공리 자체의 참을 다시 증명한다. ② 전칭명제를 반례로 바꾼다. ③ 정리에서 자동으로 따라오는 모든 명제를 뜻한다. ④ 더 큰 정리를 증명하는 과정에서 중간 발판으로 사용된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
보조정리는 이미 증명된 명제로서 더 큰 결과를 얻기 위한 중간 단계에 사용된다. 정리에서 쉽게 따라오는 명제는 따름정리이다.

3. 직접증명법의 일반적인 진행 방식은?

① 전제와 정의, 기존 정리를 논리적으로 연결해 결론을 도출한다. ② 결론의 부정을 가정하여 반드시 모순을 만든다. ③ 모든 가능한 사례를 컴퓨터로 조사한다. ④ 전칭명제를 거짓으로 만드는 반례를 찾는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
직접증명법은 명제를 다른 형태로 바꾸지 않고 공리·정의·기존 정리를 직접 연결하여 결론을 얻는다.

4. 두 홀수 x=2a+1, y=2b+1의 합이 짝수인 이유는?

① a와 b가 반드시 짝수이기 때문이다. ② x+y가 항상 0이기 때문이다. ③ x+y=2(a+b+1)이고 a+b+1이 정수이기 때문이다. ④ 홀수의 정의가 x=2a이기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
x+y=2a+1+2b+1=2(a+b+1)이다. 괄호 안이 정수이므로 합은 2의 정수배인 짝수이다.

5. 수학적 귀납법의 세 단계를 올바르게 나열한 것은?

① 귀납가정 → 반례 → 귀납단계 ② 기본단계 → 귀납가정 → 귀납단계 ③ 기본단계 → 모순가정 → 대우증명 ④ 전수조사 → 중복산정 → 결론

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
수학적 귀납법은 출발점의 성립을 보이는 기본단계, S(k)를 가정하는 귀납가정, S(k+1)을 보이는 귀납단계로 구성된다.

6. 귀납가정에서 가정하는 내용은?

① n=k일 때 명제 S(k)가 참이라는 것 ② n=k+1일 때 명제가 거짓이라는 것 ③ 모든 정수에 대해 결론이 이미 참이라는 것 ④ 기본단계를 생략해도 된다는 것

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
귀납가정은 특정한 k에서 S(k)가 참이라고 임시로 가정하는 단계이다. 이 가정을 이용하여 다음 단계 S(k+1)을 증명한다.

7. 수학적 귀납법에 관한 설명으로 옳지 않은 것은?

① 기본단계는 귀납의 출발점을 확보한다. ② 귀납단계에서는 S(k)에서 S(k+1)이 따라옴을 보인다. ③ 모든 자연수에 대한 명제를 증명하는 데 유용하다. ④ 귀납가정에서 S(k+1)을 참이라고 가정하면 증명이 완성된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
귀납가정에서는 S(k)를 가정해야 한다. 증명해야 할 S(k+1)을 미리 가정하면 순환논증이 되어 올바른 귀납증명이 아니다.

8. 조건명제 P→Q의 대우는?

① Q→P ② ¬P→¬Q ③ ¬Q→¬P ④ P∧¬Q

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
P→Q의 대우는 ¬Q→¬P이며 원래 명제와 논리적으로 동치이다. Q→P는 역이므로 구별해야 한다.

9. “x²이 홀수이면 x는 홀수이다”를 대우증명할 때 보여야 할 내용은?

① x가 홀수이면 x²도 홀수이다. ② x²이 짝수이면 x가 짝수이다. ③ x가 짝수이면 x²도 짝수이다. ④ x²이 홀수이면 x가 짝수이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
원래 명제의 대우는 “x가 홀수가 아니면 x²도 홀수가 아니다”이다. 정수에서는 이를 x가 짝수이면 x²도 짝수라고 표현할 수 있다.

10. 모순증명법의 핵심 절차는?

① 증명하려는 명제의 부정을 가정하고 모순을 유도한다. ② 결론과 무관한 사례를 여러 개 계산한다. ③ 원래 명제의 역만 증명한다. ④ 조건을 만족하는 대상을 직접 제시한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
모순증명법은 명제의 부정을 참이라고 가정한 뒤 기존 사실 또는 가정 자체와 충돌하는 결론을 이끌어 그 부정이 거짓임을 보인다.

11. √2의 무리수 증명에서 √2=a/b, a와 b는 서로소라고 가정한 뒤 얻게 되는 모순은?

① a와 b가 모두 홀수이다. ② a와 b가 모두 짝수여서 서로소 조건과 충돌한다. ③ a=0이 된다. ④ b가 무리수가 된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
계산을 통해 a와 b가 모두 짝수임을 얻는다. 이는 둘이 2를 공약수로 가지므로 서로소라는 처음 조건과 모순된다.

12. 전칭명제 ∀xP(x)가 거짓임을 보이는 가장 직접적인 방법은?

① 모든 x에 대해 P(x)를 계산한다. ② P(x)를 참으로 만드는 x 하나를 찾는다. ③ P(x)의 정의를 생략한다. ④ P(x)를 거짓으로 만드는 반례 x 하나를 제시한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
전칭명제는 단 하나의 반례만 있어도 거짓이다. 따라서 P(x)가 거짓이 되는 구체적인 x를 찾으면 충분하다.

13. “모든 실수 a,b에서 a²=b²이면 a=b이다”의 반례로 알맞은 것은?

① a=-2, b=2 ② a=1, b=1 ③ a=0, b=0 ④ a=3, b=3

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
a=-2, b=2이면 a²=b²=4이지만 a와 b는 같지 않다. 따라서 주어진 전칭명제를 거짓으로 만드는 반례이다.

14. 구성적 존재증명법의 특징은?

① 가능한 모든 경우를 컴퓨터로 검사한다. ② 명제의 부정을 가정한다. ③ 존재 여부를 알 수 없다고 결론 내린다. ④ 조건을 만족하는 구체적인 대상을 직접 제시한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
구성적 존재증명은 존재명제를 참으로 만드는 증인을 실제로 제시한다. 예를 들어 a=2, b=1/2는 a^b=√2가 무리수가 되게 한다.

15. 비구성적 존재증명법에 대한 설명으로 옳은 것은?

① 반드시 유일한 대상을 계산해 낸다. ② 구체적인 증인을 특정하지 않더라도 논리적으로 존재를 보일 수 있다. ③ 전칭명제를 거짓으로 만드는 데만 사용한다. ④ 기본단계와 귀납단계가 반드시 필요하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
비구성적 증명은 경우 구분이나 논리적 논증으로 대상의 존재를 보장하지만, 어느 대상이 실제 증인인지 확정하지 않을 수 있다.

16. 전수증명법을 사용하기 가장 적절한 상황은?

① 가능한 경우가 무한히 많고 구조가 전혀 없을 때 ② 두 집합 사이의 일대일 대응을 만들 때 ③ 가능한 경우가 유한하고 적어 모두 조사할 수 있을 때 ④ 조건명제의 대우만이 참일 때

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
전수증명법은 가능한 모든 경우를 빠짐없이 확인한다. 따라서 경우의 수가 유한하고 충분히 적을 때 효과적이다.

17. 두 유한집합의 원소 수가 같음을 일대일 대응을 만들어 보이는 조합적 방법은?

① 모순증명 ② 수학적 귀납법 ③ 반례증명 ④ 전단증명

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
전단증명은 두 집합의 원소 사이에 일대일 대응을 구성하여 두 집합의 원소 개수가 같음을 보이는 조합적 증명법이다.

18. 중복산정에 대한 설명으로 옳은 것은?

① 한 집합의 원소를 한 번만 세고 끝낸다. ② 같은 집합의 원소를 두 가지 방법으로 세어 두 결과가 같음을 보인다. ③ 반례 두 개를 찾아 전칭명제를 증명한다. ④ 귀납가정을 두 번 사용한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
중복산정은 동일한 대상을 서로 다른 두 방식으로 센다. 두 방식이 같은 집합을 세므로 얻은 식이나 수가 서로 같다는 결론을 얻는다.

19. 컴퓨터를 이용한 증명법이 특히 유용한 경우는?

① 정의 하나만 쓰면 즉시 결론이 나오는 경우 ② 가능한 경우가 하나뿐인 경우 ③ 사람이 직접 처리하기 어려울 만큼 계산이나 경우 조사가 복잡한 경우 ④ 명제에 수가 전혀 등장하지 않는 모든 경우

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
컴퓨터 증명은 대량의 계산과 복잡한 경우 조사를 빠르게 처리할 수 있다. 강의록에서는 대표 사례로 4색 정리를 소개한다.

20. 정리(theorem)에 대한 설명으로 옳은 것은?

① 공리와 기존 결과로부터 증명된 명제이다. ② 증명 없이 참으로 받아들이는 가장 기본적인 가정이다. ③ 전칭명제를 깨뜨리는 하나의 사례이다. ④ 조건을 만족하는 대상이 존재하지 않는다는 선언이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
정리는 공리와 정의, 이미 증명된 결과를 바탕으로 논리적으로 증명된 명제이다. 증명 없이 받아들이는 기본 가정은 공리이다.