[이산수학🔗] 증명법 (4장)

포스팅에 참고하는 교재 : 4차 산업혁명 시대의 이산수학 개정판 (생능출판)

 

4.1 증명의 방법론

1) 증명(proof)

- 논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도해내는 추론의 한 방법으로서, 어떠한 명제나 논증이 적절하고 타당한지를 입증하는 작업
- 공학이나 컴퓨터 관련 학문에 있어서 주어진 문제를 해결하기 위해서는 증명의 단계적 접근 방식이 매우 효과적임.
 

2) 증명의 단계적 접근 방법

①아이디어 스케치 단계

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

②구체적인 방법론 제시 단계

• 아이디어를 묶어서 구체적인 블록 다이어그램(block diagram) 등으로 표현
• 프로그래밍의 경우 유사 코드(pseudo code) 단계까지 구체회하는 단계

③엄밀한 입증이나 증명의 단계 : 자기가 내린 결론을 객관적인 증명 방법을 통해 누구나 공감할 수 있게 증명함.
 

4.2 여려 가지 증명 방법

1) 개요

- 수학이나 공학에서의 증명 문제는 p→q와 같은 논리 함축을 증명함.
- 증명 방법은 직접 증명법과 간접 증명법 그리고 기타 증명법으로 구분한다.

• 직접 증명법 :  p→q를 직접 증명
• 간접 증명법 : 논리적 동치를 이용하거나 다른 특수한 방법으로 증명한다. 

- 주어진 문제 유형에 따라 다양한 방법으로 접근하는 것이 효율적이다. 
 
* 수학이나 공학에서 새로운 결과를 얻는 중요한 2가지 방법론
- 연역법 (deduction)
: 주어진 사실(facts)들과 공리(axioms)들에 입각하여 추론(inference)을 통하여 새로운 사실을 도출하는 것
- 귀납법 (induection) : 관찰과 실험에 기반한 가설을 귀납 추론을 통하여 일반적인 규칙을 입증하는 것
 

2) 증명 방법

(1) 수학적 귀납법(Mathematical Induction)

- 명제 p₁, p₂, p₃, ... , p_n이 사실이라고 할 때 p_n+1의 경우에도 성립함을 보이면 된다. 

- 먼저 n이 1인 경우에 성립하는 것을 보이고, 모든 양의 정수 n에 대해 성립한다고 가정하면 n+1의 경우에도 성립함을 보이면 된다. 

• 기초 단계(basic) : 출발점이 되는 n의 값
• 귀납 가정(inductive assumption) : p₁, p₂, p₃, ... , p_n이 성립한다고 가정하면
• 귀납 단계(inductive step) : p_n+1의 경우에도 성립한다. 

- 수학적 귀납법은 논리식을 증명하는 데에도 이용한다.

수학적 귀납법 예시

 
(2) 모순 증명법(Proof by Contradiction)
- 모순 증명법(==귀류법)은 기존의 전통적인 방법으로는 주어진 문제를 쉽게 증명할 수 없는 경우에 매우 유용함.
- 주어진 문제의 명제를 부정해놓고 논리를 전개함. 그 결과가 모순됨을 보임으로써 본래의 명제가 사실임을 증명하는 방법
- p→q가 참인 것과 p∧(∼q)가 거짓인 것은 동치이므로 p∧(∼q)가 참이라고 가정하고 그 결과가 모순됨을 보임.

모순 증명법 예시

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

직접 증명법 예시

 
(4) 대우 증명법(Contrapositive Proof)
-  p→q와 ∼q→∼p가 대우 관계로서는 논리적 동치가 됨을 이용해서 ∼q→∼p가 참임을 증명한다. 

대우 증명법 예시

 
(5) 존재 증명법 (Existence Proof)
- p(x)가 x라는 변수를 갖는 명제라고 한다면, p(x)가 참인 x가 적어도 하나 존재한다는 것을 보이는 증명 방법
- ∃ x such that p(x)를 보이는 것이다. 

존재 증명법 예시

 
(6) 반례 증명법 (Proof by Counter-example)
- 어떤 명제가 참 또는 거짓임을입증하기 어려운 경우에 효과적인 증명 방법
- 주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로써 비교적 쉽게 증명할 수 있는 방법이다. 
- ∀x p(x)이 거짓임을 보이기 위해 ∼[∃x p(x)]와 동치인 ∃x ∼(p(x))에서 p(x)를 만족하지 않는 x가 적어도 하나 존재함을 보임 -> 이때 x를 반례라고 한다.

반례 증명법 예시

 
(7) 필요충분조건 증명법 (if and only if proof)
- 주어진 명제의 동치를 통하여 증명함
- 'p if and only if q'를 증명하기 위해 '만약 p이면 q이다'와 '만약 q이면 p이다'의 두 가지를 증명함.

 

4.3 프로그램의 입증

1) 개요

- 증명 못지 않게 엄밀한 정확성이 요구되는 컴퓨터 프로그램을 입증하는 것 또한 매우 중요하다. 
- 정확한 프로그램이 되기 위해서는 구문 오류(syntax error)를 포함하지 않아야 한다.
- 예상치 못하게 끝나서도 안 되며, 주어진 입력에 대해 정확한 결과를 도출해야 함.
 

2) 프로그램의 입증 

; 주로 제어 구조(control structure)에서 4가지의 문장 구조를 입증함.

• 순서문(Sequential statements)
• 조건문(Conditional statements)
• 반복문(Repeated statements)
• 무조건적 이동문(Unconditional transfer statements)

 

4.4 증명법의 응용과 4차 산업혁명과의 관계

• 증명과 입증은 다양한 분야에서 응용된다. 
• 무인자동차 또는 자율주행차에는 시스템에 대한 엄밀한 증명과 소프트웨어적인 입증이 필수적이다.