2022年度学院等開講科目情報理工学院数理・計算科学系数理・計算科学コース

論理と計算

開講元: 数理・計算科学コース
担当教員: 鹿島亮
授業形態: 講義 (対面型)
メディア利用科目: -
曜日・時限 (講義室): 月3-4 (S421) / 木3-4 (S421)
クラス: -
科目コード: MCS.T416
単位数: 200
開講時期: 2022年度
開講クォーター: 4Q
シラバス更新日: 2025年7月10日
使用言語: 英語

シラバス

授業の目的（ねらい）、概要

ソフトウエアの基礎理論と数理論理学には概念や手法に共通部分が多い。たとえば「プログラム」と「証明」とは本質的に同じものである，という見方ができる（カリー・ハワード同型対応）。本講義のねらいはそのようなソフトウエア基礎理論と数理論理学の共通部分を明らかにすることである。
具体的には古典論理・直観主義論理・様相論理など各種論理の自然演繹・シークエント計算・意味論などを学び，ラムダ計算の基本的な性質を学ぶ。

到達目標

ソフトウエアの基礎理論における数理論理学的な概念や手法を身に付ける。

キーワード

カリー・ハワード同型対応，ラムダ計算，古典論理，直観主義論理，様相論理，自然演繹，シークエント計算，クリプキモデル

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

講義による。
数回の宿題を課す。

授業計画・課題

	授業計画	課題
第1回	導入。直観主義論理，古典論理。	授業時に指示する。
第2回	自然演繹(1)。構文。	授業時に指示する。
第3回	自然演繹(2)。証明の正規化。	授業時に指示する。
第4回	シークエント計算（１）。構文。	授業時に指示する。
第5回	シークエント計算（２）。カット除去。	授業時に指示する。
第6回	ヒルベルト流体系。	授業時に指示する。
第7回	クリプキモデル。	授業時に指示する。
第8回	ラムダ計算(1)。構文，カリー・ハワード同型対応。	授業時に指示する。
第9回	ラムダ計算(2)。チャーチ・ロッサーの定理。	授業時に指示する。
第10回	ラムダ計算(3)。型推論。	授業時に指示する。
第11回	ラムダ計算(4)。強正規化定理。	授業時に指示する。
第12回	コンビネータ論理。	授業時に指示する。
第13回	様々な体系(1)。高階論理など。	授業時に指示する。
第14回	様々な体系(2)。様相論理など。	授業時に指示する。

準備学修(事前学修・復習)等についての指示

学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

Dirk van Dalen: Logic and Structure, Fourth Edition (Corrected 2nd printing 2008).
Henk Barendregt, Erik Barendsen: Introduction to Lambda Calculus (Revised edition December 1998, March 2000).

参考書、講義資料等

授業時に指示する。

成績評価の方法及び基準

宿題による。

履修の条件・注意事項

MCS.T404「計算論理学」を履修済の学生は履修不可。