6. 여러 가지 증명 방법(3-2)
1) 직접 증명법 (direct proof)
주어진 유용한 정보로부터 추론을 통하여 목적하는 결론에 도달할 수 있도록 유도하는 증명법
을 직접 증명법(direct proof)이라고 하며, 명제 p.q의 직접 증명은 논리적으로 p의 진리값이
참(true)일 때 q도 참임을 보이는 증명방법이다.
명제의 함축 p→q 가 참이 됨을 증명하는 방법
명제 p 를 참이라고 가정하고, 여러 가지 정리와 식을 이용하여 명제 q 또한 참이 됨을 증명
===============================================================
2) 간접 증명법(indirect proof)
증명하고자 하는 명제를 논리에 어긋나지 않는 범위에서 증명하기 쉬운 명제로 변환하여 증
명하는 방법
유형
. 대우증명법
. 모순증명법
. 반례증명법
① 대우증명법(proof by contraposition)
증명하고자 하는 명제의 대우 명제를 이용하는 방법으로, 명제의 함축 p→q와 ~q→ ~p가 대
우관계로서 논리적 동치가 됨을 이용하여, ~q→ ~p 가 참인 것을 증명함으로써 p→q가 참이
되는 것을 보여주는 증명방법을 대우증명법이라 한다.
명제의 함축 p→q 이 참이면 그 대우인 ~q→ ~p도 참이고 두 명제가 서로 동치인 것을 이용
주어진 명제의 대우명제가 참임을 증명함으로써 증명하고자 하는 명제도 참임을 증명하는 방법
② 모순증명법
주어진 문제의 명제를 일단 부정해 놓고 논리를 전개하여, 그것이 모순됨을 보임으로써 본래의
명제가 참임을 증명하는 방법을 모순증명법이라 한다. 기존의 전통적인 방법으로는 주어진 문
제를 쉽게 증명할 수 없는 경우에 매우 유용하며, 귀류법이라고도 한다.
p→q가 참인 것과 p∧~q가 거짓임은 동티이므로 p∧~q가 참이라고 가정 하고 모순이 유도되면
원래의 명제가 참임을 증명하게 된다.
함축 p→q 와 ~(p∧~q)가 동치인 것을 이용하여 증명하는 방법 (p∧~q)가 참이라고 한 뒤 그
결과가 모순되면 ~(p∧~q) 가 참이 되고 이와 동치인 함축 p→q 도 참이 됨을 이용
③ 반례에 의한 증명 (반례 증명법)
∀xp(x)이 거짓임을 보이기 위해 ~∀xp(x)와 동치인 ∃x~(px)에서 p(x)를 만족하지 않는 x가 적어
도 하나 존재함을 보이면 된다. 이때 x를 반례(counter example)라고 하며, 이러한 증명방법을
반례에 의한 증명법(proof by counter example)라고 한다.
어떤 명제가 참 또는 거짓임을 입증하기 상당히 어려운 경우, 주어진 명제에 모순이 되는 간단
한 하나의 예를 보임으로써 비교적 쉽게 증명할 수 있는 방법 중의 하나이다.
주어진 명제에 모순되는 간단한 예를 하나 보임으로써 명제를 증명하는 방법 다른 증명 방법
으로 증명하기 어려운 예제들을 증명할 때 유용
=================================================================
2. 재귀법
. 재귀법(recursion)
재귀법을 이용하여 문제를 해결하기 위해서는 일련의 규칙을 찾아 문제를 다시 정의해야 한다.
여기서 초기조건은 하나 이상일 수 있다.
. 초기조건(initial condition) 정의
. 재귀조건(recursion condition) 정의
=================================================================
3. 프로그램 검증
. 프로그램 검증(program verification)
. 프로그램이 주어짂 명세와 일치하는지를 알아보기 위해 수학적 증명 방법을 통해 특정한 성
질들을 증명하는 작업.
. 다양한 프로그래밍언어를 이용하여 프로그램을 개발한 뒤에는 반드시 작성한 프로그램이 올
바르게 작동하는지 검증해야 한다. 즉 실제 사용되는 데이터를 입력하기 전에 수학적 증명 방
법들을 통해 프로그램의 결과가 정확한지, 프로그램이 정상 종료되는지, 변수들의 값이 어떻게
변하는지 등을 검증하는 것이다.
프로그램 명령문
. 순서문
.명령들을 순서대로 실행
. 조건문
.주어진 조건이 참인지 거짓인지에 따라 명령문을 선택하여 실행
. 반복문
.조건이 참인 동안 명령문을 반복 실행
. 프로그램 명령문 순서도
. 순서문 조건문 반복문
. 명령문에 맞게 작성되었는지 확인
. 이를 위해 입력 데이터에 맞게 출력이 생기는지 확인