증명법

증명의 이해

• 증명을 위해서 참(T)인 전제들이 주어져야 함
• 이 전제들의 결론 역시 참(T)이 되어 유효추론이 성립되면 정확한 증명이라고 할 수 있음
• 유효추론: 주어진 전제를 이용해 유도된 결론이 정확한 추론, 전제가 참일 때 결론이 모두 참인 추론

공리 (Axiom)

• 별도의 증명 없이 항상 참으로 이용되는 명제
• ex) 어떤 자연수 n에 대해, (n+1)이 존재한다.

정의 (Definition)

• 논의의 대상을 보편화하기 위해 사용하는 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식
• ex) 명제는 객관적인 기준으로 진릿값을 판별할 수 있는 문장이나 수식이다.

정리 (Theorem)

• 공리와 정의를 통해 참으로 확인된 명제
• ex) 피타고라스의 정리, 이항정리, 나머지정리 등

증명 (Proof)

• 하나의 명제가 참임을 확인하는 과정

---

직접증명법

• 명제의 변형 없이 공리·정의·정리를 이용하여 증명하는 방법
• 조건명제 p→q가 참임을 증명하기 위해 전제 p를 참으로 가정했을 때 결론 q도 참임을 증명하는 방법

직접증명법의 특징

• 논리적 연결: 공리, 정의, 그리고 이미 증명된 정리를 논리적으로 직접 연결하여 증명
• 변형 없음: 명제를 다른 형태로 변형하지 않고 그대로 증명
• 연역적 접근: 직접증명법은 연역(deduction)이라고도 불리며, 주어진 사실들과 공리들에 입각하여 추론을 통해 새로운 사실을 도출

---

간접증명법

• 증명하고자 하는 명제의 결론을 직접 증명하는 대신, 그 명제의 부정이나 대우를 이용하여 간접적으로 증명하는 방법

대우증명법

• 조건명제 p → q와 그의 대우 ¬q → ¬p가 동치임을 이용하여 증명하는 방법

대우법 예시: "x²-x 가 짝수이면, x는 짝수이거나 x는 홀수이다."의 증명
1. 대우 명제: "x가 짝수도 아니고 홀수도 아니면, x²-x는 홀수이다."
2. 논리학에서 전제가 거짓인 조건문은 항상 참(공허참)
3. 대우 명제가 참이므로 원래의 명제도 참

모순증명법(귀류법)

• 조건명제 p → q와 ¬(p∧¬q)가 동치임을 이용하여 p∧¬q가 거짓임을 보여 증명하는 방법
• 아래의 두 예시는 귀류법으로만 증명이 가능

귀류법 예시: "√2는 무리수이다."의 증명
1. 가정: √2 = a/b (a, b는 정수, b ≠ 0, a/b는 하한항)
2. 양변에 제곱: [2 = a²/b²] > [2b² = a²]
3. 2b²은 짝수이므로 a²도 짝수이고 a도 짝수
4. [a = 2k] > [4k² = a² = 2b²] > [b² = 2k²] 이므로 b는 짝수
5. a와 b가 모두 짝수이므로 a/b는 하한항이 아니게 됨, 따라서 √2가 하한항인 유리수라는 것은 거짓
6. a/b가 하한항인 유리수라는 가정이 모순되므로 √2는 무리수

귀류법 예시: "√5가 무리수일 때, √3+√5가 무리수이다."의 증명
1. p: √5는 무리수이다.
2. ¬q: √3+√5는 무리수가 아니다. (유리수)
3. p∧¬q: √5는 무리수이고 √3+√5는 유리수이다.
4. 가정: √3+√5 = a (a ∈ 유리수, a ≠ 0)
5. [√3 = a - √5] > [3 = a² - 2a√5 + 5] > [(a²+2)/2a = √5]
6. a는 유리수라고 가정했으므로 [(a²+2)/2a = √5]의 좌변은 유리수이지만 우변이 √5이므로 가정이 성립하지 않음
7. 따라서 p∧¬q인 "√5는 무리수이고 √3+√5는 유리수이다."가 거짓이므로 p → q는 참

존재증명법

• 주어진 명제가 참이 되는 예를 찾아서 증명하는 방법
• ∃xP(x)

반례증명법

• 주어진 명제에 모순이 되는 예를 찾아서 증명하는 방법
• ∃x¬P(x)

---

수학적 귀납법

• 0과 자연수에 대해 일정한 규칙을 나타내는 명제 P(n)이 성립하는 것을 증명하는 방법

구분	특징
기본가정	명제의 논의영역의 첫 번째 값 a에 대해 P(a)가 참임을 보인다.
귀납가정	논의영역에 속하는 임의의 값 k에 대해 P(k)가 참이라고 가정한다.
귀납증명	기본가정과 귀납가정을 이용해 (k+1)에 대해 P(k+1)이 참인지 증명한다.