귀류법의 수리논리적 증명

귀류법의 수리논리적 증명

법칙 1

$$ (p \land \lnot q) \to c \iff p \to q $$


설명

배리법 혹은 귀류법은 수학 전반에서 정말 많이 사용되는 증명법이다. 하지만 처음 귀류법을 접하는 사람은 이게 단어부터 생소해서 거부감이 들 수 있다. 혹은 그냥 익숙해졌을 뿐, 왜 귀류법이 작동하는지 이해하지 못한 사람도 있을 것이다.

아래의 글을 읽어보면서 귀류법을 이해해보자:

이해가 안 간다면 수학을 뺀 예시로 확인해보자:

우선 말 그 자체만 보면 귀류법이고 뭐고 너무 당연한 사실이다. 팔이 적어도 하나 있지 않다면 어떻게 팔이 두 개 있겠는가? 그런데 이 당연한 논리가 바로 귀류법 그 자체다:

증명

$$ \begin{align*} (p \land \lnot q) \to c \iff & \lnot ( p \land \lnot q ) \lor c \\ \iff & \lnot (p \land \lnot q) \\ \iff & \lnot p \lor q \\ \iff & p \to q \end{align*} $$


  1. 이흥천 역, You-Feng Lin. (2011). 집합론(Set Theory: An Intuitive Approach): p39. ↩︎

  2. 동시에 참이면서 거짓일 수는 없다. ↩︎

댓글