Total
Search
1. 기본사항
1.1. 정의
•
공리 (Axiom)
◦
증명 없이 참으로 간주되는 가장 기본적인 명제
◦
예시
▪
두 점 사이에 직선 존재 (유클리드)
▪
자연수의 다음 수 존재 (페아노)
▪
공집합 존재 (집합론)
•
증명 (Proof)
◦
공리를 기반으로 명제의 참을 논리적으로 입증하는 과정
•
정리 (Theorem)
◦
공리와 이전의 정리를 통해 증명된 명제
•
보조정리 (Lemma)
◦
주요 정리를 증명하기 위해 중간 단계로 사용되는 명제
•
따름정리 (Corollary)
◦
정리에서 쉽게 도출되는 부수적인 명제
1.2. 증명 방법
•
직접 증명법
◦
공리와 정의, 그리고 정리를 논리적으로 직접 연결하여 증명한다.
•
수학적 귀납법
◦
자연수 n에 대한 명제의 성질을 증명하는 데 유용한 증명 방법.
◦
기본단계, 귀납가정, 귀납단계를 이용한다.
•
간접 증명법
◦
증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법이다.
◦
대우 증명법, 모순 증명법, 반례 증명법, 존재 증명법 등
•
그 외
◦
전수 증명법, 조합적 증명법, 컴퓨터 이용 증명법
2. 직접 증명법 (Direct Proof)
2.1. 정의 및 특징
•
연역법(deduction)이라고도 불림
•
명제를 변형하지 않고 공리, 정의, 정리를 논리적으로 연결하여 증명
2.2. 예제
•
두 홀수의 합은 짝수이다.
◦
홀수 표현
▪
x = 2a + 1, y = 2b + 1
▪
합 (x+y)
•
x + y = 2(a + b + 1)
•
여기서 a + b + 1은 정수임
•
x + y→ 짝수
•
두 유리수의 합은 유리수이다.
◦
r, s를 유리수라고 하자.
◦
(단, a, b,c, d는 정수이고 b ≠ 0)
◦
◦
여기서 ad + bc와 bd는 정수, bd ≠ 0이므로 두 유리수의 합은 유리수
2.3. 파스칼 삼각형과 이항정리
•
파스칼 삼각형
•
정리
◦
n, k는 양의 정수이고, k ≤ n이라고 가정하면
C(n +1 , k) = C(n, k) + C(n, k-1) 이다,
3. 수학적 귀납법 (Mathematical Induction)
3.1. 정의 및 특징
•
모든 자연수 n에 대해 명제를 증명하는데 유용
•
3단계 구성
1.
기본단계: n = 1일 때 성립하는지 확인
2.
귀납가정: n = k일 때 참이라고 가정
3.
귀납단계: n = k+1일 때도 참임을 증명
3.2. 예제
•
을 증명
•
기본 단계
◦
S(1) 은 1 = 이므로 성립
•
귀납 가정
◦
S(K)가 참이라고 가정. 즉
◦
•
귀납 단계
4 간접 증명법 (Indirect Proof)
4.1. 정의
•
증명해야할 명제를 증명하기 쉬운 형태로 변형하여 증명하는 방법
4.2. 종류
1.
대우 증명법 (Proof by Contrapositive)
•
P → Q 
~ Q → ~P
~ Q → ~P•
예제) x^2가 홀수라면 x도 홀수임을 증명하시오
2.
모순 증명법 (Proof by Contradiction)
•
P → Q를 증명할 때 ~P를 가정하면 모순이 발생함을 보임
•
귀류법, 배리법이라고도 함
•
예제) 가 유리수가 아님을 증명하시오
3.
반례 증명법 (Proof by Counterexample)
•
한정자가 포함된 명제의 증명
•
전체한정자(∀)가 사용된 명제가 거짓임을 증명 → 반례증명법
•
예제) 다음 명제가 거짓임을 증명하시오
◦
모든 실수 a,b에 대하여 이다.
◦
반례
▪
a=−2, b=2
4.
존재 증명법
•
존재한정자(∃)가 사용된 명자가 참임을 증명 → 존재증명법
◦
구성적 존재증명법
◦
비구성적 존재증명법
•
구성정 존재 증명법
◦
명제함수 ∃𝒙𝑷(𝒙)를 증명할 때 𝑷(𝒙)를 참으로 만드는 𝒙를 찾거나 찾는 과정을 제시함
•
비구성정 존재 증명법
◦
명제함수 ∃𝒙𝑷(𝒙)를 증명할 때 𝑷(𝒙)를 참으로 만드는 𝒙 를 찾지 않고 우회적으로 명제가 타당함을 보이는 방법
5. 다양한 증명방법
5.1. 전수 증명법 (Exhaustive Proof)
•
경우의 수가 적을 때 모든 경우를 하나하나 확인
5.2. 조합적 증명법 (Combinatorial Proof)
•
집합 간의 원소 수 비교를 통해 증명
◦
전단증명 (bijection)
▪
원소가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후, 두 집합이 일대일 관계임을 보여 n = m임을 증명함.
◦
중복산정 (double counting)
▪
동일한 집합의 원소를 두 가지 방법으로 센 다음, 그 결과가 각각 n과 m이라면 n = m임을 증명함.
5.3. 컴퓨터 이용 증명
•
복잡한 경우 컴퓨터의 계산력으로 증명
•
예: 4색 정리 (평면 지도는 4색으로 충분)