1+2=3―タしザンにヒソむメイキュウ

1+2=3―足し算に潜む迷宮

単純な足し算を題材にして、
「集合」「関数」「論理」「代数」「コンピュータハードウェア」のそれぞれに基づき、
算術とは何かを解説した本。

--------------------------------

【目次】

前書き13

主旨　　　13
構成　　　14
注意と限界　　　14
謝辞　　　15

第1章　プロローグ17

第2章　パラダイム19

2.1FAQ（Frequently Asked Questions）　　　20
2.1.1　章立て　20

第Ⅰ部　集合

第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

第Ⅱ部　関数

第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

第Ⅲ部　論理

第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

第Ⅴ部　コンピュータ・ハードウェア　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

第Ⅵ部　付録

付録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

--------------------------------