離散数学：直前対策パック

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

量化子と論証：¬∀x P(x) ≡ ∃x ¬P(x)、¬∃x P(x) ≡ ∀x ¬P(x)。否定を内側へ移し、通過する量化子をすべて入れ替え、内側の式は ¬(a → b) ≡ a ∧ ¬b のような命題論理の法則で否定します。論証は、すべての前提が 1 であるどの行でも結論が 1 のとき、妥当です。前提が真で結論が偽になる行が 1 つでもあれば、それは反例であり、その論証が妥当でないことを示します。

関係：集合 X 上の関係 R は、順序対 (x, y) の集合です。R が反射的であるとは、X のすべての x について (x, x) ∈ R となること、対称的であるとは、(x, y) ∈ R のとき必ず (y, x) ∈ R となること、反対称的であるとは、(x, y) と (y, x) の両方が R に属するのは x = y のときだけであること、推移的であるとは、(x, y) と (y, z) が R に属すれば (x, z) ∈ R となることです。同値関係は反射的・対称的・推移的で、X を互いに素な類に分けます。

関数と数え上げ：関数 f: A → B は、A のすべての要素に、B の中の像をちょうど 1 つずつ対応させます。f が単射（1 対 1）であるとは、異なる要素が異なる像をもつこと、全射（上への写像）であるとは、B のすべての要素が像になっていること、全単射であるとは、その両方が成り立つことです。|A| = m、|B| = n のとき、関数は nᵐ 個、単射は n!/(n − m)! 個（m ≤ n）、全射は包除原理により Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ 個あります。|𝒫(A)| = 2ᵐ、|A × B| = m·n です。

オイラー、ハミルトン、木：連結グラフは、すべての頂点の次数が偶数のときオイラー閉路（すべての辺を 1 回ずつ通って始点に戻る）をもち、ちょうど 2 つの頂点の次数が奇数のとき、閉路でないオイラー路をもちます。その路は、一方の奇数次数の頂点から他方へ通ります。ハミルトン閉路はすべての頂点を 1 回ずつ訪れ、K_n には (n − 1)!/2 個あります。n 個の頂点をもつ木には n − 1 本の辺があり、m 本の辺をもつ連結グラフは、m − n + 1 本の辺を取り除いても全域木が残ります。

最短経路と全域木：ダイクストラ法は毎ラウンド 1 つの頂点を確定します：暫定距離が最小の未確定の頂点です。その距離は最終となり、各隣接頂点 v は d(v) = min(d(v), d(u) + w(u, v)) と更新されます。クラスカル法は、辺を軽い順に取り、閉路をつくる辺を飛ばして最小全域木をつくります。プリム法は、始点から 1 本の木を成長させ、その木から出る最も軽い辺を常に加えます。n 個の頂点の全域木には n − 1 本の辺があります。

逆元と合同式：a が n を法として逆元をもつのは、gcd(a, n) = 1 のときに限ります。拡張ユークリッドの互除法で 1 = s·n + t·a と書くと、a⁻¹ ≡ t (mod n) です。gcd(a, n) = 1 のとき、合同式 a·x ≡ b (mod n) の解は x ≡ a⁻¹·b です。法が互いに素な 2 つの合同式 x ≡ r₁ (mod m₁) と x ≡ r₂ (mod m₂) には、m₁·m₂ を法として 1 つの解があります（中国の剰余定理）。オイラーの φ(n) は、1 から n までの数のうち n と互いに素なものの個数です：φ(n) = n·∏(1 − 1/p)。

冪剰余と RSA：aᵏ mod n は反復二乗法で計算します：k を 2 進数で書き、二乗し、毎回簡約し、ビットが 1 の冪を掛けます。フェルマー：素数 p が a を割り切らないとき aᵖ⁻¹ ≡ 1 (mod p) なので、指数は p − 1 を法として簡約できます。RSA：素数 p と q を選び、n = p·q、φ(n) = (p − 1)(q − 1) とします。公開指数 e は φ(n) と互いに素で、秘密指数は d = e⁻¹ mod φ(n) です。暗号化は c = mᵉ mod n、復号は m = cᵈ mod n で行います。