이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net

Chapter 02. 증 명

학습목표 수학적 귀납법을 이용한 증명 과정의 이해 여러 가지 증명 방법의 증명 과정 재귀법의 정의와 과정 이해 재귀 알고리즘의 작성과 검증 프로그램 검증 목적과 방법

자연수 n 에 관한 명제 p(n)에 대하여 다음 두 조건이 성립한다고 하자. Section 01. 수학적 귀납법 [정리01] 자연수 n 에 관한 명제 p(n)에 대하여 다음 두 조건이 성립한다고 하자. (1) p(1)은 참이다. (2) 임의의 k에 대하여 p(k) 참이면 p(k+1)도 참이다. 이 때 모든 자연수 n에 대하여 p(n)은 참이다. 이를 수학적 귀납법(mathematical induction)이라고 한다.

수학적 귀납법 (계속) [증명]

수학적 귀납법(계속) [예제01] 수학적 귀납법을 이용하여 다음 식이 성립함을 보여라. n!≥2n-1 (단, n=1,2,3,…) [풀이]

수학적 귀납법(계속) [예제03] 양의 정수 n에 대하여 이 성립 함을 수학적 귀납법을 이용하여 증명하여라. [풀이]

수학적 귀납법(계속) [예제05] 수학적 귀납법을 이용하여 인 정수일 때 이 성립함을 보여라. [풀이]

제 2 수학적 귀납법 / 강귀납법(strong form of mathematical induction) 수학적 귀납법(계속) 제 2 수학적 귀납법 / 강귀납법(strong form of mathematical induction) 자연수 n 에 관한 명제 p(n)에 대하여 다음 두 조건이 성립한다고 하자. (1) p(1)은 참이다. (2) 임의의 자연수 k ≥1에 대해 p(1)∧p(2)∧…∧ p(k) 참이면 p(k+1)도 참이다. 이 때 모든 자연수 n에 대하여 p(n)은 참이다.

수학적 귀납법(계속) [예제09] 제 2 수학적 귀납법을 이용하여 n≥14인 자연수 n 은 3과 8의 합으로 나타낼 수 있다는 것을 증명하여라. [풀이] 먼저 n=14면 14=8+3+3이 되어 3과 8의 합으로 나타낼 수 있다. 이제 14≤j≤k인 자연수 k들이 모두 3과 8의 합으로 나 타난다고 가정하고 k+1도 나타낼 수 있음을 보이자. 여기서 k+1=(k-2)+3이다. 그런데 k보다 작은 자연수 (k-2) 는 귀납법 가정에 의해 3과 8의 합으로 나타나는 수므로 k+1 도 (k-2)에 3을 더하면 나타낼 수 있게 된다. 그러므로 n≥14인 자연수 n은 3과 8의 합으로 나타낼 수 있 다.

수학적 귀납법(계속) [예제10] 수학적 귀납법을 이용하여 일 때 임을 증명하여 라. [풀이]

Section 02. 직접증명법 직접증명법(direct proof) 명제의 함축 p→q 가 참이 됨을 증명하는 방법

직접증명법(계속) [예제11] 짝수인 정수 n 이 있을 때 n2 도 짝수인 정수임을 직접증명법 을 이용하여 증명하여라. [풀이] p : n이 짝수 q : n2이 짝수 라고 가정하자. 명제 p가 참이므로 n은 짝수, 즉 n=2k (k∈Z)다. 따라서 n2=(2k)2=4k2=2(2k2) 가 된다. 그러므로 n2은 짝수다.

직접증명법(계속) [예제13] 두 유리수의 합이 유리수임을 직접증명법으로 증명하여라. [풀이]

간접증명법(indirect proof) Section 03. 간접증명법 간접증명법(indirect proof) 증명하고자 하는 명제를 논리에 어긋나지 않는 범위에서 증명하기 쉬운 명제로 변환하여 증명하는 방법 유형 대우증명법 모순증명법 반례증명법

대우증명법(proof by contraposition) 간접증명법 - 대우증명법 대우증명법(proof by contraposition) 명제의 함축 p→q 이 참이면 그 대우인 q→ p 도 참이고 두 명제가 서로 동치인 것을 이용 주어진 명제의 대우명제가 참임을 증명함으로써 증명하고자 하는 명제도 참임을 증명하는 방법

간접증명법 - 대우증명법(계속) [예제16] n2 이 짝수면 n 이 짝수임을 대우증명법을 이용하여 증명하라. [풀이] p : n2 짝수, q : n 짝수 라고 하면 q : n 홀수, p : n2 홀수 이다. 이제 q→ p 가 참임을 보이자. n 이 홀수라면 n=2k+1(k는 정수)이므로 n2=(2k+1)2=(4k2+4k+1)=2(2k2+2k)+1 이 되어 n2 도 홀수다. 그러므로 q→ p 이 참이 되어 주어진 명제 ‘n2 이 짝수면 n 이 짝수’도 참임을 알 수 있다.

간접증명법 - 대우증명법(계속) [예제18] 실수 x에 대하여 |x|>1이면 x>1또는 x<-1임을 대우증명법을 이용하여 증명하여라. [풀이] 명제 p: |x|>1, q: x>1 또는 x<-1 이라고 하면 p: |x|≤1, q: -1≤x≤1 이다. 이제 q→ p 가 참임을 보이자. 0≤x≤1일 때 식은 |x|= x≤1이 되어 성립, -1≤x≤0일 때 |x|= -x≤1이 되어 성립한다. 그러므로 실수 x에 대하여 |x|>1이면 x>1또는 x<-1이다.

모순증명법(proof by contradiction) 간접증명법 - 모순증명법 모순증명법(proof by contradiction) 주어진 명제를 부정한 뒤 그 식을 전개함에 있어서 결론이 모순됨을 보여 결국 명제가 참임을 증명하는 방법 함축 p→q 와 (p∧q)가 동치인 것을 이용하여 증명하는 방법 (p∧q)가 참이라고 한 뒤 그 결과가 모순되면 (p∧q) 가 참이 되고 이와 동치인 함축 p→q 도 참이 됨을 이용

간접증명법 - 모순증명법(계속) [예제20] 다음 명제를 증명하여라. n 이 정수일 때 n+m=0이 되는 m은 유일하게 하나 존재한다. [풀이] n+m=0을 만족하면서 m과는 다른 정수가 존재한다고 가정 이 정수를 k라고 하면 n+k=0이므로 n+m=n+k 양변에 정수 n은 빼주면 m=k 그런데 m≠k라고 했으므로 m=k는 가정에 모순된다. 따라서 정수 n에 대해 n+m=0을 만족하는 정수 m은 유일하다.

간접증명법 - 모순증명법(계속) [예제21] 는 유리수가 아님을 증명하여라. [풀이] 는 유리수라고 가정하면 이다. 는 유리수라고 가정하면 이다. 이때 는 유리수므로 은 공통인수를 갖지 않는다. 주어진 식을 정리하면 이 되어 이 짝수가 되어 으로 나타내면 이 된다. 즉, 도 짝수가 된다. 이는 유리수 가 공통인수를 갖지 않는다는 가정에 모순된다. 그러므로 는 유리수가 아니다.

반례에 의한 증명법(proof by counter-example) 간접증명법 – 반례에 의한 증명법 반례에 의한 증명법(proof by counter-example) 주어진 명제에 모순되는 간단한 예를 하나 보임으로써 명제를 증명하는 방법 다른 증명 방법으로 증명하기 어려운 예제들을 증명할 때 유용

간접증명법 - 반례에 의한 증명법(계속) [예제25] 다음 명제가 참인지 거짓인지 증명하여라. 는 실수 [풀이] 만약 이면 만약 이면 이고 이 되어 가 된다. 그러므로 주어진 명제는 거짓이다.

간접증명법 - 반례에 의한 증명법(계속) [예제27] 다음 명제가 참이면 증명하고 거짓이면 반례를 들어라. 양의 정수 에 대해 이면 는 소수다. [풀이] 몇 가지 경우를 살펴보면 다음과 같다. 그러나 만일 그러므로 주어진 명제는 거짓이다.

Section 04. 재귀법 재귀법(recursion) 하나의 문제를 그보다 값이 작은 동일한 문제로 계속 단순화시켜 해결하고자 하는 방법 재귀법 문제해결을 위해 규칙필요 초기조건(initial condition) 재귀조건(recursion condition)

재귀법(계속) [예제28] 재귀법을 이용하여 양의 정수 n 에 대한 팩토리얼(factorial) 값을 구해주는 함수를 정의하여라. [풀이] 구하는 함수의 이름을 factorial(n)=n! 이라고 하면 다음과 같이 정의할 수 있다. 초기조건 factorial(0)=0!=1 재귀조건 factorial(n)=n∙factorial(n-1), n≥1

재귀법(계속) 팩토리얼 재귀정의가 올바른지 보기 위해 factorial(2)를 구하는 과정을 살펴보면 다음과 같다. factorial(2)=2∙factorial(2-1) =2∙factorial(1)=2∙(1∙factorial(1-1)) = 2∙1∙factorial(0)=2

재귀법(계속) 재귀 알고리즘 재귀법을 이용한 프로그램 알고리즘 재귀 알고리즘을 이용하여 복잡한 연산을 쉽게 해결 대부분의 프로그램 언어에서 재귀 알고리즘 지원

재귀법(계속) [예제31] 1부터 자연수 n 까지의 합을 구하는 재귀 알고리즘을 구하라. [풀이]

재귀법(계속) [예제34] 양의 정수 n 의 팩토리얼(factorial) 값을 구하는 재귀 알고리즘을 구하여라. [풀이]

재귀법(계속) 하노이 탑(tower of Hanoi) 3개의 기둥 중 제일 왼쪽 기둥에 크기가 큰 것이 제일 아래에 있게 원판들이 쌓여있을 때 제일 오른쪽 기둥으로 원판을 옮기는 데 소요되는 최소 이동 회수를 구하는 문제 추가조건 원판은 한 번에 하나씩만 옮길 수 있다. 원판을 기둥과 기둥으로만 옮길 수 있다. (즉, 바닥에 내려놓을 수 없다.) 크기가 큰 원판은 작은 원판 위에 올 수 없다.

재귀법(계속) 원판이 3개인 하노이 탑의 풀이 원리

재귀법(계속) [예제35] 하노이 탑 문제의 재귀 알고리즘을 구하여라. [풀이]

Section05. 프로그램 검증 프로그램 명령문 순서문 명령들을 순서대로 실행 조건문 주어진 조건이 참인지 거짓인지에 따라 명령문을 선택 하여 실행 반복문 조건이 참인 동안 명령문을 반복 실행

프로그램 검증(계속) 프로그램 명령문

프로그램 검증(계속) [예제37] 다음 알고리즘을 실행 후 x, y 값은 어떻게 되는지 검증하여라. [풀이] 프로그램 검증을 위해 x, y 에 초기 상수값 x1, y1 을 입력해보자. 명령을 수행하면 로 변경되어 두 개의 변수에 할당되어 있던 값을 서로 교환하는 프로그램임을 알 수 있다.

프로그램 검증(계속) [예제38] [풀이] 절대값을 구하는 알고리즘이다. 정확하게 수행되는지 검증하여라. 검증을 위해 x에 초기값 x1을 할당하자. x1<0이면 x=-x 명령문 실행 x1>0이면 x=x 명령문 실행 따라서 절대값 양수 x1을 구하고 알고리즘이 정확하게 동작함을 알 수 있다.

프로그램 검증(계속) [예제41] 다음 n≥0인 정수에 대한 실수 x의 n 제곱을 구하는 알고리즘이 정확하게 수행되는지 검증하여라.

프로그램 검증(계속) [풀이] 알고리즘에서 증명하는 명제 p는 다음과 같다. 수학적 귀납법을 이용하면 일 때 성립한다고 가정하고, 일 때 성립함을 보이자. 일 때 변수 를 일 때 이라고 하면

프로그램 검증(계속) 이다. 따라서 일 때 이 되어 명제 p가 참이 된다. 또한 반복문의 I 값은 1씩 증가하다 n+1이 되면 이 되어 반복문을 정상 종료하게 된다. 그러므로 알고리즘이 정상 동작함을 알 수 있다.

Thank you ehanbit.net