Mathematical Induction 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Logic and Proofs#Mathematical Induction|Mathematical Induction]]

==개요==
수학적 귀납법(Proof by Induction)은 자연수에 대한 명제를 증명할 때 주로 사용되는 증명 방법이다. 

==Principle of Mathematical Induction==
[[파일:Figure 1. Proofs by Induction.png|대체글=Figure 1. Proofs by Induction|섬네일|Figure 1. Proofs by Induction]]
수학적 귀납법은 자연수에 대한 명제를 증명할 때 주로 사용되는 추론 규칙이다. 이의 목표는 <math>\forall n.P(n)</math>을 증명하는 것, 즉 모든 자연수 n에 대해 명제 <math>P(n)</math>이 참임을 증명하는 것이다. 귀납법은 다음 두 단계로 나뉘어진다:
# Basis (기초 단계): <math>P(0)</math><ref>혹은 상황에 따라 <math>P(1)</math></ref>을 먼저 증명한다.
# Induction Step (귀납 단계): <math>\forall n. P(n) \rightarrow P(n+1)</math>임을 증명한다. 
위 두 단계를 fitch-style 형식으로 정리하면 figure 1과 같은 꼴이 된다. 

==Complete Induction==
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>

==각주==