이산수학 - 증명, 직접증명법, 수학적 귀납법, 간접증명법, 다양한 증명방법

기본사항 

 

일반적으로 타당성을 입증하는 데는 증명이 사용된다. 증명은 주로 "P이면 Q이다"라는 형식을 따르게 되는데, 전제가 참일 때 결론이 참임을 논리적으로 보일 수 있다면 많은 사람이 Q가 타당하다고 받아들이게 될 것이다. 

 

그렇다면 P가 참임은 어떻게 증명해야 할까? 수학적으로 참으로 알려진 많은 사실이 P가 될 수 있겠지만, 이들 역시 다른 전제의 동무을 받아 증명되어야 이용할 수 있을 것이다. 이렇게 계속 거슬러 올라가게 되면 더 이상 증명할 수 없는 사실을 만나게 되는데 이들을 공리라 한다. 

 

공리

 

어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정으로, 별도의 증명없이 참으로 이용되는 명제를 공리라고 한다. 

 

 

예시 

1) 두 점이 주어졌을 때, 두 점을 통과하는 직선을 그릴 수 있다(유클리드 기하학)

2) 어떤 자연수도, 그 수의 다음 수가 존재한다. (페아노의 공리) 

3) 어떤 것도 포함하지 않는 집합이 존재한다. (공리적 집합론) 

 

 

 

증명 

증명이란 특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참임을 입증하는 작업이다. 

 

 

 

정리 

 

공리로부터 증명된 명제를 정리라고 한다. 

 

1) 보조 정리(lemma)

- 정리를 증명하는 과정 중에 사용되는 증명된 명제 

 

2) 따름 정리(corollary) 

- 정리로부터 쉽게 도출되는 부가적인 명제 

 

3) 대표적인 예시 

- 피타고라스 정리, 페르마의 마지막 정리 

 

4) 증명 방법 

- 직접증명법: 공리와 정의, 그리고 정리를 논리적으로 직접 연결하여 증명한다.

- 수학적 귀납법: 자연수 n에 대한 명제의 성질을 증명하는 데 유용한 증명 방법 -> 기본단계, 귀납 가정, 귀납 단계를 이용 

- 간접 증명법: 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명 -> 대우, 모순, 반례, 존재 증명법 

- 그 외: 전수 증명법, 조합적 증명법, 컴퓨터 이용 증명법 

 

 

 

직접증명법

직접즉명법은 다른 말로 연역(deduction)이라고도 한다. 

 

명제를 변형하지 않고 공리와 정의, 그리고 이미 증명된 정리를 논리적으로 직접 연결해 증명하는 방법이다. 

 

예시 1: 두 홀수의 합은 항상 짝수임을 증명하시오 

-> 두 홀수를 각각 x, y라고 하면, 각각 x=2a+1, y=2b+1(a,b는 정수) 형태로 나타낼 수 있다. x+y=2a+2b+2 =2(a+b+1)이므로 두 홀수의 합은 항상 짝수이다. 

 

예시 2: 파스칼의 삼각형 

파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것으로서 이항전개에서 계수들의 값을 구하는 데 사용된다. 

 

n, k는 양의 정수이고, k<=n이라고 가정하면 C(n+1, k) = C(n,k) + C(n,k-1) 이다. 

 

1. 조합의 정의에 따라 식을 전개한다:
   - $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$
   - $C(n, k-1) = \binom{n}{k-1} = \frac{n!}{(k-1)!(n-(k-1))!} = \frac{n!}{(k-1)!(n-k+1)!}$

2. 등식 왼쪽 항 전개:
   - $C(n+1, k) = \frac{(n+1)!}{k!(n+1-k)!}$

3. 등식 오른쪽 항 전개 및 공통 분모를 구하기:
   - $C(n, k) + C(n, k-1) = \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}$
   - 공통 분모를 구하기 위해 각 항에 적절한 형태로 1을 곱한다:
     - 첫 번째 항에는 $\frac{n-k+1}{n-k+1}$을, 두 번째 항에는 $\frac{k}{k}$를 곱한다.
   - 이를 통해 얻은 식: $\frac{(n-k+1)n!}{k!(n-k+1)!} + \frac{kn!}{k!(n-k+1)!}$
   - 공통 분모: $k!(n-k+1)!$

4. 분자를 단순화하여 등식 왼쪽과 일치시킨다:
   - 분자는 $(n-k+1)n! + kn! = (n+1)n!$
   - 따라서, $\frac{(n-k+1) + k}{n!} / k!(n-k+1)! = \frac{(n+1)n!}{k!(n-k+1)!}$

5. 분자와 분모에 $(n+1)$을 추가하여 조합의 정의에 따라 정리한다:
   - $\frac{(n+1)n!}{k!(n+1-k)!} = C(n+1, k)$

 

수학적 귀납법

수학적 귀납법은 모든 자연수 n에 대해 명제가 성립함을 증명하는 데 유용한 방법이다. 먼저 n=1일 때 명제가 참임을 증명하고, 그 다음에 n=k일 때 참이면 n = k+1일 때도 참임을 증명하는 방식을 따른다. 

 

여기서 출발이 되는 n의 값을 기본단계라고 하며, n=k일 때 성립한다고 가정하는 것을 귀납가정이라 하고, n=k+1일 때도 마찬가지로 성립함을 보이는 것을 귀납단계(inductive step)라고 한다. 

 

예시 1: n이 자연수일 때 다음을 증명하시오 

1+2+...n = n(n+1)/2

 

S(n)을 1 + 2 + ... + n = n(n+1)/2라 하자.


(1) 기본단계
S(1)은 1 = 1(1+1)임을 성립

(2) 귀납가정
S(k)가 참이라고 가정. 즉,
1 + 2 + ... + k = k(k+1)/2

(3) 귀납단계

귀납단계에서는 \(S(k)\)가 참이라고 가정하고 \(S(k+1)\)이 참임을 증명해야 한다. \(S(k+1)\)은 다음과 같이 표현할 수 있다:

\[
1 + 2 + ... + k + (k+1)
\]

귀납가정을 사용하면, 위 식은 아래와 같이 나타낼 수 있다:

\[
k(k+1)/2 + (k+1)
\]

이제 이 식을 공통인자 \((k+1)\)를 사용하여 인수분해한다:

\[
(k+1)(k/2 + 1)
\]

이 식을 다시 정리하면:

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

따라서, 다음과 같이 단순화할 수 있다:

\[
(k+1)(k+2)/2
\]

이 식은 \(S(k+1) = (k+1)((k+1)+1)/2\)의 형태와 정확히 일치한다. 따라서 귀납단계가 성립하며, \(S(n)\)이 모든 자연수 \(n\)에 대해 참임이 증명된다.

 

 

 

 

간접증명법

 

간접증명법은 증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법이다. 

 

(1) 대우증명법 

예시 1: x^2이 홀수라면 x도 홀수임을 증명하시오 

"x^2이 홀수라면 x도 홀수"의 대우는 "x가 홀수가 아니라면 x^2도 홀수가 아니다."이다. 

 

x는 짝수 => x = 2k (단, k는 정수)
=> x^2 = (2k)^2 = 4k^2 = 2(2k^2)
=> 2k^2도 정수이므로 x^2는 짝수

∴  대우증명법에 의해 주어진 명제는 참이다. 

 

 

예시 2: 임의의 정수 n에 대해 3n+2가 짝수이면, n도 짝수임을 증명하시오. 

명제 p를 "3n+2는 짝수이다", 명제 q를 "n은 짝수"라고 하면, 문제의 명제는 조건 명제 p→q로 나타낼 수 있다. 조건 명제의 대우 (~q →~p)는 "n이 짝수가 아니라면 3n+2도 짝수가 아니다"이다. n이 짝수가 아니면 홀수이므로 n = 2k +1이다. 이를 이용해 3n+2를 구하면 3n +2 = 3(2k+1 ) + 2 = 6k + 5 = 2(3k+2)+1이다. 3n+2도 홀수이므로 조건 명제의 대우는 참이다. 

 

 

 

 

 

(2) 모순증명법

p →q를 증명할 때 ~p를 가정하면 모순이 발생함을 보인다. 

 

예시 1: √2가 유리수가 아님을 증명하시오.

모순증명법으로 √2가 유리수가 아님을 증명하는 과정은 다음과 같다. 먼저, √2가 유리수라고 가정하면, √2를 분수 \( \frac{a}{b} \)의 형태로 표현할 수 있다고 가정한다. 여기서 \( a \)와 \( b \)는 서로소인 정수이다 (즉, 최대공약수가 1이다). 그러면 \( \sqrt{2} = \frac{a}{b} \)라는 등식이 성립하고, 양변을 제곱하면 \( 2 = \frac{a^2}{b^2} \)이 된다. 이를 다시 정리하면 \( a^2 = 2b^2 \)이다. 이 식에서 \( a^2 \)는 2의 배수이므로 \( a \)도 2의 배수이다. \( a \)를 \( 2k \)로 표현하면, \( (2k)^2 = 2b^2 \)가 되어 \( 4k^2 = 2b^2 \)이고, \( 2k^2 = b^2 \)이다. 이로부터 \( b^2 \)도 2의 배수임을 알 수 있고, 따라서 \( b \)도 2의 배수이다. 이 결과 \( a \)와 \( b \)가 모두 2의 배수라는 것은 \( a \)와 \( b \)가 서로소라는 가정과 모순이다. 따라서 처음의 가정인 √2가 유리수라는 가정이 잘못되었음을 알 수 있으며, √2는 유리수가 아님을 증명할 수 있다. 

 

 

(3) 반례증명법 

 

전체한정자가 사용된 명제함수 ∀xP(x)가 거짓임을 증명하기 위해 반례를 찾는 방법을 반례증명법이라고 한다. 

 

 

예시1: 다음 명제가 거짓임을 증명하시오. 

모든 자연수 x는 x보다 작은 두 정수 y,z의 제곱의 합으로 나타낼 수 있다. 

 

명제를 검토할 때, 두 정수 \( y \)와 \( z \)의 제곱의 합으로 나타낼 수 없는 가장 작은 자연수 \( x \)의 예를 찾는 것이 목표다. 직관적으로 생각해 보면, 아주 작은 수들부터 검토하는 것이 유리하다. 예를 들어, \( x = 1 \)인 경우를 생각해보자. \( y \)와 \( z \)가 1보다 작은 정수여야 하므로, 가능한 값은 0 또는 음수이다. \( y \)와 \( z \)가 0인 경우, \( y^2 + z^2 = 0^2 + 0^2 = 0 \)이 되어 \( x = 1 \)을 만족시키지 못한다.

더 나아가 \( y \)와 \( z \)가 각각 0과 -1, -1과 -1, -1과 0 등이 될 수 있지만, 이들 조합으로도 \( y^2 + z^2 = 1 \)이 되는 경우는 없다. 이는 1이 \( y \)와 \( z \)의 제곱의 합으로 표현될 수 없음을 의미한다. 따라서 \( x = 1 \)은 주어진 명제에 대한 반례로 충분하며, 이로써 명제가 거짓임을 증명할 수 있다. 

 

 

예시 2: 다음 명제가 거짓임을 증명하시오. 

모든 실수 a,b에 대하여, a^2 = b^2 이면 a=b이다. 

 

이 명제의 경우, \(a^2 = b^2\)는 \(a\)와 \(b\)가 서로 반대의 부호를 가질 수도 있다는 점에서 거짓일 수 있다. 예를 들어, \(a = 1\)과 \(b = -1\)을 대입하면, 두 수의 제곱은 같다:
\[ a^2 = 1^2 = 1 \]
\[ b^2 = (-1)^2 = 1 \]
따라서, \(a^2 = b^2\)의 조건은 만족하지만, \(a\)와 \(b\)는 서로 다르다 (\(a \neq b\)). 이는 \(a = 1\), \(b = -1\)이 주어진 명제의 반례가 되어, 모든 실수 \(a, b\)에 대하여 \(a^2 = b^2\) 이면 \(a=b\)라는 명제가 거짓임을 증명한다. 이 반례는 명제가 모든 경우에 참이 아니라는 것을 보여주므로, 명제는 거짓임을 증명하는 데 충분하다.

 

 

 

(4) 구성적 존재증명법 

 

존재한정자가 사용된 명제함수 ∃xP(x)를 증명하는 방법으로는 P(x)를 참으로 만드는 x를 주어진 정의역에서 찾거나 x를 찾는 일련의 과정을 제시하는 것이다. P(a)를 참으로 만드는 어떤 원소 a를 구함으로써 존재의 증명이 완료된다. 

 

예시 1: a^b이 무리수가 되는 유리수 a,b가 존재함을 증명하시오. 

 

a가 2, b가 1/2 이라고 하자.
⇒ 2² = √2 (무리수)
∴ 증명

 

 

(5) 비구성적 존재증명법 

비구성적 존재증명법은 직접적으로 P(x)를 참으로 만드는 x를 찾거나 x를 찾는 일련의 과정을 제시하는 것이 아니라 우회적인 방법을 통해서 명제가 타당함을 보이는 방법이다. 

 

예시1: a^b이 유리수가 되는 무리수 a,b가 존재함을 증명하시오. 

비구성적 존재증명법을 사용하여 \(a^b\)이 유리수가 되는 무리수 \(a, b\)의 존재를 증명하는 방법은 다음과 같다. 가장 대표적인 예로 무리수 \(a = \sqrt{2}\)를 사용할 수 있다. 우선 \(a = \sqrt{2}\)이고 \(b = \log_{\sqrt{2}} 2\)인 경우를 생각해 보자. 여기서 \(b\)는 \(a^b = (\sqrt{2})^{\log_{\sqrt{2}} 2} = 2\)이므로 \(a^b\)는 유리수 2가 된다.

하지만 이 경우 \(b = \log_{\sqrt{2}} 2 = 2\)는 명백히 유리수이므로 \(a\)와 \(b\) 둘 다 무리수인 경우를 추가로 고려해야 한다. 이를 위해 우리는 무리수 \(a\)와 \(b\)에 대한 다른 접근을 사용할 수 있다. 예를 들어, \(a = \sqrt{2}\)이고 \(b = 2\)라고 가정했을 때 \(a^b = (\sqrt{2})^2 = 2\)가 유리수가 된다. 그러나 이 예에서도 \(b\)는 유리수이다.

따라서 \(a = \sqrt{2}\)와 \(b = \log_{\sqrt{2}} 3\)의 조합을 고려할 수 있다. 이 경우 \(b\)는 무리수이며, \(a^b = (\sqrt{2})^{\log_{\sqrt{2}} 3} = 3\)로, 여기서 3은 유리수이다. 이러한 접근은 \(a\)와 \(b\)가 무리수임에도 불구하고 \(a^b\)가 유리수가 될 수 있음을 보여주는 예시로, 비구성적 증명법의 효과적인 사용을 보여준다. 이 예시는 직접적인 구성을 통하지 않고도 무리수의 특정 거듭제곱이 유리수가 될 수 있음을 증명하는 우회적인 방법을 사용하고 있다.

 

 

 

다양한 증명방법

 

(1) 전수증명법

명제에서 유도될 수 있는 경우의 수가 적을 때 일일이 모든 경우의 수를 조사하는 방법을 전수증명법이라고 한다. 

 

예시: 6 이하의 자연수 n에 대하여 (n+2)^2 >=2^n임을 증명하시오. 

 

전수증명법은 모든 가능한 경우를 조사하여 명제의 참을 증명하는 방법이다. 주어진 예시에서는 \( n \)이 6 이하의 자연수일 때, \( (n+2)^2 \geq 2^n \)임을 증명해야 한다.

\( n \)이 1부터 6까지의 각 값을 대입하여 \( (n+2)^2 \)와 \( 2^n \)을 계산하고, 각 경우에 대해 부등식이 성립하는지 확인한다.

1. \( n=1 \)일 때, \( (1+2)^2 = 9 \)과 \( 2^1 = 2 \), \( 9 \geq 2 \)
2. \( n=2 \)일 때, \( (2+2)^2 = 16 \)과 \( 2^2 = 4 \), \( 16 \geq 4 \)
3. \( n=3 \)일 때, \( (3+2)^2 = 25 \)과 \( 2^3 = 8 \), \( 25 \geq 8 \)
4. \( n=4 \)일 때, \( (4+2)^2 = 36 \)과 \( 2^4 = 16 \), \( 36 \geq 16 \)
5. \( n=5 \)일 때, \( (5+2)^2 = 49 \)과 \( 2^5 = 32 \), \( 49 \geq 32 \)
6. \( n=6 \)일 때, \( (6+2)^2 = 64 \)과 \( 2^6 = 64 \), \( 64 \geq 64 \)

 

 

 

(2) 조합적 증명법

 

조합적 증명법이란 두 집합의 원소의 개수가 같다는 것을 증명할 때 사용되는 증명법이다. 증명방법으로는 전단증명과 중복산정이 있다. 

 

전단증명은 원소가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후, 두 집합이 일대일 관계임을 보여 n=m임을 증명한다. 

 

중복산정은 동일한 집합의 원소를 두 가지 방법으로 센 다음, 그 결과가 각각 n과 m이라면 n = m임을 증명한다. 

 

 

예시: n, k가 양의 정수이고, k<=n일 때 아래 수식을 조합적 증명법을 이용하여 증명하시오. 

 

C(n+1, k) = C(n,k) + C(n, k-1) 

 

 

조합적 증명법을 사용하여 주어진 수식 \( C(n+1, k) = C(n, k) + C(n, k-1) \)을 증명하려면, 이항계수의 조합적 의미를 활용한다. 이항계수 \( C(n, k) \)는 집합에서 \( k \)개의 원소를 선택하는 방법의 수를 나타낸다.

먼저, \( n+1 \)개의 원소를 가진 집합을 생각하고, 여기서 \( k \)개의 원소를 선택하는 경우의 수를 \( C(n+1, k) \)로 표현한다. 이 선택을 두 가지 방법으로 나눌 수 있다: 특정 원소 \( x \)를 포함하는 경우와 포함하지 않는 경우.

1. **원소 \( x \)를 포함하는 경우:** 나머지 \( n \)개의 원소 중에서 \( k-1 \)개를 더 선택해야 한다. 이 경우의 수는 \( C(n, k-1) \)이다.
2. **원소 \( x \)를 포함하지 않는 경우:** \( n \)개의 원소 중에서 \( k \)개를 선택해야 하며, 이 경우의 수는 \( C(n, k) \)이다.

따라서, \( x \)를 포함하는 경우와 포함하지 않는 경우를 합하면 전체 \( k \)개의 원소를 선택하는 방법의 수는 \( C(n, k) + C(n, k-1) \)이 된다.

이로써 \( C(n+1, k) \)의 값이 \( C(n, k) + C(n, k-1) \)과 동일함을 조합적 증명법을 통해 확인할 수 있다. 이는 중복산정의 원리를 이용한 것으로, 같은 결과를 다른 방법으로 세어 일치함을 보여주는 방법이다. 이 증명은 이항정리의 재귀적 관계를 이해하는 데 중요한 기초를 제공한다.

 

 

(3) 컴퓨터를 이용한 증명 

컴퓨터를 이용한 증명은 수학적 증명과정 중에 컴퓨터를 이용한 계산이 포함되는 경우를 의미한다. 주로 사람이 직접 계산하기 힘들 정도로 많은 계산식이 포함될 경우이다. 대표적인 예시가 4색정리이다. 

 

 

4색 정리

평면을 유한개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다. 

 

만약 4색정리가 거짓이면, 다섯 가지 색이 필요한 구획들로 구성된 지도가 적어도 하나 존재할 것이다. 그런 반례가 존재하지 않다는 것을 보이기 위해 당므과 같은 가정을 한다. 

 

1) 지도에서 나라들이 배열되는 경우의 수는 무한히 많지만, 그 형태를 단순화시키면 유한개의 기본 그래프가 조합된 형태가 된다.

2) 기본 그래프가 4색문제의 반례가 되지 않고, 나머지 부분을 네 가지 색으로 칠할 수 있으면 전체 그래프는 네 가지 색으로 칠할 수 있다. 

 

지도에서 나라가 배열되는 경우는 무한히 많지만, 결국 1,936개의 단순한 형태로 줄일 수 있음을 보이고 제대로 단순화되었는지 컴퓨터로 검사하는 방법을 썼다. 

 

 

 

---

 

참고자료: 이산수학 | 손진곤 (지은이) 한국방송통신대학교출판문화원