증명법

 4장

증명법

1. 증명의 방법론

• 증명의 필요성

• 어떤 회사의 마케팅부서 직원이 신제품에 대한 기획안을 작성했 다면, 회사가 그 기획안을 채택할 수 있도록 자신의 아이디어의 우 수성을 입증해야 함

• 제품 개발의 용이성, 완제품의 판로, 시장 장악력, 경쟁사 제 품과 비교했을 때의 우수성 등

• 어떤 프로그래머가 자신이 개발한 프로그램이 이전에 다른 사람 이 개발한 프로그램보다 성능이 우수하다고 주장했다면, 이것을 입증해야 함

• 프로그램의 처리 속도, 유연성, 유지보수성 등 좋은 프로그 램이 될 수 있는 요건들을 하나하나 검증해야 함

• 공학적 접근에서 스케치된 아이디어를 구체적인 방법론으로 표 현하고, 누구나 공감할 수 있도록 객관적인 증명 방법을 이용하여 입증해야 함

• 즉, 객관적인 증명 방법이 필요 증명의 필요성

1. 증명의 방법론

• 공리(axiom)

• 별도의 증명 없이 ‘참’으로 인용되는 명제

• 예 1 : ‘어떤 자연수 n에 대하여 n+1이 반드시 존재한다.’

• 예 2 : ‘두 점이 주어졌으면 두 점을 잇는 직선을 그을 수 있다.’

• 정의(definition)

• 논의의 대상을 보편화하기 위해 사용하는 용어 또는 기호의 의미 를 확실하게 규정한 문장이나 식

• 예 : ‘한 내각의 크기가 직각인 삼각형을 직각삼각형이라고 한다.’

• 정리(theorem)

• 공리와 정의를 통해 ‘참’으로 확인된 명제

• 예 1 : 피타고라스의 정리⇒’직각삼각형은 (빗변의 길이)²=(밑변 의 길이)²+(높이)²이다.’

• 예 2 : ‘실수는 사직연산에 대해 닫혀있다.’

• 증명(proof)

• 하나의 명제가 ‘참’임을 확인 또는 입증하는 과정 증명에 대한 용어

2. 여러 가지 증명 방법

• 직접증명법(direct proof)

• 주어진 명제를 ‘참’이라고 가정하고, 정리와 공리를 이용해서 명 제가 ‘참’이 됨을 증명하는 방법

• 직접증명법 예 1

• 두 홀수의 곱이 홀수임을 증명하라.

• p : ‘두 수 m, n은 홀수이다.’ q : ‘m과 n의 곱은 홀수이다.’

• p→q : ‘두 홀수 m, n의 곱은 홀수이다.’

• <증명>

• 두 정수 k와 j이 있을 때, 홀수 m과 n은 각각 m=2k+1, n=2j+1로 표현할 수 있다. m과 n의 곱

mⅹn=(2k+1)ⅹ(2j+1)=4kj+2k+2j+1=2(2kj+k+j)+1가 된다.

• k와 j는 정수이므로 2kj+k+j 또한 정수가 되어 2(2kj+k+j)은 반드시 짝수가 되고, 2(2kj+k+j)+1은 반드시 홀수가 된다.

• ∴ p→q 즉, ‘두 홀수 m, n의 곱은 홀수이다.’라는 명제는 참 이 된다.

직접증명법

2. 여러 가지 증명 방법

• 직접증명법 예 2

• 두 유리수의 합이 유리수임을 증명하라.

• p : ‘두 수 m, n은 유리수이다.’ q : ‘m과 n의 합은 유리수이다.’

• p→q : ‘유리수인 m, n의 합은 유리수이다.’

• <증명>

• a, b, c, d가 정수(단, c≠0, d≠0)라고 했을 때 m과 n은 유 리수이므로 각각 m=a/c, n=b/d로 표현할 수 있다. m과 n의 합 m+n=(a/c)+(b/d)=(ad/cd)+(bc/cd)=(ad+bc)/cd가 된다.

c≠0, d≠0이므로, cd≠0이 되고, 정수는 곱셈과 덧셈에 닫혀 있으므로 (ad+bc)와 cd는 모두 정수이다.

• 유리수는 (정수/정수)로 표현되는데 (ad+bc)/cd는 (정수/

정수)가 되어 유리수가 된다.

• ∴ p→q 즉, ‘유리수인 m, n의 합은 유리수이다.’라는 명제 는 참이 된다.

• 직접증명법 외의 증명법

• 직접증명법을 제외한 것은 간접증명법이라 말하고, 직접적으로 증명이 안 되는 것을 우회적으로 증명하는 기법을 사용함

2. 여러 가지 증명 방법

• 연역법과 귀납법

• 연역법(deduction)은 주어진 사실들과 공리들에 입각하여 추론 을 통해 새로운 사실을 도출해내는 과정

• 통상 실증을 통해 증명하는데, 하고 싶은 주장을 먼저 하고, 사례나 근거를 나중에 제시한다는 측면에서 두괄식이라고 생 각할 수 있음

• 연역법의 예 : ‘모든 사람은 죽는다. 소크라테스는 사람이다.

그러므로 소크라테스는 죽는다.’

• 귀납법(induction)은 관찰과 실험에 기반한 가설을 귀납 추론을 통하여 일반적인 규칙을 입증하는 과정

• 통상 해석을 통해 증명하는데, 주로 경험적이라서 구체적인 자료 또는 통계를 바탕으로 현실에 근거한 결론을 내리기 때 문에 미괄식이라고 생각할 수 있음

• 귀납법 예 : ‘김유신은 죽었다. 이순신은 죽었다. 그들은 모 두 사람이다. 그러므로 모든 사람은 죽는다.’

수학적 귀납법

2. 여러 가지 증명 방법

• 수학적 귀납법 개요

• 수학적 귀납법(mathematical induction)은 자연수 n에 대하여 p₁, p₂, …, p_n이 사실이라고 할 때, p_n+1도 사실임을 증명하기 위해 다 음과 같은 3단계를 거치는 방법

• 기초단계(basis) : n의 초기값(주로 1)일 때 성립함을 보인다.

• 귀납가정(inductive assumption) : n=k일 때 성립한다고 가 정한다.

• 귀납단계(inductive step) : n=k+1일 때 성립함을 보인다.

• 도미노 이론

•첫 번째 패가 쓰러지면 두 번째 패가 쓰러지고, 같은 방법으로 n번째 패가 쓰러지면 n+1번째 패가 쓰러질 것이라는 원리

2. 여러 가지 증명 방법

• 수학적 귀납법 예 1

• 증명하고자 하는 명제

• ‘모든 자연수 n에 대하여 1+2+…+n=n(n+1)/2이 성립한다.’

• 증명

• (기초단계) 만일 n=1이면 등호 좌변과 우변이 모두 1이므로 이 식은 n=1일 때 성립한다.

• (귀납가정) n=k일 때 이 공식이 성립한다고 가정하므로 1+2+ … +k=k(k+1)/2이다.

• (귀납단계) n=k+1일 때도 성립함을 보이기 위해 1+2+ … +k=k(k+1)/2의 양변에 (k+1)을 더해 보면 1+2+ … +k+(k+1)=(k(k+1)/2)+(k+1)이 되고

이 식을 계산하면 다음과 같이 된다.

• 따라서, n=k+1일 때도 위의 명제가 ‘참’임을 알 수 있다.

2. 여러 가지 증명 방법

• 수학적 귀납법 예 2

• 증명하고자 하는 명제

• ‘n≥1일 때, n!≥2^n-1가 성립한다.’

• 증명

• (기초단계) n≥1이라는 조건이 있으므로 n의 초기값은 1이 다. n!≥2^n-1은 1!=1≥2^1-1=0=1이 되므로 n=1일 때 이 식은 성 립한다.

• (귀납가정) n=k일 때 성립한다고 가정하므로 k!≥2^k-1이 성 립한다.

• (귀납단계) n=k+1일 때도 성립함을 보이기 위해 이 식에 n 대신 k+1을 넣으면 좌변은 (k+1)!이 되는데 사실 이것은 k!(k+1)과 같다. 그런데 k!(k+1)은 귀납가정의 양변에 (k+1) 을 곱한 것과 같은 효과이므로 k!(k+1) ≥2^k-1(k+1)이 되고, n≥1이므로 k+1이 가질 수 있는 최소값은 2이므로 식 우변의 k+1 대신 2를 대입하면 2^(k+1)-1이 된다. 이를 통해 (k+1)!

≥2^(k+1)-1이 성립한다.

• 따라서, n=k+1일 때도 위의 명제가 ‘참’임을 알 수 있다.

2. 여러 가지 증명 방법

• 모순증명법(proof by contradiction)

• 전통적인 방식으로 증명하기 어려울 때, 주어진 명제의 전제는 그대로 둔 상태에서 결론을 부정함으로써 그 결론이 모순되었음을 보이고, 모순된 이유는 올바른 결론을 부정했기 때문이라고 간주 하여 결국 원래의 명제가 옳음을 증명하는 방법

• 귀류법이라고도 함

• 모순증명법 예

• 증명하고자 하는 명제

• ‘a, b가 실수일 때, a+b-2>0이면 a>1 또는 b>1이다.’

• 증명

• 먼저, 결론을 부정한다. 즉, a≤1이고, b ≤1이라고 본다. 그 러면, a-1≤0, b-1≤0이 되므로 a+b-2=(a-1)+(b-1)이 되어 당연히 (a-1)+(b-1)≤0이 된다. 즉, a+b-2 ≤0이라는 결론이 나오는데 이건 이 명제의 전제인 a+b-2>0에 정면으로 위배 된다. 그 이유는 a>1 또는 b>1인 것을 억지로 a≤1이고, b

≤1라고 했기 때문이다. 따라서, 위의 명제는 ‘참’이다.

간접증명법

2. 여러 가지 증명 방법

• 대우증명법(proof by contraposition)

• 명제와 그 명제의 대우는 논리적으로 동치라는 성질을 이용하여 명제를 직접 증명하지 않고 명제의 대우를 증명함으로써 결론적 으로는 명제도 ‘참’임을 증명하는 방법

• 대우증명법 예

• 증명하고자 하는 명제

• ‘모든 정수 n에 대해 n²이 짝수이면 n도 짝수이다.’

• 증명

• 이 명제의 대우는 ‘모든 정수 n에 대해 n이 홀수이면 n²도 홀수이다.’이므로 이 대우명제를 증명한다.

• n은 홀수라고 했으므로 임의의 정수 k에 대하여 n=2k+1로 표현할 수 있다. 양변을 제곱하면

n²=(2k+1)²=4k²+4k+1=2(2k²+2k)+1이 된다. 정수는 덧셈과 곱셈에 닫혀있으므로 2k²+2는 정수가 되고, 정수에 2를 곱하 면 언제나 짝수가 되며 짝수에 1을 더하면 언제나 홀수가 된 다. 따라서, n²은 홀수로, 증명하고자 했던 명제의 대우가 ‘참’

이므로 원래 증명하고자 했던 명제도 ‘참’이다.

2. 여러 가지 증명 방법

• 존재증명법(existence proof)

• 주어진 명제가 ‘참’ 또는 ‘거짓’인지 알기 어려운 경우에 사용하 는 방법으로 ‘참’이 되는 예를 하나 찾아서 ‘참’임을 보이는 방법

• 존재증명법 예 1

• 증명하고자 하는 명제

• ‘n이 어떤 소수라면 n+4도 소수이다.’

• 증명

• 소수는 1을 제외한 어떤 약수도 갖지 않는 수를 말한다. 예 를 들어, 2, 3, 5, 7, 11, 13, …이다. 여기서 각 소수에 4를 더하면 (2+4=6), (3+4=7), (5+4=9), (7+4=11), (11+4=15), (13+4=17)이다. n이 소수일 때 n+4도 소수인 경우가 수 차 례 발생한다. 따라서, 위 명제는 ‘참’이 된다.

• 존재증명법 예 2

• 증명하고자 하는 명제

• ‘어떤 실수 x, y에 대해 x>y이면 x²>y²이다.’

• 증명

• x=2, y=-1일 x²=4, y²=1이므로 위 명제는 ‘참’이 된다.

2. 여러 가지 증명 방법

• 반례증명법(proof by counter example)

• 주어진 명제가 ‘참’ 또는 ‘거짓’인지 알기 어려운 경우에 사용하 는 방법으로 ‘거짓’이 되는 예를 하나 찾아서 ‘거짓’임을 보이는 방법

• 반례(counter example)는 ‘거짓’인 예를 말함

• 그런데 증명은 ‘참’임을 입증하는 과정인데 반례증명법은 ‘거짓’

을 확인하는 방법이기 때문에 엄밀한 의미에서는 증명법이라고 말할 수는 없음

• 반례증명법 예

• 증명하고자 하는 명제

• ‘모든 실수 a에 대해 (a+1)²≥a²가 성립한다.’

• 증명

• 모든 양의 실수에서는 위 명제가 성립하지만, 음의 실수에 대해서는 성립하지 않을 가능성이 있다. 즉, a=-1인 경우, (a+1)² 은 0이고, a²은 1이므로 성립하지 않는다. 따라서, 거 짓이 되는 경우가 발생하므로 위 명제는 ‘참’이 되지는 않는 다.

2. 여러 가지 증명 방법

• 필요충분조건 증명법(if and only if proof)

• 주어진 명제와 동치인 명제를 통해 증명하는 방법인데, p↔q를 증명하기 위해 (p→q)∧(q→p)를 증명하는 방법

• 필요충분조건 증명법 예

• 증명하고자 하는 명제

• ‘모든 정수 n에 대해 n-1이 짝수임과 n이 홀수임은 동치다.’

• 증명

• 위 명제를 ‘n-1이 짝수이면 n이 홀수이다.’와 ‘n이 홀수이 면 n-1이 짝수이다.’로 나눠서 증명한다.

• <1> ‘n-1이 짝수이면 n이 홀수이다.’

만일, n-1이 짝수이면 어떤 정수 k에 대하여 n-1=2k로 표현할 수 있고, n=2k+1이 된다. 2k는 항상 짝수이므로 2k+1은 항상 홀수가 된다. 따라서 ‘참’이다.

• <2> ‘n이 홀수이면 n-1이 짝수이다.’

만일 n이 홀수이면 어떤 정수 k에 대하여 n=2k+1로 표현할 수 있고, n-1=2k가 된다. 2k는 항상 짝수이므로 ‘참’이다.

• 두 조건 모두 ‘참’이므로 위 명제는 ‘참’이 된다.

3. 프로그램의 입증

• 프로그램 입증

• 프로그램을 입증한다는 것은 프로그램이 정확하게 실행될 것임 을 확인하는 것으로 다음과 같은 의미를 담고 있음

• 문법적 오류(syntax error)가 없음

• 논리적 오류(logical error)가 없음

• 일정 시간 수행 후 정상 종료

• 돌발 상황에서 중단되지 않음

• 결과의 정확성

• 프로그램이 정확하게 만들어져 있음을 테스트하는 툴(tool)들을 이용함

• 프로그램의 기본 구조

• 순서문(sequential statement)

• 조건문(conditional statement)

• 반복문(repeated statement)

• 무조건적 이동문(unconditional transfer statement) 프로그램의 입증

3. 프로그램의 입증

• 프로그램의 정확성 평가 예 1

• 다음은 1부터 n까지의 정수 값을 합하는 프로그램임

void Sum_n() {

int i, n, sum=0;

scanf(“%d”, &n);

for(i=1; i≤n; i++) sum+=i;

printf(“%d, %d”, n, sum);

}

· n : 키보드를 통해 입력하는 값으로 1부터 n까지 합 중에서 마지막 값(1부터 5까지라면 5를 의미)을 저장 하는 변수

· sum : 차근차근 더해서 계속 누적되는 결과값을 저 장하는 변수

· i : 동일한 작업을 반복하기 위해 반복 회수를 카운트 하면서 저장하는 변수

· for() : 동일한 작업을 반복해주는 명령

· scanf 명령에 의해 n에 5를 입력 / n에 5를 입력한다는 것은 1부터 5까지의 합을 구하겠다는 의 미/

· 반복문 for 명령에 의해 i=1일 때, sum=0+1=1

· i=2일 때, sum=1+2=3

· i=3일 때, sum=3+3=6

· i=4일 때, sum=6+4=10

· i=5일 때, sum=10+5=15

· i=6이 되면 i≤n, 즉 i의 값이 n의 값 5보다 작거나 같은 동안만 반복하라는 조건에 위배되므로 반복을 종료해야 함

3. 프로그램의 입증

• 프로그램의 정확성 평가 예 2(다음 장 그림까지 이어짐)

• 다음은 n개의 양의 정수 중에서 가장 작은 정수를 찾는 프로그램임

Find_Min(int array[], int MIN) {

int i ;

MIN=array[0];

for(i=1; i<n; i++)

if(MIN>array[i]) MIN=array[i];

return(MIN);

}

· array[] : 양의 정수들이 모여 있는 배열

· MIN : array[]에서 가장 작은 값을 저장하는 변수

· i : 동일한 작업을 반복하기 위해 반복 회수를 카운트 하면서 저장하는 변수

· for() : 동일한 작업을 반복해주는 명령

· n : 배열 array에 저장되어 있는 데이터의 수를 나타 내주는 변수

· Find_Min이라는 함수를 부르면서 array라는 이름의 배열에 데이터를 담아줌

· 배열 array의 제일 앞(통상 0번째라고 말함)에 저장된 데이터를 잠정적으로 제일 작은 정수 라고 가정하고 MIN이라는 변수에 저장함

· 반복문 for 명령에 의해 i=1일 때, 배열 array의 i번째(1번째) 데이터와 MIN의 크기를 비교하여 더 작은 데이터를 변수 MIN에 저장함

· i=2일 때, 배열 array의 i번째(2번째) 데이터와 MIN의 크기를 비교하여 더 작은 데이터를 변수 MIN에 저장함

· 이와 같은 작업을 배열 array의 마지막 데이터까지 MIN과 비교하는 작업을 반복함

· 마지막에 MIN에 저장되어 있는 데이터가 가장 작은 데이터가 되고, return 명령에 의해

3. 프로그램의 입증

16 10 7 3 15

16 10 7 3 15

16 10 7 3 15

16 10 7 3 15

16 10 7 3 15

1단계

2단계

3단계

4단계

5단계

MIN=16

MIN=10

MIN=7

MIN=3

MIN=3

array[0] array[1] array[2] array[3] array[4]