Mathematical Induction - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:22:25Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:22 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Logic and Proofs#Mathematical Induction\|Mathematical Induction]]		상위 문서: [[Logic and Proofs#Mathematical Induction\|Mathematical Induction]]

Pinkgo: /* Well-Founded Induction */

2025-10-08T11:00:17Z

Well-Founded Induction

← 이전 판		2025년 10월 8일 (수) 11:00 판
36번째 줄:		36번째 줄:

	만약 <가 well-founded라면 아래와 같은 귀납 원리가 성립한다:		만약 <가 well-founded라면 아래와 같은 귀납 원리가 성립한다:
	<math>\forall x. (\forall y. (y<x \rightarrow P(y)) \~~Rightarrow~~ P(x)) \Rightarrow \forall x.P(x)</math>		<math>\frac{\forall x. (\forall y. (y<x \rightarrow P(y))\rightarrow P(x))}{\Rightarrow \forall x.P(x)}</math>
	이는 "어떤 원소 x에 대해, x보다 작은 모든 y에서 성립하면 x도 성립한다"면, 전체적으로 모든 원소에 대해 성립한다는 의미이다.		이는 "어떤 원소 x에 대해, x보다 작은 모든 y에서 성립하면 x도 성립한다"면, 전체적으로 모든 원소에 대해 성립한다는 의미이다.

Pinkgo: /* Generalized Induction Rules */

2025-10-08T10:42:39Z

Generalized Induction Rules

← 이전 판		2025년 10월 8일 (수) 10:42 판
27번째 줄:		27번째 줄:
	==Generalized Induction Rules==		==Generalized Induction Rules==
	귀납법이 꼭 자연수에 관한 명제에 대해서만 쓰이는 것은 아니다. 귀납법은 "비교 관계(<)"에 기초를 두고 있으므로, 일반적으로 어떠한 순서 관계가 있다면 귀납법을 정의할 수 있기 때문이다. 예를 들어 아래와 같은 공리를 살펴보자:		귀납법이 꼭 자연수에 관한 명제에 대해서만 쓰이는 것은 아니다. 귀납법은 "비교 관계(<)"에 기초를 두고 있으므로, 일반적으로 어떠한 순서 관계가 있다면 귀납법을 정의할 수 있기 때문이다. 예를 들어 아래와 같은 공리를 살펴보자:
	<math>\forall A.(\forall B.B\in A \rightarrow P(B)) \rightarrow P(A) ~~\Rightarrow~~ \forall. P(A)</math>		<math>\frac{\forall A.(\forall B.B\in A \rightarrow P(B)) \rightarrow P(A)}{\forall A. P(A)}</math>
	이는 "집합 A의 모든 원소인 집합 B가 명제 P에 대해 성립하면 A도 성립한다"라는 의미이다. 이를 <math>\in</math>-귀납법(<math>\in</math>-induction)이라고 부른다. 이 귀납법은 비교 관계로 "부등호(<)"가 아닌 "엡실론(<math>\in</math>)"을 사용한다. 즉, 이는 “어떤 집합의 원소가 그 집합보다 더 작다"라는 개념을 순서 관계로 보는 것이다.		이는 "집합 A의 모든 원소인 집합 B가 명제 P에 대해 성립하면 A도 성립한다"라는 의미이다. 이를 <math>\in</math>-귀납법(<math>\in</math>-induction)이라고 부른다. 이 귀납법은 비교 관계로 "부등호(<)"가 아닌 "엡실론(<math>\in</math>)"을 사용한다. 즉, 이는 “어떤 집합의 원소가 그 집합보다 더 작다"라는 개념을 순서 관계로 보는 것이다.

Pinkgo: /* Well-Founded Induction */

2025-09-10T19:15:46Z

Well-Founded Induction

← 이전 판		2025년 9월 10일 (수) 19:15 판
41번째 줄:		41번째 줄:
	이는 자연수 뿐만 아니라 다양한 구조에 적용가능하다. 집합 관계에는 <math>\in</math>을, 문자열에는 적절한 접두사 관계를 사용할 수 있다.<ref>예: "abc" < "abcd".</ref> 표현식 트리(expression trees)에서는 "부분식(subexpression)" 관계를 사용할 수 있다.		이는 자연수 뿐만 아니라 다양한 구조에 적용가능하다. 집합 관계에는 <math>\in</math>을, 문자열에는 적절한 접두사 관계를 사용할 수 있다.<ref>예: "abc" < "abcd".</ref> 표현식 트리(expression trees)에서는 "부분식(subexpression)" 관계를 사용할 수 있다.

			==Inductively Defined Sets==
			귀납적으로 정의된 집합(Inductively Defined Sets)은 어떤 집합을 한번에 다 정의하는 대신, 규칙(closure conditions)을 정해서 그 규칙을 만족하는 원소들만 집합에 포함시키는 방식이다. 예를 들어서 식(Expression) 집합을 정의해보자.
			# 기본 원소(Base Case): 문자 a 하나만 있어도 그것은 식(expression)이다.<ref>예: x, y, z는 다 식이다.</ref>
			# 덧셈 규칙(Closure under +): <math>E_1, E_2</math>가 식이면 <math>(E_1 + E_2)</math>또한 식이다.<ref>예: x + y</ref>
			# 곱셈 규칙(Closure under <math>\cdot</math>): <math>E_1, E_2</math>가 식이면 <math>(E_1 \cdot E_2)</math>또한 식이다.<ref>예: x <math>\cdot</math> y</ref>
			#최소성 조건(Smallest set): 위 규칙을 유한 번 적용해서 만들 수 있는 것만 식이다.

	<math></math>		===Structural Induction===
	<math></math>		구조적 귀납법(Structural Induction)은 귀납법으로 정의된 집합에 대해 사용되는 귀납법이다. 이는 "집합 원소의 생성 규칙"을 기반으로 하는 귀납법이다. 예를 들어서 식(Expression)에 대한 구조적 귀납법을 관찰하자:
	<math></math>		# 기본 단계(Basis): 문자 a에 대해 <math>P(a)</math>가 성립함을 보인다.
	<math></math>		# 귀납 단계(덧셈): 만약 <math>E_1, E_2</math>에 대해 <math>P(E_1), P(E_2)</math>가 참이면, <math>P(E_1 + E_2)</math>도 참임을 보인다.
	<math></math>		# 귀납 단계(곱셈): 만약 <math>E_1, E_2</math>에 대해 <math>P(E_1), P(E_2)</math>가 참이면, <math>P(E_1 \cdot E_2)</math>도 참임을 보인다.
			이렇게 하면 식의 전체 집합에 대해 <math>P(E)</math>가 항상 성립한다고 말할 수 있다.

	==각주==		==각주==

Pinkgo: /* Complete Induction */

2025-09-10T19:04:36Z

Complete Induction

@@ 13번째 줄: / 13번째 줄: @@
 위 두 단계를 fitch-style 형식으로 정리하면 figure 1과 같은 꼴이 된다.
-==Complete Induction==
+===Complete Induction===
-<math></math>
+[[파일:Figure 2. Complete Induction.png|섬네일|Figure 2. Complete Induction]]
-<math></math>
+귀납법 중에는 완전 귀납법(complete induction)이 존재한다. 일반적인 귀납법과는 다르게, 완전 귀납법은 <math>P(n)</math>을 증명하고자 할 때, 단순히 <math>P(n-1)</math>만을 쓰는 것이 아니라 <math>P(0), P(1), \cdots, P(n-1)</math>을 가정하고 쓸 수 있다. 즉, 아래와 같은 형식적 규칙을 가진다:
-<math></math>
+ <math>\frac{\forall n.(\forall m.m<n \rightarrow P(m)) \rightarrow P(n)}{\forall n.P(n)}</math>
-<math></math>
+따라서 모든 n에 대해 “n보다 작은 모든 수에 대해 성립하면 <math>P(n)</math>도 성립한다"가 참이면, 전체적으로 <math>\forall n.P(n)</math>또한 참이라는 것이다. 이는 figure 2와 같은 꼴을 통해 fitch style로 나타내어 진다.
 <math></math>
 <math></math>

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Mathematical Induction ==개요== 수학적 귀납법(Proof by Induction)은 자연수에 대한 명제를 증명할 때 주로 사용되는 증명 방법이다. ==Principle of Mathematical Induction== Figure 1. Proofs by Induction 수학적 귀납법은 자연수...

2025-09-10T18:04:38Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Mathematical Induction ==개요== 수학적 귀납법(Proof by Induction)은 자연수에 대한 명제를 증명할 때 주로 사용되는 증명 방법이다. ==Principle of Mathematical Induction== 대체글=Figure 1. Proofs by Induction|섬네일|Figure 1. Proofs by 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>

==각주==