증명법

Proving

序

기초 논리와 추론의 타당성에서 만든 추론 규칙이 실제 수학의 증명에서 어떤 모습으로 쓰이는지 정리한다. 증명하려는 명제를 논리 구조(조건문인가, 쌍조건문인가, 한정기호가 붙어 있는가)로 먼저 분류하면 어떤 규칙을 쓸지가 대체로 정해진다. 아래에서는 명제의 형태마다 대표적인 증명 방법과 그 근거가 되는 규칙을 짝지어 둔다.

조건문 (p→q 형태)

정리의 대부분은 "가정 p가 성립하면 결론 q가 성립한다"는 꼴이다. 이 꼴을 증명하는 길은 크게 세 가지다.

⑴ 직접증명법 — p를 출발점으로 삼아, 이미 아는 사실과 추론 규칙을 한 단계씩 이어 q에 도착한다. 근거는 조건문을 사슬처럼 잇는 추이법칙이다. [(p→s₁)∧(s₁→s₂)∧(s₂→s₃)∧⋯∧(s_n→q)] ⇒ (p→q) (기초 논리 정리13의 추이법칙을 고리마다 거듭 적용)

보기: 정수 n에 대하여 "n이 3의 배수이면 n²은 9의 배수이다."
n이 3의 배수이므로 어떤 정수 k가 있어 n=3k이다. 그러면 n² = (3k)² = 9k² 이고 k²은 정수이므로 n²은 9의 배수이다.

⑵ 대우증명법 — p→q 대신 그 대우 ∼q→∼p를 직접증명법으로 보인다. 둘은 진릿값이 늘 같으므로 하나가 참이면 다른 하나도 참이다. p→q ≡ ∼q→∼p (기초 논리 정리14의 대우법칙) 결론 q가 "~이다"처럼 다루기 어려운 꼴이고, 그 부정 ∼q가 "~를 만족하는 수가 있다"처럼 식으로 쓰기 쉬울 때 특히 편리하다.

보기: 정수 n에 대하여 "n²이 짝수이면 n은 짝수이다."
대우는 "n이 홀수이면 n²은 홀수이다."이다. n이 홀수이면 어떤 정수 k가 있어 n=2k+1이고 n² = (2k+1)² = 2(2k²+2k)+1 이므로 n²은 홀수이다. 대우가 참이므로 원래 명제도 참이다.

⑶ 귀류법 — 가정 p와 결론의 부정 ∼q를 함께 놓고 추론을 이어 가서 모순명제 c(어떤 명제와 그 부정이 동시에 성립하는 상황)에 이르면, p→q가 참임이 확인된다. p→q ≡ (p∧∼q)→c (기초 논리 정리14의 귀류법, 증명은 기초 논리의 연역적 추론에서 정리 8·15·9로)

보기: 실수 x, y에 대하여 "x+y ≥ 2이면 x ≥ 1 또는 y ≥ 1이다."
x+y ≥ 2이면서 결론이 거짓, 즉 x < 1이고 y < 1이라고 하자. 두 부등식의 변끼리 더하면 x+y < 1+1 = 2 이다. 이것은 가정 x+y ≥ 2와 함께 성립할 수 없으므로 모순이다. 따라서 x ≥ 1 또는 y ≥ 1이다.

한 개 명제

가정 없이 명제 p 하나만 주어진 경우다. 전제가 비어 있는 추론으로 보면 조건문의 방법을 그대로 쓸 수 있다.

⑴ 직접증명법 — 정의와 이미 아는 사실에서 바로 p를 이끌어 낸다.

보기: 2¹⁰ > 10³이다. 계산하면 2¹⁰ = 1024, 10³ = 1000이고 1024 > 1000이다.

⑵ 귀류법 — ∼p를 가정하여 모순을 이끌어 낸다. 그러면 ∼p가 거짓이므로 ∼(∼p), 곧 p가 참이다. ∼(∼p) ≡ p (기초 논리 정리14의 이중부정법)

보기: 2는 무리수이다.
2가 유리수라고 가정하자. 그러면 공약수가 1뿐인 자연수 m, n이 있어 2 = mn이다. 양변을 제곱하여 정리하면 m² = 2n²이므로 m²은 짝수이고, 위 대우증명법의 보기에 의해 m도 짝수이다. m=2k로 놓으면 4k² = 2n², 곧 n² = 2k²이므로 같은 이유로 n도 짝수이다. m, n이 모두 2를 약수로 가지므로 "공약수가 1뿐"이라는 것과 모순이다. 따라서 2는 무리수이다.

쌍조건문

"p일 필요충분조건은 q이다"처럼 p↔q 꼴인 명제를 보이는 방법은 두 가지다.

⑴ 두 개의 조건문이 성립함을 증명 — p→q와 q→p를 따로따로 증명한다. p↔q ≡ (p→q)∧(q→p) (기초 논리 정리10) 두 방향에 서로 다른 방법을 써도 된다.

보기: 정수 n에 대하여 "n이 짝수일 필요충분조건은 n²이 짝수인 것이다."
(⇒) n=2k이면 n² = 4k² = 2(2k²)이므로 n²은 짝수이다(직접증명법).
(⇐) 위 대우증명법의 보기에서 이미 보였다.

⑵ 동치인 식의 열을 나열하는 방법 — 처음 명제에서 끝 명제까지, 이웃한 두 명제가 서로 동치가 되도록 고리를 잇는다. 고리마다 양쪽 방향이 모두 성립해야 한다는 점이 직접증명법과 다르다. [(p↔s₁)∧(s₁↔s₂)∧⋯∧(s_n↔q)] ⇒ (p↔q) (기초 논리 정리10으로 고리마다 두 방향의 조건문으로 나눈 뒤 정리13의 추이법칙을 거듭 적용)

보기: 양수 a, b에 대하여 a < b ⇔ a² < b²이다. a < b ⇔ b−a > 0 ⇔ (b−a)(b+a) > 0 ⇔ b²−a² > 0 ⇔ a² < b² 둘째 고리에서는 b+a > 0이므로 양변에 b+a를 곱하거나 b+a로 나누어도 부등호 방향이 그대로라는 사실 (양수를 곱하는 부등식)을 양쪽 방향으로 썼다.

여러 가지 경우를 나누는 형태

가정이 "p 또는 q"로 갈라지거나, 대상이 몇 가지 부류로 빠짐없이 나뉠 때는 부류마다 따로 증명한다. (p∨q)→r을 보이려면 p→r과 q→r을 보이면 된다. [(p→r)∧(q→r)] ⇒ [(p∨q)→r] 근거: 정리8로 조건문을 ∨ 꼴로 바꾸면 (∼p∨r)∧(∼q∨r) ≡ (∼p∧∼q)∨r ≡ ∼(p∨q)∨r (교환·분배법칙, 드모르간의 법칙)이므로 두 쪽은 사실 동치이다. 경우가 n개이면 [(p₁→r)∧(p₂→r)∧⋯∧(p_n→r)] ⇒ [(p₁∨p₂∨⋯∨p_n)→r] 이다. 이때 경우들이 모든 가능성을 덮는지(p₁∨⋯∨p_n이 참인지)를 반드시 확인해야 한다.

보기: 모든 정수 n에 대하여 n(n+1)은 짝수이다.
정수 n은 짝수이거나 홀수이다.

n이 짝수일 경우	n이 홀수일 경우
n=2k이면 n(n+1) = 2k(2k+1)이므로 짝수	n=2k+1이면 n(n+1) = 2(2k+1)(k+1)이므로 짝수

두 경우 모두 n(n+1)은 짝수이므로 모든 정수 n에 대하여 성립한다.

(∀x)(p(x))의 형태

"모든 x에 대하여 p(x)"를 보이는 방법이다. (∃x)(p(x))가 거짓임, 곧 (∀x)(∼p(x))를 보일 때도 같은 방법을 쓴다.

⑴ 모든 경우를 하나씩 확인한다. 전체집합이 유한집합일 때만 쓸 수 있다.

보기: 전체집합이 {1, 2, 3}일 때, 모든 x에 대하여 x²+x는 짝수이다.
x=1이면 2, x=2이면 6, x=3이면 12로 모두 짝수이다.

⑵ 임의의 원소를 택해 성립함을 보인다. x에 대해 "어떤 조건을 만족한다"는 것 외에는 아무것도 가정하지 않고 p(x)를 이끌어 내면, 그 논증은 모든 x에 그대로 통한다.

보기: 모든 실수 x에 대하여 x²−2x+2 > 0이다.
실수 x를 임의로 택하자. x²−2x+2 = (x−1)²+1이고 (x−1)² ≥ 0이므로 x²−2x+2 ≥ 1 > 0이다.

(∃x)(p(x))의 형태

"p(x)를 만족하는 x가 있다"를 보이는 방법이다. (∀x)(p(x))가 거짓임, 곧 (∃x)(∼p(x))를 보일 때도 여기에 속한다.

⑴ 실제 예를 찾아낸다. 조건을 만족하는 x를 하나 구체적으로 제시하고 확인한다. (∀x)(p(x))를 부정하기 위해 제시하는 (∃x)(∼p(x))의 예를 반례(反例, counterexample)라 한다.

보기: "모든 자연수 n에 대하여 n²+n+41은 소수이다."는 거짓이다.
n=1, 2, …, 39에서는 실제로 소수가 나오지만, n=40이면 40²+40+41 = 40·41+41 = 41²이므로 소수가 아니다. 이 n=40이 반례이다. 앞의 몇 경우가 맞는다는 것만으로는 "모든"을 증명할 수 없다는 점도 보여 준다.

⑵ 존재할 수밖에 없다는 것을 보인다. 그 x가 무엇인지 끝내 알려 주지 않으면서도, 없다고 가정하면 모순이 생김을 보이는 방법이다. 직접 구하기 어렵거나 구할 필요가 없을 때 쓴다(미적분의 중간값의 정리가 대표적인 도구다).

보기: 13명이 모이면 태어난 달이 같은 두 사람이 반드시 있다.
그런 두 사람이 없다고 가정하면 열두 달 각각에 태어난 사람이 많아야 1명이므로 전체는 많아야 12명이다. 이것은 13명이라는 것과 모순이다. 따라서 태어난 달이 같은 두 사람이 있다. 누구와 누구인지는 이 증명이 알려 주지 않는다.

← 간접증명법 수학적 귀납법 →

prerequisite:logic source:cki_math_lab-blog