방송대 이산수학 3강: 증명법 선택과 수학적 귀납법

증명 문제에서 막히는 이유는 계산 능력보다 출발점을 잘못 잡았기 때문인 경우가 많습니다. 결론을 직접 만들지, 대우로 바꿀지, 모순을 끌어낼지, 한 사례로 반박할지를 먼저 판단해야 합니다. 이 글은 명제의 논리 형태를 진단해 증명법을 선택하고, 정의에서 결론까지 빠짐없이 연결하는 방법을 대표 풀이와 함께 설명합니다.

증명은 결론이 아니라 연결 과정으로 평가한다

“두 홀수의 합은 짝수다”라는 결론을 여러 수로 확인할 수는 있습니다. 3+5=8, 7+9=16이라는 계산은 명제를 믿을 근거가 되지만, 모든 홀수 쌍을 다룬 것은 아닙니다. 증명은 몇 개의 성공 사례를 모으는 일이 아니라 가정에서 출발해 허용된 정의·공리·정리를 논리적으로 연결하여 결론이 반드시 성립함을 보이는 작업입니다.

증명 점검 항목	물어볼 질문	빠졌을 때의 문제
출발점	무엇을 가정했고 변수의 범위는 무엇인가?	사용할 수 없는 성질을 끌어옴
연결 근거	각 식과 문장은 앞 단계에서 왜 따라오는가?	직관적인 비약이 생김
도착점	마지막 문장이 목표의 정의와 정확히 일치하는가?	관련 사실만 보이고 증명이 끝나지 않음
범위	특정 사례가 아니라 요구한 모든 대상에 적용되는가?	예시 확인을 일반 증명으로 오해함

첫 판단: 증명할 문장을 전제와 결론, 한정자, 변수의 범위로 분해한 뒤 결론의 정의에서 거꾸로 필요한 형태를 찾습니다.

공리에서 정리까지는 근거의 계보가 이어진다

공리는 다른 명제를 증명할 때 전제로 사용하는 가장 기본적인 가정이며, 해당 체계 안에서 별도의 증명 없이 참으로 받아들입니다. 증명은 특정 공리와 이미 확보한 결과를 바탕으로 제안된 명제가 참임을 입증하는 작업입니다. 정리는 그렇게 증명된 명제입니다.

정리를 만드는 과정에는 두 이름이 자주 등장합니다. 보조정리는 더 큰 정리를 증명하는 디딤돌로 먼저 증명해 사용하는 명제이고, 따름정리는 이미 증명한 정리에서 비교적 쉽게 도출되는 부가 결과입니다. 보조정리와 따름정리도 증명된 명제라는 점은 같지만, 앞의 것은 본 증명 전에 필요한 도구이고 뒤의 것은 본 정리 뒤에 따라오는 결과라는 위치가 다릅니다.

오개념 교정: 공리는 “너무 자명해서 어느 체계에서나 무조건 참인 문장”이라는 뜻이 아닙니다. 어떤 공리를 채택했는지가 그 수학 체계에서 허용되는 출발점을 정합니다.

명제의 모양이 증명법을 고르는 첫 단서다

목표의 형태·상황	먼저 검토할 방법	핵심 행동
정의에서 결론이 자연스럽게 이어짐	직접증명	전제를 정의형으로 풀어 결론의 정의형을 만듦
모든 자연수 n에 대한 연쇄적 성질	수학적 귀납법	출발점과 k→k+1의 연결을 증명함
P→Q보다 ¬Q→¬P가 다루기 쉬움	대우증명	원명제와 동치인 대우를 직접 증명함
명제의 부정이 불가능한 결과를 만듦	모순증명	부정을 가정해 공존할 수 없는 결론을 얻음
∀x P(x)가 거짓임을 보임	반례증명	P(x)를 거짓으로 만드는 한 대상을 제시함
∃x P(x)가 참임을 보임	존재증명	증인을 제시하거나 존재를 우회적으로 보임
가능한 경우가 적은 유한 범위	전수증명	빠짐없이 모든 경우를 검사함
두 수량이 같음을 보임	조합적 증명	일대일 대응 또는 두 가지 세기를 사용함

이 표는 하나의 명제에 하나의 증명법만 가능하다는 뜻이 아닙니다. 여러 방법이 가능할 때 가장 짧고 검증하기 쉬운 경로를 고르기 위한 출발점입니다. 증명 도중 정의를 펼쳤는데 목표와 멀어진다면 대우나 모순처럼 명제의 형태를 바꾸는 방법을 다시 검토할 수 있습니다.

직접증명은 결론의 정의를 만들어 내는 일이다

직접증명은 명제를 다른 동치 명제로 바꾸지 않고 전제에서 결론으로 나아가는 연역적 방법입니다. 강의자료의 “두 홀수의 합은 짝수”를 보면, 결론의 핵심 단어인 짝수의 정의가 목표 형태를 알려 줍니다. 합을 2×정수로 나타내면 됩니다.

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는 짝수

마지막의 “a+b+1은 정수”가 중요합니다. 식에 2가 보인다는 사실만으로 짝수라고 끝낼 수 없고, 2에 곱해진 값이 정수임을 확인해야 짝수의 정의와 맞습니다.

유리수의 합도 같은 설계로 증명합니다. r=a/b, s=c/d로 두되 a,b,c,d는 정수이고 b,d≠0이라는 조건을 함께 둡니다. 그러면 r+s=(ad+bc)/bd이고, 분자와 분모는 정수이며 bd≠0입니다. 따라서 합도 “정수/0이 아닌 정수” 꼴이므로 유리수입니다.

직접증명 설계법: 전제의 정의를 식으로 펼치고 → 목표 용어의 정의형으로 변형하고 → 그 형태에 필요한 범위 조건까지 확인합니다.

파스칼 항등식은 공통분모가 증명 경로를 연다

파스칼 삼각형에서 이웃한 두 수의 합이 아래 수가 되는 관계는 C(n,k)+C(n,k-1)=C(n+1,k)로 표현됩니다. n,k가 양의 정수이고 k≤n일 때, 이항계수의 팩토리얼 정의를 직접 대입해 증명할 수 있습니다.

C(n,k) + C(n,k-1)
= n!/[k!(n-k)!] + n!/[(k-1)!(n-k+1)!]
= (n-k+1)n!/[k!(n-k+1)!] + kn!/[k!(n-k+1)!]
= [(n-k+1)+k]n!/[k!(n-k+1)!]
= (n+1)n!/[k!(n-k+1)!]
= (n+1)!/[k!((n+1)-k)!]
= C(n+1,k)

둘째 줄에서 바로 분자를 더하면 안 됩니다. 첫 분수에는 n-k+1을, 둘째 분수에는 k를 분자와 분모에 각각 곱해 공통분모 k!(n-k+1)!를 만든 뒤 더합니다. 마지막에는 (n+1)n!=(n+1)!, n-k+1=(n+1)-k를 확인하면 목표 형태가 완성됩니다.

수치 검산: n=4, k=2이면 C(4,2)+C(4,1)=6+4=10이고 C(5,2)=10입니다. 한 사례의 일치는 증명 자체가 아니지만, 전개 중 첨자나 팩토리얼을 잘못 쓴 오류를 찾는 데 유용합니다.

수학적 귀납법은 출발점과 전달 고리를 모두 요구한다

자연수 n에 관한 명제 S(n)을 모두 증명하려면 세 부분이 필요합니다. 기본단계는 시작값에서 S(n)이 참인지 확인하고, 귀납가정은 임의의 k에서 S(k)가 참이라고 가정하며, 귀납단계는 그 가정을 사용해 S(k+1)이 참임을 보입니다.

단계	해야 하는 일	빠지면 생기는 문제
기본단계	주어진 범위의 실제 출발점 확인	전달 고리가 성립해도 시작할 곳이 없음
귀납가정	임의의 k에 대해 S(k)를 사용 가능하다고 둠	k+1 증명에 필요한 연결 근거가 사라짐
귀납단계	S(k)를 이용해 S(k+1)을 도출	개별 사례만 확인하고 전체 자연수로 확장하지 못함

기본단계만 여러 개 확인하는 것은 귀납법이 아닙니다. 반대로 k에서 k+1로 가는 식만 보여도 출발점이 없으면 결론이 전체 범위에 전달되지 않습니다. 또한 귀납단계에서 귀납가정을 실제로 사용하지 않았다면, 그 계산이 무엇을 근거로 k+1까지 이어지는지 다시 확인해야 합니다.

자연수의 합 공식에서 귀납가정이 쓰이는 순간을 찾는다

S(n): 1+2+···+n=n(n+1)/2를 증명해 봅시다. 기본단계 n=1에서는 왼쪽 1과 오른쪽 1×2/2=1이 같습니다. 이제 임의의 자연수 k에서 다음 등식이 참이라고 가정합니다.

1 + 2 + ··· + k = k(k+1)/2

k+1까지의 합은 k까지의 합에 k+1을 더한 것입니다. 여기서 밑줄 친 역할을 하는 첫 치환이 바로 귀납가정의 사용입니다.

1 + 2 + ··· + k + (k+1)
= k(k+1)/2 + (k+1)
= [k(k+1) + 2(k+1)]/2
= (k+1)(k+2)/2
= (k+1)((k+1)+1)/2

마지막 식은 n 자리에 k+1을 넣은 S(k+1)의 오른쪽과 정확히 같습니다. 따라서 기본단계와 귀납단계를 통해 모든 자연수 n에 대해 공식이 성립합니다. 단순히 마지막 공식을 적는 것이 아니라, 귀납가정으로 앞부분의 합을 바꾸는 연결을 보여 주는 것이 핵심입니다.

대우증명은 부정의 위치를 정확히 바꾼다

조건명제 P→Q와 그 대우 ¬Q→¬P는 논리적으로 동치입니다. 원명제의 결론 Q를 직접 만들기 어렵지만 Q가 아닐 때 P도 불가능함을 보이기 쉬우면 대우증명을 선택합니다. 여기서 역 Q→P나 이 ¬P→¬Q는 일반적으로 원명제와 동치가 아니므로 대우와 혼동하면 안 됩니다.

“정수 x에 대해 x²이 홀수이면 x도 홀수”의 대우는 “x가 홀수가 아니면 x²도 홀수가 아니다”입니다. 정수 x가 홀수가 아니면 짝수이므로 x=2k로 둘 수 있습니다.

x = 2k  (k는 정수)
x² = (2k)² = 4k² = 2(2k²)
2k²는 정수이므로 x²은 짝수

대우가 참이므로 원명제도 참입니다. “x²이 홀수라는 전제”에서 시작하지 않았다고 해서 원래 문제를 피한 것이 아닙니다. 동치인 명제를 증명했기 때문에 같은 논리적 효력을 갖습니다.

모순증명은 명제 전체의 부정에서 출발한다

모순증명은 증명하려는 명제 R의 부정 ¬R을 가정하고, 그 가정이 이미 알려진 사실이나 자기 자신과 양립할 수 없음을 보입니다. 특히 목표가 P→Q라면 그 부정은 단순한 ¬P가 아니라 P∧¬Q입니다. 즉 전제 P가 참인데 결론 Q가 거짓인 상황을 가정해야 합니다.

강의자료의 √2 무리수 증명에서는 반대로 √2가 유리수라고 가정합니다. 그러면 서로소인 정수 a,b와 b≠0에 대해 √2=a/b로 나타낼 수 있어야 합니다.

√2 = a/b
2b² = a²
a²이 짝수이므로 a도 짝수: a = 2c
2b² = 4c², 따라서 b² = 2c²
b²이 짝수이므로 b도 짝수

a와 b가 모두 짝수라면 공약수 2를 가지므로 처음의 “a와 b는 서로소”라는 조건과 모순입니다. 따라서 √2를 유리수라고 한 가정이 거짓이고 √2는 무리수입니다. 서로소 조건을 처음에 두지 않으면 마지막에 모순이 완성되지 않는다는 점을 주의해야 합니다.

한정자가 바뀌면 필요한 증거의 양도 바뀐다

전체한정자 ∀가 붙은 명제가 거짓임을 보이려면 조건을 깨뜨리는 대상 하나면 충분합니다. 이것이 반례증명입니다. “모든 실수 a,b에 대해 a²=b²이면 a=b이다”라는 문장에는 a=-2, b=2를 대입할 수 있습니다. 두 제곱은 모두 4이지만 a≠b이므로 전체명제는 거짓입니다.

반례 하나는 전체명제를 반박하지만, 사례 몇 개의 성공은 전체명제를 증명하지 못합니다. 한편 존재한정자 ∃가 붙은 명제가 참임을 보일 때는 조건을 만족하는 대상 하나를 확보하면 됩니다. 두 상황을 논리식으로 나란히 보면 방향이 분명해집니다.

목표	필요한 증거	충분하지 않은 것
`∀x P(x)`가 거짓	`P(c)`가 거짓인 반례 c 하나	P가 참인 사례 여러 개
`∃x P(x)`가 참	P를 참으로 만드는 증인 또는 존재 논증	후보를 찾지 못했다는 관찰

존재증명은 증인을 보여 주는지에 따라 갈린다

구성적 존재증명은 조건을 만족하는 구체적인 대상을 찾거나 만드는 절차를 제시합니다. 강의자료에서 유리수 a,b에 대해 aᵇ이 무리수가 되는 예로 a=2, b=1/2을 선택하면 2^(1/2)=√2이므로 명제가 성립합니다.

비구성적 존재증명은 조건을 만족하는 대상의 존재를 보이되 어느 대상이 증인인지 확정하지 않을 수 있습니다. 무리수 a,b인데 aᵇ이 유리수가 되는 상황을 다음 두 경우로 살펴봅니다.

q = (√2)^(√2)라고 두자.

경우 1: q가 유리수
  a = √2, b = √2이면 a^b = q가 유리수

경우 2: q가 무리수
  a = q, b = √2이면
  a^b = ((√2)^(√2))^(√2) = (√2)^2 = 2

q는 유리수이거나 무리수이므로 두 경우 중 하나는 반드시 성립하고, 어느 경우든 요구한 무리수 a,b가 존재합니다. 이 논증은 q가 어느 부류인지 결정하지 않은 채 경우 분할만으로 존재를 보인다는 점에서 비구성적입니다.

전수·조합적·컴퓨터 증명은 문제 규모와 구조를 이용한다

전수증명은 가능한 경우가 적을 때 전부 조사합니다. 예를 들어 n≤5인 자연수에 대해 (n+1)²≥2ⁿ을 보이려면 n=1,2,3,4,5를 각각 대입해 4≥2, 9≥4, 16≥8, 25≥16, 36≥32를 확인합니다. 범위가 n≤5로 제한되어 있으므로 다섯 경우를 빠짐없이 확인하면 증명이 끝납니다. 이 결과만으로 n=6 이후까지 증명한 것은 아닙니다.

조합적 증명은 집합의 원소 수가 같음을 구조로 보입니다. 전단증명은 두 집합 사이의 일대일 대응을 만들어 크기가 같음을 보이고, 중복산정은 같은 집합을 서로 다른 두 방식으로 세어 얻은 식을 같게 놓습니다. 계산식이 같다는 사실보다 “같은 대상을 세고 있다”는 해석이 증명의 근거입니다.

컴퓨터를 이용한 증명은 사람이 일일이 다루기 어려운 복잡한 경우를 컴퓨터의 처리 능력으로 검사합니다. 강의자료는 대표 사례로 4색 정리를 소개합니다. 컴퓨터가 사용되더라도 무엇을 모든 경우로 보았는지, 프로그램이 어떤 판정 규칙을 구현했는지, 누락 없이 검사했는지를 설명해야 증명의 신뢰 구조가 드러납니다.

완성된 증명은 네 번 감사한다

증명문을 쓴 뒤에는 답만 다시 읽지 말고 다음 네 관문을 통과시켜 보세요.

감사 관문	확인할 내용	대표 오류
논리형	원명제·대우·부정·한정자를 정확히 썼는가?	P→Q의 부정을 ¬P로 잘못 둠
범위	정수·자연수·0이 아닌 분모 같은 조건을 보존했는가?	짝수 정의에서 곱해진 값의 정수성을 생략함
연결	귀납가정이나 기존 정리를 실제로 사용했는가?	S(k+1)을 별도로 계산하고 전체 확장이라 주장함
완결	마지막 문장이 목표와 일치하고 모든 경우를 덮는가?	일부 사례 확인을 전체 증명으로 일반화함

증명법의 이름을 맞히는 것보다 이 네 관문을 통과하는 논증을 만드는 일이 중요합니다. 다른 방법을 선택했더라도 가정과 결론 사이의 연결이 타당하고 범위를 모두 덮는다면 올바른 증명이 될 수 있습니다.

핵심 개념 정리

공리는 체계의 출발 가정, 증명은 논리적 입증 과정, 정리는 그 과정으로 확보한 명제입니다.
직접증명은 전제의 정의에서 결론의 정의형을 만들고, 귀납법은 기본단계와 k→k+1의 전달 고리를 세웁니다.
대우증명은 P→Q와 동치인 ¬Q→¬P를 증명하며, 모순증명은 목표 명제 전체의 부정을 가정합니다.
반례는 전체명제를 깨는 한 사례이고, 존재증명에는 증인을 직접 제시하는 구성적 방법과 우회적으로 존재를 보이는 비구성적 방법이 있습니다.
전수증명은 작은 유한 범위, 조합적 증명은 같은 대상의 개수, 컴퓨터 이용 증명은 복잡한 경우의 체계적 처리에 초점을 둡니다.

증명 문제를 보면 먼저 변수의 범위와 한정자를 표시하고, 전제 P와 결론 Q를 분리하세요. 결론의 정의가 바로 만들어지면 직접증명, 자연수의 연쇄이면 귀납법, 대우가 단순하면 대우증명, 부정이 불가능한 결과를 낳으면 모순증명을 선택합니다. 전체명제를 거짓으로 만들 때는 반례 하나, 존재명제를 참으로 만들 때는 증인 또는 존재 논증이 필요합니다. 마지막에는 논리형·범위·연결·완결의 네 관문으로 증명을 다시 검사합니다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료 42쪽 전체를 확인하고 표지·학습 목표·본문·정리·다음 강의 안내를 구분한 뒤, 3강의 직접증명·수학적 귀납법·간접증명과 기타 증명법을 명제 진단과 풀이 순서 중심으로 재구성한 비공식 학습자료입니다. 파스칼 항등식의 공통분모 과정, 귀납가정의 실제 사용 지점, 조건명제 전체의 부정과 증명 감사 절차를 보완해 검토했습니다.

작성·편집: 올에이클래스 학습연구팀
주요 근거: 한국방송통신대학교 컴퓨터과학과 이산수학 3강 「증명」 강의자료(2021) :codex-file-citation{path="K1. 컴퓨터과학과/1. 재검토필요/2-1 이산수학/1. 강의록/이산수학_강의록_3강.pdf" purpose="source"}
편집 원칙: 올에이클래스 편집 정책
최종 내용 검토: 2026-09-05

방송대 이산수학 3강: 증명법 선택과 수학적 귀납법