[이산수학] 증명

증명이란?

---

증명은 가정에서 논리적 법칙을 이용하여 결론을 이끌어내는 것을 말한다. 이때 추론이 참이면 진위 추론이라 하고, 추론이 거짓이면 허위 추론이라 한다. 그리고 별도의 증명 없이도 항상 참(T)이라고 판단되는 명제를 공리라고 한다.

증명의 방법에는 대표적으로 직접 증명볍, 간접 증명볍, 수학적 귀납법이 있다. 증명을 이해하는 데에는 명제와 논리에 대한 이해가 필요하다. 이에 대한 부분은 전 포스팅을 참고하기 바란다.

2024.06.28 - [수학/이산수학] - [이산수학] 명제와 논리

[이산수학] 명제와 논리

 

직접 증명법

---

조건명제 p→q가 참(T)임을 증명하기 위해 전제 p를 참(T)으로 가정했을 때, 결론 q도 참(T)임을 증명하는 방법이다. 여기에도 두 가지 방법이 있다.

• p→q의 vacuous 증명 방법: p가 거짓이라 하면 p→q는 항상 참이다. 그래서 p→q가 참인 것을 보이기 위해 p가 거짓이라는 것만 보이면 된다.
• p→q의 trivial 증명 방법: q가 참이라고 하면 p→q는 참이다. 그래서 p→q가 참인 것을 보이기 위해 q가 참이라는 것만 보이면 된다.

 

간접 증명법

---

가정된 명제로부터 추론에 의해서 결론에 직접 도달되기가 어려운 경우에 간접적으로 결론이 참인 것을 이끌어내는 방법이다. 대표적으로 모순, 대우 증명, 반례 증명, 존재 증명의 4가지로 나누어 볼 수 있다.

• 모순 증명법: 조건명제 p→q와 ￢(p ∧ ￢q)가 동치임을 이용해 p ∧ ￢q가 거짓(F)임을 보임으로써 증명하는 방법이다.
• 대우 증명법: 조건명제 p→q와 이에 대한 대우 명제 ￢ q→￢p가 동치임을 이용하여 증명하는 방법이다.
• 존재 증명법: 명제가 참(T)이 되는 예를 찾아서 증명하는 방법이다.
• 반례 증명법: 명제가 모순이 되는 예를 찾아서 증명하는 방법이다.

 

수학적 귀납법

---

수학적 귀납법은 k를 어떤 정수라 할 때, 어떤 명제 P(n)이 n >= k(단, n은 정수)인 모든 수에 대해서 모두 참(T)인 것을 보여주기 위한 방법이다. 수학적 귀납법의 방법은 다음과 같다.

1. 기본 가정: 명제의 논의영역 D의 첫 번째 값 d에 대하여, P(d)가 참(T)임을 보인다.
2. 귀납 가정: 논의영역에 속하는 임의의 값 k에 대하여, P(k)가 참(T)이라고 가정한다.
3. 귀납 증명: 기본 가정과 귀납 가정을 이용해 논의영역에 속하는 값 k + 1에 대하여, P(k + 1)이 참(T)임을 증명한다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!