証明ドリル

目的

第3章「証明技法」を定着させるための追加問題です。各問題では、次の順に書いてください。

1. 示す命題
2. 使う証明方法
3. 定義展開
4. 証明本文

難易度ラベル

• [A] 基本: 定義を読む・単純計算をする。
• [B] 標準: 複数の定義を組み合わせる。
• [C] 発展: 証明・設計・実装の説明が必要。
• [D] 実装: 実行可能なコードまたは明確な擬似コードが必要。
• [E] 接続: 本体教科書の概念へ橋渡しする。

A. 定義展開

1. [A][証明] A⊆B かつ C⊆D ならば A∪C⊆B∪D を証明せよ。
2. [A][証明] A⊆B ならば A∩C⊆B∩C を証明せよ。
3. [A][証明] A\B⊆A を証明せよ。
4. [A][証明] A⊆B ならば P(A)⊆P(B) を証明せよ。
5. [A][証明] f: A→B と g: B→C が単射ならば、g∘f も単射であることを証明せよ。
6. [A][証明] f: A→B と g: B→C が全射ならば、g∘f も全射であることを証明せよ。

B. 偶奇・整除

1. [A][証明] 偶数と奇数の和は奇数であることを証明せよ。
2. [A][証明] 奇数同士の和は偶数であることを証明せよ。
3. [B][証明] a が3で割り切れ、b が3で割り切れるなら、a+b も3で割り切れることを証明せよ。
4. [B][証明] n^2 が奇数ならば n は奇数であることを証明せよ。
5. [B][証明] ab が偶数ならば a または b は偶数であることを対偶で証明せよ。

C. 帰納法

1. [B][証明] 1+2+...+n=n(n+1)/2 を帰納法で証明せよ。
2. [B][証明] 1^2+2^2+...+n^2=n(n+1)(2n+1)/6 を帰納法で証明せよ。
3. [B][証明] 2^n≥n+1 を n≥0 で証明せよ。
4. [B][証明] 3^n≥2n+1 を n≥0 で証明せよ。
5. [B][証明] 長さ n の 0/1 文字列が 2^n 個あることを帰納法で証明せよ。

D. 関係

1. [C][証明] 整数上の関係 aRb ⇔ a-b が5で割り切れる、が同値関係であることを証明せよ。
2. [C][証明] 整数上の関係 aRb ⇔ a≤b が半順序であることを証明せよ。
3. [C][証明] 集合上の関係 A R B ⇔ A⊆B が半順序であることを証明せよ。
4. [C][証明] 有向グラフの到達可能性関係が反射的かどうか、パス長0を許す定義と許さない定義で比較せよ。

E. 構造帰納法

1. [C][証明] 文字列長について |uv|=|u|+|v| を、v の構造に関する帰納法で証明せよ。
2. [C][証明] 二分木の葉数が内部節点数+1になる条件を明示し、その条件下で証明せよ。
3. [C][証明] 命題論理式の構造に関する帰納法の基底ケースと帰納ステップを説明せよ。

解答方針

このドリルは、完全解答を丸写しする用途ではなく、証明の型の訓練用です。採点では、結論よりも次を重視してください。

• 任意の対象を正しく取っているか。
• 存在命題では構成対象を示しているか。
• 帰納法で基底部と帰納ステップが分かれているか。
• 関係の証明で、必要な性質を漏れなく示しているか。