알고리즘 증명하는 법

알고리즘은 어떻게 증명해야할까?

나도 모르겠다..

같이 한 번 알아보도록 하자.

---

증명을 위해서는 명제에서 시작된다.

명제.

명제는 참, 거짓을 판단할 수 있는 문장이나 식을 뜻한다.

조건 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는 참이다.