증명증명

2 2 ^{장 장 증명 증명}

• 수학적 귀납법

• 직접 증명법

• 간접 증명법

• 재귀법

• 프로그램 검증

• 수학적 귀납법

• 직접 증명법

• 간접 증명법

• 재귀법

• 프로그램 검증

학습목표 학습목표

22

수학적 귀납법과 이를 이용한 증명 과정을 이해한다 . 여러 가지 증명 방법들의 증명 과정을 익힌다 .

재귀법을 이용한 정의와 과정을 이해한다 . 재귀 알고리즘을 작성하고 검증한다 .

프로그램을 검증하는 목적과 방법을 살펴본다 .

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

33

수학적 귀납법

수학적 귀납법

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

44

수학적 귀납법

수학적 귀납법

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

55

수학적 귀납법

수학적 귀납법

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

66

수학적 귀납법

수학적 귀납법

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

77

수학적 귀납법

수학적 귀납법

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

88

수학적 귀납법 수학적 귀납법

제 2 수학적 귀납법 / 강귀납법

자연수 n 에 관한 명제 p(n ) 에 대하여 다음 두 조건이 성립한다고 하자 . (1) p(1) 은 참이다 .

(2) 임의의 자연수 k ≥1 에 대해 p(1)∧p(2)∧…∧ p(k) 참이 면

p(k+1) 도 참이다 .

이 때 모든 자연수

^{에 대하여 p(n} ) 은 참이다 .

Section 01 Section 01 Section 01

Section 01 IT CookBookIT CookBookIT CookBookIT CookBook

99

수학적 귀납법

수학적 귀납법

1010

Section 02 Section 02 Section 02

Section 02

직접 증명법 직접 증명법

1111

Section 02 Section 02 Section 02

Section 02

직접 증명법 직접 증명법

직접증명법 (direct proof)

명제의 함축 p→q 가 참이 됨을 증명하는 방법

명제 p 를 참이라고 가정하고 , 여러 가지 정리와 식을 이용하여 명제

q 또한 참이 됨을 증명

1212

Section 02 Section 02 Section 02

Section 02

직접 증명법 직접 증명법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

1313

간접 증명법

간접 증명법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

1414

간접 증명법 간접 증명법

간접증명법 (indirect proof)

증명하고자 하는 명제를 논리에 어긋나지 않는 범위에서 증명하기 쉬운 명제로 변환하여 증명하는 방법

유형

 대우증명법

 모순증명법

 반례증명법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

1515

간접 증명법 간접 증명법

대우증명법 (proof by contraposition)

명제의 함축 p→q 이 참이면 그 대우인  q→ p 도 참이고 두 명제가 서로 동치인 것을 이용

주어진 명제의 대우명제가 참임을 증명함으로써 증명하고자 하는 명제도

참임을 증명하는 방법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

1616

간접 증명법

간접 증명법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

1717

간접 증명법

간접 증명법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

1818

간접 증명법 간접 증명법

모순증명법 (proof by contradiction)

주어진 명제를 부정한 뒤 그 식을 전개함에 있어서 결론이 모순됨을 보여 결국 명제가 참임을 증명하는 방법

함축 p→q 와  (p∧q) 가 동치인 것을 이용하여 증명하는 방법

(p∧q) 가 참이라고 한 뒤 그 결과가 모순되면  (p∧q) 가 참이 되고

이와 동치인 함축 p→q 도 참이 됨을 이용

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

1919

간접 증명법

간접 증명법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

2020

간접 증명법

간접 증명법

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

2121

간접 증명법 간접 증명법

반례에 의한 증명법 (proof by counter-example)

주어진 명제에 모순되는 간단한 예를 하나 보임으로써 명제를 증명하는 방 법

다른 증명 방법으로 증명하기 어려운 예제들을 증명할 때 유용

Section 03 Section 03 Section 03

Section 03 IT CookBookIT CookBookIT CookBookIT CookBook

2222

간접 증명법

간접 증명법

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

2323

재귀법 재귀법

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

2424

재귀법 재귀법

재귀법 (recursion)

하나의 문제를 그보다 값이 작은 동일한 문제로 계속 단순화시켜 해결하고자 하는 방법

재귀법 문제해결을 위해 규칙필요

 초기조건(initial condition)

 재귀조건(recursion condition)

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

2525

재귀법 재귀법

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

2626

재귀법 재귀법

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

2727

재귀법 재귀법

재귀 알고리즘

재귀법을 이용한 프로그램 알고리즘

재귀 알고리즘을 이용하여 복잡한 연산을 쉽게 해결

대부분의 프로그램 언어에서 재귀 알고리즘 지원

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

2828

재귀법 재귀법

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

2929

재귀법 재귀법

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

3030

재귀법 재귀법

하노이 탑 (tower of Hanoi)

3 개의 기둥 중 제일 왼쪽 기둥에 크기가 큰 것이 제일 아래에 있게 원판들 이 쌓여있을 때 제일 오른쪽 기둥으로 원판을 옮기는 데 소요되는 최소 이동 횟수를 구하는 문제

추가조건

 원판은 한 번에 하나씩만 옮길 수 있다 .

 원판을 기둥과 기둥으로만 옮길 수 있다 . ( 즉 , 바닥에 내려놓을 수 없다 .)

 크기가 큰 원판은 작은 원판 위에 올 수 없다 .

Section 04 Section 04 Section 04

Section 04 IT CookBookIT CookBookIT CookBookIT CookBook

3131

재귀법 재귀법

원판이 3 개인 하노이 탑의 풀이 원리

3232

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

3333

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

프로그램 명령문

순서문

 명령들을 순서대로 실행

조건문

 주어진 조건이 참인지 거짓인지에 따라 명령문을 선택하여 실행

반복문

 조건이 참인 동안 명령문을 반복 실행

3434

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

프로그램 명령문

3535

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

3636

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

3737

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

3838

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

3939

Section 05 Section 05 Section 05

Section 05

프로그램 검증 프로그램 검증

IT CookBook IT CookBook IT CookBook IT CookBook

Thank you