提出日等：９月２２日・２９日（金）講義終了時
注： 事情により当日提出不可能な場合には、後日理由を明記して提出のこと
ではレポート問題
課題 １ （１） 構造帰納法について述べよ。
（２） 定理：「述語論理の定理は恒真である」の構造帰納法による証明の手順を
述べよ。（実際の証明はここでは不要）
課題 ２ 上記（２）の定理の証明の部分のうち、次の二つについて示せ：
プリントの公理７ および 推論９
課題 ３ スーザン「花が露でできているならば、星が降るわ」
ぺトラ「それだったら、星が降らないならば花は露でできているわね」
ボニー「ぺトラったら、でたらめ言って」
アン「あら、ぺトラの言うことはほんとよ」
ボニーとアンのどちらが正しい？ （分解の木を利用せよ）
（でたらめ：恒真でない、 ほんと：恒真 と考える）
以上
9月22日：資料一枚配布
完全性証明開始：命題論理の完全性を分解の木の応用として証明。（分解を上から下に見て、推論になるように書きなおす）
述語論理（全称記号）について、分解を定義。
9月29日：分解の木におけるいろいろな性質；完全性証明の概要；ケース１の場合（証明構成）
10月６日：ケース２の場合（恒真ならば証明可能）；完全性定理証明完了；自動証明；述語論理の
不決定性；レポート２の解説
１０月１３日： 再帰的関数 （情報系数学入門の2.4 [1]）
なぜこれらが計算できるのか、計算できない関数とはどのようなものか、については
２．３の最初と２．４[2]を読んでみてください。
10月２０日：計算できない関数の作り方（対角線論法）、カットの特殊性、
カット不要性とカット除去定理の相違、カット除去の方法（２重帰納法）
演習問題数題
10月27日：カット除去手続きの概観（１ カットする論理式の複雑度を減少させる。
２ カットをできるだけ上のほうへ上げる）
演習問題
レポート３ 完全性定理についてレポート用紙３枚程度にまとめる。
形式は自由。どこに焦点をあわせるか、も自由。読者に主旨がわかるように 書いてください。
提出：11月17日
演習問題発表：11月17日
sequent型の論理体型とカット除去の参考書について
「９９年度論理学」にあげてある参考書のうち、「証明論入門」が 一番読みやすいと思う。ほかにGentzenのオリジナル(Collected works of Gerhard Gentzen, Springer)、Gaisi Takeutiの Proof Theory (Springer)などがある。
どれも絶版になっていると思うが、学内のどこかの図書館にはあると思う。
期末レポート：今年度の講義のテーマのうち一つ選んで、レポート用紙３枚
程度にまとめる。書き方、内容の取り上げ方は自由。読者が納得するように
書いてください。
提出日時等：教務課の指示にしたがってください。
Last modified: Sun Nov 26 00:03:31 JST 2000