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 |