[이산수학] 증명법

증명의 방법론

증명이란

논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도해내는 추론의 한 방법으로서 어떠한 명제나 논증이 적절하고 타당한지를 입증하는 작업이다.

 

증명은 문제를 단계적인 접근 방법을 사용하면 매우 효과적으로 해결할 수 있다. 

증명의 단계적 접근 방법

1. 아이디어 스케치 단계 : 문제를 해결할 수 있는 방법론 등의 아이디어를 개략적으로 스케치
2. 구체적 방법론 제시 단계 : 아이디어를 묶어 구체적인 블록 다이어그램 또는 유사 코드 단계로 구체화하는 작업
3. 엄밀한 입증 또는 증명 단계 : 자신이 내린 결론을 객관적인 증명 방법을 통해 증명하는 작업

증명법의 종류

증명 방법에는 직접 증명, 간접 증명 그리고 기타 증명으로 크게 3가지로 나눌 수 있다. 

• 직접 증명 : p → q를 직접 증명하는 것
• 간접 증명 : 논리적 동치를 이용하거나 다른 특수한 방법으로 증명하는 것
  • 가정된 명제로부터 결론을 직접 유도해내기 쉽지 않은 경우 사용

수학이나 공학에서 새로운 결과를 얻는 2가지 방법론이 존재한다.

• 연역법 : 주어진 사실들과 공리들에 입각하여 추론을 통하여 새로운 사실을 도출하는 것
• 귀납법 : 관찰과 실험에 기반한 가설을 귀납 추론을 통하여 일반적인 규칙을 입증하는 것

수학적 귀납법

프로그래밍 알고리즘에 대해서 많이 사용되는 증명법으로 명제 p1, p2, …pn이 사실이라고 할 때 pn+1의 경우에도 성립한다는 것을 보이는 방법이다. 기초 - 귀납 가정- 귀납 단계를 통해 증명이 이루어진다.

 

• 기초 단계 : 출발점이 되는 n의 값을 제시 ( 예를 들어 1)
• 귀납 가정 단계 : p1, p2, …pn이 참인 것을 가정
• 귀납 단계 : 귀납 가정에 따라 pn+1의 경우도 성립됨을 보이는 단계

모순 증명법

모순 증명법은 귀류법이라고도 하며 주어진 문제의 명제를 일단 부정해 놓고 논리를 전개하여 그것이 모순됨을 보임으로써 본래의 명제가 사실임으 증명하는 방법이다.

 

p→q가 참인 것과 p →∧(~q)가 거짓임은 동치임으로 p →∧(~q)가 참이라고 하고 모순이 유도되면 원래의 명제가 참임을 증명하는 것이다.

모순 증명법

 

직접 증명법

통상 주어진 유용한 정보로부터 추론을 통하여 목적하는 결론에 도달할 수 있도록 유도하는 증명법으로 명제 p→q의 직접 증명은 논리적으로 p의 진리값이 참일 때 q도 참임을 보이는 증명 방법이다.

명제 6x + 9y = 7 이라면 x 또는 y가 정수가 아님을 증명

7/3은 정수가 아니므로 2x+3y도 정수가 될 수 없다. 따라서 x와 y는 정수가 아니다.

대우 증명법

대우 관계에서 논리적 동치가 됨을 이용하여 명제가 참이 되는 것을 보여주는 증명 방법이다.

대우 증명법

x가 짝수이면 x는 2이거나 소수가 아님을 증명
p : x가 짝수이다.
q : x = 2 이거나 소수가 아니다.

p→q를 증명하기 위해 대우(~q→~p)를 이용한다.
~q : x는 2가 아니고 소수이다.
~p : x는 홀수이다.

x가 2가 아닌 소수는 홀수 밖에 없으므로 원래의 명제는 성립한다.

존재 증명법

P(x)를 x라는 변수를 가지는 명제라고 할 때, P(x)가 참인 x가 적어도 하나가 존재한다는 것을 보이는 증명 방법이다.

존재 증명법

반례 증명법

어떤 명제가 참 또는 거짓임을 입증하기 어려운 경우 사용하는 방법으로 주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로써 비교적 쉽게 증명할 수 있는 방법이다.

반례 증명법

필요충분조건 증명법

주어진 명제의 동치를 통하여 증명하는 방식이다.

필요충분조건 증명법