情報科学特別研究Ⅰ

科目名	情報科学特別研究Ⅰ
教員名	戸田誠之助
単位数	4	課程	前期課程	開講区分	文理学部
科目群	地球情報数理科学専攻
学期	通年	履修区分	必修

授業概要	数理論理学について，その専門文献を読み解くことができるように，基本的な知識と全体的な枠組みを学習する．一階論理の完全生定理と算術の第一不完全性定理の証明を細部まで理解することを目標とする．
授業のねらい・到達目標	一階論理の完全性と算術の不完全性が理解できるようになる．この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。
授業の方法	履修者の論理学に対する知識や数学的素養の度合いに応じて，参考文献に記載した教科書などから一つを選んで講読する．学習に使用する教科書は第1回目の授業のときに決定する．教科書を事前に学習し，その内容をまとめた資料を作成し，授業時間に資料に基づいて発表する．教科書に記載されている演習問題を時間の許す限り解くことが望ましい．下記の授業計画はHodelによる教科書を選択した場合の学習のモデルケースを示している．本授業の事前・事後学習は，各４時間の学習を目安とする．
履修条件	本講義の担当者が別途担当するコンピュータ科学特論Iを履修することが望ましい．

授業計画
1	ガイダンス：履修者と相談しながら学習用の教科書を選定する．【事前学習】シラバスを事前に確認する【事後学習】選定した教科書を用意する．
2	準備：数理論理学の概要，数学的な基礎知識．【事前学習】発表用資料を準備する．【事後学習】数理論理学の基本的な目的を理解する．
3	準備：公理系，決定可能性と計算可能性，【事前学習】発表用資料を準備する．【事後学習】数理論理学における基礎概念を理解する．
4	準備：再帰関数と再帰関係【事前学習】発表用資料を準備する．【事後学習】再帰関数について理解を深める．
5	命題論理：言語，トートロジー的帰結，コンパクト性．【事前学習】発表用資料を準備する．【事後学習】命題論理の意味論的概念について理解を深める．
6	命題論理：形式的公理系【事前学習】発表用資料を準備する．【事後学習】命題論理の構文論的概念について理解を深める．
7	命題論理：健全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系においてトートロジーだけが証明可能であることを理解する．
8	命題論理：演繹定理【事前学習】発表用資料を準備する．【事後学習】演繹定理の理論的な意義だけでなく，証明図を構成する際の有用性についても理解を深める．
9	命題論理：完全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系の正当性を理解する．
10	命題論理：ヒルベルト流の公理系【事前学習】発表用資料を準備する．【事後学習】命題論理について様々な公理系があり得ることを理解する．
11	命題論理：シーケント計算【事前学習】発表用資料を準備する．【事後学習】命題論理について様々な公理系があり得ることを理解する．
12	一階論理：算術の言語【事前学習】発表用資料を準備する．【事後学習】一階論理による数学的理論の形式化について理解を深める．
13	一階論理：言語，解釈，モデル【事前学習】発表用資料を準備する．【事後学習】一階論理の基礎概念を理解する．
14	一階論理：タルスキ意味論【事前学習】発表用資料を準備する．【事後学習】一階論理式の解釈について理解を深める．
15	一階論理：自由変数と代入【事前学習】発表用資料を準備する．【事後学習】代入の概念を理解する．
16	一階論理：形式的公理系【事前学習】発表用資料を準備する．【事後学習】一階論理の構文論的概念についてりかいする．
17	一階論理：健全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系において恒真式だけが証明可能であることを理解する．
18	一階論理：演繹定理【事前学習】発表用資料を準備する．【事後学習】演繹定理の有用性についても理解を深める．
19	一階論理：完全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系の正当性を理解する．
20	一階論理：置換定理【事前学習】発表用資料を準備する．【事後学習】恒真性が形式的概念であることを理解する．
21	数学と論理：一階理論とヒルベルト計画【事前学習】発表用資料を準備する．【事後学習】不完全性定理の歴史的背景としてヒルベルト計画について理解を深める．
22	数学と論理：レーベンハイム・スコーレムの定理【事前学習】発表用資料を準備する．【事後学習】一階理論のモデルについて理解を深める．
23	数学と論理：コンパクト性定理【事前学習】発表用資料を準備する．【事後学習】一階理論のモデルについて理解を深める．
24	数学と論理：決定可能理論【事前学習】発表用資料を準備する．【事後学習】決定可能な一階理論の具体例を理解する．
25	数学と論理：ツェルメロ・フレンケル集合論【事前学習】発表用資料を準備する．【事後学習】公理的集合論の不完全性について理解する．
26	不完全性：不完全性定理の概要【事前学習】発表用資料を準備する．【事後学習】不完全性定理の証明の全体像を理解する．
27	不完全性：符号化と表現可能性【事前学習】発表用資料を準備する．【事後学習】ゲーデル数による符号化の方法を理解する．
28	不完全性：再帰的関係の表現可能性【事前学習】発表用資料を準備する．【事後学習】再帰的関係がペアノ算術において表現可能であることを理解する．
29	不完全性：ゲーデルの定理【事前学習】発表用資料を準備する．【事後学習】不完全性定理の証明を理解する．
30	不完全性：ロッサ―の定理【事前学習】発表用資料を準備する．【事後学習】不完全性定理について理解を深める．

その他
教科書	使用しない
参考書	Richard E. Hodel, An Introduction to Mathematical Logic , Dover Publications, 2013, 1 edition 菊池誠『不完全性定理』共立出版 2014年第1版
成績評価の方法及び基準	授業参画度(100%) 授業参画度は，毎回の発表用資料（レジメ，プレゼン資料等）をもとに評価します．
オフィスアワー	毎週水曜日１２：１０〜１３：００

授業計画
1	ガイダンス：履修者と相談しながら学習用の教科書を選定する．【事前学習】シラバスを事前に確認する【事後学習】選定した教科書を用意する．
2	準備：数理論理学の概要，数学的な基礎知識．【事前学習】発表用資料を準備する．【事後学習】数理論理学の基本的な目的を理解する．
3	準備：公理系，決定可能性と計算可能性，【事前学習】発表用資料を準備する．【事後学習】数理論理学における基礎概念を理解する．
4	準備：再帰関数と再帰関係【事前学習】発表用資料を準備する．【事後学習】再帰関数について理解を深める．
5	命題論理：言語，トートロジー的帰結，コンパクト性．【事前学習】発表用資料を準備する．【事後学習】命題論理の意味論的概念について理解を深める．
6	命題論理：形式的公理系【事前学習】発表用資料を準備する．【事後学習】命題論理の構文論的概念について理解を深める．
7	命題論理：健全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系においてトートロジーだけが証明可能であることを理解する．
8	命題論理：演繹定理【事前学習】発表用資料を準備する．【事後学習】演繹定理の理論的な意義だけでなく，証明図を構成する際の有用性についても理解を深める．
9	命題論理：完全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系の正当性を理解する．
10	命題論理：ヒルベルト流の公理系【事前学習】発表用資料を準備する．【事後学習】命題論理について様々な公理系があり得ることを理解する．
11	命題論理：シーケント計算【事前学習】発表用資料を準備する．【事後学習】命題論理について様々な公理系があり得ることを理解する．
12	一階論理：算術の言語【事前学習】発表用資料を準備する．【事後学習】一階論理による数学的理論の形式化について理解を深める．
13	一階論理：言語，解釈，モデル【事前学習】発表用資料を準備する．【事後学習】一階論理の基礎概念を理解する．
14	一階論理：タルスキ意味論【事前学習】発表用資料を準備する．【事後学習】一階論理式の解釈について理解を深める．
15	一階論理：自由変数と代入【事前学習】発表用資料を準備する．【事後学習】代入の概念を理解する．
16	一階論理：形式的公理系【事前学習】発表用資料を準備する．【事後学習】一階論理の構文論的概念についてりかいする．
17	一階論理：健全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系において恒真式だけが証明可能であることを理解する．
18	一階論理：演繹定理【事前学習】発表用資料を準備する．【事後学習】演繹定理の有用性についても理解を深める．
19	一階論理：完全性定理【事前学習】発表用資料を準備する．【事後学習】形式的公理系の正当性を理解する．
20	一階論理：置換定理【事前学習】発表用資料を準備する．【事後学習】恒真性が形式的概念であることを理解する．
21	数学と論理：一階理論とヒルベルト計画【事前学習】発表用資料を準備する．【事後学習】不完全性定理の歴史的背景としてヒルベルト計画について理解を深める．
22	数学と論理：レーベンハイム・スコーレムの定理【事前学習】発表用資料を準備する．【事後学習】一階理論のモデルについて理解を深める．
23	数学と論理：コンパクト性定理【事前学習】発表用資料を準備する．【事後学習】一階理論のモデルについて理解を深める．
24	数学と論理：決定可能理論【事前学習】発表用資料を準備する．【事後学習】決定可能な一階理論の具体例を理解する．
25	数学と論理：ツェルメロ・フレンケル集合論【事前学習】発表用資料を準備する．【事後学習】公理的集合論の不完全性について理解する．
26	不完全性：不完全性定理の概要【事前学習】発表用資料を準備する．【事後学習】不完全性定理の証明の全体像を理解する．
27	不完全性：符号化と表現可能性【事前学習】発表用資料を準備する．【事後学習】ゲーデル数による符号化の方法を理解する．
28	不完全性：再帰的関係の表現可能性【事前学習】発表用資料を準備する．【事後学習】再帰的関係がペアノ算術において表現可能であることを理解する．
29	不完全性：ゲーデルの定理【事前学習】発表用資料を準備する．【事後学習】不完全性定理の証明を理解する．
30	不完全性：ロッサ―の定理【事前学習】発表用資料を準備する．【事後学習】不完全性定理について理解を深める．