[이산 수학] 직접 증명법

직접 증명법

• 직접 증명법은 주어진 명제를 변형하거나 예를 구하는 것이 아니라, 공리, 정의, 정리 등을 이용하여 주어진 그대로 증명하는 방식이다.

 

직접 증명법(Direct Proof)

조건 명제 `p → q` 가 참(T)임을 증명하기 위해 전제 `p` 를 참(T)으로 가정했을 때, 결론 `q` 도 참(T)임을 증명하는 방법

 

예 : '두 홀수 `m` 과 `n` 의 곱은 홀수이다.' 를 직접 증명법으로 증명하기

• '두 홀수 `m` 과 `n` 의 곱은 홀수이다' 라는 명제를 조건 명제의 형태로 나타내면 다음과 같다.

`p → q` : 두 정수 `m, n` 이 홀수이면, `m` 과 `n` 의 곱은 홀수이다.
`p` : 두 정수 `m, n` 은 홀수이다.
`q` : `m` 과 `n` 의 곱은 홀수이다.

 

• 홀수 `m` 과 `n` 은 홀수의 정의에 따라 다음과 같이 표현할 수 있다.

$$m = 2k + 1 \; (k ∈ \mathbb{Z}), \quad n = 2l + 1 \; (l ∈ \mathbb{Z})$$

• 위와 같이 표현한 두 홀수 `m` 과 `n` 의 곱 `mn` 을 구하면 다음과 같다.

$$mn = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1 = 2a + 1 \quad \text{(2kl + k + l을 a로 치환)}$$

 

• 홀수 정의에 따라 계산 결과인 `2a + 1` 은 홀수이다. 
• 따라서 홀수 `m` 과 `n` 의 곱 `mn` 은 홀수이므로, 주어진 명제 '두 홀수 `m` 과 `n` 의 곱은 홀수이다'가 참(T)임을 증명할 수 있다.
• 이 예에서는 조건에 해당하는 명제 `p` (두 정수 `m, n` 은 홀수이다)를 그대로 이용하여 결론 `q` (`m` 과 `n` 의 곱은 홀수이다)가 참(T)임을 판단할 수 있다.
  • 이처럼 조건으로 주어진 명제를 증명에 직접 이용할 수 있는 경우에 직접 증명법을 사용한다.