|
［目次］
前書き13
主旨 13
構成 14
注意と限界 14
謝辞 15
第1章 プロローグ17
第2章 パラダイム19
2.1FAQ（Frequently Asked Questions） 20
2.1.1 章立て 20
第1部 集合
第3章 集合23
3.1 集合の定義 23
3.1.1 要素（element, member） 23
3.2 外延性公理（Principle of Extensionality） 24
3.2.1 定義 24
3.2.2 新しい定義 24
3.2.3 「イフ・アンド・オンリー・イフ」iff 25
3.3 空集合（empty set） 26
3.4 対集合（pair set） 26
3.4.1 リンゴを使って計算してみましょう 26
3.4.2 ｛x, x｝ ＝ ｛x｝ 27
3.5 部分集合（subset） 28
3.5.1 空集合（empty set） 28
3.6 合併（union）と共通部分（intersection） 28
3.6.1 合併（union） 28
3.6.2 共通部分（intersection） 29
3.7 自分自身を要素として含まない集合 29
3.7.1 であるような（such that） 30
3.7.2 ラッセルのパラドックス 30
第4章 自然数 33
4.1 ツェルメロによる自然数の定義 34
4.1.1 ゼロの定義 34
4.1.2 ゼロ以降の数の定義 35
4.1.3 ツェルメロの集合に対して合併は加法でしょうか 35
4.2 フォン・ノイマンによる自然数の定義 36
4.2.1 フォン・ノイマンの集合に対して合併は加法でしょうか 37
4.3 次（successor） 38
4.3.1 次による数の定義 38
4.4 数詞（numeral） 39
4.4.1 アラビア数字 39
4.4.2 ローマ数字 39
4.5 FAQ 40
4.5.1 自然数 40
第5章 ペアノの公理43
5.1 ペアノの公理（Peano Postulates） 43
5.1.1 公理 I 43
5.1.2 公理 II 44
5.1.3 公理 III 44
5.1.4 公理 IV 45
5.1.5 公理 V 46
5.2 加法 46
5.2.1 加法の定義 47
5.2.2 閉じている事（Closure law） 47
5.2.3 交換法則、または可換律（Commutative law） 47
5.2.4 結合法則（Associative law） 48
5.2.5 簡約律（Cancellation law） 48
5.3 1＋2＝3 48
5.3.1 ペアノの公理による計算 その1 48
5.3.2 ペアノの公理による計算 その2 49
5.3.3 ペアノの公理による計算 その3 50
第2部 関数
第6章 関係と関数 57
6.1 順序対（ordered pair） 57
6.2 関係（relation） 58
6.2.1 ドメイン、レンジ、フィールド 59
6.3 関数（function） 59
第7章 ラムダ計算 61
7.1 式（expression） 62
7.1.1 名前（name） 62
7.1.2 関数（function） 62
7.1.3 本体（body） 63
7.1.4 適用（application） 63
7.1.5 関数式（function expression） 63
7.1.6 引数式（argument expression） 64
7.2 バッカス・ナウア・フォーム（BNF） 64
7.3 式の図式表現 65
7.4 ベータ変換（β reduction） 65
7.5 関数（function） 66
7.5.1 単位元（identity） 66
7.5.2 自己適用（self-application） 66
7.5.3 関数適用の関数（function application function） 68
7.6 アルファ変換（αreduction） 70
7.6.1 束縛変数 70
7.7 イータ変換（ηreduction） 71
7.8 レデックス（redex） 72
7.9 正規形（normal form） 72
7.10 チャーチ・ロッサ（Church-Rosser） 73
第8章 関数プログラミング 75
8.1 チャーチの数詞（Church Numerals） 75
8.2加法（add）の定義 76
8.3 計算 76
8.3.1 add 1 2 76
8.3.2 アルファ変換 77
8.3.3 ベータ変換 その1 77
8.3.4 ベータ変換 その2 78
8.3.5 ベータ変換 その3 79
8.3.6 ベータ変換 その4 79
8.3.7 ベータ変換 その5 79
8.3.8 3の獲得 80
第3部 論理
第9章 論理学 85
9.1 命題論理学（propositional logic） 85
9.2 命題（proposition） 86
9.3 論理演算（logical operation） 86
9.4 well-formed formula（wff） 87
9.5 解釈（interpretation）とモデル（model） 88
9.5.1 and 88
9.5.2 解釈（interpretation） 88
9.5.3 モデル（model） 88
9.5.4 or 88
9.5.5 if 89
9.6 明日雨が降ったら遠足は中止です 89
9.6.1 お金を返そうにも無ければ返せません 90
9.6.2 ifと同じ真偽表 91
9.6.3 動くと撃つぞ 91
9.7 空集合の扱い 92
第10章 論理プログラミング 95
10.1 定義 95
10.1.1 項（Term） 95
10.1.2 原子元（Atom） 96
10.1.3 節（Clause） 96
10.2 数 99
10.2.1 数詞 99
10.2.2 自然数 99
10.3 1＋2＝3 99
10.3.1 加法の定義 100
10.3.2 計算 100
第11章 代数 105
11.1 形式的方法（formal approach） 105
11.1.1 形式的方法（formal approach） 103
11.1.2 ソフトウェア（プログラム）の意味論 104
11.2 代数的方法 109
11.2.1 自然数の定義 109
11.2.2 加法の定義 111
11.3 計算 112
11.3.1 理論 113
第5部 コンピュータ・ハードウェア 117
第12章 電気回路 119
12.1 原子模型 119
12.2PNダイオード 120
12.2.1 P型半導体 120
12.2.2 N型半導体 120
12.2.3 PN接合 121
12.3 トランジスタ 122
12.4 MOS 123
12.4.1 構造 123
12.4.2 機能 124
12.4.3 P型MOS 124
12.4.4 N型MOS回路記号 124
12.4.5 P型MOS回路記号 124
12.5 CMOS 125
12.5.1 構造 125
12.5.2 CMOS NAND回路 125
12.5.3 CMOS NAND回路の動作 125
第13章 加算器 131
13.1 半加算器 131
13.1.1 半加算器の動作論理 131
13.2 2進数 132
13.2.1 2進数の足し算 132
13.2.2 半加算器 133
13.3 全加算器 133
13.3.1 全加算器の動作原理 136
13.4 1＋2＝3 136
13.4.1 3段の加算器 137
13.4.2 3段の加算器による計算 137
第6部 付録
付録A 加法の法則の証明 141
A.1 数学的帰納法 141
A.2 加法（add） 141
A.2.1 閉じている事（Closure law） 141
A.2.2 交換法則（Commutative law） 143
A.2.3 結合法則（Associative law） 144
付録B 形式理論 147
B.1 推論規則 147
B.1.1 三段論法（modus pones, MP） 148
B.1.2 演繹（dedustion） 148
B.1.3 導出（derivation）、証明（proof） 148
B.1.4 証明の例 149
B.2 バリディティ（validity）とインコンシステンシー（inconsistency） 149
B.2.1 バリッド（valid） 149
B.2.2 インコンシステント（inconsistent） 150
B.2.3 言葉の整理 151
B.3 同値（equivalence） 152
B.4 論理的帰結（logical consequence） 152
B.5 完全性（complete）と正しさ（sound） 152
付録C 代数的仕様 153
C.1 代数的意味論（algebraic semantics） 153
C.1.1 定義 153
C.1.2 代数AN 154
C.1.3 代数AB 154
C.2 準同型（Homomorphism） 155
C.2.1 例 156
付録D 計算機アーキテクチャ 159
D.1 計算モデル 159
D.1.1 入力 160
D.1.2 出力 160
D.1.3 処理 160
D.1.4 メモリー 160
D.1.5 プログラム 160
D.2 計算機ハードウェアのモデル 161
D.2.1 計算機ハードウェア・アーキテクチャ 161
D.2.2 計算機ハードウェアによる計算 162
付録E コンパイラの意味論 165
E.1関数（function） 165
E.1.1 シグネチャ（signature） 166
E.1.2 合成関数（composition） 166
E.2カレー化（curry） 166
E.3反復（Iterate）と適用（Apply） 167
E.3.1 シグネチャ（signature） 167
E.3.2 カレー化（curry） 167
E.4コンパイラとインタープリタ 168
E.4.1 コンパイラ 168
E.4.2 インタープリタ 168
E.4.3 コンパイラとインタープリタ 168
付録F オートマタ 169
F.1 自動販売機 169
F.1.1 安すぎるジュース、コーヒーと高すぎるお茶の自動販売機 169
F.1.2 ちょっとした改良 170
付録G ペトリネット 171
G.1 基本構成要素 171
G.1.1 基本動作 171
G.1.2 複数の条件 172
G.1.3 複数の結果 172
G.2 分散処理 172
G.2.1 プロデューサ・コンシューマ 173
G.2.2 プロデューサの仕事 173
G.2.3 さらにプロデューサの仕事 174
G.2.4 さらにさらにプロデューサの仕事 174
G.2.5 コンシューマの仕事 175
G.2.6 結果を受け取る 175
付録H プログラミング言語 177
H.1 エドバック（EDVAC） 177
H.2 アセンブラ（assemblers） 178
H.3 マクロ・アセンブラ（macro assemblers） 178
H.4 フォートラン（Fortran） 179
H.5 アルゴル（Algol 60） 179
H.6 コボル（COBOL 61） 179
H.7 ピーエル・ワン（PL/I） 179
H.8 アルゴル68（Algol 68） 180
H.9 シミュラ（Simula 67） 180
H.10 リスプ（LISP） 180
H.11 スノーボル（SNOBOL 4） 180
H.12 パスカル（Pascal） 181
H.13 エー・ピー・エル（APL） 181
H.14 プロローグ（Prolog） 181
H.15 シー（C） 181
H.16 エイダ（Ada） 181
H.17 スモールトーク（Smalltalk 80） 182
H.18 シー・プラス・プラス（C＋＋） 182
H.19 ジャバ（Java） 182
付録I エイダ（Ada） 183
I.1 パスカル（Pascal） 183
I.1.1 概念的簡略性 183
I.1.2 使い勝手の簡略性 183
I.1.3 実装上の簡略性 184
I.2 エイダ（Ada） 184
I.2.1 パッケージ（Package）とジェネリック（Generics） 184
I.3 エイダ・パッケージ（Ada package） 186
付録J オブジェクト指向 189
J.1 オブジェクトの概念 189
J.1.1 オブジェクト（object） 189
J.1.2 プログラム 189
J.1.3 プログラムの集まり 190
J.2 クラス（class）の概念 190
J.2.1 継承（inheritance） 191
J.3 オブジェクトとクラス 191
J.3.1 オブジェクトはクラスのインスタンス 192
J.3.2 継承 192
J.3.3 オブジェクトとクラス 192
J.3.4 クラスのクラス 193
J.3.5 メタクラス 193
J.3.6 クラス‘Class’ 194
J.3.7 メタクラスへの道 194
J.3.8 Object, Behavior, Class, Meta Class 194
J.3.9 インスタンスの関係と継承の関係 195
J.3.10 オブジェクトとクラスの結果 195
付録K あとがき 197
進化 197
謝辞 199
関連図書 201 |
