学部後期課程
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2024年4月22日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2024年4月22日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
情報論理
情報論理／ Information Logic
計算機科学の基礎となる記号論理学と，計算可能性の理論について，入門的な講義を行う．
具体的には以下の項目について解説する．
記号論理学：
等式論理を用いた形式論理の導入，
命題論理の構文論と意味論，構造帰納法による証明，極大無矛盾集合による完全性証明
一階述語論理の構文論と意味論，Herbrandの定理
計算可能性の理論：
原子帰納的関数，帰納的関数，クリーネの標準形定理，
ゲーデルの不完全性定理
In this lecture, we introduce basic concepts of symbolic logic and computability theory.
The main topics are as follows.
Symbolic logic:
syntax and semantics of propositional logic, proofs by structural induction,
proofs of completeness by using a maximally consistent set,
syntax and semantics of first-order predicate logic, Herbrand's theorem
Computability theory:
primitive recursive functions, recursive functions, Kleene's normal form theorem,
Gödel's incompleteness theorems
具体的には以下の項目について解説する．
記号論理学：
等式論理を用いた形式論理の導入，
命題論理の構文論と意味論，構造帰納法による証明，極大無矛盾集合による完全性証明
一階述語論理の構文論と意味論，Herbrandの定理
計算可能性の理論：
原子帰納的関数，帰納的関数，クリーネの標準形定理，
ゲーデルの不完全性定理
In this lecture, we introduce basic concepts of symbolic logic and computability theory.
The main topics are as follows.
Symbolic logic:
syntax and semantics of propositional logic, proofs by structural induction,
proofs of completeness by using a maximally consistent set,
syntax and semantics of first-order predicate logic, Herbrand's theorem
Computability theory:
primitive recursive functions, recursive functions, Kleene's normal form theorem,
Gödel's incompleteness theorems
時間割／共通科目コード
コース名
教員
学期
時限
0510014
FSC-IS3014L1
情報論理
谷中 瞳
水曜2限
マイリストに追加
マイリストから削除
講義使用言語
日本語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
理学部
授業計画
計算可能性の理論についての講義（前半）、記号論理学に関する講義（後半）ののち，両方の内容について期末試験を行う．
1. 原始帰納関数
2. 帰納関数
3. whileプログラム・Churchのテーゼ
4. 万能帰納関数・停止問題
5. 帰納定理・帰納的可算述語
6. 集合論の復習
7. 等式論理 --- 構文論・意味論
8. 等式論理 --- 健全性・完全性
9. 命題論理(LK) --- 構文論・意味論
10. 命題論理 --- 完全性・コンパクト性
11. 述語論理(LK) --- 構文論・意味論・健全性
12. Herbrandの定理・完全性
13. 導出原理
14. コンパクト性・強い完全性
15. Gödelの不完全性
授業の方法
講義は対面で行う．その他の情報はITC-LMSにて連絡する．
本講義の講義時間は90分(10:30開始、12:00終了)で、小テストを用いた補完的対応を行う．
各回の要点をまとめたノートによる解説と教科書の該当箇所の確認を行う．必要に応じて板書を行う．
成績評価方法
レポート＋期末試験の成績
教科書
教科書（英語）とノート（日本語）を配布する．
参考書
小野寛晰：情報科学における論理（日本評論社）
鹿島亮：C言語による計算の理論（サイエンス社）
高橋正子：計算論（近代科学社）
萩谷昌己，西崎真也：論理と計算のしくみ（岩波書店）
戸次大介：数理論理学（東京大学出版会）
履修上の注意
集合論について予習しておくと良い．計算可能性を先に扱う予定．
