증명 기법 (Proof Techniques)

Proof Techniques, 증명 기법, 수학적 귀납법, 귀류법, 직접 증명, 구조 귀납법, 존재 증명

정의

증명 (proof) 은 명제가 참임을 논리적으로 확립하는 절차입니다. 컴퓨터 과학에서는 알고리즘 정확성, 자료구조 불변식, 암호 안전성, 형식 검증 등에 필수.

이 문서는 주요 증명 기법을 정리합니다.

1. 직접 증명 (Direct Proof)

“if $P$ then $Q$” 를 증명하려면:

1. $P$ 를 가정
2. 논리 규칙과 이미 알려진 사실로부터
3. $Q$ 를 도출

예: 두 홀수의 합은 짝수

증명: $a,b$ 를 홀수라고 하자. $a=2m+1$, $b=2n+1$ ($m,n\in \{Z\}$).

$a+b=(2m+1)+(2n+1)=2(m+n+1)$

$m+n+1\in \{Z\}$ 이므로 $a+b$ 는 짝수. QED.

2. 대우 증명 (Proof by Contrapositive)

$P\to Q$ 를 증명하려면 대우 $\neg Q\to \neg P$ 를 증명.

예: $n^2$ 가 짝수이면 $n$ 도 짝수

증명: 대우로 ”$n$ 이 홀수이면 $n^2$ 도 홀수” 를 증명.

$n$ 이 홀수 -> $n=2k+1$ -> $n^2=4k^2+4k+1=2(2k^2+2k)+1$. 홀수. QED.

3. 귀류법 (Proof by Contradiction, Reductio ad Absurdum)

명제 $P$ 를 증명하려면 $\neg P$ 를 가정하고 모순을 유도.

예: $\sqrt{2}$ 는 무리수

증명: $\sqrt{2}$ 가 유리수라 가정. $\sqrt{2}=\frac{\{}{p}\}\{q\}$ (기약분수, $\gcd (p,q)=1$).

$2q^2=p^2$

$p^2$ 가 짝수 -> $p$ 짝수 -> $p=2m$.

$2q^2=4m^2$

$q^2=2m^2$

$q^2$ 짝수 -> $q$ 짝수.

$p$ 와 $q$ 모두 짝수 -> $\gcd (p,q)\ge 2$. 기약분수 가정과 모순. QED.

예: 소수는 무한하다

증명 (유클리드): 소수가 유한하다고 가정. $p_1,p_2,\dots ,p_n$ 이 모든 소수.

$N=p_1{p}_2\cdots p_n+1$ 을 고려.

$N$ 을 어떤 $p_i$ 로 나누면 나머지 1. 따라서 $N$ 은 모든 $p_i$ 로 나누어떨어지지 않음.

두 경우:

1. $N$ 이 소수 -> 목록에 없는 새 소수 -> 모순
2. $N$ 이 합성수 -> 목록에 없는 소인수 존재 -> 모순

QED.

4. 존재 증명 (Existence Proof)

$\exists x,P(x)$ 를 증명.

구성적 (Constructive)

실제로 $x$ 를 찾음.

예: “짝수인 소수가 존재한다”

• 증명: $2$ 를 제시. 짝수이고 소수. QED.

비구성적 (Non-constructive)

존재를 논리적으로 보이지만 실제 $x$ 는 제시 안 함.

예: ”$a^b$ 가 유리수인 무리수 $a,b$ 가 존재한다”

• 후보: $a=\sqrt{2},b=\sqrt{2}$.
• ${\sqrt{2}}^{\{}\sqrt{2}\}$ 가 유리수라면: $a=b=\sqrt{2}$ 로 완료.
• 아니면 무리수. $a^{\prime }={\sqrt{2}}^{\{}\sqrt{2}\},b^{\prime }=\sqrt{2}$. $a^{\prime \{}{b}^{\prime }\}=({\sqrt{2}}^{\{}\sqrt{2}\}{)}^{\{}\sqrt{2}\}={\sqrt{2}}^2=2$ 유리수. QED.

두 경우 중 어느 것이 성립하는지 몰라도 존재 확인 가능.

5. 반례 증명 (Proof by Counterexample)

$\forall x,P(x)$ 가 거짓 임을 보이려면 하나의 반례를 제시.

예: “모든 소수는 홀수” 는 거짓

반례: 2 는 소수이지만 짝수.

6. 수학적 귀납법 (Mathematical Induction)

$P(n)$ 이 모든 $n\ge n_0$ 에 대해 참임을 증명.

단계:

1. 기저 (base): $P(n_0)$ 참 증명.
2. 귀납 단계 (inductive step): $P(k)$ 참 -> $P(k+1)$ 참 증명.

결론: $P(n)$ 이 모든 $n\ge n_0$ 에 대해 참.

시각화

flowchart LR
  Base["기저: P(n₀) 참"] --> Step1["P(n₀) → P(n₀+1)"]
  Step1 --> Step2["P(n₀+1) → P(n₀+2)"]
  Step2 --> Step3["P(n₀+2) → P(n₀+3)"]
  Step3 --> Dots["..."]
  Dots --> Concl["모든 n ≥ n₀"]

도미노 비유: 첫 도미노를 넘어뜨리면 (기저), 그리고 각 도미노가 다음을 넘어뜨리면 (귀납 단계), 모든 도미노가 넘어짐.

예: $1+2+\dots +n=n(n+1)/2$

기저: $n=1$. 좌변 = 1, 우변 = $1\cdot 2/2=1$. 성립.

귀납 단계: $P(k)$ 참이라 가정, $P(k+1)$ 증명.

$1+2+\dots +k+(k+1)=\frac{\{}{k}(k+1)\}2+(k+1)$ (귀납 가정)

$=(k+1)\left(\frac{\{}{k}\}2+1\right)=\frac{\{}{(}k+1)(k+2)\}2$

$P(k+1)$ 성립. QED.

예: 2^n 개의 조합 (부분집합 수)

$n$ 원소 집합의 부분집합 수 = $2^n$.

기저: $n=0$. 공집합 $\varnothing$ 의 부분집합은 $\varnothing$ 하나. $2^0=1$. 성립.

귀납 단계: $|S|=k$ 인 집합의 부분집합이 $2^k$ 라 가정.

$|S^{\prime }|=k+1$ 인 집합 $S^{\prime }=S\cup \{x\}$ ($x\notin S$). $S^{\prime }$ 의 부분집합은:

• $x$ 를 포함 X: $S$ 의 부분집합 = $2^k$ 개
• $x$ 를 포함 O: $S$ 의 부분집합에 $x$ 추가 = $2^k$ 개

총 $2^k+2^k=2^{\{}k+1\}$. QED.

7. 강귀납법 (Strong Induction)

$P(k+1)$ 증명 시 $P(n_0),P(n_0+1),\dots ,P(k)$ 모두 를 가정.

기저 + 강한 귀납 가정.

예: 모든 $n\ge 2$ 는 소인수 분해 가능

기저: $n=2$ 는 소수. 성립.

귀납 단계: $2,3,\dots ,k$ 가 모두 소인수 분해 가능이라 가정. $k+1$ 도 가능 증명.

두 경우:

1. $k+1$ 이 소수. 완료.
2. $k+1=ab$ ($1\text{<}a,b\text{<}k+1$). 강귀납 가정으로 $a,b$ 각각 소인수 분해 가능. 그 곱이 $k+1$ 의 분해.

QED.

8. 구조 귀납법 (Structural Induction)

트리, 리스트, 문자열 등 재귀적 구조에 대한 귀납.

예: 이진 트리의 잎 수

주장: 정점이 $n$ 개인 이진 트리의 잎 수 $\le \lceil n/2\rceil +1$ … (사실은 더 정확한 결과 있음)

구조 귀납:

• 기저: 정점 1 개 -> 잎 1 개.
• 귀납: 뿌리 + 왼쪽 부트리 + 오른쪽 부트리. 각 부트리에 귀납 가정 적용.

9. 반대칭 원리 (Well-Ordering Principle)

자연수의 공집합이 아닌 부분집합은 최소 원소를 가짐.

귀납법과 논리적으로 동치.

예: 나눗셈 정리

주장: 정수 $a$ 와 양의 정수 $b$ 에 대해 유일한 $q,r$ 이 존재해 $a=bq+r$, $0\le r\text{<}b$.

증명: 집합 $S=\{a-bq\mid q\in \{Z\},a-bq\ge 0\}$.

$S$ 는 공집합 아님. 최소값 $r=a-bq$ 존재. $0\le r$. $r\text{<}b$ 를 보이면 완료.

귀류: $r\ge b$ 라 가정. $r^{\prime }=r-b=a-b(q+1)\ge 0$. $r^{\prime }\text{<}r$ 이면서 $S$ 에 속함. 최소성 모순.

컴퓨터 과학 응용

알고리즘 정확성

루프 불변식 (loop invariant): 루프의 각 반복마다 유지되는 성질.

귀납법으로 증명:

• 초기화: 첫 반복 전에 성립
• 유지: 한 반복 후에도 성립
• 종료: 종료 시 원하는 성질 함의

자료구조 불변식

• AVL 트리: 각 정점의 두 부트리 높이 차 $\le 1$.
• B-tree: 모든 잎이 같은 깊이.

각 연산이 불변식을 유지함을 귀납법으로 증명.

형식 검증

• 모델 검사: 상태 공간 모든 경로 확인
• 정리 증명기 (Coq, Lean): 대화형 증명

재귀 알고리즘

• 분할 정복: 강귀납법으로 정확성
• 트리 순회: 구조 귀납

함정

1. 기저 오류

$n=0$ 또는 $n=1$ 이 실제 기저인지 확인. $n=0$ 특수 케이스 잊기 쉬움.

2. 귀납 가정의 잘못된 적용

$P(k)$ 를 가정하고 $P(k+1)$ 증명해야. 순환 논증 (증명하려는 것을 가정) 주의.

3. 무한 케이스 오류

“모든 유한 케이스에 대해 성립하므로 무한 케이스에도” 는 오류. 귀납법으로 명시적 증명.

4. 존재 vs 유일

$\exists x,P(x)$ 와 $\exists !x,P(x)$ (유일 존재) 는 다름. 유일성은 별도 증명.

관련 위키

• 이산수학 (개요)
• 명제 논리
• 집합, 관계, 함수
• 점화식
• 그래프 이론
• 조합론