[이산수학] 유일성 증명, 가설의 형식화, 증명, 반례

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 일때