プログラムの数理

計算可能性の理論についての講義（前半）、記号論理学に関する講義（後半）ののち，両方の内容について期末試験を行う． 1. 原始帰納関数 2. 帰納関数 3. whileプログラム・Churchのテーゼ 4. 万能帰納関数・停止問題 5. 帰納定理・帰納的可算述語 6. 集合論の復習 7. 等式論理 --- 構文論・意味論 8. 等式論理 --- 健全性・完全性 9. 命題論理 --- 意味論・LK 10. 命題論理 --- 完全性・コンパクト性 11. 述語論理 --- 構文論・LK・健全性 12. Herbrandの定理・完全性 13. 導出原理 14. コンパクト性・強い完全性 15. Gödelの不完全性

レポート＋期末試験の成績

教科書（英語）とノート（日本語）を配布する．小野寛晰：情報科学における論理（日本評論社） 鹿島亮：C言語による計算の理論（サイエンス社） 高橋正子：計算論（近代科学社） 萩谷昌己，西崎真也：論理と計算のしくみ（岩波書店）

指示しない

前提となる知識と項目：集合論について予習しておくと良い．