간접증명법

전제에서 출발해 추론 규칙을 차례로 적용하여 결론에 도착하는 증명을 직접증명법(直接證明法, Direct Proof)이라 한다. 추론의 타당성에서 본 형식적 증명은 모두 이 방식이다. 이와 달리 "결론이 거짓이라면 무엇이 잘못되는가"를 따져서 결론을 얻는 증명을 간접증명법이라 한다. 그중 가장 많이 쓰는 것은 결론의 부정을 전제에 하나 더 보태어 모순명제 c를 끌어내는 방법으로, 귀류법(歸謬法) 또는 배리법(背理法)이라 부른다. 근거가 되는 동치 (p→q) ≡ ((p∧∼q)→c)는 아래 상자에서 증명한다. 전제가 여러 개이면 p 자리에 전제 전부의 논리곱을 놓는다.

다음 추론이 타당함을 간접증명법으로 보이자. "수요일이면 도서관이 일찍 문을 닫는다. 도서관이 일찍 문을 닫으면 동아리 모임은 강당에서 열린다. 오늘 동아리 모임은 강당에서 열리지 않았다. 따라서 오늘은 수요일이 아니다."

①	p→q	전제
②	q→r	전제
③	∼r	전제 (보일 것 : ∼p)
④	∼(∼p)	귀류법 (결론의 부정을 추가로 가정)
⑤	p	④ 이중부정법
⑥	q	①,⑤ 삼단긍정법
⑦	r	②,⑥ 삼단긍정법
⑧	r∧∼r	③,⑦ 논리곱(정의 2)
⑨	c	⑧ 모순명제

모순명제가 나왔으므로 아래 상자의 동치에 의해 주어진 추론은 타당하다.
같은 추론을 직접증명법으로 보이면 ①,②에서 추이법칙으로 p→r을 얻고, 여기에 ③을 붙여 삼단부정법으로 ∼p를 얻는다. 간접증명법은 "가정을 하나 더 얻고 시작한다"는 점에서 어느 규칙을 쓸지 떠올리기 쉬운 경우가 많다.

귀류법의 근거 (p→q) ≡ ((p∧∼q)→c)

(p∧∼q)→c	≡ ∼(p∧∼q)∨c	∵ 정리8 (P→Q ≡ ∼P∨Q)
	≡ ∼(p∧∼q)	∵ 정리15 (P∨c ≡ P)
	≡ p→q	∵ 정리9 (p→q ≡ ∼(p∧∼q))

즉 "p이면서 q가 아니면 모순"이라는 것과 "p이면 q"는 같은 말이다.