| 授業方針・テーマ |
本授業では，数理論理学を情報科学において計算や推論を厳密に記述・評価するための基礎理論として位置づける．
命題論理および述語論理を中心に，推論の形式化や論理体系の性質を学び，計算理論，プログラミング，形式検証などの情報科学分野との関係を意識しながら，数理論理学の基本的考え方を理解することを主題とする． |
習得できる知識・能力や授業の
目的・到達目標 |
本授業を通じて，論理式や推論規則を用いて命題や推論過程を形式的に表現し，その妥当性を論理的に判断する能力を身につける．
また，計算可能性や決定可能性，不完全性といった概念を理解し，情報処理や自動化が持つ原理的な限界を理論的に説明できるようになることを目標とする． |
授業計画・内容
授業方法 |
第1回
ガイダンス／数理論理学とは何か
― 情報科学における論理・計算・証明の位置づけ
第2回
命題論理の基礎
― 命題、論理結合子、真理値表
第3回
命題論理の意味論
― 恒真式、充足可能性、論理的帰結
第4回
命題論理の証明論
― 推論規則、自然演繹、健全性の直感
第5回
命題論理の完全性と決定可能性
― SAT問題と計算機科学との関係
第6回
述語論理の構文
― 量化子、述語、自由変数と束縛変数
第7回
述語論理の意味論
― 構造、解釈、モデル
第8回
述語論理の証明論
― 推論規則、証明と意味の関係
第9回
述語論理の性質
― 完全性定理とその意義
第10回
計算可能性の導入
― アルゴリズム、計算モデル、直観的計算概念
第11回
再帰関数・チューリング機械（概念）
― 計算可能性の形式化
第12回
決定不能性
― 停止問題とその意味
第13回
ゲーデルの不完全性定理（概念的理解）
― 証明可能性と真理の違い
第14回
情報科学への応用と展望
― プログラム検証、型理論、AI、形式手法との関係
第15回
総括
― 数理論理学が示す「計算と推論の可能性と限界」 |
| 授業外学習 |
講義内容の予習と復習を，授業資料や参考書を用いて行うこと． |
| テキスト・参考書等 |
参考書
「数学基礎論入門」，前原著，朝倉書店
「数学基礎論 =ゲーデルの不完全性定理= 」．隈部著，放送大学教育振興会
「情報理論のための数理論理学」，板井著，共立出版 |
| 成績評価方法 |
試験，授業への関与・取り組みによって評価 |
質問受付方法
(オフィスアワー等) |
授業に関する質問は，事前に日時を調整の上，教員居室（１号館２０３室）まできてください．
電子メールによる質問は，随時受け付けます． |
特記事項
(他の授業科目との関連性) |
強く関係する他授業はないが，アルゴリズム論，ブール代数，集合論の知識があることが望ましい． |
| 備考 |
|
シラバス照会