이산수학
2장. 수학적 증명
1
이산수학
출처
본 강좌 자료는 이산수학 (2학년 / 3학점/ 3시간 / 이론) 수업에서 사용한 교재 [이산수학 (수학으로 이해하는 디지털 논리), 한빛
아카데미 출판사] 의 내용 등을 출처로 작성하였음을 알리는 바입니다.
2
이산수학
학습 목표
■
공리, 정의, 정리를 이해하여 증명에 활용할 수 있다.■
다양한 증명의 종류를 이해할 수 있다.■
주어진 문제에 적당한 증명방법을 선택하여 증명할 수 있다.3
이산수학
학습 내용
■
증명의 정의■
직접증명법■
간접증명법■
수학적 귀납법4
이산수학
수학 용어
■
공리(Axiom)◻
증명 없이 참 (T)으로 이용되는 명제■
정의(Definition)◻
논의의 대상을 보편화하기 위해 사용하는 용어 또는 기호의 의미를 확실하게 규정한 문장 또는 식■
정리(Theorem)◻
공리와 정의를 통해 참으로 확인된 명제■
증명 (Proof)◻
명제가 참임을 확인하는 과정5
이산수학
직접증명법
■
직접 증명법(Direct Proof)◻
함축명제 𝑝 → 𝑞 가 참임을 증명하는 방법6
이산수학
예제
■
모든 정수 n에 대해 n이 짝수이면, 𝑛2도 짝수이다.(증명)
Let p : 모든 정수 𝑛 은 짝수이다.
Let q : 정수 𝑛2 은 짝수이다.
Let p → q : 모든 정수 n에 대해 n이 짝수이면, 𝑛2도 짝수이다.
Let 𝑘 ∈ 𝑍. ∴ n = 2𝑘 . n ² = (2𝑘)2 = 4𝑘2 = 2(2𝑘2)
∴ 명제 p → q 는 참이다.
7
이산수학
예제
■
자연수 m이 짝수이면, m =2 이거나 소수가 아니다.(증명)
Let p : 자연수 𝑚 은 짝수이다.
Let q : m =2 or 𝑚 ≠ 소수
Let p → q : 자연수 m이 짝수이면, m =2 이거나 소수가 아니다.
Note 𝑚 = 2𝑘 , for some 𝑘 ∈ 𝑁.
(1) 𝑘=1 ⇒ 𝑚 = 2 (true)
(2) 𝑘 ≥ 2 ⇒ 𝑘|𝑚 ∴ 𝑚 ≠ 소수
∴ 명제 p → q 는 참이다.
8
이산수학
간접증명법
■
함축명제 𝑝 → 𝑞 를 다양한 형태로 변형하여 증명하는 방법■
대우증명법( Contraposition)◻
함축명제 𝑝 → 𝑞 가 ¬𝑞 → ¬𝑝 와 동치임을 이용하여 증명■
모순증명법( Contradiction)◻
함축명제 𝑝 → 𝑞 가 ¬ (𝑝 ∧ ¬ 𝑞) 와 동치임을 이용하여 증명 ¬ (𝑝 ∧ ¬ 𝑞) ≡ ¬ 𝑝 ∨ ¬(¬𝑞) ∵ 드모르간의 법칙≡ ¬ 𝑝 ∨ 𝑞 ∵ 이중부정의 법칙 ≡ 𝑝 → 𝑞 ∵ 함축법칙
■
반례증명법 (Counter Example)◻
주어진 명제에 모순이 되는 예를 찾아 증명: ∃ 𝑥 𝑠. 𝑡 ¬𝑝(𝑥)9
이산수학
예제
■
완전수이면 소수가 아니다.(증명)
Let 𝑝 : 자연수 𝑚 은 완전수이다.
Let 𝑞 : 𝑚 ≠ 소수
Let ¬ 𝑝 : 자연수 𝑚 은 완전수가 아니다.
Let ¬ 𝑞 : 𝑚 = 소수
Let ¬ 𝑞 → ¬ 𝑝 : 자연수 𝑚이 소수이면, 𝑚 은 완전수가 아니다.
𝑚은 𝑚 이외의 약수는 1만 가지므로, 1과 𝑚 이외의 다른 약수들의 합이 𝑚 이 될 수 가 없다. m 은 완전수가 아니다. ∴ ¬ 𝑞 → ¬ 𝑝 는 참.
∴ 대우증명법에 의해 명제 𝑝 → 𝑞 는 참이다.
10
이산수학
예제
■
소수는 완전수가 아니다.(증명)
Let 𝑝 : 자연수 𝑚 은 소수이다.
Let 𝑞 : 𝑚 ≠ 완전수 Let ¬ 𝑞 : 𝑚 = 완전수
Let 𝑝 ∧ ¬𝑞 : 자연수 𝑚 은 소수이고, 완전수이다.
위의 가정에 의해 𝑚 의 약수는 1과 𝑚 이고, 𝑚 과 1 이외의 다른 약수가 존재하지 않으므로 약수들의 합은 𝑚 이 될 수 가없다. 따라서 명제
𝑝 ∧ ¬𝑞 는 거짓이다.
∴ 모순증명법에 의해 명제 𝑝 → 𝑞 는 참이다.
11
이산수학
예제
■
∀ 𝑥, 𝑦 ∈ 𝑅, 𝑥 > 𝑦 이면 𝑥2 > 𝑦2이다.(증명)
Let 𝑝 : ∀ 𝑥, 𝑦 ∈ 𝑅, 𝑥 > 𝑦 이면 𝑥2 > 𝑦2이다.
Let 𝑥 = 0, 𝑦 = −1. ⇒ 𝑥 > 𝑦 , but 𝑥2 ≯ 𝑦2
∴ 반례증명법에 의해 명제 𝑝 (x)는 참이다.
12
이산수학
예제
■
모든 소수 𝑛에 대해 𝑛 + 4도 소수이다.(증명)
Let 𝑝(𝑛) : 모든 소수 𝑛에 대해 𝑛 + 4도 소수이다.
Set 𝑛 = 2 ⇒ 𝑛 + 4 = 6 ⇒ 2|6, 3|6 ⇒ 𝑛 + 4는 소수가 아니다.
∴ 반례증명법에 의해 명제 𝑝 (𝑛)는 참이다.
13
이산수학
예제
■
∀ 𝑥 ∈ 𝑅, (𝑥 + 1)2> 𝑥2 이다.(증명)
Let 𝑝(𝑥) : ∀ 𝑥 ∈ 𝑅, (𝑥 + 1)2> 𝑥2 이다.
Let 𝑥 = −1 ⇒ −1 + 1 2 = 0, (−1)2=1 ⇒ (𝑥 + 1)2≯ 𝑥2
∴ 반례증명법에 의해 명제 𝑝 (x)는 참이다.
14
이산수학
존재증명법
■
주어진 명제가 참(T)이 되게 하는 예를 찾아 증명하는 방법■
∃𝑥 𝑠. 𝑡 𝑝(𝑥)■
명제를 참으로 만드는 예가 한 가지라도 존재한다면 그 명제는 참이 된다.15
이산수학
예제
■
어떤 소수 𝑛에 대해 𝑛 + 4도 소수이다.(증명)
Let 𝑝(𝑛) : 어떤 소수 𝑛에 대해 𝑛 + 4도 소수이다.
Let 𝒑 : 2, 3, 5, 7, 11, 13, ….
∴ 𝒑 + 4 ⇒ 6, 7, 9, 11, 15,…
∃ 3, 7, … s.t 𝒑 + 4 : prime number ∴ ∃𝑛 ∈ 𝑁 𝑠. 𝑡 𝑛 + 4 is prime.
∴ 존재증명법에 의해 명제 𝑝 (𝑛)는 참이다.
16
이산수학
예제
■
어떤 𝑥, 𝑦 ∈ 𝑅에 대하여, 𝑥 > 𝑦 이면 𝑥2 > 𝑦2이다.(증명)
Let 𝑝(𝑥) :어떤 𝑥, 𝑦 ∈ 𝑅에 대하여, 𝑥 > 𝑦 이면 𝑥2 > 𝑦2이다.
Let 𝑥 = 2, 𝑦 = −1. ⇒ 𝑥 > 𝑦 , but 𝑥2 > 𝑦2 ∴ ∃𝑥, 𝑦 ∈ 𝑅 𝑠. 𝑡, 𝑥 > 𝑦 이면 𝑥2 > 𝑦2
∴ 존재증명법에 의해 명제 𝑝(𝑥) 는 참이다.
17
이산수학
예제
■
어떤 𝑥 ∈ 𝑅에 대해, (𝑥 + 1)2> 𝑥2 이다.(증명)
Let 𝑝(𝑥) : 어떤 𝑥 ∈ 𝑅에 대해, (𝑥 + 1)2> 𝑥2 이다.
Let 𝑥 = 3 ⇒ 3 + 1 2 = 16, (3)2=9 ⇒ (𝑥 + 1)2 > 𝑥2
∴ ∃𝑥 ∈ 𝑅 𝑠. 𝑡 (𝑥 + 1)2> 𝑥2 .
∴ 존재증명법에 의해 명제 𝑝(𝑥) 는 참이다.
18
이산수학
수학적 귀납법증명
■
수학적 귀납법 증명(Mathematical Induction)■
자연수 𝑛에 관한 명제 𝑝(𝑛)이 모든 자연수에 대해 성립한다는 것을 다음 세 단계의 과정으로 증명하는 방법◻
기본가정 : 𝑝(논의영역에 속하는 초기값)가 참임을 증명◻
귀납가정: 임의의 자연수 𝑘에 대해 𝑝(𝑘)가 참이라고 가정◻
귀납단계: 기본가정과 귀납과정을 이용해 자연수 𝑘+1에 대해 𝑝(𝑘 + 1)이 참임을 증명19
이산수학
예제
■ ∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 1, 1 + 2 + ⋯ + 𝑛 = 𝑛(𝑛+1)2 .
(증명) Let 𝑝(𝑛) : ∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 1, 1 + 2 + ⋯ + 𝑛 = 𝑛(𝑛+1)2 . (1) Let 𝑘=1. 𝑝(1) = 1 = 1(1+1)2 = 1 (∴ true)
(2) Assume that 𝑝(𝑘) : 1 + 2 + ⋯ + 𝑘 = 𝑘(𝑘+1)2 , for 𝑘 ∈ 𝑁.
(3) 𝑝(𝑘 + 1) : 1 + 2 + ⋯ + 𝑘 + (𝑘 + 1) = 𝑘(𝑘+1)2 +(𝑘 + 1) = 𝑘+1 * 𝑘+1 +1+
2
∴ 기본가정 (1)과 귀납가정 (2)에 의해 명제 𝑝(𝑘 + 1) 이 참이다.
∴ 수학적 귀납법에 의해 명제 𝑝(𝑛) 은 참이다.
20
이산수학
예제
■ ∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 3, 𝑛2 > 2𝑛 + 1 이다.
(증명) Let 𝑝(𝑛) : ∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 3, 𝑛2 > 2𝑛 + 1 (1) Let 𝑘=3. 𝑝(3) : 32 = 9 > 2·3 + 1 = 7 ∴ true.
(2) Assume that 𝑝(𝑘) : ∀ 𝑘 ∈ 𝑁, 𝑘 ≥ 3, 𝑘2 > 2𝑘 + 1 .
(3) w. t. s 𝑝(𝑘 + 1) : ∀ 𝑘 ∈ 𝑁, (𝑘 + 1) ≥ 3, (𝑘 + 1)2 > 2(𝑘 + 1) + 1 ∵ (𝑘 + 1)² = 𝑘² + 2𝑘 + 1 > 2(𝑘 + 1) + 1 = 2𝑘 + 3,
𝑘² + 2𝑘 + 1 > 2𝑘 + 1 + 2𝑘 + 1 = 4𝑘 + 2 ⇒ 𝑘² > 2𝑘 + 1 > 4𝑘 + 2
> 2𝑘 + 3
∴ (𝑘 + 1)² > 2𝑘 + 3 (= 2 (𝑘 + 1) + 1) ∴ 기본가정 (1)과 귀납가정 (2)에 의해 명제 𝑝(𝑘 + 1) 이 참이다.
∴ 수학적 귀납법에 의해 명제 𝑝(𝑛) 은 참이다.
21
이산수학
예제
■
∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 5에 대해 2𝑛 > 𝑛2 이다.(증명) Let 𝑝(𝑛) : ∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 5에 대해 2𝑛 > 𝑛2 . (1) Let 𝑘=5. 𝑝(5) : 25 > 52 ∴ true.
(2) Assume that 𝑝(𝑘) : ∀ 𝑘 ∈ 𝑁, 𝑘 ≥ 5, 2𝑘 > 𝑘2 .
(3) w. t. s 𝑝(𝑘 + 1) : ∀ 𝑘 ∈ 𝑁, (𝑘 + 1) ≥ 5, 2𝑘+1 > (𝑘 + 1)2 . From (2) 2𝑘+1 = 2 ∙ 2𝑘 > 2 ∙ 𝑘2 & 2 ∙ 𝑘2 > (𝑘 + 1)2
⇒ 2 ∙ 𝑘2 − 𝑘 + 1 2 = 𝑘2 − 2𝑘 − 1 = 𝑘 − 1 2 − 2 > 0 (∵ 𝑘 ≥ 5) ∴ 2𝑘+1 > 2 ∙ 𝑘2> 𝑘 + 1 2
∴ 수학적 귀납법에 의해 명제 𝑝(𝑛) 은 참이다.
22
이산수학
예제
■ ∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 2에 대해 𝑛−1𝑖=1 𝑖(𝑖 + 1) = 𝑛(𝑛−1)(𝑛+1)
3 이다.
(증명) Let 𝑝(𝑛) : ∀ 𝑛 ∈ 𝑁, 𝑛 ≥ 2에 대해 𝑛−1𝑖=1 𝑖(𝑖 + 1) = 𝑛(𝑛−1)(𝑛+1) 3 . (1) Let 𝑘 = 2. 𝑝(2) : 2−1𝑖=1 𝑖(𝑖 + 1) =1 × 2 = 2(2−1)(2+1)
3 (2) Assume that 𝑝(𝑘) : 𝑘−1𝑖=1 𝑖(𝑖 + 1) = 𝑘(𝑘−1)(𝑘+1)
3
(3) w. t. s 𝑝(𝑘 + 1) : (𝑘+1)−1𝑖=1 𝑖(𝑖 + 1) = (𝑘+1)(𝑘)(𝑘+2)
3 .
From (2), 1(2) + 2(3) + 3(4) + ⋯ + (𝑘 − 1)𝑘 = 𝑘(𝑘−1)(𝑘+1) 3
∴ 1 2 + 2 3 + 3 4 + ⋯ + 𝑘 − 1 𝑘 + 𝑘 𝑘 + 1 = 𝑘(𝑘−1)(𝑘+1)
3 + 𝑘 𝑘 + 1 = 𝑘(𝑘+1)(𝑘+2) 3
∴ 수학적 귀납법에 의해 명제 𝑝(𝑛) 은 참이다.
23
이산수학
예제
■ 𝑎 + 𝑎𝑟 + 𝑎𝑟² + 𝑎𝑟³ + … + 𝑎𝑟ⁿ = 𝑎(𝑟𝑛+1𝑟−1 −1)
(증명) Let 𝑝(𝑛) : 𝑎 + 𝑎𝑟 + 𝑎𝑟2 + 𝑎𝑟3 + … + 𝑎𝑟ⁿ = 𝑎 𝑟𝑛+1𝑟−1 −1 (1) Let 𝑛 = 0. 𝑝(0) : 𝑎=𝑎 𝑟𝑟−11 −1
(2) Assume that 𝑝(𝑘) : 𝑎 + 𝑎𝑟 + 𝑎𝑟² + 𝑎𝑟³ + … + 𝑎𝑟𝑘 = 𝑎(𝑟𝑘+1𝑟−1 −1)
(3)w. t. s 𝑝(𝑘 + 1) : 𝑎 + 𝑎𝑟 + 𝑎𝑟² + 𝑎𝑟³ + … + 𝑎𝑟𝑘 + 𝑎𝑟𝑘+1 = 𝑎(𝑟 𝑘+1 +1𝑟−1 −1) 𝑙. ℎ. 𝑠 = 𝑎(𝑟𝑘+1𝑟−1 −1) + 𝑎𝑟𝑘+1 = 𝑎 𝑟
𝑘+1−1 +𝑎𝑟𝑘+1(𝑟−1)
𝑟−1 == 𝑎(𝑟(𝑘+1)+1𝑟−1 −1)
∴ 수학적 귀납법에 의해 명제 𝑝(𝑛) 은 참이다.
24
이산수학
예제
■
𝑛 ≥ 1일 때, 𝑛! ≥ 2𝑛−1(증명) Let 𝑝(𝑛) : 𝑛 ≥ 1일 때, 𝑛! ≥ 2𝑛−1
(1) Let 𝑛 = 1. 𝑝(1) : 1! = 1 ≥ 21−1 = 20 = 1 (2) Assume that 𝑝(𝑘) : 𝑘! ≥ 2𝑘−1
(3)w. t. s 𝑝(𝑘 + 1) : (𝑘 + 1)! ≥ 2 𝑘+1 −1 Note (𝑘 + 1)! = 𝑘! (𝑘 + 1) .
(𝑘 + 1)! ≥ 2𝑘−1(𝑘 + 1) ≥ 2𝑘−1× 2 = 2 𝑘+1 −1
∴ 수학적 귀납법에 의해 명제 𝑝(𝑛) 은 참이다.
25
이산수학
예제
■
𝑛 bits로 표현할 수 있는 데이터의 최대 개수는 2𝑛. (증명) Let 𝑝(𝑛) : 2𝑛(1)
Let 𝑛 = 1. 𝑝(1) : 21 = 2. 1비트로 2 개의 데이터 즉, 0 또는 1 표현.(2) Assume that 𝑝(𝑘) : 2𝑘 (3) w. t. s 𝑝(𝑘 + 1) : 2𝑘+1
𝑘 + 1 bits ⇒ 데이터 표현 최대 개수: 2 + 2𝑘=2𝑘+1
∴ 수학적 귀납법에 의해 명제 𝑝(𝑛) 은 참이다.
26
