SW Expert Academy Computial Thinking

p -> q 의 전체 문장의 결과를 직관적으로 판단하면 안된다.

조건(p)가 거짓이면 항상 참이고 결과(q)가 참이면 항상 참이다.

수학적 귀납법 : p(1)이 참이고 p(n)->p(n+1)이면 모든 n에 대해 p(n)은 참이다.

• 소수가 무한한지 증명하는 문제 : O
  • p(n) : n개의 소수의 곱 + 1의 값을 가지면 새로운 소수를 만들 수 있다.
  • 만약 p(k)가 소수가 아니라면 조건이 거짓이므로 위 명제는 참이다.
  • 그러므로 p(n)->p(n+1)은 참이고 소수는 무한히 존재한다.

강한 수학적 귀납법 : p(1)이 참이고 p(1)^p(2)^…p(n-1)^p(n)->p(n+1)이 참이면 모든 n에 대해 p(n)은 참이다.

• p(n) : 1부터 n까지의 합이다.
• p(n-1)은 1부터 n-1부터의 합이므로(거짓이면 항상 전체문장은 참) p(n) = n + p(n-1)이므로 양변이 같고 참이다.