[알고리즘] Mathematical Induction & Vacuous Truth

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

Mathematical Induction, 수학적 귀납법

---

'P(n)이 모든 자연수 n에 대해서 참이다'라는 것을 보이기 위해 사용하는 증명 방법 중 하나이다.

 

수학적 귀납법의 기본형

P(1)이 참이고, P(n-1) → P(n)이 참이면

P(n)은 모든 자연수 n에 대해서 참이다.

Base: P(1)
Step: P(n-1) → P(n)

 

수학적 귀납법의 강한 형태

P(1)이 참이고, P(1) ∧ P(2) ∧ ... ∧ P(n-1) → P(n)이 참이면

P(n)은 모든 자연수 n에 대해서 참이다.

Base: P(1)
Step: P(1) ∧ P(2) ∧ ... ∧ P(n-1) → P(n)

 

 

명제 P → Q의 의미

---

P → Q : P이면 Q이다

 

Vacuously True, Vacuous Truth

P가 False인 상황에서는 약속, 즉 조건들이 의미가 없다. → Vacuous

따라서 result는 엄밀하게는 총 3가지 상태(True, False, Vacuous)를 가진다.

 

하지만 Vacuous를 따로 두는 것이 불편(귀찮)다..

→ Vacuous는 True와 False 둘 중 하나로 몰아넣기로 하였는데, True라고 말하는 것이 더 자연스럽기 때문에 전부 True가 되었다.

 

Vacuous는 True로 몰아넣고, 더 이상 신경 쓰지 않는다

이에 따라 증명 시에는 Vacuous는 참으로 가정하고 계속 진행한다.

(Vacuous인 부분 = 조건과 부합하지 않는 경우들)

 

즉, 수학적 귀납법에서 P(n-1) → P(n)을 증명할 때

P(n-1)이 거짓인 경우는 생각하지 않고, P(n-1)이 진짜 참일 때 P(n)도 진짜 참인 경우만을 생각한다.