반례와 필요충분조건

단 하나의 반례가 보편 주장을 무너뜨리는 모습을, 네 개의 거짓 주장 — 모든 소수는 홀수,

4 \mid n^2 \Rightarrow 4 \mid n

, 무리수끼리의 합은 무리수,

|x| = |y| \Rightarrow x = y

— 위에서 확인하세요.

n

을 밀며 가정과 결론의 표시등을 켜고 끄다 보면

\lnot(\forall x\, P(x)) = \exists x\, \lnot P(x)

가 손에 잡힙니다. 반대 방향의 기술 —

P \iff Q

의 양쪽 화살표를 각각 증명하는 일 — 은 문제에서 이어집니다.

예제

“ $n^2$ 이 4로 나누어떨어지면 $n$ 도 4로 나누어떨어진다”는 주장을 반례 $n = 2$ 로 반박하세요. 주장의 논리형 $\forall n\,(4 \mid n^2 \Rightarrow 4 \mid n)$ 과 그 부정 $\exists n\,(4 \mid n^2 \text{ and } 4 \nmid n)$ 을 명시적으로 쓰고, 왜 단 하나의 증인으로 증명이 끝나는지 설명하세요.

\forall n\,(4 \mid n^2 \Rightarrow 4 \mid n),\qquad \lnot\Big(\forall n\,P(n)\Big) = \exists n\,\lnot P(n)

n = 2:\quad n^2 = 4,\; 4 \mid 4,\; \text{but } 4 \nmid 2

주장

4 \mid n^2 \Rightarrow 4 \mid n

, 테스트

n = 2

n^2 = 4

이므로 가정이 참, 결론

4 \mid 2

는 거짓 — 반례 확정.

증명 보기

주장은 전칭 명제입니다: $\forall n\,(4 \mid n^2 \Rightarrow 4 \mid n)$ . 논리학의 기본 규칙에 따라 그 부정은 존재 명제 $\exists n\,\lnot(4 \mid n^2 \Rightarrow 4 \mid n)$ 이고, 함축의 부정 $\lnot(P \Rightarrow Q) = P \wedge \lnot Q$ 에 의해 $\exists n\,(4 \mid n^2 \wedge 4 \nmid n)$ 이 됩니다. 즉 “가정은 참인데 결론은 거짓인 $n$ 이 하나라도 존재한다”를 보이면 충분하고, 그 역도 마찬가지입니다.
$n = 2$ 를 취합니다. $n^2 = 4$ 이고 $4 \mid 4$ 이므로 가정은 참입니다. 그런데 $n = 2$ 는 4로 나누어떨어지지 않으므로 결론 $4 \mid n$ 은 거짓입니다. 따라서 $n = 2$ 는 부정 명제 $\exists n\,(4 \mid n^2 \wedge 4 \nmid n)$ 의 증인이고, 원래 전칭 주장은 거짓입니다.
$n = 2:\quad 4 \mid n^2 = 4\ \text{true},\qquad 4 \nmid 2\ \text{false}\ \Rightarrow\ \text{counterexample}$
주석: 백 개의 $n$ 에서 가정이 결론을 따라다니는 것을 확인해도 — 예를 들어 $n = 4, 8, 12$ 에서는 모두 참입니다 — 전칭 주장은 증명되지 않습니다. 반례 하나가 무한한 지지 예보다 강합니다. (이 주장의 ‘고친 버전’ — $n$ 이 짝수 $\iff$ $n^2$ 이 짝수 — 은 아래 문제 2에서 양방향으로 증명합니다.)

$n$ 이 짝수인 것과 $n^2$ 이 짝수인 것이 동치임을 양방향으로 완전히 증명하세요. $\Rightarrow$ 방향은 직접 증명 ( $n = 2k$ 에서 $n^2 = 2(2k^2)$ ), $\Leftarrow$ 방향은 대우 (홀수 $n = 2k+1$ 에서 $n^2 = 2(2k^2+2k)+1$ 은 홀수)를 사용하고, 두 방향이 왜 서로 다른 증명인지 명시하세요.

n\ \text{even} \iff n^2\ \text{even}

\Rightarrow:\ n = 2k \;\Rightarrow\; n^2 = 2(2k^2),\qquad \Leftarrow:\ \lnot(n\ \text{even}) \Rightarrow \lnot(n^2\ \text{even})

씐에 이 양방향 주장을 직접 시험하는 프리셋은 없으므로(반례 장면의 주장만 있음), 가장 작은 반례

n = 2

위치의 프리셋 — 이 문제는 증명 연습입니다.

증명 보기

( $\Rightarrow$ ) $n$ 이 짝수라 하세요. 그러면 어떤 정수 $k$ 에 대해 $n = 2k$ 입니다. 제곱하면 $n^2 = 4k^2 = 2(2k^2)$ 이고, $2k^2$ 가 정수이므로 $n^2$ 은 짝수입니다. 이것은 직접 증명 — 가정에서 출발해 정의를 풀고 결론에 도달했습니다.
( $\Leftarrow$ ) 역방향은 직접 증명이 막힙니다: “ $n^2$ 이 짝수”라는 가정에서 $n$ 을 꺼내 쓸 방법이 없기 때문입니다. 대신 대우를 증명합니다: $n$ 이 홀수이면 $n^2$ 도 홀수이다. $n = 2k+1$ 이라 두면 $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ 이고, $2k^2 + 2k$ 가 정수이므로 $n^2$ 은 홀수입니다. 대우가 참이므로 원래 함축 $n^2$ 짝수 $\Rightarrow$ $n$ 짝수도 참입니다.
$(2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\ \text{odd}$
두 방향은 서로 다른 증명입니다: $\Rightarrow$ 는 짝수의 정의 $n = 2k$ 를 직접 풀어 썼고, $\Leftarrow$ 는 정의가 아닌 대우 명제로 우회했습니다. 둘 중 하나만 증명하면 동치가 아니라 함축 하나만 얻습니다. “ $P \iff Q$ ”를 주장하려면 두 화살표가 모두 필요하고, 보통은 이렇게 서로 다른 논증이 필요합니다.

실수 $x, y$ 에 대해 $x^2 = y^2$ 인 것과 $x = y$ 또는 $x = -y$ 인 것이 동치임을 증명하세요. $\Rightarrow$ 방향은 $x^2 - y^2 = (x-y)(x+y) = 0$ 과 곱이 0이면 인자가 0이라는 성질을, $\Leftarrow$ 방향은 각 경우에 대한 직접 대입을 사용하세요.

x^2 = y^2 \iff (x = y\ \text{or}\ x = -y)

\Rightarrow:\ x^2 - y^2 = (x-y)(x+y) = 0,\qquad \Leftarrow:\ (-y)^2 = y^2

주장

|x| = |y| \Rightarrow x = y

, 테스트 쌍

(3, -3)

|3| = |-3| = 3

이지만

3 \ne -3

— 이 문제의 양방향 버전에 대한 반례입니다.

증명 보기

( $\Rightarrow$ ) $x^2 = y^2$ 이라 가정합니다. 양변에서 $y^2$ 을 빼면 $x^2 - y^2 = 0$ 이고, 인수분해하면 $(x-y)(x+y) = 0$ 입니다. 실수에서는 두 수의 곱이 0이면 둘 중 하나가 0이므로 (0이 아닌 수로 나누면 되기 때문입니다), $x - y = 0$ 또는 $x + y = 0$ — 즉 $x = y$ 또는 $x = -y$ 입니다.
( $\Leftarrow$ ) 역방향은 두 경우를 각각 직접 확인합니다. $x = y$ 이면 $x^2 = y^2$ 는 자명하고, $x = -y$ 이면 $x^2 = (-y)^2 = y^2$ 입니다. 두 경우 모두 $x^2 = y^2$ 이 성립합니다.
주석: 이 양방향 정리는 씬의 반례를 설명합니다 — $|x| = |y|$ 는 $x^2 = y^2$ 와 동치이므로, 실제로 강제되는 것은 “ $x = y$ ”가 아니라 “ $x = y$ 또는 $x = -y$ ”입니다. 씬의 쌍 $(n, -n)$ 은 바로 두 번째 경우의 증인입니다. 반례를 만난 뒤 주장을 어떻게 고쳐야 하는지 보여 주는 전형적인 예입니다.