離散数学：練習問題と試験問題

コンピュータサイエンスとあらゆる証明の数学：命題論理と量化子、集合・関係・関数、最短経路と全域木を扱うグラフ、そして RSA に至る整数論。試験では厳密な答えが求められるので、電卓よりも丁寧な表や図が大切です。

この科目を無料で練習するこの科目を練習する模擬試験を受ける毎日 5 問まで無料。カード登録は不要です。

直前対策パック（PDF）公式集、解法のステップ、完全な解答つきの演習問題。そのまま印刷できます。

この科目のトピック

  1. 命題論理と証明真理値表 · 同値と証明法 · 量化子と論証計算
  2. 集合・関係・関数ベン図と部分集合 · 包除原理と関係 · 関数と数え上げ計算
  3. グラフ理論次数と辺 · オイラー路と木 · 最短経路と全域木計算
  4. 整数論と合同式gcd と余り · 逆元と合同式 · 冪剰余と RSA計算

離散数学の試験のコツ

  • 真理値表やベン図を最後まで書き出しましょう。ミスの多くは、行や領域を飛ばすことから生まれます。
  • 主張を反証するには反例が 1 つあれば十分です。証明するには、すべての場合を確かめるか、一般的な議論を示す必要があります。
  • 合同式の計算では、ステップごとに剰余をとり、余りを 0 から n − 1 の間に保ちます。

解答例

命題論理と証明やさしい
pq¬(p ∨ q) → q11100100

真理値表のちょうど 1 行が ¬(p ∨ q) → q を偽にします。その行をクリックしてください。

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
ヒントを表示
  1. a → b は、a = 1 かつ b = 0 のときだけ 0 です。 ¬a は値を反転させます。 a ∨ b は、両方が 0 のときだけ 0 です。
  2. まず主結合子を考えましょう：論理式全体が 0 になるには、その両辺がどうでなければなりませんか？
  3. 各部分に列を用意しましょう：p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q。
答えと解説を表示

真理値表：n 個の異なる変数をもつ論理式には、真理値のすべての組み合わせに対応する 2ⁿ 行があります（1 = 真、0 = 偽）。内側から順に進め、部分式ごとに列を用意します。¬a は値を反転させ、a ∧ b は両方が 1 のときだけ 1、a ∨ b は両方が 0 のときだけ 0、a → b は a = 1 かつ b = 0 のときだけ 0、a ↔ b は両辺が等しいとき 1 です。

真理値表を行ごとに見る

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

その行

p = 0, q = 0 → ¬(p ∨ q) → q = 0

答え

p = 0, q = 0
集合・関係・関数ふつう
UMPC

53 人の 1 年生のうち、35 人が数学（M）、28 人が物理（P）、29 人が化学（C）に合格しました。M と P の両方に合格したのが 20 人、M と C が 18 人、P と C が 10 人、3 科目すべてに合格したのが 6 人です。 3 つの集合のどれにも属さないのは何人ですか？

|U| = 53

求めるもの： |(M ∪ P ∪ C)′|

ヒントを表示
  1. ベン図は中心から外へ向かって埋めましょう：まず 3 つすべて、次に 2 つずつ、最後に各集合だけ。
  2. M と P だけ（C は含まない）：20 − 6 = 14。M だけ：35 − 14 − 12 − 6 = 3。
  3. 少なくとも 1 つの集合：35 + 28 + 29 − 20 − 18 − 10 + 6 = 50。
答えとステップごとの解答を表示

集合とベン図：A ∪ B は A または B（または両方）に属する要素、A ∩ B は両方に属する要素、A − B は A の要素のうち B に属さないもの、補集合 A′ は U の要素のうち A に属さないものすべてです。ベン図では、どの集合の式も領域の和集合なので、領域ごとに数えます。包除原理：|A ∪ B| = |A| + |B| − |A ∩ B|、|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|。

中心と 2 つずつの組

M ∩ P ∩ C: 6
M ∩ P 単独: 20 − 6 = 14
M ∩ C 単独: 18 − 6 = 12
P ∩ C 単独: 10 − 6 = 4

各集合だけ

M 単独: 35 − 14 − 12 − 6 = 3
P 単独: 28 − 14 − 4 − 6 = 4
C 単独: 29 − 12 − 4 − 6 = 7

答え

|M ∪ P ∪ C| = 50
|(M ∪ P ∪ C)′| = 53 − 50 = 3

答え

|(M ∪ P ∪ C)′| = 3

練習のしかた

  • 「この科目を練習する」では、本番の試験のように、すべてのトピックの問題が混ざって出題されます。
  • 問題ごとに数値が変わるので、答えではなく解き方が身につきます。
  • 行き詰まったら、まず小さなヒントを開き、必要なときだけ詳しい解説を見ましょう。
  • 模擬試験には制限時間があり、ヒントはありません。最後にスコアと詳しい振り返りが表示されます。

関連する科目

コンピュータサイエンス基礎データ構造とアルゴリズム微分積分学 I統計学入門工業数学統計学 II：統計的推測微分方程式工学数学 2
この科目を無料で練習するこの科目を練習する模擬試験を受ける毎日 5 問まで無料。カード登録は不要です。