数理論理学入門

高崎金久(京都大学)

〜京都大学での全学共通科目講義に基づく〜

目次
読み物
参考書
講義資料

読み物

E.T. ベル「数学をつくった人々(下)」(田中勇・銀林浩訳,東京図書)
著名な数学者の生涯と仕事を紹介するベルのこの有名な本は 19世紀のイギリス・アイルランドの数学者(ハミルトン,ケイリー, シルベスター,ブール)にかなりのページを費やしている. ジョージ・ブールについても生い立ちから数学以外の教養も含めて 詳しく紹介している.
竹内外史「現代集合論入門」(日本評論社,1971)
これはもともと公理的集合論の本格的な解説を目的とした本であり, その意味でも重要だが,序章の「Logician小伝」はゲーデル以降の 有名な数理論理学者の履歴や業績を紹介していて,評伝としても読める. 筆者はほとんどの人たちと直接・間接に交流があったので, かなり生々しい話も出てくる.
ダグラス・ホフシュタッター 「ゲーデル,エッシャー,バッハ」 (野崎昭弘・はやしはじめ・柳瀬尚紀訳,白揚社,1985)
ゲーデルの不完全性定理を絵画・音楽・生命・知能・計算機などと絡めて 多角的に紹介し,大変な評判になった著作.この種の話題を扱う本は 不完全性定理の説明を単なるお話に終わらせることが少なくないが, ホフシュタッターの本は記号論理学のかなり技術的な部分まで立ち入って 説明しているので,記号論理学を学ぶための題材として十分に通用する. 原著はアメリカでベストセラーになり,ピュリツァー賞を受賞した.
アンドリュー・ホッジズ 「Alain Turing --- the Enigma」(第一版 Burnett Books Ltd 1983, 第二版 Random House 1992)
アラン・チューリングの生い立ちから自殺に至るまでの生涯を 膨大な資料に基づいて紹介する力作.伝記的内容に加えて,チューリングの 重要な仕事をその背景とともに詳しく解説している.表題の「Enigma」は 本来は「謎」という意味で,チューリングの生涯が国家機密や同性愛絡みの 謎に包まれれていることを指すが,第二次大戦中にチューリングが 解読に成功したドイツ軍の暗号機械の名称でもある. 著者は チューリングを紹介するWebページも開設している.
内井惣七 「うそとパラドックス ゲーデル論理学への道」 (講談社文庫881,講談社,1987)
論理をめぐる推理小説風の例題や世間話風の対話を交えながら, 命題論理の初歩からゲーデルの不完全性定理までを解説している. 19世紀に記号論理学が誕生し成長して行く歴史的背景も紹介している. 手製の「論理尺」なる原始的教材が登場するのも楽しい.
内井惣七 「シャーロック・ホームズの推理学」 (講談社文庫922,講談社,1988)
シャーロック・ホームズの活躍する小説を題材にして, 19世紀イギリスのウィリアム・ジェヴォンズらによる「帰納論理」 の研究を紹介するユニークな本.帰納論理は演繹論理と違って 事例・観察・経験から一般的な法則を引き出す論理であるが, ジェヴォンズは帰納論理に確率論的方法を導入することによって その信頼性を高めた.
林晋 「ゲーデルの謎を解く」(岩波科学ライブラリー6,岩波書店1993)
ゲーデルの不完全性定理の歴史的背景から説き起こし,記号化の考え方, 不完全性定理の内容と証明の考え方,対角線論法との関係,などを わかりやすく解説している.数式や論理式をほとんど使わずに, ドラエモンから借りてきたような「変身機械」という概念を用いて, 不完全性定理の証明の本質を見事に説明しているのがすばらしい.
八杉満利子林晋 「お話・数学基礎論」(ブルーバックス,講談社2002)
京都の名所や散歩コースを織り混ぜながら綴る,全編会話形式の 数学基礎論超入門.市内某所(京都産業大学へのバスが発着する 北大路バスターミナルか北山通りのどこかではないかと思われる) のショッピングモール3階,喫茶室「カフェ・ド・ロンリ」で, 日曜ごとに,店員と常連客との数学基礎論をめぐる対話が華開く. 話題は集合の話から始まり,連続体仮説,集合論のパラドックス, 記号論理の考え方,数学の基礎をめぐる論争,ゲーデルの不完全性定理を経て, 数学基礎論の未来にまで及ぶ.
グレゴリー・チャイティン 「セクシーな数学」(黒川利明訳,岩波書店,2003)
ゲーデルの不完全性定理を情報理論的に再構成して 「アルゴリズム的情報理論」を創始したことで知られる筆者の さまざまなインタビュー記事や講演録を集めた本. 大部分は数学を専門としない一般の読者を対象にしたものだが, 最後の9章「数学の基礎についての一世紀にわたる論争」は 数学の研究者(数学基礎論や数理論理学の専門家とは限らない) を対象としている.全体を通じて筆者の個性が強く打ち出された本で, 時に誤解を招きかねない部分も見受けられるので注意を要する.
林晋八杉満利子 「ゲーデル 不完全性定理」(岩波文庫青944-1,岩波書店2006)
「読みもの」の項に入れたが,本書は筆者達の数学史研究の成果の 紹介を兼ねた本格的な学術書であり,単なる読みものではない (文系分野の基準で言えば,著書による研究発表に相当する). 本書は短い第I部と長大な第II部からなるが,第I部はゲーデルの 原論文の日本語訳である.ゲーデルの不完全性定理は数学の基礎に関する 「ヒルベルトの計画」に大きな打撃を与えたものとして知られるが, 第II部ではこのヒルベルトの計画について数学史的研究の最新成果を 採り入れつつ詳しく解説した後,ゲーデルの論文の内容と意義を論じている.

目次に戻る


参考書

前原昭二「記号論理入門」(日本評論社,初版1967,新装版 2005)
自然演繹に基づく古典論理の形式化と意味論を非常に丁寧に 説明している.記号論理学を初歩から学べる本であるが, 記号的にも内容的にかなり古めかしいことは否定できない.
松本和夫「数理論理学」(共立出版,初版1970,復刊2001)
数学基礎論の立場から記号論理学を解説している. 論理体系としては古典論理・直観主義論理・様相論理を, また方法としては意味論から各種の形式化までを網羅的に扱っている. さらに自然数論の無矛盾性の証明への応用も紹介している.
林晋 「数理論理学」(コロナ社,1989)
数理論理学の本格的な解説書.自然演繹とシークェント計算 による形式化を非常に厳密な枠組みで展開している.また, 導出原理・単一化やカリー・ハワード対応など計算機科学と 関連の深い話題についても詳しい.説明がかなり「硬い」ので, 読むには相当の覚悟が必要である.
萩谷昌己 「ソフトウェア科学のための論理学」 (岩波講座ソフトウェア科学11,岩波書店,1994)
計算機科学への応用を示しながら,多彩な内容を形式張らずに 紹介している.前半はシークェント計算に基づいて古典命題論理・ 述語論理を解説し,後半はその発展として様相論理・動的論理・ 直観主義論理・構成的解釈を論じている.またカテゴリー論にも触れている.
小野寛晰「情報科学における論理」(日本評論社,1994)
おもにシークェント計算に基づいて,古典論理,直観主義論理, 様相論理を解説している.計算機科学と関連の深い導出原理・単一化 についても詳しく紹介している.情報科学向けの記号論理学の教科書の 「標準」と呼ぶべき内容を備えている.
竹内外史「線型論理入門」(日本評論社,1995)
線形論理の解説書.「入門」と題しているが,決して入門書 ではない.読むためには記号論理学(特にシークェント計算) についてすでにかなりの経験を積んでいることが要求される. しかし挑戦に値する面白い本である.論理回路・オートマトン・ ペトリネットなどをモデルにして線形論理のさまざまな可能性を 紹介している.
桔梗宏孝「応用論理」(情報数学講座,共立出版,1996)
前半では,素朴な論理パズルから説き起こして,古典論理の 意味論と形式化(自然演繹に基づく)をわかりやすく説明している. 後半では,論理プログラミングの考え方,不完全性定理との関わり, ラムダ計算との関わりなど,幅広い話題を紹介している. 計算機科学を意識した新しい形の入門書である. 残念ながら版元品切れの状態である.
角田譲「数理論理学入門」(朝倉書店,1996)
述語論理の形式的取り扱いを基礎から説き起こし,形式的体系に まとめ上げて,そこから健全性・完全性・決定可能性についての 結論を引き出すまでの過程を,非常に丁寧かつ詳しく解説している. 例も豊富に用意されている.用語や流儀に若干独特なところがある.
小松寿「記号論理学入門」(森北出版,1997)
古典論理の意味論と形式化(特にヒルベルト流の形式化) を詳細に解説している.意味論を丁寧に説明しているのが特色である. タブロー法による恒真性の判定方法など,他の本ではあまり 採り上げられていない話題も紹介している.
田中俊一「位相と論理」(日本評論社,2000)
論理と位相の関係を詳細に解説する極めて特色のある本である. 話はブール代数・ハイティング代数と位相空間の対応関係を軸に展開し, 最後はカテゴリー論にまで至る.読むためには代数系や位相空間についての 基礎知識が要求される.
田中一之「数の体系と超準モデル」(裳華房,2002)
現在の数学基礎論における自然数論や実数論の見方を紹介する本. 数学基礎論の三つの柱である計算論,証明論,モデル論のそれぞれについて 簡潔で明快な解説を行っている.記号論理についてはむしろ必要最小限の説明に とどめている.読むにあたっては代数系・離散数学・記号論理についての 基礎的知識を持っているほうが望ましい.
田中一之・鈴木登志雄 「数学のロジックと集合論」(培風館,2003)
初心者を対象として,普通の数学の基盤としての集合論を素朴なレベルから 公理的集合論に至るまで一通り解説する,他にあまり例を見ない本である. 0章から2章までは集合の記号,論理記号,関係・関数・濃度などの 基本的な概念から出発して自然数・実数の集合の基本的性質などを解説する. 3章以降では俄に集合論的色彩が強くなる.3章では順序数・基数の基礎理論を, 4章と5章では数理論理学・公理的集合論の入門的解説を行っている. 公理的集合論の解説書は初心者には敷居が高いものが少なくないが, この本は普通の数学的素養があれば十分に理解できるだろう.
田中一之編「ゲーデルと20世紀の論理学」1〜4巻(東京大学出版会,2006〜2007)
ゲーデル生誕100年 (2006年) を記念して出版された画期的な4分冊シリーズ. 20世紀における数理論理学(数学基礎論) の成果を歴史的・哲学的背景も踏まえて 網羅的に紹介している.第1巻は数学的な内容にはほとんど立ち入らないで, ゲーデルの論理学・哲学研究の背景やそれらが日本において受け入れられた 経緯を紹介している.第2巻〜第4巻では,数理論理学におけるゲーデルの研究の 三つの柱である完全性定理,不完全性定理,公理的集合論について, その基礎からその後の発展の一端までを紹介している. 第2巻・第3巻の基礎的部分は,抽象代数などを学んだ経験や 離散数学の基礎的知識があれば,すぐに読み始めることができる. ただし,かなり圧縮した書き方をしている部分も多いので, 慣れない読者は読み解くのに苦労するかもしれない. 第4巻は全般に公理的集合論についてある程度の知識を前提としている.
鹿島亮「数理論理学」(朝倉書店,2009)
自然演繹を軸にして数理論理学の基礎を丁寧に解説している. 最初に数学の定理やその証明を例として述語論理の記号の使い方を説明し, そこから自然演繹流の形式的証明へ話をつなげる,というわかりやすい (自然演繹の「自然さ」をよく生かした) 構成になっている. 完全性定理や不完全性定理などの基本的定理を一通り解説し, シークエント計算のカット除去定理や 直観主義論理とそのクリプキモデルも紹介している.
新井敏康「数学基礎論」(岩波書店,2011)
筆者が「まえがき」に 「一冊の本で,数学基礎論という分野を一望できる眺望が得られる ようにしたつもりである」と書くほどの意欲的な本である. A5判で550ページを超える.第I部では1階論理,計算理論,不完全定理を紹介し, 第II部では数学基礎論の主要テーマであるモデル理論,計算理論,集合論,証明論を 証明付きで解説している.この決定版ともいうべき本の出現によって, 数理論理学の専門的和書をこれから新たに書こうとする人は かなり苦労することになりそうである.

目次に戻る


講義資料

注意:この講義資料は通年で講義を担当していた2000年〜2003年頃のものです. 2006年〜現在は前期だけ担当していて,講義内容もこの資料とは異なります. また,最近の講義では記号や言葉遣いも少し変えています.
I. 記号論理学とは何か
1. 記号論理学の誕生
2. 記号化の基本的な考え方
3. 数学基礎論との関わり
4. 計算機科学等との関わり
5. さまざまな論理

II. 数学的準備
1. 集合
2. 写像
3. 関係
4. ブール代数

III. 命題論理の意味論(その1)
1. 命題論理は何を記号化したものか
2. 命題変数と論理演算子
3. 論理式の構文と付値による意味解釈
4. 同値性・恒真性・充足関係

IV. 命題論理の意味論(その2)
1. 論理式の標準形
2. 標準形への同値変形
3. 恒真性・充足可能性との関係
4. 導出原理の考え方

V. 述語論理の意味論
1. 述語論理は何を記号化したものか
2. 論理式の構文と意味解釈
3. 同値性・恒真性・充足関係
4. 理論とモデル

VI. 論理の形式化
1. 形式化の考え方
2. 形式的証明・演繹の例
3. ヒルベルト流の形式化

VII. 自然演繹(その1)
1. 命題論理の形式化
2. 証明・演繹のさまざまな例
3. 排中律と直観主義論理

VIII. 自然演繹(その2)
1. 命題論理の形式化の完全性
2. 述語論理の形式化
3. 理論・モデル・完全性定理

IX. シークェント計算
1. シークェントとは何か
2. シークェント計算による論理の形式化
3. 命題論理の形式化の完全性

目次に戻る