귀류법에 대한 쉽고 자세한 이해

수학, 논리학, 수리논리학

수학자들이 가장 선호(?) 하는 증명 방법 중에 하나가 귀류법입니다. 그만큼 강력하기도 하고 과제할 때 귀류법으로 모순을 보였을 때의 짜릿함을 못 잊어서 일 것도 같습니다.

귀류법에 대한 인터넷 수학밈

그런데 인터넷상에서 귀류법에 대해서 잘못 설명되는 경우를 많이 보아서 맷수달이 한번 짤막하지만 핵심을 자세히 풀어서 설명해 보겠습니다.

귀류법에 대한 직관적인 현실의 예제는 다음과 같은 것이 있습니다. 주로 법정 영화 같은 곳에서 많이 볼 수 있는 장면인데요.

예를 들어

피고인: 저는 그날 밤 9시에 집에서 TV를 보고 있었어요.

검사: 피고인의 말을 맞다고 가정해 보겠습니다. 범죄 현장은 피고인의 집에서 1시간 이상이나 떨어져 있죠. 그런데 그날 밤 9시에 피고인을 범죄 현장에서 보았다는 증인이 있습니다. 그러므로 피고인은 지금 모순된 거짓말을 하고 있는 것입니다!

이것 이외에서 흔히들 "그래 너 말이 맞다고 해 보자. 그런데~" 이런 식으로 논증을 진행하는 방식이 귀류법의 방식이라고 말할 수 있겠습니다.

그런데 귀류법에 대해서 하나 헷갈려하는 부분이 있는데요. 귀류법은 증명하고자 하는 조건명제에 대한 결론을 부정해서 논증을 진행하는 것이 아닙니다.

증명하고자 하는 조건명제 자체에 대해 부정을 하고 논증 전개를 해서 Contradiction (모순)을 이끌어 내는 증명법이 귀류법입니다.

이 부분에 대해서 구체적으로 논리식으로 살펴보겠습니다.

위의 대한 논리적 정당성은 아래의 동치관계에 근거합니다.

If (~(P=> Q) ≡ (P and ~Q)) => C, (여기서 C는 Contradiction을 의미)

then P=>Q ≡ T, (vice versa)

위의 내용을 분석해 보겠습니다.

우리가 증명하고자 하는 명제 R이 P=> Q 라 하면

귀류법의 수행 절차는 아래와 같습니다.

1. 명제 R을 부정

~R ≡ (P and ~Q)

2. ~R을 True (참)로 가정 한 뒤 연역 추론

3. 연역 추론의 결과 ~P가 유도됨

4. 이것은 (P and ~P)가 발생한 것으로 Contradiction (모순)을 의미.

5. 4번까지 유도된 내용의 결과는 다음의 조건명제로 요약 가능

~R => C

6. 그러므로 (~R => C ≡ (P and ~Q) => C) => ((P=> Q) ≡ R ≡ T)

(즉, 풀어서 설명하면 ~R => C ≡ R 이므로  ~R => C를 연역추론으로 유도했다는 의미는 R이 참임을 증명했다는 의미입니다.)

Note: 

1. 위에서 ~R => C의 결과가 True 이므로 ~R이 가질 수 있는 값은 False 밖에 없으므로 배중률에 의해 R은 자동으로 True가 됩니다.

2. 참고로 실제로 증명할 때는 3번에서 모순이 발생하면 거기서 모순이 발생했음을 기호 등으로 선언하고 증명을 끝냅니다. 아래의 4,5,6은 이해를 돕기 위해 적은 추가 내용이고 실제 증명의 결과에 영향을 끼치지 않습니다.

3. 4번에서 모순이 발생하면 모순을 발생했음을 선언하는 여러 가지 기호가 있는데요. 주로 사용되는 기호들은 ⊥, -><-, ※, ↯ 등입니다.