n이 정수이면 n^2 >= n 임을 증명하라
경우에 의한 증명 n = 0, n >= 1 , n <= -1 의 세 가지 경우를 고려
- n = 0 일 때, 0^2 = 0이므로 0^2 >= 0 이 성립
- n >=1 일때, 양변을 n으로 곱하면 n^2 >= n 이 성립
- n <=-1 일 때, n^2 >= 0 이므로 n^2 >= n 이 성립\
따라서 세 경우 모두에 대해 성립하므로 증명하였다.
유일성 증명
-유일하게 하나의 값만이 주어진 특성을 만족하는 경우를 유일성이라고 하고 이에 대한 증명을 유일성 증명이라고 합니다.
유일성 증명 과정
존재성 : x가 주어진 특성을 가짐을 보인다.
유일성 : 만일 y != x 이면 y는 주어진 특성을 가지지 않음을 보인다.
즉 하나의 원소만이 주어진 특성을 갖는지 보이면 됩니다.
예시
a와 b는 실수이고 a != 0 이라면, ar + b = 0을 만족하는 유일한 실수 r이 존재함을 증명하라
-존재성 : 실수 r = - b/a 은 ar+b=0의 해이다. 왜냐하면 a(-b/a) + b = -b + b = 0이기 때문이다.
-유일성 : s가 as+b=0을 만족하는 실수라고 하자. 그러면 ar + b = as + b 이다. 여기서 r = -b/a이다. 양벼에서 b를 뺀 후 0이 아닌 a로 나누면 r = s 이다.
가설의 형식화
-가능한 많은 형태의 증거에 기초하여 가설을 형식화한다.
-기존의 정리나 명제를 사용하여 원하는 가설을 만들어내거나, 직관이나 결과가 성립한다는 믿음에 기초하여 가설을 만들어낸다.
가설의 증명
-가설이 형식화되면 목표는 이를 증명하는 것이다. 증명하게 되면 가설은 정리가 된다.
-증명하지 못하면, 가설은 결국 가설로 남게 된다.
예제)
가설 : a > 2이고 n이 양의 정수라면, a^n -1은 합성수이다 (예 : 3^2 -1 = 8 = 2^3)
(누군가의 직관을 사용하면 이런 가설을 생각했다 하자)
증명
- a^n -1 = (a-1)(a^n-1 + ... + a + 1)
- 1 < a-1 < a^n -1 이므로 a -1은 a^n -1의 인수이고, 결국 a^n-1은 합성수이다. 따라서 상기 가설은 정리가 된다.
a-1을 인수로 가지는 것을 통해 2개 이상의 약수를 가지므로 합성수라고 본 것입니다.
가설의 반례
-그럴듯한 가설을 제시하였는데, 증명이 어려운 경우 반례를 생각하면 된다.
-반례를 들 수 있으면 그 가설은 false가 되어 정리가 되지 못한다.
가설
n >= 3인 모든 정수 n에 대하여, n-1의 양의 정수들의 n 제곱의 합은 어떤 수의 n제곱이 될 수 없다.
-반례 1 : n = 4 일때
-반례 2 : n = 5 일때
'IT 프로그래밍 > 이산수학' 카테고리의 다른 글
[이산수학] 수열, 문자열 ,점화관계를 푸는 법 ( 반복 ) (0) | 2024.04.12 |
---|---|
[이산수학] 멱집합, 순서가 있는 n쌍, 데카르트 곱 (0) | 2024.04.09 |
[이산수학] 전칭예시화 일반화, 존재예시화 일반화 (0) | 2024.04.09 |
[이산수학] 중첩된 한정자 (0) | 2024.04.08 |
[이산수학] 존재한정자 (0) | 2024.04.08 |