[Discrete Mathematics] 여러가지 증명(proof) 및 수학적 귀납법

---

수학적 체계

 

• 공리 (Axioms)

증명없이 참으로 받아들여지는, 즉 다른 명제로부터 연역되지 않는 명제를 말한다.

• 정의 (Definitions)

기존 개념을 사용하여 어떠한 개념의 의미를 규정하는 것이다. 수학적 방법을 통해 좀 더 명확히 표현 가능하다.

• 무정의 용어 (Undefined Terms)

명시적으로 정의되지 않으며, 공리나 직관에 의해 암묵적으로 이해되는 기초적인 용어이다. 다른 개념을 설명하기 위해 필요한 기본 용어로, 순환 오류를 방지하기 위해 명시적으로 정의하지 않는다. 예를 들어, 집합론에서의 '집합'이나 기하학에서의 '점'과 '선'이 무정의 용어에 해당한다.

• 정리 (Theorem)

공리, 정의를 기초로 연역적으로 이끌린 명제로 참임이 증명된 명제이다.

• 보조정리 (Lemma)

다른 정리를 증명하는 데에 사용되는 정리이다.

• 따름정리 (Corollary)

다른 정리로부터 쉽게 도출되는 정리이다.

• 증명 (Proof)

어떤 명제가 참인지를 논리적으로 풀어내 입증하는 것이다. 

 

---

직접 증명 (Direct Proof)

 

직접 증명은 어떤 명제를 증명할 때 전제를 참이라 가정하고 연역하여 증명하는 방법이다. 주로 "만약 $ A $ 라면 $ B $ 이다"와 같은 조건 명제 형태에서 사용된다. 이 경우 $ A $ 를 참이라 가정하고, 그것을 기반으로 결론 $ B $ 가 참임을 논리적으로 보여야 한다.

예를 들어 "모든 $ x_1, x_2, \dots, x_n $ 에 대해 $ p(x_1, x_2, \dots, x_n) $ 이면 $ q (x_1, x_2, \dots, x_n) $ 이다" 와 같은 문장이 있다 가정하자. 이 전칭된 문장은 $ p $ 가 참일 때 $ q $ 가 참이면 참이다. 이를 증명하기 위해 $ x_1, x_2, \dots, x_n $ 이 논의영역에 속하는 원소임을 가정하고, 아래와 같이 진리표를 그려 확인할 수 있다.

$ p $	$ q $	$ p \to q $
True	True	True
True	False	False
False	True	True
False	False	True

또 하나의 예로 "짝수와 홀수를 더하면 홀수이다"라는 명제를 직접 증명해보자. 홀수와 짝수의 정의는 다음과 같다.

"정수 $ n $ 이 짝수라면 어떤 정수 $ k $ 가 존재하여 $ n = 2k $ 가 성립해야 한다. 정수 $ n $ 이 홀수라면 어떤 정수 $ k $ 가 존재하여 $ n = 2k + 1 $ 이 성립해야 한다."

증명하기 위한 명제를 좀 더 명확히 다음과 같이 써보자.

" $ m $ 과 $ n $ 을 임의의 정수라 하고, $ m $ 이 홀수, $ n $ 이 짝수라면 $ m + n $ 은 홀수이다." 

이제 $ m $ 을 홀수, $ n $ 을 짝수라 가정하자. 즉 전제를 참이라 가정하자. 정의에 따르면 $ m $ 이 홀수이므로 어떤 정수 $ k_1 $ 이 존재하고, 따라서 $ m = 2k_1 + 1 $ 이다. 또한 정의에 따르면 $ n $ 이 짝수이므로 어떤 정수 $ k_2 $ 가 존재하고, 따라서 $ n = 2k_2 $ 이다. 이제 $ m + n = (2k_1 + 1) + (2k_2) = 2(k_1 + k_2) + 1 $ 이므로 어떤 정수 $ k = k_1 + k_2 $ 가 존재하여 $ m + n = 2k + 1 $ 이 성립하며, 따라서 $ m + n $ 은 홀수이다.

 

---

간접 증명 (Indirect Proof)

 

• 모순에 의한 증명 (Proof by Contradiction)

모순에 의한 증명은 귀류법, 배리법이라고도 하며, 어떤 명제를 참이라 가정하고 모순을 이끌어내서 그 가정이 거짓이므로 해당 명제가 거짓임을 증명하는 방법이다.

모순은 $ r \land \lnot \text{ } r $ 와 같은 형태의 명제이다. $ p \to q $ 이 참임을 증명하려면 $ p $ 가 참이고, $ q $ 가 거짓이라는 가정을 하고 모순을 도출하면 된다. 이 도출 과정에서 $ (p \land \lnot \text{ } q) \to (r \land \lnot \text{ } r) $ 이 참임을 보이면 $ (p \land \lnot \text{ } q) \to (r \land \lnot \text{ } r) \equiv p \to q $ 기 때문에 증명된다. 조건 명제가 아닌 명제 $ p $ 가 참임을 증명하려면 $ \lnot \text{ } p \to (r \land \lnot \text{ } r) $ 이 참임으로 보이는 것으로 $ \lnot \text{ } p $ 가 거짓임을 알 수 있기 때문에 $ p $ 가 참임을 증명할 수 있다.

 

• 대우에 의한 증명 (Proof by Contrapositive)

대우에 의한 증명은 $ p \to q $ 와 $ \lnot \text{ } q \to \lnot \text{ } p $ 가 동치임을 이용하는 증명 방법이다. 즉 대우가 참이나 거짓임을 증명하여 원래 명제가 참이나 거짓임을 증명하는 것이다.

 

• 경우의 의한 증명 (Proof by Cases)

경우에 의한 증명은 원래의 가정이 자연스럽게 여러 경우로 나뉘는 경우에 사용하는 증명 방법이다. 예를 들어 " $ x $ 는 실수이다"라는 문장은 " $ x $ 는 음이 아닌 실수이다"와 " $ x $ 는 음수이다"라는 문장으로 나눌 수 있다. 즉 $ p \to q $ 를 증명해야 하고, $ p $ 가 $ p_1 \lor p_2 \lor \cdots \lor p_n $ 으로 나뉜다면 $ ( p_1 \lor p_2 \lor \cdots \lor p_n) \to q $ 를 증명하는 대신 $ (p_1 \to q) \land (p_2 \to q) \land \cdots \land (p_n \to q) $ 를 증명한다.

 

• 전수 증명 (Exhaustive Proof)

증명해야 하는 경우의 수가 유한한 경우 각 경우를 하나하나 모두 확인하여 증명할 수도 있다.

 

• 동치 증명 (Proofs of Equivalence)

동치 증명은 상호 조건문에 대한 증명 방법이다. "$ p $ 이면 $ q $ 이고, $ q $ 이면 $ p $ 이다"와 같이 $ p \leftrightarrow q $ 인 명제를 증명하려면 $ p \to q $ 와 $ q \to p $ 를 각각 증명해야 한다. 이는 $ p \leftrightarrow q \equiv (p \to q) \land (q \to p) $ 에 의해 정당화된다.

조건이 많아지는 경우 전부 동치로 해결하기 보다 $ p \to q , q \to r , r \to s \cdots $ 을 모두 보인 후에 각 명제들이 모두 동치라는 것을 보이는 것이 낫다. 

 

• 존재 증명 (Existence Proofs)

존재한정된 명제에 대한 증명 방법이다. 어떤 $ \exists x P(x) $ 를 증명할 때 $ P(a) $ 를 참으로 만드는 논의영역의 $ a $ 라는 원소를 제시하는 것으로 이 때의 증명을 건설적인 증명(constructive proof)이라 한다.

 

• 반례 증명 (Proof by Counter-example)

주로 전칭한정된 명제에 대한 증명 방법이다. 전칭한정된 명제를 거짓으로 만들 수 있는 반례를 제시하는 것으로 증명이 끝난다.

 

---

수학적 귀납법 (Mathematical Induction)

 

수학적 귀납법의 원리는 다음과 같다. 우리가 논의영역이 양의 정수인 명제 $ S(n) $ 을 가지고 있고, $ S(1) $ 이 참임을 증명할 수 있으며 모든 $ n \geq 1 $ 에 대해 $ S(n) $ 이 참이면 $ S(n+1) $ 이 참임을 증명할 수 있다면 $ S(n) $ 은 모든 양의 정수 $ n $ 에 대해 참이다. 이때 $ S(1) $ 을 증명하는 단계가 기본단계(basis step)이고, $ S(n+1) $ 도 참임을 증명하는 단계가 귀납단계(inductive step)이다. 이 원리를 통해서 특정한 값 $ n_0 $ 에서 시작하는 명제 $ S(n) $ 이 참임을 증명할 수 있다.

강한 수학적 귀납법은 표준 수학적 귀납법(상대적으로 대비하기 위해 약한 귀납법이라고도 한다)과 달리 $ S(n) $ 을 증명할 때 $ S(k) $ 가 $ n_0 \leq k < n $ 인 모든 경우에 대해 참임을 가정한다. 약한 귀납법과 논리적으로는 동등하다.

 

---

루프 불변식 (Loop Invariant)

 

while (condition)
    loop

루프 불변식은 프로그램 변수에 대한 명제로 루프가 실행되기 전과 각 반복 후에 항상 참인 명제이다. 이를 증명하기 위해서 수학적 귀납법을 활용할 수 있다. 루프가 실행되기 전 불변식이 참임을 증명하고, 루프가 반복될 때 마다 불변식이 유지됨을 증명하면 된다.

예를 들어 아래와 같은 의사코드가 종료될 때 fact 변수가 n! 과 같음을 증명하자.

i = 1
fact = 1
while (i < n)
  i = i + 1
  fact = fact * i

루프가 시작되기 전 i = 1 이고 fact = 1 이므로 fact = 1! 이다. 이로써 기본단계가 증명되었다. fact = i! 이라 가정하면, i < n 일 때 루프가 한  번 더 실행되면 i = i + 1 이 되고,  fact = fact × (i + 1) = (i + 1)! 이므로 귀납단계가 증명되었다. 따라서 루프가 종료되면 i = n 이 되고, fact = n! 이 된다. 즉, fact = i! 가 루프 불변식임이 증명되었다.

 

---

정렬 원리 (Well-ordering Principle)

 

정수론에서 공집합이 아닌 자연수의 임의의 부분집합 $ X \subseteq \mathbb{N} $ 의 최소원 $ \min X $ 가 존재한다는 원리이다.

집합 $ S \subseteq \mathbb{N} $이 최소원을 갖지 않는다고 하자.

$ 1 \notin S $ 의 증명은 귀류법을 이용하면 간단하다. $ 1 \notin S $ 이면 $ \forall x \in \mathbb{N}, x \geq 1 $ 에서 $ \forall x \in S, x \geq 1 $ 이므로 $ S $ 는 최소원소를 가지므로 모순된다. 따라서 $ 1 \notin S $ 이어야 한다.

$ \forall x < k $ 에 대해서 $ k \neq S $ 일 때 $ k + 1 \notin S $ 의 증명 역시 귀류법을 이용하면 간단하다. $ k + 1 \in S $ 일 때 $ \{ n \in \mathbb{N} \mid n < k + 1 \} \cap S = \emptyset $ 이므로 $ \forall x \in S, x \geq k + 1 $ 이 되어 $ k + 1 $ 이 최소원이어야 하므로 모순이다. 따라서 $ k + 1 \notin S $ 이어야 한다.

따라서 강한 수학적 귀납법에 의해 $ \forall x \in \mathbb{N}, x \notin S $ 로 $ S = \emptyset $, 최소원이 없는 자연수의 부분집합은 공집합 뿐이다.

 

---

몫-나머지 정리 (Quotient-Remainder Theorem)

 

$ d $ 와 $ n $ 이 정수이고 $ d > 0 $ 일 때, 정수 몫 $ q $ 와 나머지 $ r $ 이 존재하여 다음을 만족하며 $ q $ 와 $ r $ 은 유일하다.

$$ n = dq + r \quad \quad 0 \leq r < d $$

집합 $ X = \{ n - dk \mid n - dk \leq 0 , k \in \mathbb{Z} \} 을 정의한다. 이 $ X $ 가 공집합이 아님을 증명하여 그 안에 최소 원소가 존재함을 보일 수 있다.

$ n \leq 0 $ 일 경우, $ n - d \dot 0 = n \leq 0 $ 이므로 $ n \in X $ 이다.

$ n < 0 $ 인 경우, $ d $ 는 양수이므로 $ 1 - d \geq 0 $ 이다. 이 경우에도 $ n - dn \in X $ 이다. 따라서 $ X \neq \emptyset $ 이다.

이로써 $ X $ 는 최소 원소를 가지며, 이 원소가 나머지 $ r $ 이다. 또한 이 조건에 맞는 유일한 $ q $ 와 $ r $ 이 존재함을 알 수 있다.