[이산 수학] 간접 증명법

간접 증명법

• 간접 증명법은 증명해야 하는 명제를 변형하여 증명하는 방법으로, 모순 증명법, 대우 증명법 그리고 존재/반례 증명법이 있다.
  • 모순 증명법 : 증명해야 하는 조건 명제에서 결론에 해당하는 명제를 부정하여 증명하는 방법
  • 대우 증명법 : 증명해야 하는 조건 명제를 대우 명제로 변형하여 증명하는 방법
  • 존재/반례 증명법 : 명제를 참(T)으로 만드는 원소가 있는지, 혹은 명제를 거짓(F)으로 만드는 원소가 있는지를 판단하여 증명하는 방법

 

모순 증명법(Proof by Contradiction)

조건 명제 `p → q` 와 $\neg (p \land \neg q)$ 가 동치임을 이용해, $p \land \neg q$ 가 거짓(F)임을 보임으로써 증명하는 방법

$\neg (p \land \neg q)$
$≡ \neg p \lor \neg (\neg q)$    (∵ 드 모르간의 법칙)
$≡ \neg p \lor q$    (∵ 이중 부정 법칙)
$≡ p → q$    (∵ 함축 법칙)

• $\neg(p \land \neg q)$ 에서 알 수 있듯이, 모순 증명법은 결론에 해당하는 명제 `q` 를 부정(NOT)하여 증명하는 방식이다.
• $p \land \neg q$ 의 진릿값이 거짓(F)이면 증명해야 하는 본 명제 $p → q$ 가 참(T)이라고 확인할 수 있는 증명법이다.

 

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

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

`p` : 두 정수 `m, n` 은 홀수이다.
`q` : `m` 과 `n` 의 곱은 홀수이다.
$\neg q$ : `m` 과 `n` 의 곱은 홀수가 아니다. (짝수이다.)
$p \land \neg q$ : 두 정수 `m, n` 은 홀수이고, `m` 과 `n` 의 곱은 홀수가 아니다. (짝수이다.)

 

• 명제 `p` 는 '두 정수 `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` 은 홀수이다.
  • 그러므로 명제 $p \land \neg q$ '두 정수 `m, n` 은 홀수이고, `m` 과 `n` 의 곱은 홀수가 아니다(짝수이다)'는 거짓(F)이다.
  • 결국 $\neg (p \land \neg q)$ 는 참(T)이고, 이 명제와 동치인 본 명제 '두 홀수의 곱은 홀수이다'는 참(T)이라고 결론지을 수 있다.

 

대우 증명법(Proof by Contrapositive)

조건 명제 `p → q` 와 이에 대한 대우 명제 $\neg q → \neg p$ 가 동치임을 이용하여 증명하는 방법

• 명제에 따라서 주어진 조건으로 증명하기 어려운 경우도 있다.
  • 예를 들어, 명제 '두 정수 `m` 과 `n` 의 곱이 홀수이면, `m` 과 `n` 은 모두 홀수이다' 는 조건에 해당하는 명제 '두 정수 `m` 과 `n` 의 곱이 홀수이다' 를 이용하여 결론에 해당하는 명제 '`m` 과 `n` 은 모두 홀수이다'를 증명하는 것이 간단하지 않다.
  • 이처럼 조건 그대로를 증명에 활용하기에 제약이 있는 경우, 대우 명제의 형태로 바꿔서 증명해야 한다.
• 대우 증명법은 대우 명제가 본 명제와 같은 진릿값을 갖는다는 특징을 이용한 증명법이다.
  • 본 명제에 대한 대우 명제를 구하고, 대우 명제가 참(T)임을 증명함으로써 본 명제도 참(T)임을 증명한다.

 

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

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

`p → q` : 두 정수 `m` 과 `n` 의 곱이 홀수이면, `m` 과 `n` 은 모두 홀수이다.
`p` : 두 정수 `m` 과 `n` 의 곱이 홀수이다. 
`q` : `m` 과 `n` 은 모두 홀수이다.
$\neg p$ : 두 정수 `m` 과 `n` 의 곱은 홀수가 아니다. (짝수이다.)
$\neg q$ : `m` 과 `n` 중 적어도 하나는 홀수가 아니다. (짝수이다.)
$\neg q → \neg p$ : `m` 과 `n` 중 적어도 하나는 홀수가 아니다. (짝수이다.)
                                 두 정수 `m` 과 `n` 의 곱은 홀수가 아니다. (짝수이다.)

 

• 대우 명제의 조건에 해당하는 명제 $\neg q$ '`m` 과 `n` 중 적어도 하나는 홀수가 아니다(짝수이다)'는 `m` 과 `n` 중 하나만 짝수인 경우와 `m` 과 `n` 모두 짝수인 경우를 모두 고려하여 증명해야한다.
• 그래서 두 경우 모두에 대하여 대우 명제가 참(T)이라고 증명되면, 명제 '`m` 과 `n` 중 적어도 하나는 홀수가 아니면(짝수이면), 두 정수 `m` 과 `n` 의 곱은 홀수가 아니다(짝수이다)' 가 참(T)이라고 할 수 있다.

 

(i) `m` 과 `n` 중 하나만 짝수인 경우

• $m = 2k \; (k ∈ \mathbb{Z}), \quad n = 2l + 1 \; (l ∈ \mathbb{Z})$ 로 가정하고 `m` 과 `n` 의 곱을 구하면 다음과 같다.

$$mn = 2k(2l + 1) = 4kl + 2k = 2(2kl + k)$$

• 위 결과처럼 `m` 과 `n` 중 하나만 짝수인 경우, `m` 과 `n` 의 곱 `mn` 은 짝수이다.
  • 그러므로 두 정수 `m` 과 `n` 중 하나만 짝수이면, `m` 과 `n` 의 곱은 홀수가 아니다.

 

(ii) `m` 과 `n` 모두 짝수인 경우

• $m = 2k \; (k ∈ \mathbb{Z}), \quad n = 2l \; (l ∈ \mathbb{Z})$ 로 가정하고 `m` 과 `n` 의 곱을 구하면 다음과 같다.

$$mn = 2k × 2l = 4kl = 2(2kl)$$

• 위 결과처럼 `m` 과 `n` 모두 짝수인 경우, `m` 과 `n` 의 곱 `mn` 은 짝수이다.
  • 그러므로 두 정수 `m` 과 `n`이 모두 짝수이면, `m` 과 `n` 의 곱은 홀수가 아니다.

 

• 위의 두 가지 경우에 대한 증명을 통해 대우 명제 '`m` 과 `n` 중 적어도 하나는 홀수가 아니면(짝수이면), 두 정수 `m` 과 `n` 의 곱은 홀수가 아니다(짝수이다)' 가 참(T)임을 보였다.
  • 그러므로 본 명제 '두 정수 `m` 과 `n` 의 곱이 홀수이면, `m` 과 `n` 은 모두 홀수이다' 는 참(T)임 또한 증명된다.
• 다음과 같이 `m` 과 `n` 이 모두 홀수인 경우 또한 증명할 수 있다.

 

(iii) `m` 과 `n` 모두 홀수인 경우

• $m = 2k - 1 \; (k ∈ \mathbb{Z}), \quad n = 2l - 1 \; (l ∈ \mathbb{Z})$ 로 가정하고 `m` 과 `n` 의 곱을 구하면 다음과 같다.

$$mn = (2k - 1)(2l - 1) = 4kl - 2k - 2l + 1 = 2(2kl - k - l) + 1$$

• 위 결과처럼 `m` 과 `n` 모두 홀수인 경우, `m` 과 `n` 의 곱 `mn` 은 홀수이다.
  • 그러므로 두 정수 `m` 과 `n`이 모두 홀수이면, `m` 과 `n` 의 곱은 홀수이다.

 

존재  증명법(Existence Proof : $\exists x \; P(x)$)

명제가 참(T)이 되는 예를 찾아서 증명하는 방법

 

예 : 어떤 소수 `n` 에 대하여 `n + 4` 도 소수인지 증명하라.

• 소수는 1과 자기 자신만을 약수로 갖는 자연수로, $2, 3, 5, 7, 11, 13, \cdots$ 가 있다.
• 각 소수에 4를 더하면 $6, 7, 9, 11, 15, 17, \cdots$ 인데, 이 중 7(3+4), 11(7+4), 17(13+4)의 경우에는 여전히 소수이다. 그러므로 `n + 4` 를 소수로 만드는 소수 `n` 이 있음을 알 수 있다.
  • ∴ 명제 '어떤 소수 `n` 에 대하여, `n + 4` 도 소수이다' 는 참(T)이다.

 

반례 증명법(Proof by Counter-Example : $\exists x \; \neg P(x))$

• 반례 증명법은 존재 증명법과 달리, 증명을 위해 주어진 명제를 거짓(F)으로 하는 예를 찾아서 명제가 거짓(F)임을 증명하는 방법이다.

명제가 모순이 되는 예를 찾아서 증명하는 방법

 

예 : 모든 소수 `n` 에 대하여 `n + 4` 도 소수인지 증명하라.

• 소수는 1과 자기 자신만을 약수로 갖는 자연수로, $2, 3, 5, 7, 11, 13, \cdots$ 가 있다.
• 각 소수에 4를 더하면 $6, 7, 9, 11, 15, 17, \cdots$ 인데, 6, 9, 15는 소수가 아니다.
•  그러므로 모든 소수 `n` 에 대하여 `n + 4` 가 소수인 것은 아님을 알 수 있다.
  • ∴ 명제 '모든 소수 `n` 에 대하여, `n + 4` 도 소수이다' 는 거짓(F)이다.