離散数学
このノートの問いがそのまま復習カードになり、忘れかけたころに出題されます。
シラバス Ver.6.5 の小分類 33「離散数学」（大分類 7：基礎理論／中分類 13：基礎理論）。
2026-08-05 にシラバス本文と突合済み。
0. 何を押さえるか
コンピュータが数を扱う仕組みです。この小分類には用語例が置かれておらず、
問われるのは手を動かせるかです。
出るのは 3 つだけです。
- 基数変換（2 進数 ⇄ 10 進数）
- 2 進数の加算
- 論理演算と真理値表
2 進数の各桁は 1・2・4・8・16・32… という重みを持ちます。
これさえ体に入っていれば、変換は足し算で済みます。
1. 数と表現
根拠: シラバス 7-13-33
2 進数の各桁の重みは？
右から順に 1・2・4・8・16・32・64・128（2 のべき乗）。
10 進数に直すには、1 が立っている桁の重みを足すだけ。
例：1011 → 8 + 0 + 2 + 1 = 11
10 進数の 13 を 2 進数にせよ。
1101
13 を超えない最大の重みから引いていく。
| 重み | 8 | 4 | 2 | 1 |
|---|---|---|---|---|
| 使うか | ○ | ○ | × | ○ |
8 + 4 + 1 = 13 なので 1101。
2 進数 101 + 011 を計算せよ。
101 + 011 を計算せよ。1000（10 進数で 5 + 3 = 8）
1 + 1 は 10（桁上がり） になるのが 10 進数との違い。
右の桁から: 1+1 = 10 なので 0 を書いて 1 繰り上がり。
次の桁は 0+1+1 = 10 なので 0 を書いて 1 繰り上がり。
次の桁は 1+0+1 = 10 なので 0 を書いて 1 繰り上がり → 1000。
n ビットで表現できる値は何通りか？
2 の n 乗 通り
| ビット数 | 通り数 | 符号なし整数の範囲 |
|---|---|---|
| 8 | 256 | 0〜255 |
| 16 | 65,536 | 0〜65,535 |
「範囲の上限は 2ⁿ − 1」（0 から数えるため）。
表現できる範囲を超えるとオーバーフローになる。
2. 集合
根拠: シラバス 7-13-33
集合の和集合・積集合・差集合とは？
| 意味 | |
|---|---|
| 和集合（A ∪ B） | A または B に属する要素 |
| 積集合（A ∩ B） | A かつ B に属する要素 |
| 差集合（A − B） | A に属し、B に属さない要素 |
ベン図で 2 つ（3 つ）の円の重なりとして描くと、
検索条件（AND・OR・NOT）との対応が見える。
検索条件「A AND B」「A OR B」は、集合でいうと何か？
| 検索条件 | 集合 |
|---|---|
| A AND B | 積集合（両方を満たすものだけ） |
| A OR B | 和集合（どちらかを満たすもの） |
| A AND NOT B | 差集合 |
AND は絞り込み（件数が減る）、OR は広げる（件数が増える）。
3. 論理演算
根拠: シラバス 7-13-33
AND・OR・NOT の真理値表を書け。
| A | B | A AND B | A OR B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
NOT は 1 つの入力を反転する（0 → 1、1 → 0）。
AND は両方 1 のときだけ 1、OR は片方でも 1 なら 1。
XOR（排他的論理和）とは？ AND・OR と何が違うか？
2 つの入力が異なるときだけ 1 になる。
| A | B | XOR |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
OR との違いは最後の行——OR は 1、XOR は 0。
「どちらか一方だけ」という意味になる。
真理値表は何に使うか？
条件の組合せをすべて書き出し、結果を確かめるため
条件が n 個あれば行数は 2ⁿ 行になる。
複雑な条件式が正しいかを、漏れなく機械的に検証できるのが利点。