귀류법의 수리논리적 증명
법칙 1
$$ (p \land \lnot q) \to c \iff p \to q $$
- $c$ 는 모순을 의미한다.
설명
배리법 혹은 귀류법은 수학 전반에서 정말 많이 사용되는 증명법이다. 하지만 처음 귀류법을 접하는 사람은 이게 단어부터 생소해서 거부감이 들 수 있다. 혹은 그냥 익숙해졌을 뿐, 왜 귀류법이 작동하는지 이해하지 못한 사람도 있을 것이다.
아래의 글을 읽어보면서 귀류법을 이해해보자:
- (1) 결론 $q$ 는 참이거나 거짓이다. 배중률2에 의해 당연하다.
- (2) 그런데 $\lnot q$ 가 참일 경우 모순이 일어난다면, 적어도 $\lnot q$ 이 참은 아니라는 것을 알 수 있다.
- (3) (1)에서 $q$ 는 참이거나 거짓이라고 했는데, $\lnot q$ 가 거짓이라면 $q$ 는 참이어야한다.
- (4) 따라서, $p \to q$ 다.
이해가 안 간다면 수학을 뺀 예시로 확인해보자:
- $p$ : 나는 팔이 두 개다
- $q$ : 나는 팔이 적어도 하나 있다
- $p \to q$ : 내 팔이 두 개면 적어도 하나는 있다
우선 말 그 자체만 보면 귀류법이고 뭐고 너무 당연한 사실이다. 팔이 적어도 하나 있지 않다면 어떻게 팔이 두 개 있겠는가? 그런데 이 당연한 논리가 바로 귀류법 그 자체다:
- 일단 결론 $q$ 를 부정해서 내가 팔이 하나도 없다고 가정하자.
- 그런데 가정 $p$ 에서 내 팔은 두 개라고 했고, 이것은 모순이다.
- 그렇다면 내가 팔이 하나도 없다는 $\lnot q$ 가 틀렸다고 생각할수밖에 없다. 물론 이것은 내가 팔이 두 개라는 가정 $p$ 가 성립할 때의 이야기니까, $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*} $$
■