서론
- 입과하기 이전 사전 교육을 들으면서 정리할 것이 있으면 정리하는 글을 몇 개 적을 것 같다.
- 이번 주제는 명제와 증명에 관해서이다.
명제와 증명
- 명제식이란 $p \rightarrow q$ 의 형식으로 나타낼 수 있는 구조를 이야기한다.
- 가장 단편적인 예시로 A 이면 B이다 라고 하는 구조가 있다. 증명은 이 명제식이 참이라면 왜 참인지를, 거짓이라면 왜 거짓인지를 논리적으로 설명하는 과정을 이야기한다.
- 명제식의 전체적인 참 거짓은 다음의 기준을 따른다.
- $p \rightarrow q$ 에서 $p$가 참일 때 $q$가 거짓이라면 전체적인 명제식은 거짓이 된다.
- 그 이외의 모든 조건에서 전체적인 명제식은 참이 된다.
- 여기서 소위 직관이라 부르는 접근과 논리적으로 접근하는 것에서 괴리가 발생한다. 직관적으로는 $p$가 거짓이라면 $q$ 역시 거짓이어야 한다라는 생각이 들지만 논리적 접근에서는 $p$가 거짓이라면 어떤 경우에서든 전체 명제식이 참이 된다는 것이다.
- 이는 수학적 귀납법에서도 동일하게 비슷한 오해가 발생할 수 있다. 수학적 귀납법에서 기본적으로 $F(1)$ 이 참 이고, $F(n) \rightarrow F(n + 1)$이 참이라면 $F(n)$은 모든 자연수 $n$에 대해 참이다 가 핵심이다.
- 이때 $F(n) \rightarrow F(n + 1)$에서 굳이 $F(n)$의 진위성에 대해서는 따지지 않아도 된다. 만약 참이라고 가정하게 된다면 $F(n + 1)$이 참인지 거짓인지를 확인해야 할 것이다.
실제 예시
1. $n$이 홀수이면 $4n^3 + 6n^2 + 12$는 짝수이다. 라는 명제가 모든 $x$에 대해 참임을 증명하라
더보기
- 명제식으로 분석하면 다음과 같이 나타낼 수 있다.
- $P(x)$ : $n$이 홀수이면
- $Q(x)$ : $4n^3 + 6n^2 + 12$는 짝수이다.
- 이때 $4n^3 + 6n^2 + 12$ 은 $2( 2n^3 + 3n^2 + 6 )$ 으로 나타내질 수 있으므로 2로 나누어떨어질 수 있다. 따라서 $4n^3 + 6n^2 + 12$은 짝수이고 $Q(x)$는 참이다.
- $Q(x)$가 참이므로 $ \forall x, P(x) \rightarrow Q(x)$이다.
2. $x \in \mathbb{R}$ 에 대해, $2x^2 - 4x + 4 < 0$ 이면 $x > 8$이다. 라는 명제가 모든 $x$에 대해 참임을 증명하라.
더보기
- 동일하게 명제식으로 분석하면 다음과 같이 나타낼 수 있다.
- $P(x)$ : $2x^2 - 4x + 4 < 0$
- $Q(x)$ : $x > 8$
- 이때 $2x^2 - 4x + 4$는 다음과 같이 변형시킬 수 있다.
- $2x^2 - 4x + 4 = 2(x^2 - 2x) + 4$
- $= 2(x^2 - 2x + 1 - 1) + 4$
- $= 2(x^2 - 2x + 1) - 2 + 4$
- $= 2(x - 1)^2 + 2$
- 이때 $2(x - 1)^2 + 2 \leq 0$이므로 $P(x)$는 거짓이다. 따라서 $ \forall x, P(x) \rightarrow Q(x)$