C9주차 — 증명 기법 리뷰: 채점자 되기 + 전반부 종합 시험

C9주차 — 증명 기법 리뷰: 채점자 되기 + 전반부 종합 시험#

이 주의 길잡이

핵심 문장: Chartrand 전반부의 여덟 주는 하나의 기법 지도로 접히고, 그 지도의 마지막 단계가 증명 평가다 — 남의 답안을 채점하는 절차와 자기 답안을 검사하는 절차는 같은 다섯 걸음이다.

이 주의 위치: 2학기(Chartrand) 20주의 C9주차. 새 진도가 없는 첫 평가 주간이며, 범위는 C1주차~C8주차 전체(글쓰기\(\cdot\)집합\(\cdot\)논리\(\cdot\)양화사\(\cdot\)직접\(\cdot\)대우\(\cdot\)자명\(\cdot\)공허\(\cdot\)증명 평가\(\cdot\)나눗셈\(\cdot\)합동\(\cdot\)반례\(\cdot\)귀류\(\cdot\)존재\(\cdot\)귀납)다. 1권 24주차의 중간 종합 평가와 S17주차의 기법 선택 시험이 여기서 Chartrand의 소재로 다시 놓인다. 다음 주 C10주차부터는 참\(\cdot\)거짓이 표시되지 않은 명제를 받으므로, 그 전에 기법 선택 절차와 채점 절차를 고정해 둔다.

원서 대응: Chartrand 7장(Reviewing Proof Techniques)과 그 앞의 장 전체. 새로 읽을 장은 없다. 시험 전날 각 장의 요약 절만 훑는 것으로 충분하다.

이번 주 목표#

  1. C1주차~C8주차(글쓰기\(\cdot\)집합\(\cdot\)논리\(\cdot\)양화사\(\cdot\)직접\(\cdot\)대우\(\cdot\)자명\(\cdot\)공허\(\cdot\)귀류\(\cdot\)존재\(\cdot\)귀납)를 하나의 기법 지도로 통합한다.

  2. 증명 평가(C5주차)를 채점 훈련으로 옮긴다 — 제시된 증명을 다섯 걸음으로 검사하고 옳음\(\cdot\)틀림\(\cdot\)불완전 가운데 하나로 판정한다.

  3. 종합 시험 20문항으로 전반부의 기법을 점검하고, 오답을 주차별 재학습으로 되돌린다.

  4. 후반부(C10주차~C20주차: 추측\(\cdot\)동치관계\(\cdot\)함수\(\cdot\)기수\(\cdot\)정수론\(\cdot\)조합론\(\cdot\)해석학\(\cdot\)군론)로 가는 다리를 확인한다.

준비 운동 (C1~C8 총복습)#

  1. S17주차의 기법 선택 결정 나무를 백지에 재현하시오. Chartrand 전반부도 같은 나무를 쓴다.

  2. C5주차의 증명 평가 다섯 걸음을 쓰시오.

  3. C1주차~C8주차의 [백지 암기 대상] 가운데 불안한 것 세 개를 골라 다시 채우시오.

세 항목에서 막힌 자리는 그대로 시험에서 막히는 자리다. 채워지지 않은 항목이 있으면 아래 §1을 읽기 전에 해당 주차의 [백지 암기 대상] 상자로 돌아간다. §1은 새 내용을 주는 절이 아니라 이미 가진 것을 하나의 순서로 배열하는 절이므로, 배열될 재료가 비어 있으면 §1도 비어 있는 채로 외우게 된다.

자주 나오는 세 가지 답 — 1번 문항#

1번에 적은 답은 대개 다음 세 유형 중 하나다. 셋 다 나무의 일부를 정확히 붙들었고, 셋 다 이번 주에 메울 간격이 하나씩 있다.

  • 유형 1 — 갈래 이름은 적었으나 갈래를 가르는 물음이 없다. “부정형이면 귀류”,

“\(\exists\)이면 구성”처럼 잎의 이름을 나열한다. 잎의 목록은 옳다. 간격은 명제를 받았을 때 어느 잎으로 내려갈지 정해 주는 물음이 적혀 있지 않다는 것이다 — 이름만 있는 나무는 검색표이지 절차가 아니다. 문제 1의 여섯 명제 앞에서 이 간격이 그대로 드러난다.

  • 유형 2 — 기법 이름 목록만 나열하고 순서를 잃는다. 직접\(\cdot\)대우\(\cdot\)귀류\(\cdot\)존재\(\cdot\)귀납을

적되 어느 것을 먼저 묻는지가 없다. 재료는 전부 있다. 간격은 순서이며, 순서가 없으면 조건문 앞에서 대우와 귀류 중 무엇을 먼저 시도할지가 매번 새로 결정된다. 문제 3이 요구하는 것이 정확히 그 순서다.

  • 유형 3 — 진리 상태 점검을 아예 빠뜨린다. 나무를 “겉모양 \(\to\) 기법”의 한 걸음으로

적는다. 그 한 걸음은 옳다. 간격은 그 앞에 명제가 참인지를 묻는 단계가 있다는 것이고, 이 단계가 없으면 거짓 명제에도 기법이 지목된다. 문제 1(e)와 문제 19가 이 자리를 본다.

Chartrand 전반부 기법 지도 [백지 암기 대상]#

C1주차~C8주차는 기법을 하나씩 새로 들여온 여덟 주가 아니다. S17주차의 기법 선택 결정 나무를 Chartrand의 무대 — 나눗셈\(\cdot\)합동\(\cdot\)집합\(\cdot\)데카르트 곱 — 위에서 재조직한 여덟 주다. 시험장에 오는 것은 명제 한 줄뿐이고, 그 한 줄에서 첫 문장을 뽑아내는 절차만 있으면 된다. 그 절차를 한 장으로 접은 것이 아래의 지도다.

백지 암기 대상

Chartrand 전반부 기법 지도 — 0~4단계

0단계 — 소통과 판 세팅 (항상 한다). 기호 사용 10원칙(C1주차)을 지키고, 명제를 가정과 결론으로 분해하며, 숨은 양화사와 정의 속에 접힌 구조를 문면으로 끌어낸다(C2주차\(\cdot\)C4주차).

1단계 — 진리 상태 점검 (C5주차). 증명 노동에 들어가기 전에 세 물음을 이 순서대로 한 번 돌린다. ① 가정이 무대의 어떤 대상에서도 거짓인가 \(\to\) 공허한 증명. ② 아니면, 결론이 무대의 모든 대상에서 참인가 \(\to\) 자명한 증명. ③ 아니면, 가정을 만족하는 대상이 하나라도 있는데 그 대상에서 결론이 거짓인가 \(\to\) 명제가 거짓이므로 반례. 순서가 물음의 일부다 — ①을 건너뛰고 ③만 보면, 결론이 무대 전체에서 거짓이어도 가정이 무대 전체에서 거짓이면 참인 명제(무대 \(\mathbb{R}\)의 “\(x^2 < 0\)이면 \(x^2 + 1 < 0\)이다”)를 거짓으로 판정하게 된다.

2단계 — 결론의 겉모양에서 기법으로.

\(\cdot\) 부정형(무리수\(\cdot\)\(\neq\)\(\cdot\)부재) \(\to\) 논리 동치로 부정을 전개한 뒤(C3주차) 귀류(C7주차) 또는 대우(C5주차)

\(\cdot\) \(\exists\) 또는 숨은 \(\exists\) \(\to\) 구성적 존재(증인 제시) 또는 비구성적 존재(C7주차)

\(\cdot\) \(\forall\) 또는 총칭 \(\to\) 직접 증명(C5주차), 집합 무대이면 원소 추적(C6주차)

\(\cdot\) \(\lor\) \(\to\) 소거법 / \(\land\) \(\to\) 조각마다 따로 / “정확히 하나” \(\to\) 존재 + 유일

\(\cdot\) 자연수 전체에 대한 \(\forall\) \(\to\) 귀납(약한\(\cdot\)강한\(\cdot\)최소 반례, C8주차)

\(\cdot\) 거짓인 \(\forall\) \(\to\) 반례(C7주차)

3단계 — 무대별 정의 전개 (C6주차). 나눗셈\(\cdot\)합동\(\cdot\)실수 부등식\(\cdot\)집합 포함\(\cdot\)데카르트 곱 가운데 어느 무대인지 정하고, 그 무대의 정의를 펼쳐 전진면과 후진면을 잇는다.

4단계 — 검증 (C5주차). 증명 평가 다섯 걸음을 자기 답안에 돌린다.

4단계가 부르는 절차는 그 자체로 백지 암기 대상이며, 이번 주 문항의 절반이 이 다섯 걸음을 남의 답안에 돌리는 일이다.

백지 암기 대상

증명 평가 다섯 걸음 (C5주차)

① 명제 진위 — 명제 자체가 참인가. 거짓 명제에 붙은 증명은 반드시 틀렸다.

② 논리 — 각 줄이 앞 줄\(\cdot\)정의\(\cdot\)이미 증명한 명제에서 따라오는가.

③ 가정 사용 — 가정을 실제로 소비했는가. 소비하지 않았다면 자명한 증명인가, 다른 명제를 증명한 것인가.

④ 양화사와 자격 — 특정 값 몇 개로 전칭을 대신하지 않았는가. 문자에 붙은 자격을 지켰는가.

⑤ 전달 — 문자를 소개했는가, 완결된 문장인가(C1주차).

판정은 셋 중 하나로 적는다: 옳음 / 틀림(어느 줄이 왜) / 불완전(무엇이 빠졌는가).

다섯 걸음의 순서는 임의가 아니다. 각 걸음이 맡은 일과, 그 걸음을 빼면 무엇이 무너지는지를 표로 둔다. 셋째 열은 이번 주 문항으로 채운다.

걸음

하는 일

이 걸음을 빼면 무엇이 무너지는가

① 명제 진위

채점 대상이 참인 명제인지 먼저 확인한다

문제 1(e)류의 거짓 명제에 붙은 매끄러운 계산을 옳음으로 통과시킨다

② 논리

줄과 줄 사이의 연결을 검사한다

문제 15의 “이것이 짝수이므로”가 걸리지 않고, 문제 9의 마지막 “모순” 한 줄도 딛고 설 자리 없이 통과한다

③ 가정 사용

이 답안이 무엇을 증명했는지 묻는다

문제 11에서 답안이 실제로 증명한 명제가 원명제의 대우라는 사실을 채점표에 적을 수 없다

④ 양화사와 자격

일반성을 검사한다

문제 8\(\cdot\)19(a)의 특정 값 확인이 전칭 명제의 증명으로 통과한다

⑤ 전달

읽힘을 검사한다

문제 13의 미완결 표기가 그대로 남고, 채점자가 머릿속으로 재구성한 문장을 채점하게 된다

지도의 다섯 단계도 마찬가지다. 같은 형식으로 해부한다.

단계

하는 일

이 단계를 빼면 무엇이 무너지는가

0단계 — 판 세팅

가정\(\cdot\)결론을 분해하고 숨은 양화사와 정의 속 구조를 문면으로 끌어낸다

2단계가 읽을 겉모양이 없다 — “\(A \cap B \subseteq A\)”는 \(\subseteq\)를 풀기 전에는 \(\forall\)로 보이지 않아 원소 추적에 닿지 못한다

1단계 — 진리 상태 점검

증명 노동에 들어가기 전에 가정과 결론의 진리 상태를 잰다

언제나 거짓인 결론에 매끄러운 계산을 붙이게 된다 — 문제 1(e)가 정확히 이 자리다

2단계 — 구조 판독

전개된 결론의 최상위 구조에서 기법 하나를 지목한다

답안의 첫 문장 동사가 정해지지 않는다 — “…를 증명한다” 한 줄에서 멈춘다

3단계 — 무대 전개

무대를 정하고 그 정의를 전진\(\cdot\)후진 양면으로 펼친다

첫수만 있고 몸통이 빈 답안이 된다 — “임의로 잡자” 다음 줄에 결론이 곧바로 나온다

4단계 — 검증

다섯 걸음을 자기 답안에 돌린다

결론이 참이라는 이유로 자기 답안의 논리 결함을 통과시킨다

걸음 삭제 실험 — 1단계를 빼면. 진리 상태 점검의 의무를 지우고 2단계부터 돌리면 다음 답안이 합법이 된다.

삭제 실험 — 진리 상태 점검을 건너뛴 답안

명제: 모든 정수 \(n\)에 대해 \(n^2 + n + 3\)이 짝수이다 (문제 1(e)).

“겉모양이 ‘모든 \(n\)에 대해 …’이므로 \(n\)에 대한 귀납법으로 증명한다. 기저 \(n = 1\):

\(1 + 1 + 3 = 5\)이다. 귀납 가정으로 \(n^2 + n + 3\)이 짝수라 하자. 그러면

\((n+1)^2 + (n+1) + 3 = (n^2 + n + 3) + (2n + 2)\)이고, 앞 덩어리는 가정으로 짝수,

뒤 덩어리 \(2n + 2\)도 짝수이므로 합도 짝수다. 따라서 모든 \(n\)에서 \(n^2 + n + 3\)은

짝수이다.”

이 답안에서 귀납 단계의 계산은 한 줄도 틀리지 않았다. 무너지는 곳은 기저다 — \(n = 1\)에서 나온 값은 \(5\)이고 \(5\)는 홀수이므로 기저가 성립하지 않는데, 답안은 “\(5\)이다”까지만 적고 짝수인지를 확인하지 않은 채 지나갔다. 그리고 기저가 무너지는 이유는 계산 실수가 아니라 명제 자체가 거짓이라는 데 있다 — \(n^2 + n = n(n+1)\)은 연속한 두 정수의 곱이라 언제나 짝수이므로 \(n^2 + n + 3\)은 언제나 홀수다. 1단계를 돌렸다면 2단계에 내려가기 전에 이 명제는 반례 갈래로 빠졌을 것이고, 귀납 단계의 매끄러운 계산에 쓴 시간은 처음부터 발생하지 않았을 것이다. 1단계가 없는 지도에서 이 답안을 잡아 줄 자리는 없다.

확인 1. 지도에서 1단계가 2단계보다 앞에 오는 이유는 무엇인가. 순서를 뒤집으면 어떤 답안이 나오는가.

답

2단계는 결론의 겉모양을 읽어 기법을 지목하는 단계이고, 그 지목은 명제가 참이라는

전제 위에서만 뜻이 있다. 순서를 뒤집으면 거짓인 명제에도 기법이 지목되고, 지목된

기법대로 증명을 밀어붙이다 어딘가에서 막힌 채 시간을 다 쓰게 된다. 문제 1(e)가

그 사례다 — 그 명제의 무대는 정수 전체이므로 2단계의 귀납 갈래(“자연수 전체에 대한

\(\forall\)”)가 문면 그대로 적용되지는 않지만, 겉모양이 (d)의 “모든 자연수 \(n\)에 대해 …”와

구별되지 않아 1단계를 건너뛰면 귀납으로 읽기 쉽다. 그런데 \(n^2 + n + 3\)은 어떤

정수에서도 짝수가 아니므로 귀납을 시작하면 기저에서 이미 무너진다. 1단계는 노동을

시작할 자격이 있는지 묻는 단계다.

확인 2. 명제 “정수 \(a, b\)에 대해 \(a \mid b\)이면 \(a \mid 3b\)이다”는 지도의 어느 단계에서 무엇으로 내려가는가.

답

1단계에 걸리는 것은 없다. 가정 “\(a \mid b\)”는 참이 되는 쌍이 있고, 결론

“\(a \mid 3b\)”도 거짓이 되는 쌍이 있으므로 자명하지도 공허하지도 않다. 2단계에서

결론은 부정형이 아니고 숨은 \(\exists\)다 — “\(3b = ak\)인 정수 \(k\)가 존재한다”이므로 직접

증명이다. 3단계의 무대는 나눗셈이고, 펼칠 정의는 C6주차의 정의 6.1이다. 전진면이

주는 것은 \(b = am\)인 정수 \(m\)이고, 후진면이 요구하는 것은 \(3b\)를

“\(a \times (\text{정수})\)” 꼴로 제작하는 일이다. 둘을 이으면 \(3b = 3am = a(3m)\)이 된다.

확인 3. 제시된 증명이 특정 값 두세 개만 확인하고 끝났다. 다섯 걸음 중 어느 걸음에서 걸리며, 판정 낱말은 무엇인가.

답

걸음 ④에서 걸리고, 판정은 불완전이다. “틀림”이 아니라는 점이 중요하다 —

적힌 계산 가운데 거짓인 문장이 하나도 없고 명제 자체도 참이므로, 지적할 것은

잘못된 줄이 아니라 없는 줄이다. 이 경우 채점표에는 “무엇이 빠졌는가”를 적는다.

곧 “확인한 값 밖의 대상 전부에 대한 논증이 없다”라고 적고, 임의의 대상을 잡는

첫 문장을 대안으로 제시한다.

확인 4. 3단계에서 합동 무대를 골랐다. 전진면과 후진면은 각각 무엇을 주고 무엇을 요구하는가.

답

펼칠 정의는 C6주차의 정의 6.2이고, 그 정의는 다시 정의 6.1로 되돌려진다. 가정

\(a \equiv b \pmod n\)의 전진면이 주는 것은 \(a - b = ns\)인 정수 \(s\)이고, 결론

\(c \equiv d \pmod n\)의 후진면이 요구하는 것은 차 \(c - d\)를

“\(n \times (\text{정수})\)” 꼴로 제작하는 일이다. 계산 문항에서는 이 전개 대신

합동의 대수 (C1)~(C5)와 거듭제곱 보존을 근거 ④로 인용하고, 큰 수를 합동인 작은

대표로 갈아 끼운다.

핵심 관찰. 이 절에 새 기법은 없다. 지도는 C1주차~C8주차를 “언제 쓰는가”로 재배열한 색인이고, 각 갈래 끝에 있는 것은 이미 이름을 가진 기법이다. 다만 S17주차의 기법 선택 결정 나무에 없던 항목이 둘 있다 — 1단계의 진리 상태 점검과 4단계의 증명 평가다. 둘 다 증명을 만드는 절차가 아니라 증명을 재는 절차이고, 이번 주 문항의 절반이 그 둘을 본다.

그 둘은 1권에서 감각으로 하던 일이 여기서 이름을 얻은 것이다. 1권 23주차 §1.5의 선택 순서도가 “무엇부터 시도할지”를 감각으로 잡던 자리는 여기서 지도의 2단계가 되고, 1권 24주차 문제 19의 “다음 답안의 결함을 모두 찾으시오”가 눈썰미로 요구하던 채점은 여기서 다섯 걸음이라는 순서와 판정 낱말 셋이라는 서식을 얻는다. 1권에서는 결함을 찾아내면 되었지만, 여기서는 어느 걸음에서 걸렸는지와 판정 낱말이 답안에 적혀야 한다.