이 글은 이산수학에서 헷갈리는 개념인 간접 증명(귀류법)을 쉽게 이해하고자 작성된 글이다. 직접 증명과의 비교와 구체적 예시를 통해 설명한다. 내가 이해한 내용을 바탕으로 정리한 글이기 때문에 내용 상 오류가 있을 수 있음을 미리 밝힌다.
(간접증명은 모순에 의한 증명이나 귀류법으로 불리기도 한다.)
🏹직접 증명과 간접 증명의 목표
직접 증명과 간접 증명은 둘 다 조건 명제의 참과 거짓을 판별하는 데 그 의의가 있다.
조건 명제란 명제 p와 q에 대해, "p이면 q이다." 라고 표현한 명제이다.
📌직접 증명
직접 증명은 선 인정, 후 반박하는 형태이다.
영희 : "교실 책상에 있던 네 마카롱 내가 먹은 거 아니라니까? 난 계속 운동장에 있었다고."
철수 : "그래, 네 말이 맞다고 치자. 그럼 내 책상 위에 있던 너의 머리카락은 어떻게 설명할건데?"
위의 대화를 살펴보자. 영희는 철수의 초콜릿이 사라진 시간에 본인이 운동장에 있었다고 주장하고 있다. 철수에게 있어 이 주장은 가설이 된다. 그리고 철수는 '영희가 본인의 초콜릿을 먹었다'라는 결론을 이끌어내려 하기 위해 먼저 영희의 가설을 맞다고 인정해주고 있다.
📌간접 증명(귀류법)
개념
간접 증명은 일단 결론을 부정하고, 그 근거를 제시하는 형태이다.
영희 : "교실 책상에 있던 네 마카롱 내가 먹은 거 아니라니까? 난 계속 운동장에 있었다고."
철수 : "네가 운동장에 있었다손 치더라도, 너는 내 마카롱을 먹었을 거야. 왜냐하면 내 책상 위에 너의 머리카락이 떨어져 있었거든."
위의 대화를 살펴보자. 철수는 영희의 말을 냅다 반박부터 하고 있다. 즉 영희의 가설은 인정하더라도, 결론은 부정하는 것이다. 그 후 영희의 머리카락이라는 증거를 이용해 영희의 가설이 이와 모순된다는 것을 증명하고 있다.
증명 원리
간접 증명이 가능한 이유는 어차피 결론은 참 또는 거짓 두 가지 밖에 존재하지 않기 때문이다.
"너가 마카롱 먹은 범인이지? 아님 말고. 어차피 너가 범인이거나 아니거나 둘 중 하나지 뭐."
