| 1 集合 |
| 1.1 集合と組 1 |
| 1.1.1 集合の定義 1 |
| 1.1.2 集合の同一性と部分集合 5 |
| 1.1.3 組，列，記号列 8 |
| 1.2 集合演算 10 |
| 1.2.1 共通部分（∩） 10 |
| 1.2.2 和（∪） 12 |
| 1.2.3 補（） 14 |
| 1.2.4 差（） 15 |
| 1.2.5 直積（×） 16 |
| 1.2.6 直和（＋） 18 |
| 1.2.7 べき（2A） 19 |
| 1.2.8 まとめ 20 |
| 1.3 集合の性質 21 |
| 演習問題 23 |
| 2 写像 |
| 2.1 写像 26 |
| 2.1.1 写像の定義 26 |
| 2.1.2 写像の同一性 30 |
| 2.1.3 写像の集合 30 |
| 2.2 写像の合成 32 |
| 2.3 様々な写像 34 |
| 2.3.1 単射 34 |
| 2.3.2 全射 36 |
| 2.3.3 全単射 39 |
| 2.4 写像と集合 45 |
| 2.4.1 全単射と同型 45 |
| 2.4.2 単射と全射の対応 45 |
| 2.4.3 写像と集合の対応 47 |
| 演習問題 49 |
| 3 関係 |
| 3.1 関係 52 |
| 3.1.1 関係の定義 52 |
| 3.1.2 関係の同一性 55 |
| 3.2 関係の合成 55 |
| 3.2.1 合成の定義 55 |
| 3.2.2 関係のべき乗 56 |
| 3.3 様々な関係 59 |
| 3.3.1 反射律，対称律，反対称律，推移律 59 |
| 3.3.2 同値関係と同値類 62 |
| 3.3.3 順序関係と整列 68 |
| 演習問題 71 |
| 4 無限 |
| 4.1 無限集合 73 |
| 4.2 集合の濃度 75 |
| 4.3 可算と非可算 78 |
| 演習問題 83 |
| 5 論理 |
| 5.1 命題論理 85 |
| 5.1.1 命題の定義 85 |
| 5.1.2 命題の同一性と必要十分条件 86 |
| 5.1.3 命題論理式と論理結合子 88 |
| 5.2 命題の解釈と論理演算 92 |
| 5.2.1 命題の解釈 92 |
| 5.2.2 論理積（∧） 92 |
| 5.2.3 論理和（∨） 94 |
| 5.2.4 否定（－） 95 |
| 5.2.5 含意（⇒） 96 |
| 5.2.5 同値（⇔） 97 |
| 5.2.7 まとめ 98 |
| 5.3 命題論理の性質 99 |
| 5.3.1 同値変形 99 |
| 5.3.2 標準形 101 |
| 5.3.3 論理回路 103 |
| 5.3.4 加算器の論理回路実現 105 |
| 5.3.5 恒真式と証明系 108 |
| 5.4 述語論理 111 |
| 5.4.1 述語 111 |
| 5.4.2 限量子 113 |
| 5.5 述語論理の性質 115 |
| 5.5.1 同値変形 115 |
| 5.5.2 妥当な式と証明系 116 |
| 演習問題 118 |
| 6 数え上げ |
| 6.1 数え上げ技法 120 |
| 6.1.1 和の法則 120 |
| 6.1.2 積の法則 121 |
| 6.1.3 包除原理 121 |
| 6.1.4 2重数え上げ 123 |
| 6.2 順列と組合せ 124 |
| 6.2.1 順列と組合せの定義 125 |
| 6.2.2 総数の表記と階乗 127 |
| 6.2.3 順列の総数 128 |
| 6.2.4 重複順列の総数 129 |
| 6.2.5 組合せの総数 130 |
| 6.2.6 重複組合せの総数 131 |
| 6.2.7 円順列と数珠順列の総数 132 |
| 6.3 組合せの性質 133 |
| 6.3.1 総数の表記 133 |
| 6.3.2 対称性 134 |
| 6.3.3 帰納的性質 135 |
| 6.3.4 組合せと単調経路 137 |
| 6.3.5 組合せと2項定理 140 |
| 演習問題 143 |
| 7 定義と証明 |
| 7.1 非構成的証明 144 |
| 7.1.1 背理法 144 |
| 7.1.2 鳩の巣原理 146 |
| 7.2 数学的帰納法と証明 152 |
| 7.2.1 数学的帰納法 152 |
| 7.2.2 数学的帰納法の正当性 152 |
| 7.2.3 包除原理 155 |
| 7.2.4 矩形分割 158 |
| 7.2.5 単調ブール関数と単調論理回路 161 |
| 7.3 再帰的定義 165 |
| 7.3.1 階乗 165 |
| 7.3.2 アッカーマン関数 166 |
| 7.3.3 フィボナッチ数列 167 |
| 7.3.4 実係数多項式 168 |
| 7.3.5 加算 169 |
| 7.4 記号列 172 |
| 7.4.1 記号列 172 |
| 7.4.2 記号列の帰納的定義 173 |
| 7.4.3 記号列の性質 174 |
| 7.4.4 記号列と順序関係 177 |
| 7.4.5 辞書式順序 177 |
| 7.4.6 標準順序 181 |
| 7.4.7 プログラムと関数の濃度 182 |
| 演習問題 183 |
| 8 木構造とアルゴリズム |
| 8.1 グラフと木 186 |
| 8.2 2分木 188 |
| 8.3 アルゴリズム 194 |
| 8.3.1 アルゴリズムと計算量 194 |
| 8.3.2 探索アルゴリズム 194 |
| 8.3.3 逐次探索 194 |
| 8.3.4 2分探索 195 |
| 8.3.5 ユークリッドの互除法 197 |
| 演習問題 200 |
| 演習問題解答 201 |
| 索引 217 |
