이산수학 추론, 연역, 귀납, 수학적 귀납법

이산수학: 연역법과 귀납법, 수학적 귀납법

추론 (Reasoning, interface)

• 이미 "참"으로 알고있는 명제로부터 새로운 "참"인 명제를 찾아내는 과정을 통해 새로운 지식을 얻는 것

  (위키백과: 어떠한 판단을 근거로 삼아 다른 판단을 이끌어 내는 것'이라고 할 수 있다.)

• 올바른 추론의 규칙 == 논리

• 전제(이미 "참"으로 알고있는 명제) → 결론(새로운 "참"인 명제) ⇒ 추론

• 추론의 종류

  • 연역법(deduction)
  • 귀납법(induction)

---

연역법(deduction)

• 이미 알고있는 판단을 근거로 새로운 판단을 유도하는 추론

• 대표적인 예: 3단논법

  모든 사람은 죽는다
  소크라테스는 사람이다
  그러므로 소크라테스는 죽는다

  p→q ⇒ T
  p는 T이다
  ⇒ 그러므로 q는 T이다

---

귀납법(induction)

• 개별적인 사실을 말하는 명제들로부터 일반적인 결론을 도출하는 방법

  백조 1은 하얗다
  백조 2,3,.....100은 하얗다
  ⇒ 그러므로 모든 백조는 하얀색 일 것이다(확률적인 결론)

  철수, 영희, 복동은 컴퓨터 공학과 학생이다
  철수는 C언어를 수강한다 (참)
  영희는 C언어를 수강한다 (참)
  복동은 C언어를 수강한다 (참)
  ⇒ "그러므로 모든 컴퓨터 공학과 학생들은 C언어를 수강한다"라는 명제가 참일까?

• 귀납법의 한계

  • 현실적으로 모든 원소에 대해서 참인 것을 밝힐 수 없다
    (도출된 결론은 확률적인 결론이다)

---

수학적 귀납법(mathematical induction)

• 귀납법의 한계를 극복하고 집합의 모든 원소에 대해서 명제가 성립하는것을 보여준다

  집합 X = {x1,x2,x3,....}
  ∀x P(x) is true

  1. n=1일때, P(x1)은 참이다

  2. n=k(k>1인 자연수)일 때, P(xk)이 참이라 가정하였을때
     P(x(k+1))이 참임을 보인다

     그렇다면 ∀x P(x)에 대해서 참이다

• 도미노와 유사한 거임

  1. 첫번째 도미노가 쓰러진다
  2. 앞 도미노가 쓰러지면 뒤 도미노가 쓰러진다

• 도미노를 수학적 귀납법으로

  1. n=1일때 P(x1)은 참이다
  2. n=k일때 성립하면 n=k+1일때도 성립한다