최근 수정 시각 : 2019-07-08 02:34:55

귀류법

파일:Semi_protect1.png   로그인 후 편집 가능한 문서입니다.

1. 개요2. 설명3. √2가 무리수임의 증명
3.1. 초보적인 증명 : √2가 유리수가 아님의 증명3.2. 해석학적으로 진짜 엄밀한 증명
4. 여담

1. 개요

歸謬法

수학과 논리학의 증명법 중 하나.

어떤 명제가 거짓이라고 가정한 후 추론했을 때, 모순이 발생함을 이끌어내어 가정이 거짓임을, 즉 처음의 명제가 참임을 증명하는 방법이다. 일상 언어 생활에서도 은근히 자주 볼 수 있는 방식이다. ''그래, 네 말이 맞는다고 치자. 그렇게 했는데 문제가 생겼네. 따라서 니말이 틀렸어"식의 말이 다름 아닌 귀류법.

수학에서는 흔히 간접적 증명이라고도 부른다.

2. 설명

불합리로의 회귀, Reductio ad absurdum; RAA (라틴어)

기본적인 추리 규칙 중 하나이면서 간접증명법 중의 하나로 논증의 타당성을 보이기 위해 사용한다.

어떤 논증이 있다고 하자.
pp
q\therefore q

위 논증에서 pp는 전제들을 통칭하며, qq는 결론을 말한다. 모든 논증은 그와 상응하는 조건명제(Conditional statement)로 바꾸어 쓸 수 있다. 따라서 위 논증은
pqp\rightarrow q
라는 조건명제를 가리킨다. 이 조건명제가 항진일때, 그리고 오직 그 때에만 위 논증은 타당하다
만약 전제들 pp가 참이면 qq가 참임을 보여야 논증이 타당해지는데, 직접적으로 추론이 불가능한 경우, 다음과 같은 과정을 거친다.
pqp\rightarrow q 라는 조건명제의 논리적 동치는 (pq)\sim(p\wedge\sim q) 이며[1], 이 명제와 논리적 동치는 다음과 같다.
(pq)F(p\wedge\sim q)\rightarrow F
위 조건명제의 후건은 FF를 말하는데 이것은 진리값 할당이 항상 거짓(False)임을 의미한다. 위 조건명제에 진리값을 할당해보면, 우리는 위 조건명제가 바로 pqp\rightarrow q 와 논리적 동치임을 알 수 있다.
"모든 논증은 그와 상응하는 조건명제와 바꾸어 쓸 수 있으며, 모든 조건명제는 그와 상응하는 논증과 바꾸어 쓸 수 있다."
그러므로, 우리는 (pq)F(p\wedge\sim q)\rightarrow F 를 다음과 같은 논증으로 바꾸어 쓸 수 있다.
pp
q\sim q
F\therefore F
위 논증을 설명하면, "결론 qq를 부정하면 q\sim q가 되는데 그것을 다른 전제들 pp 과 똑같이 [전제들]로 가정한 후에, 연역을 통해 모순을 이끌어내면 원래 논증이 타당하는 것" 을 의미한다. 이것이 바로 우리가 논리학, 기호논리학, 수학에서 말하는 귀류법의 진정한 의미이다.
그런데 인터넷상에서 그리고 학교내의 강의에서 심지어 수학 전공자들, 수학 강사들, 수학 교사들마저도 귀류법에 대해서 잘못된 서술을 하는 경우가 많은데, 그 중 가장 많은 오류가 바로 다음과 같은 설명이다.

잘못된 설명 : " pqp\rightarrow q 를 증명하기가 까다로우니 pqp\rightarrow\sim q 를 가정하고 [모순]을 이끌어낸다. 이것이 귀류법이다."

라는 잘못된 설명이 가장 많은 사례로 발견된다. 이것은 귀류법에 대한 엄청난 오개념이다. 위에서 설명했다시피 귀류법은 pqp\rightarrow\sim q 임을 가정하는게 아니라, (pq)(p\wedge\sim q)임을 [전제]로 한 설정한 다음에, 그것으로부터 FF = 모순을 이끌어냄으로써 (pq)F(p\wedge\sim q)\rightarrow F 가 항진임을 증명한다. 그래서 그것과 논리적 동치인 pqp\rightarrow q가 항진임을 보이는 것이다. 그러니까, q\sim q 가 조건 명제의 후건에 위치해서는 안되고, 반드시 [전제]에 들어가야 한다는 뜻이다. 즉, (pq)(p\wedge\sim q)자체가 하나의 전제가 되어야 한다.
따라서, 귀류법에 대해 제대로 설명하면 다음과 같이 설명해야 한다.

올바른 설명: "pqp\rightarrow q 를 증명하기가 까다로우니 (pq)(p\wedge\sim q) 를 [전제]로 가정하고 [모순]을 이끌어낸다. 이것이 귀류법이다."

전제들이 여러개인 형태 : (pqrst)z(p\wedge q\wedge r\wedge s\wedge t)\rightarrow z 또한 귀류법을 적용하면, (pqrstz)F(p\wedge q\wedge r\wedge s\wedge t\wedge\sim z)\rightarrow F 로 증명하면 된다. 결론을 부정해서 전제에 추가한 다음, 모순을 이끌어낸다.
다음 주어진 논증을 예로 들어보겠다. 전제들이 여러개이지만, 귀류법을 적용하는 것은 쉽다.
전제 :A(BC):\quad A\rightarrow(B\wedge C)
전제 :(BD)E:\quad (B\vee D)\rightarrow E
전제 :DA:\quad D\vee A
결론 :E:\quad \therefore E
위 논증의 타당성을 귀류법으로 증명해보이겠다. 우리는 결론 EE 를 부정한 다음에 그것을 반드시 전제에 넣어야 한다.
전제 :A(BC):\quad A \rightarrow(B\wedge C)
전제 :(BD)E:\quad (B\vee D)\rightarrow E
전제 :DA:\quad D\vee A
전제 :E:\quad \sim E
이런식으로 결론을 부정한 후에 그것을 전제에 추가한 다음, 위 전제들로부터 결론을 FF = 모순으로 이끌어내야 한다. 아래는 추론과정이다.
전제 1.A(BC)1.\quad A\rightarrow(B\wedge C)
전제 2.(BD)E2.\quad (B\vee D)\rightarrow E
전제 3.DA3.\quad D\vee A
전제 4.E4.\quad \sim E
추론 5.(BD)5.\quad \sim(B\vee D)\quad\quad (∵전제 4, 전제 2의 대우)
추론 6.BD6.\quad \sim B\wedge\sim D\quad\quad (∵추론 5 → 드 모르간의 법칙)
추론 7.DB7.\quad \sim D\wedge\sim B\quad\quad
추론 8.D8.\quad \sim D\quad\quad\quad\quad\;\;\;
추론 9.A9.\;\;\quad A\quad\quad\quad\quad\quad\;\;\, (∵전제 3)
추론 10.BC10.\quad B\wedge C\quad\quad\quad\;\; (∵추론 9, 전제 1)
추론 11.B11.\quad B\quad\quad\quad\quad\quad\;\;\,
추론 12.B12.\quad\sim B\quad\quad\quad\quad\;\, (∵추론 7)
추론 13.BB13.\quad B\wedge\sim B\quad\quad\quad (∵추론 11, 추론 12)
결론 14.F14.\quad F\quad
위 증명의 방식이 우리가 흔히 말하는 추론이다. 전제들로부터 차례대로 아래로 내려오면서 연역을 통해 결론을 도출한다.
A(BC)A\rightarrow(B\wedge C), (BD)E(B\vee D)\rightarrow E, DAD\vee A, E\sim E 이러한 전제들이 참(True)이라 가정했을때, 결론이 모순 FF가 나오므로 우리는 원래 주어진 논증이 타당함을 알 수 있다. 이렇게 전제들이 여러개 일떄도 그냥 결론을 부정한 다음, 전제들에 추가하면 된다. 그리고 모순을 이끌어낸다.


또 다른 예를 들어보자. 이번엔 간단한 수학이다.
"정수 aabb가 덧셈에 대한 항등원이라 하자. 그러면 a=ba=b이다."
일단, 위 논증을 분석해보자. "정수 aabb가 덧셈에 대한 항등원이다. " 라는 명제는 전제이고, "a=ba=b이다. " 라는 명제는 결론이다.
위 논증은 "정수 aabb가 덧셈에 대한 항등원이면 a=ba=b 이다." 라는 조건명제꼴로 바꿀 수 있다. 즉, pqp\rightarrow q 꼴의 조건명제라고 볼 수 있다.
위 논증을 귀류법으로 증명한다고 해보자.
pqp\rightarrow q 꼴의 조건명제를 귀류법으로 증명하려면 (pq)(p\wedge\sim q) 를 전제로 가정하고 모순을 이끌어내라고 분명히 설명했다.

" 전제 : 정수 aabb가 덧셈에 대한 항등원이고, a=ba=b가 아니라고 가정하자." ---- (pq)(p\wedge\sim q)

전제1 : 정수 aabb가 덧셈에 대한 항등원이다.
전제2 : aba\neq b이다.
추론과정(1) : 전제1에 의해 a+b=aa+b = a 이고, b+a=bb + a = b (둘 다 항등원이라는 전제)
추론과정(2) : 정수의 성질에 의해 a+b=b+aa+b = b + a (정수의 성질은 전제에 나와있지는 않지만 암묵적인 전제.)
추론과정(3) : 따라서 a=ba=b이다.
추론과정(4) : [aba\neq b이다]라고 전제에 나와있는데 동시에 [a=ba = b이다]라는 추론이 나온다.
추론과정(5) : 어떤 명제가 참인 동시에 거짓이라는 것은 모순이다.
마침내 결론 : 따라서 a=ba=b가 아니다. 라고 가정하면 모순이 나온다.

이 간단한 증명에서도 나와있지만, 결국 pqp\rightarrow q 형태를 귀류법으로 증명하는 것은
(pq)(p\wedge\sim q) 를 가정한 다음에 모순을 보이는 것이다. 이게 제일 중요하다. 절대 pqp\rightarrow\sim q를 가정하는게 아님을 명심하자.


그렇다면 "2\sqrt{2}가 무리수이다." 를 귀류법으로 증명하라는 것은 어떻게 이해해야 할까?
위에서 서술한 것처럼 pqp\rightarrow q 꼴의 명제가 아니라, 단지 결론 하나만 덜렁 존재하는 경우다. 이것은 사실 전제가 없는 것이 아니라, 수학적 사실들(공리, 정리 따위들)을 암묵적으로 전제로 가정하고 있다고 봐야 한다. 수학이나 논리학에서 항진명제가 아닌 어떤 우연 명제가 참이라는 것은 다른 공리나 전제들로부터 도출되는 것이지, 자기 혼자서 참이라는 것을 주장하는 것이 아니다. 이 명제를 다시 쓰면 다음과 같다.
"수학의 공리들이 참이고 수학의 정리들이 참이다. 그러한 전제들에 의해 2\sqrt{2}가 무리수이다. "
"(pqrst)z(p\wedge q\wedge r\wedge s\wedge t)\rightarrow z 의 형태"
즉, 이미 수학적 사실들을 전제로 존재한다음, 그것으로부터 "2\sqrt{2}가 무리수이다." 라는 결론이 도출되는 셈이다. 그래서 여기에 귀류법을 적용하는 것도 마찬가지로 똑같다. "2\sqrt{2}가 무리수이다." 를 부정한다음, 그것을 우리가 알고 있는 수학의 공리, 정리들과 함께 전제로 취급한 다음, 모순을 이끌어내면 된다.

"수학의 어떤 공리들과 정리들이라는 전제들이 참이고 2\sqrt{2}는 무리수가 아니라고 한다면, 모순이 나온다. "
"(pqrstz)F(p\wedge q\wedge r\wedge s\wedge t\wedge\sim z)\rightarrow F 의 형태"

그런데 실제 증명에서는 암묵적인 전제들을 전부 일일이 찾아서 나열하지 않고, 그냥 결론을 부정한 후에 추론할때마다 하나씩 하나씩 전제들들을 추가시키면서 증명을 한다. 그래서 그냥 결론을 부정한 다음,
q\sim q
F\therefore F
위 추론과정에서 전제들을 하나씩 추가하면서 q\sim q 으로부터 모순을 이끌어낸다. 본문이 이해가 되지 않는다면, 처음부터 다시 자세히 읽어보고 그래도 이해가 안된다면 위키러들에게 논리학이나 기호논리학을 공부해보길 권한다. 수학의 연역적 추론은 기호 논리학의 형식적 연역 추론에 밑바탕을 두고 있기 때문에 이러한 사소한 논리적 지식 하나하나가 수학의 증명 능력에 상당한 영향을 미친다.

3. √2가 무리수임의 증명

고등학생 레벨에서 제일 유명한 사례는 √2가 무리수임을 증명하는 문제. 원래는 서울대학교 본고사 문제였다. 나왔을 당시에는 수험생들에게 충격과 공포를 선사해 주었다고 하지만 특별한 테크닉이 필요없어 난이도도 상당히 낮고, 문제가 뜬 뒤로 전국에 소개되어 지금은 제대로 공부한 고등학생이면 누구든지 증명할 수 있는 문제가 되어 버렸다. (일부 중3 교과서에도 나오고, 사실 과고 대비 중이라면 중학교 저학년 때 찝적거릴 수도 있다.)

2=p/q\sqrt{2}= p/q (단 ppqq서로소자연수[2].)로 놓은 다음에, 양변을 제곱하여 ppqq가 모두 22의 배수가 된다는 것을 증명하는[3][4] 방식으로 한다.

3.1. 초보적인 증명 : √2가 유리수가 아님의 증명

고등학교 교과과정상으로는 다음과 같은 과정을 거친다.
  1. 고등학교 교과과정에서 무리수를 "유리수가 아닌 실수"로 정의함을 안다.
  2. 유리수의 정의가 "서로소인 두 정수 ppqq가 있을 때, p/qp/q(단, q0q\ne0)로 표현 가능한 수"임을 설명한다.
  3. m2m^222의 배수이면 mm22의 배수임을 보인다.[5]
  4. 귀류법을 이용하여 2\sqrt{2}가 유리수라고 가정했을 때, ppqq22라는 공통인수를 가짐을 보인다.[6]
  5. 이는 ppqq가 서로소라는 가정에 모순이므로 2\sqrt{2}가 무리수라고 결론짓는다.

3.2. 해석학적으로 진짜 엄밀한 증명

위의 증명에서 논리적 비약을 찾았는가? 엄밀히 말해서 위의 증명은 무리수인 2\sqrt{2}가 실수라는 것을 그냥 깔고 들어가고 있다.[7] 즉, 2\sqrt{2}가 실수 집합에 속한다는 것이 먼저 증명되어야 한다.

실수의 구성방법에는 공리적 방법과 구성적 방법이 있는데, 구성적 방법은 페아노 공리계로부터 시작해 유리수를 구성하고, 데데킨트 절단이나 코시 수열을 이용하여 무리수를 만드는 방법이다. 공리적 방법은 체의 공리, 완비성 공리, 순서 공리를 만족하는 수체계를 실수라고 정의하는 방법이다. 일반적으로는 공리적 방법을 많이 사용한다. 구성적 방법으로 실수를 구성하는 것은 매우 어렵다. 혹시 궁금하다면 Rudin의 Principle of Mathematical Analysis의 1장 부록에 실수 구성 방법이 10단계에 걸쳐 나와 있다. 이해할 수만 있다면 말이지

중등교육과정은 이러한 공리들을 언급하고 있지 않기 때문에, 관념적으로 사용하는 실수에 대해 모든 양수에는 제곱근이 되는 실수가 당연히 있다고 가정하고 있기에 여기까지만 해도 증명이 되지만, 대수학적으로는 2\sqrt{2}가 무리수임을 보이려면 2\sqrt{2}가 실수임을, 다시 말해 완비성 공리를 이용하여 실수체의 원소 중에 x2=2 x^2 = 2 를 만족하는 원소가 있는지를 먼저 보여야 한다.

여러 가지 방법이 있으나 시중의 웬만한 해석학 입문용 교재에 2\sqrt{2} 한정으로 그 존재성을 밝히는 과정이 있으니[8] 그걸 참고해도 좋겠다. 대부분의 경우 데데킨트 컷이나 코시 수열, 실수의 완비성으로 증명하는데, 어떻게 증명하든 그 과정에서 실수 구조 자체를 엄밀하게 구성하는 방법을 요구하기 때문에 고등학교 과정에선 이를 다룰 수 없는 것이 당연.

4. 여담

이 논법은 니시오 이신의 소설 '데스노트 어나더 노트 로스앤젤레스 BB 연속 살인사건' 후반부에 미소라 나오미가 살인사건의 범인인 'B'를 잡는 데에 쓰이기도 했다.

특이하게 과학 명제의 증명에서도 쓰일 수가 있는데 대표적으로 열역학 법칙 같은 표현을 증명할 때도 쓰인다.

더욱 특이하게도 성범죄의 증명에서도 쓰인 적이 있는데, 진중권은 이러한 귀류법을 이용하여 정봉주 성추행 의혹을 증명했다고 주장하였다. 2018년 3월 17일 프레시안 [기고] 응답하라, 정봉주-정봉주 '미투' 사건에 관하여 2018년 3월 17일 네이버-프레시안

5.18 민주화운동 북한군 개입설을 반박할 때도 쓸 수 있다.[9]


[1] ∧=and[2] 참고로 우변이 유리수의 정의. 따라서 이 식은 '2\sqrt{2}는 무리수이다'라는 사실을 일단 부정한 것[3] 즉 멀쩡한 명제의 결론을 부정했더니 말이 안 되더라는 것을 보여주는[4] 다른 방법으로 제곱한 다음 양변을 소인수분해 했을시 '22의 개수'가 서로 다르다는 방식으로도 증명이 가능하다. 좌변은 22가 홀수개, 우변은 짝수개이므로[5] 이 역시 귀류법을 이용하거나 대우증명법을 이용해서 증명해주어야 한다.[6] 2=p/q\sqrt{2}=p/q 에서 양변을 제곱하면 2=p2/q22=p^{2}/q^{2} 가 되고, 이를 정리하면 p2=2q2p^{2}=2q^{2}가 된다. p2p^2q2q^222배이므로 p2p^2는 짝수이고, 자연스럽게 pp도 짝수임을 알 수 있다.(pp가 홀수라면 p2p^2도 홀수여야 한다. 그렇지 않으므로 짝수) pp를 어떤 정수 rr22배라고 표현하여 식에 대입하면 4r2=2q24r^2=2q^{2}, 즉 q2=2r2q^2=2r^2이고 따라서 qq도 짝수임을 알 수 있다.[7] 일단 유리수까지는 별 어려움없이 실수 구성에 들어간다. 자연수와 0으로 파생되기 쉽기 때문이다.[8] Rudin의 Principle of Mathematical Analysis가 대표적이다. 김김계 서울대학교 해석개론 교재에는 임의의 양수에 대한 증명이 나와 있다. 유일성은 덤.[9] "광주사태 때 북한군이 개입했다고? OK, 네 말이 맞다고 해볼 게. 1960년 4월 5일 이래로 대법원은 여타 판례에서 북한을 일관되게 반국가단체로 보고 있어. 1.21사태, 판문점 도끼 사건이 터져서 박정희가 사회 안정을 위해 통제를 강화해서 치안이 좋아졌지. 광주 시내에는 130여 명의 정보보안 형사가 있었고 23곳에 정보센터가 있었어. 이런 삼엄한 경비 속에서 북한군 수백 명이 감히 얼쩡거렸다면 분명 티가 났겠지? 만약 그들 중 1명이라도 사살했다면, 우리의 주적을 응징한 거니까 정부에서는 당연히 말단 사수부터 장성급 인사까지 두루 훈장을 수여하며 융숭한 대접을 했을 거야. 그런데 그랬다는 말이 없지? 그리고 북한군이 광주에 진입할 때까지, 과연 광주 주변에만 병력이 배치됐겠냐는 거야. 그들이 휴전선 좀 넘어 파주까지만 도달해도 기적이었을 텐데, 용케도 광주까지 당도했다? 그럼 그 길목에 있던 부대들 사단장 다 모가지 날아갔겠지? 그리고 광주가 목포나 부산처럼 매력적인 항구도시도 아니고 어정쩡한 내륙에 처박혀 있는데 설령 북한군이 남한으로 침투해봤자 얼마나 탐냈을까? 결정적인 사실 하나, 전두환이 북한군 들어왔다고 신나게 언론에 대고 떠들었으면서 나중에 슬쩍 뒷조사 해보니까 정작 그들이 들어왔다는 소식은 듣도 보도 못했대. 근데, 만약 진짜 들어왔으면 나라를 지켜야 하는 보안사령관 주제에 주적 북한의 침투사실도 몰랐다는 얘기니 군인으로서 최악의 직무유기였겠지? 그런데 지금 전두환에 대한 그런 평은 없잖아. 따라서 북한군은 개입 안했어."