03. 추론 규칙과 증명 방법

수학적 증명은 그럴듯한 예를 많이 모으는 일이 아니라, 주어진 가정에서 결론이 반드시 따라온다는 것을 보이는 과정이다. 추론 규칙은 그 과정의 작은 단위이고, 직접증명·대우증명·귀류법은 여러 단계를 구성하는 방법이다. 어떤 조건을 가정했는지, 그 조건을 어디에서 사용했는지 드러내며 쓰는 것이 중요하다.

연습문제로 바로 가기 · 먼저 풀어 본 뒤 각 문제의 해설 보기를 눌러 확인할 수 있다.

1. 타당한 논증과 참인 결론

전제가 p1,…,pnp_1,\ldots,p_n, 결론이 qq인 논증은

(p1∧⋯∧pn)→q(p_1\land\cdots\land p_n)\to q

가 항진명제일 때 **타당(valid)**하다. 전제가 모두 참인 경우에 결론이 거짓일 수 없다는 뜻이다. 논증의 형식이 타당하다는 것과 실제 전제가 참이라는 것은 다르다. 타당한 형식에 거짓 전제를 넣었다면 결론이 참이라고 보장할 수 없다. 타당하고 전제도 모두 참인 논증은 건전(sound)하다고 한다.

예를 들어 p→q,p∴qp\to q,p\therefore q는 언제나 타당한 형식이다. 그러나 pp를 2>3/2\sqrt2>3/2로 놓으면 전제 pp부터 거짓이다. 양수끼리의 비교에서 제곱해도 부등호가 유지된다는 추론은 맞지만, 거짓 전제를 사용해 얻은 2>9/42>9/4가 참이 되는 것은 아니다.

2. 명제 논리의 추론 규칙

규칙전제결론
긍정 논법, Modus Ponensp→qp\to q, ppqq
부정 논법, Modus Tollensp→qp\to q, ¬q\neg q¬p\neg p
가설적 삼단논법p→qp\to q, q→rq\to rp→rp\to r
선언적 삼단논법p∨qp\lor q, ¬p\neg pqq
가산논법ppp∨qp\lor q
단순화p∧qp\land qpp
논리곱 도입pp, qqp∧qp\land q
용해법, Resolution¬p∨r\neg p\lor r, p∨qp\lor qq∨rq\lor r

긍정 논법은 (p∧(p→q))→q(p\land(p\to q))\to q가 항진명제라는 사실에 근거한다. 나머지 규칙도 전제를 모두 묶은 조건문이 항진명제임을 확인하면 된다.

“비가 오면 소풍이 취소된다”와 “취소되지 않았다”에서는 부정 논법으로 “비가 오지 않았다”를 얻는다. 반면 “취소되었다”에서 “비가 왔다”를 얻을 수는 없다. 다른 이유로 취소되었을 수 있기 때문이다. 이것이 후건 긍정의 오류다. p→q,¬pp\to q,\neg p에서 ¬q\neg q를 얻는 전건 부정의 오류도 마찬가지다.

용해법은 pp의 진리값으로 나누면 이해하기 쉽다. pp가 참이면 ¬p∨r\neg p\lor r에서 rr이 참이어야 하고, 거짓이면 p∨qp\lor q에서 qq가 참이어야 한다. 어느 경우든 q∨rq\lor r은 참이다. 이 규칙은 자동 정리 증명과 논리 프로그래밍의 기초가 된다.

여러 규칙을 연결하는 예제

pp: 화창하다, qq: 어제보다 춥다, rr: 수영한다, ss: 카누를 탄다, tt: 해질녘까지 귀가한다고 하자. 전제는

¬p∧q,r→p,¬r→s,s→t\neg p\land q,\qquad r\to p,\qquad\neg r\to s,\qquad s\to t

이다. “화창할 때만 수영한다”가 r→pr\to p라는 방향에 주의한다.

단계얻은 식근거
1¬p\neg p첫 전제의 단순화
2¬r\neg rr→pr\to p와 1의 부정 논법
3ss¬r→s\neg r\to s와 2의 긍정 논법
4tts→ts\to t와 3의 긍정 논법

다섯 변수의 진리표는 32행이 필요하지만, 필요한 전제를 따라가면 네 단계로 끝난다.

메일을 보내면 프로그램을 마치고(p→qp\to q), 보내지 않으면 일찍 자고(¬p→r\neg p\to r), 일찍 자면 개운하게 일어난다(r→sr\to s)고 하자. 첫 전제의 대우 ¬q→¬p\neg q\to\neg p에 나머지를 연결하면 ¬q→s\neg q\to s가 된다.

또 (p∧q)∨r(p\land q)\lor r와 r→sr\to s에서 p∨sp\lor s를 얻으려면

(p∧q)∨r≡(p∨r)∧(q∨r)(p\land q)\lor r\equiv(p\lor r)\land(q\lor r)

로 분배한 뒤 p∨rp\lor r를 꺼내고, r→s≡¬r∨sr\to s\equiv\neg r\lor s와 용해법을 적용한다.

추가로 p→¬q,¬q→r,¬rp\to\neg q,\neg q\to r,\neg r에서는 부정 논법으로 qq를 얻고 다시 부정 논법으로 ¬p\neg p를 얻는다. ¬p∨q\neg p\lor q와 p∨¬rp\lor\neg r의 용해 결과는 q∨¬rq\lor\neg r다.

3. 한정 명제에 대한 추론

규칙내용주의할 조건
전칭 예시화(UI)∀xP(x)\forall xP(x)에서 P(a)P(a)aa가 정의역의 원소
전칭 일반화(UG)임의의 aa에 대해 P(a)P(a)를 보여 ∀xP(x)\forall xP(x)특정 원소만의 성질에 의존하면 안 됨
존재 예시화(EI)∃xP(x)\exists xP(x)의 증인을 새 이름 aa로 둠이미 정해진 원소와 같다고 가정하면 안 됨
존재 일반화(EG)P(a)P(a)에서 ∃xP(x)\exists xP(x)실제로 조건을 만족하는 증인이 필요

∀x(P(x)→Q(x))\forall x(P(x)\to Q(x))와 P(a)P(a)에서 Q(a)Q(a)를 얻는 전칭 긍정 논법은 UI와 긍정 논법을 합친 것이다. ¬Q(a)\neg Q(a)에서 ¬P(a)\neg P(a)를 얻는 전칭 부정 논법도 같은 방식이다.

“모든 사람은 죽는다”를 ∀x(Man⁡(x)→Mortal⁡(x))\forall x(\operatorname{Man}(x)\to\operatorname{Mortal}(x))로 쓰고 소크라테스에 대입하면, 소크라테스가 사람이라는 전제에서 죽는다는 결론이 나온다. 양의 정수에 대해 n>4→n2<2nn>4\to n^2<2^n이 참이라고 주어졌다면 n=100n=100을 대입해 1002<2100100^2<2^{100}을 얻는 것도 같은 형식이다.

존재 증인 하나를 끝까지 유지하기

C(x)C(x)는 이 반의 학생, B(x)B(x)는 책을 읽었다, P(x)P(x)는 시험에 합격했다는 뜻이라고 하자.

∃x(C(x)∧¬B(x)),∀x(C(x)→P(x)).\exists x(C(x)\land\neg B(x)),\qquad \forall x(C(x)\to P(x)).

첫 전제의 증인을 새 이름 aa로 두면 C(a)∧¬B(a)C(a)\land\neg B(a)다. 따라서 C(a)C(a)이고, 둘째 전제를 aa에 적용하면 P(a)P(a)다. 다시 P(a)∧¬B(a)P(a)\land\neg B(a)로 묶고 존재 일반화하면

∃x(P(x)∧¬B(x))\exists x(P(x)\land\neg B(x))

를 얻는다. 책을 읽지 않은 사람과 시험에 합격한 사람이 같은 aa라는 점이 핵심이다. 서로 다른 존재 전제의 증인을 이유 없이 같은 사람으로 두면 안 된다.

전칭 명제의 연쇄

∀x(P(x)→Q(x)),∀x(Q(x)→R(x))\forall x(P(x)\to Q(x)),\qquad\forall x(Q(x)\to R(x))

에서 임의의 aa를 잡는다. P(a)P(a)를 가정하면 Q(a)Q(a), 다시 R(a)R(a)가 따라오므로 P(a)→R(a)P(a)\to R(a)다. aa에 특별한 조건을 쓰지 않았으므로 전칭 일반화하여 ∀x(P(x)→R(x))\forall x(P(x)\to R(x))를 얻는다.

결론이 따라오지 않는 추론

다음 전제들을 살펴보자.

∀x(P(x)∨Q(x)),∀x(¬Q(x)∨S(x)),∀x(R(x)→¬S(x)),∃x¬P(x).\forall x(P(x)\lor Q(x)),\quad \forall x(\neg Q(x)\lor S(x)),\quad \forall x(R(x)\to\neg S(x)),\quad \exists x\neg P(x).

여기서 ∃xR(x)\exists xR(x)를 결론으로 삼을 수 있을까? 마지막 전제의 증인 aa를 잡으면 ¬P(a)\neg P(a)이므로 Q(a)Q(a), 따라서 S(a)S(a)다. R(a)→¬S(a)R(a)\to\neg S(a)와 부정 논법을 적용하면 오히려 ¬R(a)\neg R(a)가 나온다. 따라서 얻을 수 있는 결론은 ∃x¬R(x)\exists x\neg R(x)다.

∃xR(x)\exists xR(x)가 따라오지 않는다는 것은 반례 해석으로도 확인할 수 있다. 정의역을 {a}\{a\}로 두고 P(a)=FP(a)=\mathrm F, Q(a)=S(a)=TQ(a)=S(a)=\mathrm T, R(a)=FR(a)=\mathrm F로 두면 모든 전제는 참인데 ∃xR(x)\exists xR(x)는 거짓이다.

4. 증명에서 사용하는 정의

정리는 정의·공리·이미 증명된 정리와 추론 규칙으로 참임을 보인 주장이다. 다른 증명을 돕는 정리를 보조정리(lemma), 정리에서 바로 따라오는 결과를 따름정리(corollary)라고 한다. 추측(conjecture)은 아직 증명하지 않은 주장이다.

많은 수학 문장에는 전칭 한정이 생략되어 있다. “양의 실수 x,yx,y에서 x>yx>y이면 x2>y2x^2>y^2”는 그런 모든 x,yx,y에 대한 주장이다. 반면 “모든 소수는 2보다 크다”는 전칭 명제지만, 2가 반례이므로 참인 정리가 아니다.

증명을 시작할 때는 정의를 식으로 풀어 쓴다.

n은 짝수  ⟺  ∃k∈Z (n=2k),n은 홀수  ⟺  ∃k∈Z (n=2k+1),r은 유리수  ⟺  ∃a,b∈Z (b≠0∧r=a/b).\begin{aligned} n\text{은 짝수}&\iff\exists k\in\mathbb Z\ (n=2k),\\ n\text{은 홀수}&\iff\exists k\in\mathbb Z\ (n=2k+1),\\ r\text{은 유리수}&\iff\exists a,b\in\mathbb Z\ (b\ne0\land r=a/b). \end{aligned}

5. 직접증명과 대우증명

직접증명은 pp를 가정하고 qq를 도출한다. 홀수 n=2k+1n=2k+1에 대해

n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1

이므로 제곱도 홀수다. 짝수 n=2kn=2k라면 n2=2(2k2)n^2=2(2k^2)로 짝수다. 두 홀수 a=2k+1a=2k+1, b=2ℓ+1b=2\ell+1의 합도

a+b=2(k+ℓ+1)a+b=2(k+\ell+1)

이므로 짝수다. 여기서 k,ℓk,\ell은 서로 다른 정수일 수 있으므로 같은 기호로 놓지 않는다.

유리수 r=a/br=a/b, s=c/ds=c/d에서 b,d≠0b,d\ne0이면

r+s=ad+bcbd.r+s=\frac{ad+bc}{bd}.

분자는 정수이고 분모는 0이 아닌 정수이므로 합이 유리수다. nn이 3의 배수일 때도 n=3kn=3k를 대입하면 n2=3(3k2)n^2=3(3k^2)이므로 제곱이 3의 배수임을 바로 보인다.

대우를 증명하는 편이 쉬운 경우

p→qp\to q와 ¬q→¬p\neg q\to\neg p는 동치다. “3n+23n+2가 홀수이면 nn은 홀수”는 대우를 사용하면 짧아진다. n=2kn=2k로 놓으면

3n+2=6k+2=2(3k+1)3n+2=6k+2=2(3k+1)

이므로 짝수다. “n2n^2이 홀수이면 nn도 홀수”도 짝수의 제곱이 짝수임을 보여 증명한다. 반대로 “n2n^2이 짝수이면 nn도 짝수”의 대우는 홀수의 제곱이 홀수라는 주장이다.

n=abn=ab이고 a,ba,b가 양의 정수이면 a≤na\le\sqrt n 또는 b≤nb\le\sqrt n이다. 둘 다 n\sqrt n보다 크다고 가정하면 ab>nab>n이 되어 ab=nab=n과 맞지 않는다. 두 인수가 모두 기준보다 크다는 부정 조건이 곱셈으로 바로 연결된다.

“두 정수의 곱이 홀수이면 두 정수가 모두 홀수”도 적어도 하나가 짝수이면 곱이 짝수임을 보이는 대우증명이 자연스럽다. 이 주장은 존재 명제가 아니므로 구성적·비구성적 존재증명 중 하나로 억지로 분류할 필요가 없다.

6. 귀류법과 동치 증명

귀류법은 보이려는 명제의 부정을 가정하고 모순을 얻는 방법이다.

제곱근 2의 무리성

2=a/b\sqrt2=a/b라고 가정하되 a,ba,b는 서로소인 정수이고 b≠0b\ne0이라고 하자. 그러면

a2=2b2.a^2=2b^2.

a2a^2이 짝수이므로 aa도 짝수다. a=2ca=2c를 대입하면 4c2=2b24c^2=2b^2, 즉 b2=2c2b^2=2c^2이므로 bb도 짝수다. a,ba,b가 모두 2로 나누어져 서로소라는 가정과 모순이다. 따라서 2\sqrt2는 무리수다.

3\sqrt3도 같은 구조로 시작한다. 서로소 a,ba,b에 대해 3=a/b\sqrt3=a/b라고 가정하면 a2=3b2a^2=3b^2다. 정수의 제곱을 3으로 나눈 나머지는 0 또는 1이므로 3∣a23\mid a^2이면 3∣a3\mid a다. a=3ca=3c를 대입하면 b2=3c2b^2=3c^2여서 bb도 3의 배수다. 역시 모순이다.

무리수와 유리수의 합

무리수 xx와 유리수 rr의 합이 유리수 ss라고 가정하자. 그러면 x=s−rx=s-r인데, 유리수의 차는 유리수이므로 xx가 무리수라는 조건과 모순이다. 따라서 합은 무리수다.

22일 중 같은 요일이 네 번 나오는 이유

어떤 요일도 네 번 나타나지 않는다고 가정하면 각 요일은 최대 세 번이다. 요일은 일곱 종류이므로 고른 날짜는 최대 7⋅3=217\cdot3=21개여야 한다. 22개를 골랐다는 조건과 모순이므로 같은 요일인 날짜가 적어도 네 개 있다.

필요충분조건은 양쪽을 증명한다

p↔qp\leftrightarrow q를 증명하려면 p→qp\to q와 q→pq\to p가 모두 필요하다. 앞서 보인 두 방향을 합치면

n이 홀수  ⟺  n2이 홀수,n이 짝수  ⟺  n2이 짝수n\text{이 홀수}\iff n^2\text{이 홀수},\qquad n\text{이 짝수}\iff n^2\text{이 짝수}

다. 또한 n=2kn=2k이면 n−1=2(k−1)+1n-1=2(k-1)+1이고, n−1=2k+1n-1=2k+1이면 n=2(k+1)n=2(k+1)이므로 “nn이 짝수”, “n−1n-1이 홀수”, “n2n^2이 짝수”는 서로 동치다.

조건문에서 결론 자체가 참임을 확인하는 것은 자명한 증명이다. 예를 들어 p→(1=1)p\to(1=1)은 pp와 무관하게 참이다. 전건이 거짓임을 확인하는 것은 공허한 증명이다. (p∧¬p)→q(p\land\neg p)\to q는 qq와 무관하게 참이다. 단순히 전제가 제시되지 않은 문장을 마음대로 거짓 전건을 가진 조건문으로 바꾸는 것은 증명이 아니다.

7. 경우를 나누는 증명

모든 가능한 경우를 빠짐없이 나누고 각 경우에서 결론을 보인다.

(p1∨⋯∨pk)→q≡⋀i=1k(pi→q).(p_1\lor\cdots\lor p_k)\to q \equiv \bigwedge_{i=1}^{k}(p_i\to q).

n(n+1)n(n+1)이 짝수라는 주장은 두 경우면 충분하다. n=2kn=2k이면 곱은 2k(n+1)2k(n+1)이고, n=2k+1n=2k+1이면 n+1=2(k+1)n+1=2(k+1)이므로 곱은 2n(k+1)2n(k+1)이다.

정수에서 n2≥nn^2\ge n은 n=0n=0, n≥1n\ge1, n≤−1n\le-1로 나눈다. 첫 경우는 등호이고, 둘째는 n≥1n\ge1의 양변에 양수 nn을 곱하면 된다. 셋째는 n2≥0>nn^2\ge0>n이다. 양의 정수 n≤4n\le4처럼 경우가 유한하고 적으면 값을 모두 확인하는 전수 증명도 가능하다. 예를 들어 (n+1)3≥3n(n+1)^3\ge3n은 각각 8≥38\ge3, 27≥627\ge6, 64≥964\ge9, 125≥12125\ge12로 확인된다.

절댓값의 곱

∣xy∣=∣x∣∣y∣|xy|=|x||y|는 부호에 따라 네 경우로 확인한다.

조건∣xy∣\lvert xy\rvert∣x∣∣y∣\lvert x\rvert\lvert y\rvert
x≥0,y≥0x\ge0,y\ge0xyxyxyxy
x≥0,y<0x\ge0,y<0−xy-xyx(−y)x(-y)
x<0,y≥0x<0,y\ge0−xy-xy(−x)y(-x)y
x<0,y<0x<0,y<0xyxy(−x)(−y)(-x)(-y)

모든 경우에서 두 값이 같다.

최대 연산의 결합법칙

a@b=max⁡(a,b)a@b=\max(a,b)라고 정의하자. a,b,ca,b,c의 크기 순서는 여섯 경우로 나눌 수 있다. a≥b≥ca\ge b\ge c 또는 a≥c≥ba\ge c\ge b이면 (a@b)@c(a@b)@c와 a@(b@c)a@(b@c)는 모두 aa다. bb가 최대인 두 경우에는 둘 다 bb, cc가 최대인 두 경우에는 둘 다 cc다. 같은 값이 있는 경우도 이 부등식들에 포함된다. 따라서 두 식은 항상 max⁡(a,b,c)\max(a,b,c)로 같다.

정수 제곱의 마지막 자리

n=10a+bn=10a+b로 쓰되 a∈Za\in\mathbb Z, 0≤b≤90\le b\le9로 잡으면

n2=10(10a2+2ab)+b2.n^2=10(10a^2+2ab)+b^2.

따라서 마지막 자리는 b2b^2의 마지막 자리와 같다.

bb0123456789
b2b^2의 마지막 자리0149656941

정수의 제곱은 0, 1, 4, 5, 6, 9 중 하나로 끝난다. 몇 개의 제곱수를 관찰한 것과 달리, 이 표는 가능한 나머지를 모두 다루므로 증명이다.

일반성을 잃지 않는다는 말

xyxy와 x+yx+y가 모두 짝수이면 x,yx,y가 모두 짝수임을 보이자. 대우를 위해 둘 중 적어도 하나가 홀수라고 가정한다. 식들이 x,yx,y를 바꾸어도 같으므로 일반성을 잃지 않고 xx가 홀수라고 둘 수 있다. yy가 짝수이면 합이 홀수이고, yy가 홀수이면 곱이 홀수다. 따라서 둘 다 짝수일 수 없다. WLOG라는 표현은 이렇게 변수 교환의 대칭성이 있을 때만 경우를 줄이는 근거가 된다.

8. 존재·비존재·유일성

구성적 존재증명은 조건을 만족하는 대상을 직접 준다.

1729=103+93=123+131729=10^3+9^3=12^3+1^3

이므로 두 가지 서로 다른 방식으로 양의 정수 두 개의 세제곱 합으로 나타낼 수 있는 수가 존재한다. 12=5+712=5+7도 12가 두 소수의 합이라는 구성적 증명이다.

비구성적 존재증명은 구체적인 증인을 확정하지 않고도 존재를 보인다. a=(2)2a=(\sqrt2)^{\sqrt2}를 생각하자. aa가 유리수이면 x=y=2x=y=\sqrt2가 무리수이면서 xyx^y가 유리수인 예다. aa가 무리수이면 x=a,y=2x=a,y=\sqrt2로 잡아

xy=((2)2)2=(2)2=2x^y=\bigl((\sqrt2)^{\sqrt2}\bigr)^{\sqrt2}=(\sqrt2)^2=2

를 얻는다. 두 경우 중 어느 것이 실제 경우인지 결정하지 않아도 존재는 증명된다. 비구성적 증명이 반드시 귀류법 형태여야 하는 것은 아니다.

타일링과 비존재 증명

8×8 체스판은 각 행을 가로 도미노 네 개로 채우면 총 32개로 덮인다. 이것은 배치 방법을 직접 제시한 구성적 증명이다.

모서리 한 칸을 제거하면 63칸이라 두 칸씩 덮는 도미노로 채울 수 없다. 대각선 양끝 모서리를 제거하면 62칸으로 짝수지만 여전히 덮을 수 없다. 대각선 모서리는 같은 색이어서 남은 칸의 색별 개수가 30과 32가 된다. 도미노 하나는 항상 흰 칸과 검은 칸을 하나씩 덮으므로 모든 칸을 덮으면 색별 개수가 같아야 한다. 이 불변량과 모순이 생긴다.

유일성은 존재성에 한 단계를 더한다

a≠0a\ne0인 실수 a,ba,b에 대해 ar+b=0ar+b=0의 해는 유일하다. 먼저 r=−b/ar=-b/a를 대입하면 0이 되어 존재성이 확인된다. 다른 해 ss가 있다고 하면

ar+b=as+b ⇒ a(r−s)=0 ⇒ r=s.ar+b=as+b\ \Rightarrow\ a(r-s)=0\ \Rightarrow\ r=s.

따라서 유일하다. “해가 있다”만 보이거나 “두 해가 있다면 같다”만 보여서는 유일하게 존재한다는 전체 주장이 완성되지 않는다.

9. 반례와 증명 전략

전칭 명제를 반박할 때는 반례 하나가 충분하다. “모든 양의 정수는 세 정수의 제곱의 합이다”에 대해 7을 보자. 7 이하의 제곱은 0, 1, 4뿐이다. 4를 두 번 쓰면 7을 넘고, 한 번 쓰면 나머지 두 제곱의 합으로 3을 만들어야 하지만 불가능하다. 4를 쓰지 않으면 최대 합은 3이다. 따라서 7은 반례다.

“nn보다 작은 모든 소수의 합은 소수”도 n=6n=6에서 2+3+5=102+3+5=10이므로 거짓이다. 반면 “5보다 큰 소수는 홀수”는 직접증명할 수 있다. 짝수인 소수는 2뿐이기 때문이다.

증명을 찾을 때는 가정에서 출발하는 전향 추론과 결론에 필요한 조건을 거슬러 찾는 후향 추론을 함께 쓸 수 있다. 양의 실수의 산술평균과 기하평균을 비교할 때

(x+y2)2−xy=(x−y)24≥0\left(\frac{x+y}{2}\right)^2-xy=\frac{(x-y)^2}{4}\ge0

를 발견하면 x+y2≥xy\frac{x+y}{2}\ge\sqrt{xy}가 따라온다. 양변이 음수가 아니므로 제곱을 비교해도 되며, 등호는 x=yx=y일 때만 성립한다. 증명을 찾으면서 결론에서 출발했더라도, 완성된 증명에서는 각 변형이 동치인지 또는 어느 방향의 함의인지 밝혀야 한다.

돌 15개에서 번갈아 1~3개를 가져가고 마지막 돌을 가져간 사람이 이기는 게임도 끝에서 거꾸로 생각할 수 있다. 상대에게 4개를 남기면 상대가 kk개 가져간 뒤 내가 4−k4-k개를 가져가 이긴다. 같은 방식으로 상대에게 8개, 12개를 남기면 된다. 따라서 처음에 3개를 가져가 12개를 남기고, 이후 상대와 내가 한 번씩 가져간 합을 항상 4로 맞추면 승리한다.

잘못된 대수 조작을 찾기

a=ba=b에서 a2=aba^2=ab를 얻고 인수분해하면

(a−b)(a+b)=b(a−b).(a-b)(a+b)=b(a-b).

여기서 a−ba-b를 약분해 a+b=ba+b=b라고 하면 안 된다. 처음 가정에 의해 a−b=0a-b=0이기 때문이다. 나눗셈, 제곱근, 부등식의 곱셈처럼 조건이 필요한 연산에서는 그 조건을 확인해야 한다.

유한한 수치 검증과 일반적인 증명도 구별한다. 예를 들어 짝수는 반으로, 홀수는 세 배에 1을 더하는 반복에서

13→40→20→10→5→16→8→4→2→113\to40\to20\to10\to5\to16\to8\to4\to2\to1

을 확인한 것은 시작값 13에 관한 결과다. 모든 양의 정수에 대한 주장을 이것만으로 증명할 수는 없다. 전칭 명제를 다룰 때는 경우별 증명 외에도 수학적 귀납법, 재귀 구조에 대한 구조적 귀납법, 무한집합에 대한 대각선법, 같은 대상을 두 방법으로 세는 조합론적 증명 등 주장에 맞는 도구를 선택한다.

10. 연습문제

문제를 읽고 풀이를 적어 본 뒤 해설을 펼쳐 비교해 보자. 계산 결과뿐 아니라 사용한 정의와 추론 근거까지 설명하는 연습을 한다.

01. 타당성 및 추론 규칙

  1. 전제와 결론은 무엇이며, 전제 p1,p2p_1,p_2에서 결론 qq가 타당할 조건은?
  2. “비가 오면 소풍이 취소된다”, “소풍이 취소되지 않았다”에서 무엇을 추론하는가?
  3. 다음에서 사용한 규칙을 쓰자: (가) 영하이다 → 영하이거나 비가 온다. (나) 영하이고 비가 온다 → 영하이다. (다) 오늘 비가 오면 오늘 바비큐를 안 한다; 오늘 안 하면 내일 한다 → 오늘 비가 오면 내일 한다. (라) Jasmine이 스키를 타거나 눈이 안 온다; 눈이 오거나 Bart가 하키를 한다 → Jasmine이 스키를 타거나 Bart가 하키를 한다.
  4. p∧(p→q)p\land(p\to q)에서 qq를 단계별로 얻자.
해설 보기
  1. 전제는 출발점으로 주어진 명제, 결론은 그 전제에서 도출하려는 명제다. (p1∧p2)→q(p_1\land p_2)\to q가 항진명제이면 타당하다.
  2. 부정 논법으로 “비가 오지 않았다”를 얻는다.
  3. 차례로 가산논법(p∴p∨qp\therefore p\lor q), 단순화(p∧q∴pp\land q\therefore p), 가설적 삼단논법(p→q,q→r∴p→rp\to q,q\to r\therefore p\to r), 용해법(q∨¬p,p∨r∴q∨rq\lor\neg p,p\lor r\therefore q\lor r)이다.
  4. 전제를 단순화하여 pp와 p→qp\to q를 각각 얻고, 긍정 논법으로 qq를 얻는다.

02. 명제 추론을 이어 붙이기

  1. p→q,¬p→r,r→sp\to q,\neg p\to r,r\to s에서 ¬q→s\neg q\to s를 도출하자. pp: 메일 보냄, qq: 프로그램 완성, rr: 일찍 잠, ss: 개운하게 일어남이다.
  2. (p∧q)∨r(p\land q)\lor r와 r→sr\to s에서 p∨sp\lor s를 도출하자.
  3. “모든 문제를 풀면 이산수학을 배운다. 이산수학을 배웠다. 따라서 모든 문제를 풀었다”는 타당한가?
  4. p→¬q,¬q→r,¬rp\to\neg q,\neg q\to r,\neg r에서 ¬p\neg p를 도출하자.
  5. ¬p∨q\neg p\lor q와 p∨¬rp\lor\neg r의 용해 결과를 쓰자.
해설 보기
  1. 첫 전제의 대우는 ¬q→¬p\neg q\to\neg p. 이를 ¬p→r\neg p\to r와 연결하면 ¬q→r\neg q\to r, 다시 r→sr\to s와 연결하면 ¬q→s\neg q\to s다.
  2. 분배하면 (p∨r)∧(q∨r)(p\lor r)\land(q\lor r)이다. 단순화로 p∨rp\lor r, 둘째 전제에서 ¬r∨s\neg r\lor s를 얻어 용해하면 p∨sp\lor s다.
  3. 부당하다. p→q,q∴pp\to q,q\therefore p는 후건 긍정의 오류다. p=F,q=Tp=F,q=T이면 전제는 모두 참인데 결론은 거짓이다.
  4. ¬q→r\neg q\to r와 ¬r\neg r에 부정 논법을 적용해 ¬¬q\neg\neg q, 즉 qq를 얻는다. 이어 p→¬qp\to\neg q와 qq로부터 ¬p\neg p를 얻는다.
  5. pp와 ¬p\neg p를 제거하여 q∨¬rq\lor\neg r를 얻는다.

03. 한정 명제의 추론

  1. 모든 양의 정수 nn에서 n>4→n2<2nn>4\to n^2<2^n이 참이라고 주어졌다. 1002<2100100^2<2^{100}을 도출하자.
  2. 모든 반 학생이 이산수학을 좋아하고 철수가 반 학생이다. 철수가 이산수학을 좋아함을 도출하는 두 규칙은?
  3. ∃x(P(x)∧¬Q(x))\exists x(P(x)\land\neg Q(x)), ∀x(P(x)→R(x))\forall x(P(x)\to R(x))에서 ∃x(R(x)∧¬Q(x))\exists x(R(x)\land\neg Q(x))를 도출하자.
해설 보기
  1. 전칭 예시화로 100>4→1002<2100100>4\to100^2<2^{100}. 100>4100>4와 긍정 논법을 적용하면 결론이다. 전칭 명제 자체는 여기서 전제로 주어진 것이다.
  2. 전칭 예시화로 철수에 대한 조건문을 얻고 긍정 논법을 적용한다.
  3. 존재 예시화로 새 증인 aa를 잡아 P(a)∧¬Q(a)P(a)\land\neg Q(a)를 얻는다. 단순화로 두 성분을 꺼내고, 전칭 예시화로 P(a)→R(a)P(a)\to R(a)를 얻는다. 긍정 논법으로 R(a)R(a), 논리곱 도입으로 R(a)∧¬Q(a)R(a)\land\neg Q(a), 존재 일반화로 결론을 얻는다. 처음부터 끝까지 같은 증인 aa를 사용한다.

04. 전칭 명제의 연쇄

∀x(P(x)→Q(x))\forall x(P(x)\to Q(x))와 ∀x(Q(x)→R(x))\forall x(Q(x)\to R(x))에서 ∀x(P(x)→R(x))\forall x(P(x)\to R(x))를 증명하자.

해설 보기

임의의 원소 aa를 잡는다. 전칭 예시화로 P(a)→Q(a)P(a)\to Q(a)와 Q(a)→R(a)Q(a)\to R(a)를 얻는다. P(a)P(a)를 가정하면 두 번의 긍정 논법으로 Q(a)Q(a), R(a)R(a)가 따라온다. 가정을 해제하면 P(a)→R(a)P(a)\to R(a)다. aa가 임의였으므로 전칭 일반화하여 ∀x(P(x)→R(x))\forall x(P(x)\to R(x))를 얻는다.

05. 결론이 실제로 따라오는지 확인하기

다음 전제에서 ∃xR(x)\exists xR(x)가 따라오는지 판단하자. 따라오지 않으면 반례 해석을 제시하고 실제로 도출되는 결론을 찾자.

∀x(P(x)∨Q(x)),∀x(¬Q(x)∨S(x)),∀x(R(x)→¬S(x)),∃x¬P(x).\forall x(P(x)\lor Q(x)),\quad \forall x(\neg Q(x)\lor S(x)),\quad \forall x(R(x)\to\neg S(x)),\quad \exists x\neg P(x).
해설 보기

∃xR(x)\exists xR(x)는 따라오지 않는다. 정의역을 {a}\{a\}로 두고 P(a)=F,Q(a)=T,S(a)=T,R(a)=FP(a)=F,Q(a)=T,S(a)=T,R(a)=F로 두면 네 전제는 모두 참인데 ∃xR(x)\exists xR(x)는 거짓이다.

실제로는 ∃x¬R(x)\exists x\neg R(x)를 도출할 수 있다.

단계식근거
1¬P(a)\neg P(a)존재 예시화, 새 증인
2P(a)∨Q(a)P(a)\lor Q(a)전칭 예시화
3Q(a)Q(a)1, 2의 선언적 삼단논법
4¬Q(a)∨S(a)\neg Q(a)\lor S(a)전칭 예시화
5S(a)S(a)3, 4의 선언적 삼단논법
6R(a)→¬S(a)R(a)\to\neg S(a)전칭 예시화
7¬R(a)\neg R(a)5, 6의 부정 논법
8∃x¬R(x)\exists x\neg R(x)존재 일반화

∃x¬R(x)\exists x\neg R(x)가 참이라고 해서 항상 ∃xR(x)\exists xR(x)가 거짓이라는 뜻은 아니다. 다른 원소에서 RR이 참일 수 있다. 위의 한 원소 반례가 보여 주는 것은 요청된 결론이 전제에 의해 보장되지 않는다는 점이다.

06. 직접증명과 대우증명

  1. 정수 nn이 짝수이면 n2n^2이 짝수임을 직접증명하자.
  2. 두 유리수의 합이 유리수임을 보이자.
  3. n2n^2이 홀수이면 nn이 홀수임을 대우로 보이자.
  4. 양의 정수 a,ba,b와 n=abn=ab에 대해 a≤na\le\sqrt n 또는 b≤nb\le\sqrt n임을 보이자.
  5. 두 홀수의 합이 짝수임을 직접증명하자.
해설 보기
  1. n=2kn=2k인 정수 kk가 있으므로 n2=4k2=2(2k2)n^2=4k^2=2(2k^2)다.
  2. a=p/q,b=r/sa=p/q,b=r/s로 쓰되 p,q,r,sp,q,r,s는 정수이고 q,s≠0q,s\ne0이다. a+b=(ps+qr)/(qs)a+b=(ps+qr)/(qs)는 정수 분자와 0이 아닌 정수 분모의 비다.
  3. 대우인 “nn이 짝수이면 n2n^2이 짝수”를 1에서 증명했다.
  4. 둘 다 n\sqrt n보다 크다고 가정하면 ab>(n)2=nab>(\sqrt n)^2=n으로 ab=nab=n과 모순이다.
  5. a=2k+1,b=2ℓ+1a=2k+1,b=2\ell+1로 놓으면 a+b=2(k+ℓ+1)a+b=2(k+\ell+1)이다. 서로 다른 홀수일 수 있으므로 k,ℓk,\ell을 따로 둔다.

07. 세 명제의 동치와 3의 배수

  1. 정수 nn에 대해 “nn이 짝수”, “n−1n-1이 홀수”, “n2n^2이 짝수”가 동치임을 보이자.
  2. 3∣n3\mid n이면 3∣n23\mid n^2임을 직접증명하자.
  3. 3∤n23\nmid n^2이면 3∤n3\nmid n임을 보이자.
  4. 3\sqrt3의 무리성을 귀류법으로 증명하려면 어떤 가정으로 시작하는가?
해설 보기
  1. n=2kn=2k이면 n−1=2(k−1)+1n-1=2(k-1)+1이다. 반대로 n−1=2k+1n-1=2k+1이면 n=2(k+1)n=2(k+1)이다. 또한 짝수의 제곱은 짝수다. 역방향은 대우로, n=2k+1n=2k+1이면 n2=2(2k2+2k)+1n^2=2(2k^2+2k)+1이 홀수임을 보이면 된다.
  2. n=3kn=3k이므로 n2=9k2=3(3k2)n^2=9k^2=3(3k^2)다.
  3. 대우가 바로 2번이다. 나누어떨어지지 않음을 직접 다루는 대신 배수의 정의를 쓸 수 있다.
  4. 3=a/b\sqrt3=a/b인 서로소 정수 a,ba,b가 있으며 b≠0b\ne0이라고 가정한다. 그러면 a2=3b2a^2=3b^2. 정수 제곱의 3에 대한 나머지는 0 또는 1이므로 3∣a3\mid a. a=3ca=3c를 대입하면 b2=3c2b^2=3c^2여서 3∣b3\mid b도 따라와 서로소 조건과 모순이다.

08. 공허한 증명과 자명한 증명

  1. “모든 소수는 2보다 크다”에서 한정 기호를 쓰고 참인지 판정하자.
  2. “정수 nn에 대해 3n+23n+2가 짝수다”를 공허하게 증명할 수 있는가? 공허한 증명이 가능한 조건을 설명하자.
  3. 공허한 증명과 자명한 증명을 비교하자.
해설 보기
  1. ∀n(Prime⁡(n)→n>2)\forall n(\operatorname{Prime}(n)\to n>2)다. 소수 2가 반례여서 거짓이다.
  2. 전건 없이 모든 정수에 대해 주장한다면 거짓이다. n=1n=1에서 3n+2=53n+2=5가 홀수다. 공허한 증명은 p→qp\to q에서 전건 pp가 거짓임을 보일 때 가능하다. 존재하지 않는 전제를 임의로 붙여 주어진 주장을 증명했다고 할 수는 없다.
  3. 공허한 증명은 전건이 거짓이어서, 자명한 증명은 후건이 참이어서 조건문이 참임을 보인다. 예를 들어 (n<n)→q(n<n)\to q는 공허하고, p→(n2≥0)p\to(n^2\ge0)는 실수 nn에서 자명하다.

09. 귀류법으로 무리수의 합 증명하기

무리수 xx와 유리수 rr의 합 x+rx+r가 무리수임을 귀류법으로 보이자.

해설 보기

x+r=sx+r=s가 유리수라고 가정한다. 유리수 s=a/b,r=c/ds=a/b,r=c/d로 쓰되 b,d≠0b,d\ne0이면

x=s−r=ad−bcbd.x=s-r=\frac{ad-bc}{bd}.

이는 정수의 비이므로 유리수다. xx가 무리수라는 가정과 모순이다. 따라서 x+rx+r는 무리수다. 두 무리수의 합까지 항상 무리수라는 뜻은 아니다. 예를 들어 2+(−2)=0\sqrt2+(-\sqrt2)=0이다.

10. 경우별 증명

  1. 모든 정수 nn에서 n2≥nn^2\ge n임을 보이자.
  2. 모든 실수 x,yx,y에서 ∣xy∣=∣x∣∣y∣|xy|=|x||y|임을 네 부호 경우로 보이자.
  3. 모든 정수 nn에서 n(n+1)n(n+1)이 짝수임을 보이자.
해설 보기
  1. n=0n=0이면 등호다. n≥1n\ge1이면 n≥1n\ge1에 양수 nn을 곱해 n2≥nn^2\ge n. n≤−1n\le-1이면 n2≥0>nn^2\ge0>n이다. 정수는 이 세 경우로 빠짐없이 나뉜다.
  2. 다음 표에서 두 값이 항상 같다.
조건∣xy∣\lvert xy\rvert∣x∣∣y∣\lvert x\rvert\lvert y\rvert
x≥0,y≥0x\ge0,y\ge0xyxyxyxy
x≥0,y<0x\ge0,y<0−xy-xyx(−y)x(-y)
x<0,y≥0x<0,y\ge0−xy-xy(−x)y(-x)y
x<0,y<0x<0,y<0xyxy(−x)(−y)(-x)(-y)
  1. n=2kn=2k이면 n(n+1)=2k(n+1)n(n+1)=2k(n+1), n=2k+1n=2k+1이면 n(n+1)=2n(k+1)n(n+1)=2n(k+1)로 모두 2의 배수다.

11. 존재·유일성·반례와 증명 방법 선택

  1. 구성적 존재증명과 비구성적 존재증명의 차이는?
  2. “두 정수의 곱이 홀수이면 두 정수 모두 홀수”에 적합한 증명 방법은?
  3. “nn보다 작은 모든 소수의 합은 소수다”를 판정하자.
  4. 유일하게 존재함을 보일 때 필요한 두 부분은?
  5. “n2n^2이 짝수이면 nn이 짝수”에 대우증명이 편리한 이유는?
  6. 5보다 큰 모든 소수가 홀수임을 보이자.
  7. 12가 두 소수의 합임을 구성적으로 보이자.
해설 보기
  1. 구성적 증명은 조건을 만족하는 대상을 직접 제시한다. 비구성적 증명은 어떤 대상인지 확정하지 않고 존재를 보인다. 비구성적 증명이 반드시 귀류법인 것은 아니다.
  2. 대우증명이 자연스럽다. 적어도 하나가 짝수이면 곱이 짝수다. 예를 들어 a=2ka=2k이면 ab=2(kb)ab=2(kb). 이 명제는 존재 명제가 아니므로 구성적/비구성적 존재증명 중 하나로 분류할 필요가 없다.
  3. 거짓이다. n=6n=6이면 2+3+5=102+3+5=10으로 소수가 아니다.
  4. 실제 해가 있다는 존재성과, 임의의 두 해가 같다는 유일성이 모두 필요하다.
  5. nn이 홀수일 때 n=2k+1n=2k+1을 대입하면 n2=2(2k2+2k)+1n^2=2(2k^2+2k)+1이 되어 바로 홀수임을 보일 수 있다.
  6. 소수 p>5p>5의 약수는 1과 pp뿐이다. 22는 어느 쪽도 아니므로 2∤p2\nmid p, 즉 pp는 홀수다.
  7. 12=5+712=5+7이고 5와 7은 소수다. 조건을 만족하는 두 수를 실제 제시했으므로 존재가 증명된다.
Discussion

Comments