[이산수학] 증명론

증명의 일반적인 방법론을 고찰하고 여러 가지 증명법을 살펴보면서 주어진 문제를 해결하기 위한 단계적 접근 방법을 제시한다

증명의 방법론

증명

논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도해내는 추론의 한 방법

어떠한 명제나 논증이 적절하고 타당한지 입증하는 작업

증명의 단계적 접근 방법

1. 아이디어 스케치

• 문제 해결의 핵심적인 실마리를 찾아내 기술
• 문제를 해결할 수 있는 방법론을 구상하게 되며 개략적인 아이디어 스케치

1. 구체적인 방법론 제시

• 아이디어를 묶어서 구체적인 블록 다이어그램 등으로 표현
• 프로그래밍의 경우 유사 코드 단계까지 구체화

1. 엄밀한 입증이나 증명

• 결론을 객관적인 증명 방법을 통해 누구나 공감할 수 있게 증명함

여러 가지 증명 방법

수학이나 공학에서의 증명 문제는 p→q와 같은 논리 함축을 증명

논리 함축 p→q가 참이 되기 위해서는 p, q가 모두 참이거나 q에 관계없이 p가 거짓임

#1 연역법

주어진 사실들과 공리들에 입각하여 추론을 통하여 새로운 사실을 도출하는 것

#2 귀납법

관찰과 실험에 기반한 가설을 귀납 추론을 통하여 일반적인 규칙을 입증하는 것

수학적 귀납법

명제 p1, p2, p3, p4, p5, … p(n)이 사실이라고 할 때, p(n+1)의 경우에도 성립한다

n이 1인 경우에 성립하는 것을 보이고, 모든 양의 정수 n에 대해 성립한다고 가정하면 n+1 경우에도 성립하는 것을 보여주면 됨

기초 단계 → 귀납 과정 → 귀납 단계의 순서로 증명

모순 증명법

귀류법은 기존의 전통적인 방법으로는 주어진 문제를 쉽게 증명할 수 없는 경우에 유용

주어진 문제의 명제를 부정해놓고 논리를 전개

모순됨을 보임으로써 본래의 명제가 사실임을 증명하는 방법

가정은 그대로 두고 결론을 부정 ⇒ 모순 유도 ⇒ p→q를 증명

직접 증명법

통상 주어진 유용한 정보로부터 추론을 통하여 목적하는 결론에 도달할 수 있도록 유도하는 증명법

명제 p→q의 직접 증명은 논리적으로 p의 진리 값이 참일 때 q도 참임을 보이는 증명 방법

대우 증명법

p→q와 ~q→~p가 대우 관계로서 논리적 동치가 됨을 이용하여 ~q→~p가 참인 것을 증명

p→q가 참이 되는 것을 보여주는 증명

존재 증명법

p(x)를 x라는 변수를 가지는 명제

p(x)가 참인 x가 적어도 하나가 존재한다는 것을 보이는 증명

반례 증명법

어떤 명제가 참 또는 거짓임을 입증하기가 어려운 경우

주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로써 비교적 쉽게 증명 가능

필요충분조건 증명법

주어진 명제의 동치를 통하여 증명

p↔q를 보이기 위해 p→q, q→p를 증명

프로그램의 입증

엄밀한 정확성이 요구되는 컴퓨터 프로그램을 입증하는 것은 매우 중요

프로그램의 입증은 주로 제어 구조에서 4가지 문장 구조를 입증함

1. 순서문
2. 조건문
3. 반복문
4. 무조건적 이동문

위의 증명법을 배움으로써 수학, 자연과학, 여러 가지 공학에 폭넓게 활용되며 학문적 기반을 이루는 기초를 세울 수 있음