선행학습 · PREREQUISITE
증명법
Proving
원문 : blog.naver.com/cki_math_lab/220731319490
序
추론의 타당성을 보이는 것은 많은 분야에서 나타나는데 유형별로 여러 가지 상황에 어떻게 적용되는지
알아볼 필요가 있다.
조건문 (p→q 형태)
수학에서 가장 많이 나타나는 조건문 p→q 형태의 증명법에는 다음 세 가지 방법이 주로 사용된다.
⑴ 직접증명법 — 조건 p에서부터 직접 결론 q를 이끌어 낸다.
[(p→s₁)∧(s₁→s₂)∧(s₂→s₃)∧⋯∧(sₙ→r)] ⇒ (p→r)
의 추론 규칙을 사용하는 것이다.
추론: "n이 홀수이면 n²도 홀수이다."를 직접증명법으로 증명해보자.
n이 홀수라고 하자. 그러면 적당한 자연수 k에 대해 n=2k−1이 된다. n² = (2k−1)² = 4k²−4k+1 = 2(2k²−2k)+1 이 되고, 따라서 n²은 홀수이다.
추론: "n이 홀수이면 n²도 홀수이다."를 직접증명법으로 증명해보자.
n이 홀수라고 하자. 그러면 적당한 자연수 k에 대해 n=2k−1이 된다. n² = (2k−1)² = 4k²−4k+1 = 2(2k²−2k)+1 이 되고, 따라서 n²은 홀수이다.
⑵ 대우증명법 — 대우명제인 ∼q→∼p 를 보임으로써 명제를 증명한다.
p→q ≡ ∼q→∼p
(기초 논리 정리14 참고)의 추론 규칙을 사용하는 것이다.
추론: "a²이 홀수이면 a도 홀수이다."를 대우증명법으로 증명해보자.
주어진 명제의 대우명제는 "a가 짝수이면 a²도 짝수이다."이다. a는 짝수이므로 적당한 자연수 k에 대해 a=2k가 된다. a² = (2k)² = 2(2k²) 이 되고, 따라서 a²은 짝수이다. 그러므로 대우명제는 성립한다. 이때 원명제 p→q와 대우명제 ∼q→∼p는 논리적 동치이므로 원명제도 성립한다.
추론: "a²이 홀수이면 a도 홀수이다."를 대우증명법으로 증명해보자.
주어진 명제의 대우명제는 "a가 짝수이면 a²도 짝수이다."이다. a는 짝수이므로 적당한 자연수 k에 대해 a=2k가 된다. a² = (2k)² = 2(2k²) 이 되고, 따라서 a²은 짝수이다. 그러므로 대우명제는 성립한다. 이때 원명제 p→q와 대우명제 ∼q→∼p는 논리적 동치이므로 원명제도 성립한다.
⑶ 귀류법 — 어떤 명제가 참임을 증명하려 할 때 그 명제의 결론을 부정함으로써 가정 또는 공리 등이
모순됨을 보여 간접적으로 그 결론이 성립한다는 것을 증명하는 방법이다.
p→q ≡ (p∧∼q)→c
(기초 논리 귀류법 참고)의 추론 규칙을 사용하는 것이다.
추론: "m²이 홀수이면 m도 홀수이다."를 귀류법으로 증명해보자.
m²이 홀수이면서 m이 홀수가 아니라고 가정하자. 그러면 m은 짝수이므로 적당한 자연수 k에 대해 m=2k가 된다. m² = (2k)² = 2(2k²) ⋯ ① 이 되고, 따라서 m²은 짝수이다. 그러므로 m²은 (가정에 의해) 홀수이면서 (①에 의해) 짝수이다. 이것은 모순이다. 그러므로 귀류법에 의해 명제가 성립한다.
추론: "m²이 홀수이면 m도 홀수이다."를 귀류법으로 증명해보자.
m²이 홀수이면서 m이 홀수가 아니라고 가정하자. 그러면 m은 짝수이므로 적당한 자연수 k에 대해 m=2k가 된다. m² = (2k)² = 2(2k²) ⋯ ① 이 되고, 따라서 m²은 짝수이다. 그러므로 m²은 (가정에 의해) 홀수이면서 (①에 의해) 짝수이다. 이것은 모순이다. 그러므로 귀류법에 의해 명제가 성립한다.
쌍조건문
수학의 정리 등에서 많이 나타나는 쌍조건문 형태의 타당성을 보일 경우 아래와 같은 두 가지 방법이 있다.
⑴ 두 개의 조건문이 성립함을 증명 — (p→q)와 (q→p)라는 두 가지 사실을 보인다.
p↔q ≡ (p→q)∧(q→p)
(기초 논리 정리9 참고)의 추론 규칙을 사용하는 것이다.
예: 실수 a,b가 방정식 x²+px+q=0의 해가 되기 위한 필요충분조건은 a+b=−p, ab=q 이다.
(⇒) a,b가 방정식의 해가 된다고 하자. 근의 공식에 의해 a = −p−p²−4q2, b = −p+p²−4q2 이다. (혹은 반대로) 따라서 a+b=−p, ab=q이다.
(⇐) a+b=−p이고 ab=q라 하자. 그러면 b=−p−a가 된다. 결국 q = ab = a(−p−a) = −ap−a² ∴ a²+ap+q = 0 즉 a는 x²+px+q=0의 해가 된다. 마찬가지 방법으로 a=−p−b를 대입한 후 정리하면 b도 해가 된다.
예: 실수 a,b가 방정식 x²+px+q=0의 해가 되기 위한 필요충분조건은 a+b=−p, ab=q 이다.
(⇒) a,b가 방정식의 해가 된다고 하자. 근의 공식에 의해 a = −p−p²−4q2, b = −p+p²−4q2 이다. (혹은 반대로) 따라서 a+b=−p, ab=q이다.
(⇐) a+b=−p이고 ab=q라 하자. 그러면 b=−p−a가 된다. 결국 q = ab = a(−p−a) = −ap−a² ∴ a²+ap+q = 0 즉 a는 x²+px+q=0의 해가 된다. 마찬가지 방법으로 a=−p−b를 대입한 후 정리하면 b도 해가 된다.
⑵ 동치인 식의 열을 나열하는 방법 — 직접 동치인 식을 나열하여 이끌어 낸다.
[(p↔s₁)∧(s₁↔s₂)∧⋯∧(sₙ↔r)] ⇒ (p↔r)
(기초 논리 정리13의 추이법칙 참고)의 추론 규칙을 사용하는 것이다.
예: 모든 실수 x,y에 대해 (x+y)² = x²+2xy+y² 이 성립함을 보이자.
임의의 실수 x,y에 대해 (x+y)² = (x+y)(x+y) = x²+xy+yx+y² = x²+2xy+y² 이므로 성립한다.
예: 모든 실수 x,y에 대해 (x+y)² = x²+2xy+y² 이 성립함을 보이자.
임의의 실수 x,y에 대해 (x+y)² = (x+y)(x+y) = x²+xy+yx+y² = x²+2xy+y² 이므로 성립한다.
여러 가지 경우를 나누는 형태
한 가지 방법으로 증명하기 어려울 때는 여러 가지 경우를 나누어 증명할 수 있다. (p∨q)→r을 보이기 위해서
(p→r)이고 (q→r)임을 보이는 것이다.
[(p→r)∧(q→r)] ⇒ [(p∨q)→r]
n개의 경우가 있는 형태는
[(p₁→r)∧(p₂→r)∧⋯∧(pₙ→r)] ⇒ [(p₁∨p₂∨⋯∨pₙ)→r]
의 추론 규칙을 사용하는 것이다.
예: 모든 실수 x에 대해 x² = |x| 임을 보이자.
x가 실수이므로 x<0, x=0, 0<x 중 하나이다.
위 두 가지 모두 x²=|x|이다. 따라서 모든 실수 x에 대해 x²=|x|이다.
예: 모든 실수 x에 대해 x² = |x| 임을 보이자.
x가 실수이므로 x<0, x=0, 0<x 중 하나이다.
| x<0일 경우 | x≥0일 경우 |
| x<0이므로 x² = (−x)² = −x = |x| | x² = x = |x| |
한 개 명제
한 개 명제의 타당성을 증명할 경우는 추론에서 전제 부분이 없을 경우로 생각할 수 있다.
⑴ 직접증명법 — 위 조건문 ⑴에서처럼 직접 증명한다.
⑵ 귀류법 — ∼p를 가정하면 모순이 생긴다는 것을 보인다. ∼p가 성립하지 않는다는 것을 보이는 것이므로
이중부정법으로 볼 수도 있다. 즉 ∼(∼p) ≡ p
(기초 논리 정리14 참고)의 추론 규칙을 사용하는 것이다.
추론: "모든 실수 x에 대해 x≠0 → 1x≠0 이다."를 귀류법으로 증명해보자.
주어진 명제는 ∀x∈R (x≠0 → 1x≠0) 이므로 부정을 구하면 ∃x∈R (x≠0 ∧ 1x=0) (∵ ∼(p→q) ≡ ∼(∼p∨q) ≡ p∧∼q)이다. 즉 어떤 실수 x에 대해 x≠0 ∧ 1x=0이다. 역수의 정의에 의해 1 = x×(1x) = x·0 = 0 ∴ 1=0 이는 모순이다. 따라서 주어진 명제가 성립한다.
추론: "모든 실수 x에 대해 x≠0 → 1x≠0 이다."를 귀류법으로 증명해보자.
주어진 명제는 ∀x∈R (x≠0 → 1x≠0) 이므로 부정을 구하면 ∃x∈R (x≠0 ∧ 1x=0) (∵ ∼(p→q) ≡ ∼(∼p∨q) ≡ p∧∼q)이다. 즉 어떤 실수 x에 대해 x≠0 ∧ 1x=0이다. 역수의 정의에 의해 1 = x×(1x) = x·0 = 0 ∴ 1=0 이는 모순이다. 따라서 주어진 명제가 성립한다.
(∀x)(p(x))의 형태
전칭기호가 포함되어 있는 명제의 경우 아래와 같은 방법을 사용할 수 있다. (∃x)(p(x))의 부정을 보이는 경우도 여기에 해당된다.
⑴ 모든 x에 대해서 p(x)가 성립하는 것을 보인다.
예: 전체집합이 {2,3}일 때 모든 x에 대해 1<x → 1<x²임을 보이자.
x=2일 때, 1<2 → 1<2²=4이다. 또, x=3일 때, 1<3 → 1<3²=9이다. 따라서 모든 x에 대해 성립한다.
예: 전체집합이 {2,3}일 때 모든 x에 대해 1<x → 1<x²임을 보이자.
x=2일 때, 1<2 → 1<2²=4이다. 또, x=3일 때, 1<3 → 1<3²=9이다. 따라서 모든 x에 대해 성립한다.
⑵ x를 임의로 택했을 경우 성립하는 것을 보인다.
예: 모든 x에 대해 1<x → 1<x²이다.
임의의 1<x인 x를 생각하자. 0<1이므로 추이법칙에 의해 0<x이다. 그러면 1<x이고 0<x이므로 부등식의 성질 a>b, m>0 ⟹ ma>mb 9)에 의해 x<x²이고 1<x이므로 추이법칙에 의해 1<x²이다.
예: 모든 x에 대해 1<x → 1<x²이다.
임의의 1<x인 x를 생각하자. 0<1이므로 추이법칙에 의해 0<x이다. 그러면 1<x이고 0<x이므로 부등식의 성질 a>b, m>0 ⟹ ma>mb 9)에 의해 x<x²이고 1<x이므로 추이법칙에 의해 1<x²이다.
(∃x)(p(x))의 형태
수학에서 존재기호가 들어 있는 정리가 많이 나타나는데, 이런 정리의 증명에는 아래와 같은 방법이 사용된다. 앞에서 (∀x)(p(x))의 부정 형태인 (∃x)(∼p(x))을 보이는 경우도 여기에 해당된다.
⑴ 실제 예를 찾아낸다. (∃x)(∼p(x))와 같은 부정 형태의 예를 반례(反例, Counter Example)라 한다.
예: 연속이지만 미분 불가능한 함수가 존재함을 보이자.
f:R→R, f(x)=|x|라 하면 f(x)= −x (x<0), x (x≥0) 이다. 이때 함수 f(x)는 (−∞,∞)에서 연속함수이지만 x=0에서 limh→0⁻ f(h)−f(0)h = limh→0⁻ −hh = −1
limh→0⁺ f(h)−f(0)h = limh→0⁺ hh = 1 이므로 x=0에서 미분 불가능하다.
예: 연속이지만 미분 불가능한 함수가 존재함을 보이자.
f:R→R, f(x)=|x|라 하면 f(x)= −x (x<0), x (x≥0) 이다. 이때 함수 f(x)는 (−∞,∞)에서 연속함수이지만 x=0에서 limh→0⁻ f(h)−f(0)h = limh→0⁻ −hh = −1
limh→0⁺ f(h)−f(0)h = limh→0⁺ hh = 1 이므로 x=0에서 미분 불가능하다.
⑵ 존재할 수밖에 없다는 것을 보인다. 직접 구하는 것이 어렵거나 불가능할 때 사용한다.
예: x³−x²+3x−5=0의 근이 (1,2)에 적어도 하나 존재함을 보이자.
f(x)=x³−x²+3x−5라 하자. f(x)는 [1,2]에서 연속이고 f(1)=1−1+3−5=−2<0, f(2)=8−4+6−5=5>0 이다. 따라서 f(1)·f(2)<0 이므로 중간값의 정리11)에 의해서 f(c)=0이 되는 c가 (1,2)에 적어도 하나 존재한다.
예: x³−x²+3x−5=0의 근이 (1,2)에 적어도 하나 존재함을 보이자.
f(x)=x³−x²+3x−5라 하자. f(x)는 [1,2]에서 연속이고 f(1)=1−1+3−5=−2<0, f(2)=8−4+6−5=5>0 이다. 따라서 f(1)·f(2)<0 이므로 중간값의 정리11)에 의해서 f(c)=0이 되는 c가 (1,2)에 적어도 하나 존재한다.
- 1) 論理 : 말이나 글에서 사고나 추리 따위를 이치에 맞게 이끌어 가는 과정이나 원리
- 2) 기초 논리 정리14 참고
- 3) 진위(참과 거짓)가 모든 경우에 대해 서로 같다.
- 4) 간접증명법 중의 하나로 배리법이라고도 부른다.
- 5) 기초 논리 정리14 참고
- 6) 기초 논리 정리9 참고
- 7) 기초 논리 정리13의 추이법칙 참고
- 8) 기초 논리 정리14 참고
- 9) 부등식의 성질 — 원문 블로그 참고: blog.naver.com/cki_math_lab/220513994261 (아직 사이트에 이관되지 않은 글)
- 10) 反例, Counter Example
- 11) 中間값의 定理 원서 — 원문 블로그 참고: blog.naver.com/cki_math_lab/220101535515 (아직 사이트에 이관되지 않은 글)