알고리즘 증명하는 법
알고리즘은 어떻게 증명해야할까?
나도 모르겠다..
같이 한 번 알아보도록 하자.
증명을 위해서는 명제에서 시작된다.
명제.
명제는 참, 거짓을 판단할 수 있는 문장이나 식을 뜻한다.
조건 P와 Q가 있을 때, "P이면 Q이다"가 명제이다. 기호로는 P->Q로 나타낸다.
그런데 이떄, P이면이라는 것은 거짓인 상태이다.
예를들어, P가 5시 전이면, Q가 공부를 한다. 라고 가정해보자.
if, 5시가 되지 않았으면 P는 참이다. 이때 공부를 하면 Q도 참이므로 P->Q도 참이다.
하지만 공부를 하지 않았다면 Q는 거짓이고 P->Q도 거짓이다.
그런데 5시가 지났다고 가정해보자. 그러면 P는 거짓이다. 이때 Q, 공부를 한다면 참인데, P->Q는 뭘까?
| P 시간🕐 | Q 공부🏫 | P->Q 🕐 🏫 |
| 참 | 참 | 참 |
| 참 | 거짓 | 거짓 |
| 거짓 | 참 | 공부함. |
| 거짓 | 거짓 | 거짓. |
즉, Q가 무엇이든, P가 거짓이면 참이 될 수가 없다.
알고리즘 증명법
명제를 알았으니, 귀납법을 알고 증명해보자.
증명은 다음과 같은 과정을 따른다.
1. Base Setp: P(1)이 참이라고 가정한다.
2. Inductive Setp: P(n-1) -> P(n)이 참이면,
3. Result: P(n)은 모든 자연수 n에 대해서 참이다.
1번과 2번을 각각 증명해서 합치면 Result가 된다.
Example.
P(n) = n > 0 일때
1. Base: P(1)은 1 > 0이므로 True
2. Inductive: P(n-1) -> P(n)은 ( n - 1 > 0) -> ( n > 0 )이다.
proof:
1) a > 0 이고 b > 0 이면, a + b > 0 이다.
2) n - 1 + 1 = n
3) a에 n - 1 을, b에 1을 대입하면 2번에 따라 n - 1 + 1 = n이므로, n > 0 True
n(n+1)/2를 증명하시오.
1. Base: n=1일때 참임을 보인다.
1(1+1)/2 = 1 => 참
2. Inductive Step
1) Hypo: n = k - 1 일때 참이라고 가정한다.
k-1(k)/2 = 참 2) proof: n=k일때 참임을 증명.
k(k+1)/n은 k에서 1을 더한 것과 같으므로 참이다.
수열에서 k-1의 다음 순서는 k 이기 때문.
따라서 k-1이 참이라고 가정하면 k는 참이다.